Exercițiul Huffman de codare a arborelui binar de către Rozo2 - OpenClassrooms

O intrebare ? Nu vă faceți griji, vă vom ajuta !

huffman

În legătură (foarte departe) cu exercițiul „cel mai lung cuvânt” și dicționarul său de cuvinte franceze, m-am gândit să propun un exercițiu derivat pe codarea Huffman și pe crearea unui arbore binar.
Mi-am dat seama după faptul că acest subiect a fost tratat în forumurile C și C ++, dar nu și în Python. și nu putem rezista plăcerii de a folosi recursivitatea


Codificarea Huffman este o metodă de comprimare a datelor fără a pierde informații.
Pentru o text, codificarea standard (de ex. ASCII sau UTF-8) folosește unul (cel puțin) sau mai mulți octeți per caracter. Vom înlocui această codificare cu o codificare cu lungime variabilă în care cele mai utilizate caractere sunt codificate mai scurt decât cele mai puțin utilizate (de exemplu, real: „e” = 010 - codificat pe 3 biți, ”

'= 1 0101 1011 1001 1101 0111 - codificat pe 21 biți!).
În așa-numitul mod semi-adaptiv, tabelul de codare este calculat pentru A fișier sursă. Calculul se face din frecvențele de apariție a caracterelor din acest fișier, astfel încât codificarea este optimă pentru acest fișier.
Algoritmul este descris în http://fr.wikipedia.org/wiki/Codage_de_huffman (sau http://en.wikipedia.org/wiki/Huffman_coding, în engleză, dar mai explicit): folosește în principal un arbore binar pentru a construi atunci a merge.