Упражнение на двоично дърво за кодиране на Huffman от Rozo2 - OpenClassrooms

Въпрос ? Не се притеснявайте, ние ще ви помогнем !

дърво

Във връзка (много далеч) с упражнението "най-дългата дума" и нейния речник на френски думи, помислих да предложа производно упражнение върху кодирането на Huffman и за създаването на двоично дърво.
Разбрах след факта, че тази тема е била обхваната във форумите C и C ++, но не и в Python. и не можем да устоим на удоволствието от използването на рекурсия


Кодирането на Huffman е метод за компресиране на данни без загуба на информация.
За текст, стандартното кодиране (например ASCII или UTF-8) използва един (поне) или повече байта на символ. Ние ще заменим това кодиране с кодиране с променлива дължина, където най-използваните символи са кодирани по-къси от по-малко използваните (напр. Реално: 'e' = 010 - кодирано на 3 бита, '

'= 1 0101 1011 1001 1101 0111 - кодирано на 21 бита!).
В така наречения полуадаптивен режим се изчислява кодиращата таблица за а изходен файл. Изчисляването се извършва от честотите на поява на символи в този файл, така че кодирането е оптимално за този файл.
Алгоритъмът е описан в http://fr.wikipedia.org/wiki/Codage_de_huffman (или http://en.wikipedia.org/wiki/Huffman_coding, на английски, но по-изрично): той използва предимно двоично дърво за изграждане след това да вървя.