Проект за кодиране на текст - PDF безплатно изтегляне

1 ISN обучение за преподаватели в терминале Денис Бухо, Ерик Гасие, Александър Термие, Кирил Лабе, Филип Бизар, Ан Рас, Жан-Марк Винсент UFR IM 2 AG Обучение за учители в терминали Ниво I 1/34

кодиране

2 План 1 Цел 2 Тема 3 Алгоритъм 4 Изпълнение 5 Кодиране на дължина на изпълнение 6 Реализация 2/34

3 Цели на проекта 1 Анализ на алгоритъма и дизайна на дърветата, приоритетни опашки, итерации на рекурсия 2 Писане на код на език C, подсилващ практиката на този език, файлове, съвместна разработка 3 Валидиране на всеки етап анализ на сложността, оценка на изпълнението (експериментиране) Mini -структура на проекта: работа в екип: двойки на пълен работен ден (над една седмица) автономност Оценка: защита/демонстрация на софтуер Процедура: демонстрация: 15 минути въпроси: 15 минути Цели: покажете какви работи подгответе тестови игри планирайте хода на презентационната работа по речта 3/34

4 Планиране на организацията: организация: TD от 8:30 до 9:30, машинно помещение, след това понеделник: начало [TD стая] вторник: архитектура на проекта [машинно помещение] сряда: бит-битови входове/изходи [TD стая] четвъртък: разработка [машинна стая] петък: валидиране, анализ на разходите, демонстрация [TD стая] Надзор: Денис Бухо, Ерик Гасие, Александър Термие, Сирил Лаббе, Филип Бизар, Ан Рас, Жан-Марк Винсент Уеб страница: 4/34

5 Тема на проекта: компресия без загуби В менюто: алгоритъм на Huffman за кодиране и декодиране на компресия/декомпресия на двоични файлове за компресиране/декомпресиране в движение Алгоритъм за кодиране на дължина на изпълнение Основни варианти на версията (история, изходна последователност, PackBits) Експериментиране върху различни формати на данни: текстове програми (източник и двоичен файл), изображения и др. 5/34

6 напомняния: Huffman кодираща въведена азбука A (символи, пиксели и др.) Извежда азбука (бит) a Huffman код: асоциира се с всеки елемент от A последователност на: A кодиране декодиране A характеристики: код с променлива дължина (= Morse код; Ascii код) Свойство на префикс: кодиране (a 1) = w 1, кодиране (a 2) = w 2 w 1 и w 2 не са префикси един към друг (ефективен алгоритъм за декодиране) 6/34

7 Прилагане на кодирането на Huffman Кодирайте последователност от елементи на A в двоичен файл: свържете кратък код с най-честото компресиране на елементите на началната последователност Забележки: кодът трябва да бъде конструиран според първоначалния текст. преди кодиране: Статичен Huffman по време на кодиране: Dynamic Huffman Трябва да се знае по време на декодиране. (предадени или преизчислени на идентични) 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. a 0 1 EABDCF 1 обхождане на дървото на Хафман по R (0: ляво дете; 1: дясно дете) 2 на всеки лист е достигнало: запис на бутон в 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