Проект кодування тексту - PDF скачати безкоштовно
1 ISN-тренінг для викладачів Термінале Дени Бушо, Ерік Гассьє, Александр Терм'є, Сіріл Лаббе, Філіп Бізард, Енн Рассе, Жан-Марк Вінсент UFR IM 2 AG Тренінг для викладачів терміналів Рівень I 1/34
2 План 1 Завдання 2 Тематика 3 Алгоритм 4 Впровадження 5 Кодування довжини циклу 6 Реалізація 2/34
3 Цілі проекту 1 Аналіз алгоритму та проектування дерев, черги пріоритетів, ітерації рекурсії 2 Написання коду мовою C, що підсилює практику цієї мови, файли, спільна розробка 3 Перевірка на кожному етапі Аналіз складності, оцінка продуктивності (експеримент) Міні -структура проекту: робота в команді: штатні пари (більше одного тижня) автономність Оцінка: захист/демонстрація програмного забезпечення Процедура: демонстрація: 15 хвилин запитання: 15 хвилин Цілі: показати, які роботи підготувати тестові ігри планувати хід презентаційної роботи на промова 3/34
4 Планування організації: організація: TD з 8:30 до 9:30, машинна кімната, потім понеділок: початок [кімната TD] вівторок: архітектура проекту [машинна кімната] середа: побітові входи/виходи [кімната TD] четвер: розробка [машинна кімната] П’ятниця: перевірка, аналіз витрат, демонстрація [TD кімната] Супервізія: Дени Буньо, Ерік Гассьє, Александр Терм’є, Сіріл Лаббе, Філіп Бізард, Енн Рассе, Жан-Марк Вінсент Веб-сторінка: 4/34
5 Тема проекту: стиснення без втрат У меню: Алгоритм Хаффмана для кодування та декодування стиснення/декомпресії двійкових файлів для читання/запису дрібних файлів на ходу Алгоритм кодування довжини виконання Варіанти базових версій (історія, послідовність виходів, PackBits) Експериментування на різних форматах даних: тексти, програми (вихідні та двійкові), зображення тощо. 5/34
6 Нагадування: вхідний алфавіт кодування Хаффмана A (символи, пікселі тощо) виводить алфавіт (біт) код Хаффмана: асоціюється з кожним елементом A послідовності на: кодування декодування A характеристики: код змінної довжини (= код Морзе; Ascii код) Властивість префікса: кодування (a 1) = w 1, кодування (a 2) = w 2 w 1 і w 2 не є префіксами один до одного (ефективний алгоритм декодування) 6/34
7 Застосування кодування Хаффмана. Кодуйте послідовність елементів на A у двійковому файлі: зв'яжіть короткий код із найчастішим стисненням елементів початкової послідовності Примітки: код повинен бути побудований відповідно до початкового тексту. перед кодуванням: Статичний Хаффман під час кодування: Динамічний Хаффман Це повинно бути відомо під час декодування. (передано або перераховано до ідентичного) 7/34
8 Дерево Хаффмана Відображення коду Хаффмана = набір дерева Хаффмана з листя = елементи доступу лівої дитини = 0; доступ до правої дочірньої організації = 1 код (a) = послідовність σ міток шляху: корінь σ a 0 1 E A B D C F код (e) = 1; код (а) = 001; код (c) = 0110; тощо властивість префікса поважається! 8/34
9 Алгоритм кодування з урахуванням дерева Хаффмана: S = a 1. a R 0 1 EABDCF 1 побудова таблиці кодування C перше сканування глибини дерева Хаффмана шляхом запам'ятовування послідовності σ кореня σ поточного вузла для кожного аркуша a: C [a] = σ Rq: рекурсивний або ітераційний алгоритм (з явним стеком) 2 обхід S і вироблення R за допомогою C 9/34
10 Алгоритм декодування з урахуванням дерева Хаффмана: RS = a 1. an 0 1 EABDCF 1 обхід дерева Хаффмана вздовж R (0: лівий дочірній; 1: правий дочірній) 2 на кожному аркуші досягнуто: запис a у S повертається до корінь дерева Хаффмана/34
11 Побудова дерева Хаффмана? Залежить від частоти елементів A в S: висока частота = елементи, близькі до кореня Отримання таблиці частот: Freq [ai] = fi (fi = частота ai в S, реальна від 0 до 1) Статичний підхід: 1 побудова Freq по 1-му шляху S (fi = кількість випадків ai/S) 2 побудова дерева Хаффмана (за допомогою Freq) 11/34
12 Неформальний алгоритм побудови дерева Ми використовуємо чергу пріоритетів (Fap) F, з яких: елементи - вузли дерева, пріоритети - реальні (високе значення високий пріоритет) Algo: 1 вставити елементи (ai, Freq [ai]) у fap F 2 до тих пір, поки F містить щонайменше 2 елементи, витягують два елементи (n 1, f 1) та (n 2, f 2) мінімальної ваги вставки F (n, f 1 + f 2) у F, де n - новий вузол лівих дочірніх елементів n 1 і правих дочірніх елементів n 2 3, що залишився елемент у F - корінь дерева Хаффмана 12/34
13 Структури даних Набір A: символи розширеного коду Ascii (від 0 до 255) Частота таблиці: таблиця дійсних чисел, індексованих від 0 до 255 Дерево Хаффмана: або ланцюжок комірок за допомогою покажчиків, або таблиця (256 аркушів 511 вузлів) Fap F: послідовність пари (вузол дерева, реальний) Послідовність на: послідовність символів 0 та 1 13/34
14 Глобальна архітектура Набір взаємопов'язаних програм: Декодування S Розрахунок частоти Частота Конструкція Вал дерева R Кодування зв'язку можливе за допомогою файлів або труб (труба)/34
15 Приклад розбиття на команди Команда обчислення частоти: обчислення частоти Frequency.txt Кодування (будує дерево, потім код): кодування частоти.txt code.txt Декодування (будує дерево, потім декодує): декодування частоти.txt output.txt Результат перевірки: diff input.txt output.txt Розмір вхідного тексту: stat -f% z input.txt Розмір закодованого тексту: stat -f% z code.txt 15/34
16 Додаткові поняття: файли, що маніпулюються своїми іменами в інтерпретаторі команд Доступ в C через дескриптор: структура, що містить інформацію про поточний доступ Використання: Відкриття отримання нового дескриптора FILE * fopen (char * name, char * mode); Access/Test int fscanf (файл * f, char * формат.); int fprintf (файл * f, char * формат.); int feof (файл * f); Закрити безкоштовні ресурси int fclose (файл * f); 16/34
18 Корисна інформація про файли режиму: r або w, але існують інші. У разі помилки відкриття використовуйте perror void perror (повідомлення char *); Дескриптори, відкриті за замовчуванням: stdin: стандартний вхід (клавіатура) stdout: стандартний вихід (екран) stderr: стандартний вихід помилки (екран) 18/34
20 Розширення 1: двійкове читання/запис R повинно бути в двійковому форматі (значення 0 та 1 закодовані на один біт) Проблема: мінімальним елементом, яким керують файли, є байт Рішення: буферизація групи 8 бітів в 1-байтовому буфері (тип char) void write (FILE * f, Buffer T, char b): додати біт b до T (наприклад: перемістивши T вліво і помістивши b в низький біт T), якщо T заповнений, запишіть l відповідний байт у f читання символів (ФАЙЛ * f, буфер T): якщо T порожнє, прочитайте T з файлу, прочитайте наступний біт T (наприклад: найзначніший біт, а потім змістіть T вліво для наступного доступу) Увага: Біти повинні бути читати в тому ж порядку, що і під час написання (як у наведеному прикладі) 20/34
21 Бінарне читання/запис (продовження) В ідеалі, управління буфером повинно бути інкапсульовано: визначити структуру відкритої функції BINARY FILE, щоб отримати BINARY FILE з файлового дескриптора, функції тестування та закриття Проблема для послідовностей бітів, не кратних 8: визначити послідовність виходу (напр .: 0xFF) Кінець послідовності: 0xFF, за якою слідує кількість бітів та неповний буфер. Під час запису 0xFF кодуйте його 0xFFFF і враховуйте при написанні читання 21/34
22 Розширення 2: стиснення на льоту Недолік землі. static: кодування вимагає 2 шляхів S Динамічний підхід: будуйте Freq під час кодування! ініціалізувати Freq з однаковим значенням для кожного елемента A (fi = 1/A) та побудувати початкове дерево для кожного нового елемента e S: код e за допомогою поточного оновлення дерева Freq побудувати нове дерево з de Freq Rq: декодування алгоритм дотримується того самого принципу (реконструкція дерева після кожного декодованого символу) 22/34
23 Вміст, адаптований до стиснення RLE Будь-який вміст, що складається з серії однакових байтів: Джерела різними мовами: відступ (пробіли + вкладка) Рівномірні діапазони зображень у форматі без максимального стиснення 1 байт/піксель: рівні сірого/кольори 8 біт. Та виконувані файли: розділ даних (початкові нульові значення) та 0 полів у таблицях. Частково порожні сторінки пам'яті: 0 в кінці. 23/34
Кодування довжини циклу: принцип Послідовність 15 послідовних однакових байтів у послідовності з 16 символів: S = abbbbbbbbbbbbbbb (a та 15 разів b) можна зменшити до 3 байт: S = a, b, #, 14 1-й байт ідентичний байт: ba спеціальний маркер: # із зазначенням повторення кількість повторень: 14 (байт: макс. 25 Вибір маркера повторення Простий регістр: текстовий файл (ASCII, iso-latin1, utf8.). використовуйте псевдосимволи (дисплей або телеком керування) Приклад: Ctrl-Q/Ctrl-S коди керування потоком Xon/Xoff ASCII коди 0x17 (DC1/Xon) та 0x19 (DC3/Xoff) Загальний випадок: будь-який двійковий вміст, усі значення d байт можуть бути частиною вміст Простий метод: [x, x, n] представляє [x. x] (n + 2 рази x) два однакових послідовних байта = спеціальний маркер. 25/34
26 Приклади s1 = abbbbcdddeffg0h та s2 = abcdeeegga 0: символ 0, 0: ціле число 0 (повторення nb) a b b b b c d d d e f f g 0 h rle a b b 2 c d d 1 e f f 0 g 0 h a b c d e e g g a rle a b c d e 26/34
27 Швидкість стиснення відповідно до довжини n, кодованої на b 8 біт (1 байт): nmax = 2 b 1. 3 байти RLE xxn кодують послідовність x. x (L = n + 2 рази). L = 1: (чорне) RLE-кодування на 1 байт (0%) L = 2: (червоне) RLE-кодування на 3 байти (втрата 1, 50%) L = 3: (зелене) RLE-кодування на 3 байти (0%) ) L = 4: (жовте) RLE-кодування на 3 байти (посилення 1, 25%) L = 5: (жовте) RLE-кодування на 3 байти (посилення 2, 40%) біти n (b) nmax (2 b 1 ) Lmax = nmax Прибуток (%) Lmax 3 Lmax:/34
28 Оптимізація послідовностей довжини 2 Недолік маркера = 2 однакові значення: nb послідовності (s, n = 2)> nb послідовності (s, n> 2) можуть надати length (rle (s))> length (s) Завдання: оптимізувати кодування послідовностей xxy (xy). достатньо повторення кодування на 7 бітів (максимальний коефіцієнт підсилення 98%) n> 0: код x. x (> 2 рази) n 29 Історія обмеженого розміру Виберіть E так, щоб y E максимум xxy: 1 Без інформації: статичний вибір, просте програмування Приклад: ставка на ASCII (E = [0,127]). 2 З уже накопиченою інформацією: ставка на вже побачені цінності. Принцип історії обмеженого розміру: Значення картки (E), одна копія (остання) кожної з послідовностей або ролей (послідовностей), пронумерованих останніми (0) до найстарішого (Картка (E) -1) включає чи не повторює кількість: гісто (и) або гісто (рле (и)). 29/34
30 Приклади: історія s1, rle (s1), s2, rle (s2) При кодуванні xxy ми шукаємо y в історії частини обробленої послідовності (обробленої xx). Врешті-решт: a b b b b c d d d e f f g 0 h a b b 2 c d d 1 e f f 0 g 0 h a b c d e e g g a b c d e 1 g g 0 a 30/34
31 Застосування RLE з історією Приклад використання історії для послідовності RLE. Порівняння ролі без історії та історії. (s) abb 2 cdd 1 eff 0 g 0 h (a) abb 2 cdd 1 eff 0 g 0 hn = 0: буква gn не належить до історії (ів) abcdee 1 gg 0 a (a) abcdee 1 ggn 32 Обов’язково! базова версія кодування Хаффмана статичної версії S і R в оцінці файлів Ascii для різних форматів даних (HTML, джерело програми, двійковий файл, зображення тощо) порівняння отриманих коефіцієнтів стиснення 32/34
33 Різноманітні розширення на замовлення. двійкове стиснення читання/запис на льоту RLE без та/або з історією комбінацій Хаффмана/RLE стиснення зі слів стиснення зображення оцінка цих різних розширень 33/34
34 Вибір теми. Багатство та важливість історичної проблеми, кодування, стиснення. Успіх та виклик для труднощів, що закінчуються (заклик) Запросити до різних навичок програмування, аналізу, самостійної роботи, адаптованої підтримки 34/34