Вправа кодування двійкового дерева Хаффмана від Rozo2 - OpenClassrooms
Питання ? Не хвилюйтеся, ми допоможемо вам !
У зв'язку (дуже далеко) з вправою "найдовше слово" та його словником французьких слів, я подумав запропонувати похідну вправу на кодування Хаффмана та на створення бінарного дерева.
Я зрозумів, що ця тема висвітлювалась на форумах C та C ++, але не на Python. і ми не можемо протистояти задоволенню від використання рекурсії
Кодування Хаффмана - це метод стиснення даних без втрати інформації.
Для текст, стандартне кодування (наприклад, ASCII або UTF-8) використовує один (принаймні) або більше байт на символ. Ми замінимо це кодування на кодування змінної довжини, де найбільш використовувані символи кодуються коротше, ніж менш використовувані (наприклад, реальне: 'e' = 010 - кодується на 3 біти, '
'= 1 0101 1011 1001 1101 0111 - закодовано на 21 біт!).
У так званому напівадаптивному режимі розраховується таблиця кодування a вихідний файл. Розрахунок проводиться з частоти появи символів у цьому файлі, тому кодування є оптимальним для цього файлу.
Алгоритм описаний в http://fr.wikipedia.org/wiki/Codage_de_huffman (або http://en.wikipedia.org/wiki/Huffman_coding, англійською мовою, але більш чітко): він в основному використовує двійкове дерево для побудови тоді йти.
РЕДАГУВАТИ: пояснення статті Wikipedia.fr трохи суворі: я додав публікацію, де докладно викладено принцип кодування для будь-яких цілей.
Рекомендована вправа:
Зі словника французьких слів у вихідному файлі (http://documents.epfl.ch/users/m/ms/mschalle/www/liste_finale.txt) розрахуйте прибуток (у розмірі файлу), який би отримав на цьому файлі застосовуючи кодування Хаффмана.
Принцип:
- обчислити частоту появи символів у вихідному файлі
- обчислити і відобразити таблицю кодування Хаффмана, що відповідає цьому файлу (таблиця: символ двійкового коду) - це суть вправи, очевидно !
- обчислити потенційний коефіцієнт посилення цього файлу порівняно з фіксованим 8-бітовим кодуванням (тип ASCII або EBCDIC)
- (необов’язково): запишіть відповідні функції huffman_encode (текст => бітовий потік) та huffman_decode (бітовий потік => текст).
Для вправи ми можемо бути задоволені розглядати бітові рядки як рядки (тип str) символів '0' та '1', а не як реальні пакети бітів: напр. 01010 з кодом '01010', а не 0b01010
Примітка: запропонований файл словника є досить великим (> 350 000 слів), але спрощений: він містить лише 26 малих літер без наголосів чи цедиль, а також тире "-" та розриви рядків після кожного слова (це полегшує будь-яку налагодження).
Приблизний рівень Python: середній (складність скоріше на алгоритмічному)
Знання: рядки, списки, словники, текстовий файл .
-
Відредаговано Rozo2 21 серпня 2014 о 12:12:38