Encodage Huffman: pourquoi n'y a-t-il pas besoin d'un séparateur?

17 
Char        Code
====        ====
E           0000
i           0001
y           0010
l           0011
k           0100
.           0101
space       011
e           10
r           1100
s           1101
n           1110
a           1111

Texte original:

Yeux étranges vus près du lac


Encodé : 0000101100000110011100010101101101001111101011111100011001111110100100101

Pourquoi n'y a-t-il pas besoin d'un séparateur dans l'encodage Huffman?

coding-theory encoding-scheme huffman-coding BufBills
la source
1
Parce que lorsque vous décodez une valeur binaire, vous prenez le morceau de bits "de gauche à droite", celui qui correspond en premier à la valeur du texte d'origine. Comme dans ce cas, le segment le plus à gauche (0000) correspond à E. S'il y avait un symbole avec une valeur de 000 dans votre code de caractère, vous remplaceriez le 000 par ce symbole, puis recommenceriez à rechercher à partir des bits restants dans d'une manière "de gauche à droite". C'est pourquoi vous n'avez pas besoin de séparation.
Syed Ali Hamza
1
La question implique que des séparateurs sont généralement nécessaires. Vous savez déjà que vous n'avez pas besoin de séparateurs Eerie eyes seen near lake(enfin, sauf pour le caractère espace). Mais les personnages eux-mêmes n'ont pas besoin de séparateurs. Pourquoi n'est-ce pas?
MSalters
essayez de le décoder vous-même, il n'y a jamais d'ambiguïté.
njzk2
@MSalters: Mais les séparateurs sont généralement nécessaires avec des mots de longueur variable: cat cheat for mice≠ catch eat form ice. Votre analogie est défectueuse: chaque lettre est atomique; les lettres sont trivialement distinguées et intrinsèquement séparables. Une meilleure analogie serait "Pourquoi pouvez-vous lire un script cursif (manuscrit), alors que chaque mot n'est qu'une seule ligne longue, se tortillant et se croisant?", Et même cela est une mauvaise analogie, car vous pouvez regarder un mot manuscrit ( ou même une partie de celle-ci) et discerner les lettres individuelles - alors qu'une chaîne codée par Huffman est du charabia si vous ne pouvez pas voir le début.
G-Man dit 'Reinstate Monica' le
@MSalters Je ne vois pas votre point. Je n'ai pas besoin de séparateurs pour les caractères car nous utilisons un encodage à largeur fixe: chaque bloc successif de huit bits correspond à un caractère. Mais le codage Huffman n'est pas à largeur fixe, d'où la question.
David Richerby

Réponses:

50

Vous n'avez pas besoin d'un séparateur parce que les codes Huffman sont des codes sans préfixe (également appelés «codes de préfixe»). Cela signifie qu'aucun mot de code n'est un préfixe d'un autre mot de code. Par exemple, le mot de code pour «e» dans votre exemple est 10, et vous pouvez voir qu'aucun autre mot de code ne commence par les chiffres 10.

Cela signifie que vous pouvez décoder goulûment en lisant la chaîne codée de gauche à droite et en sortant un caractère dès que vous avez vu un mot de code. Par exemple, 0, 00 et 000 ne codent rien, vous continuez donc à lire des bits. Lorsque vous lisez 0000, cela code "E" et, comme le code est sans préfixe, vous savez qu'il n'y a pas d'autre mot de code 0000x, vous pouvez donc maintenant sortir "E" et commencer à lire le mot de code suivant. Encore une fois, 1 ne code rien, mais 10 code "e". Aucun autre mot de code ne commence par «10», vous pouvez donc sortir «e». Etc.

David Richerby
la source
1
Les codes de préfixe sont également connus sous le nom de codes instantanés (voir, par exemple, Elements of Information Theory par Cover & Thomas). Je pense que le terme code préfixe revient beaucoup plus souvent que le code sans préfixe.
Batman
3
Il convient également de mentionner que pour décoder une séquence de codes Huffman concaténés, il faut d'abord donner la frontière de mot de code correcte. Si l'on essaie de décoder la séquence à une mauvaise limite de mot de code, le processus de décodage générera une mauvaise séquence de symboles de sortie.
rwong
@rwong: Si le code Huffman démarre incorrectement synchronisé, il peut continuer à produire des symboles incorrects indéfiniment, mais chaque fois qu'il détermine incorrectement la longueur d'un symbole, le nombre d'états incorrects possibles sera réduit.
supercat du
@supercat Je suppose que je le formulerais d'une manière différente: si un décodeur Huffman est initialement réglé sur une mauvaise limite de mot de code et commence le traitement, il y a une possibilité (qui peut être zéro ou autre, et peut dépendre à la fois du dictionnaire et du contenu de flux binaire) qu'il pourrait atterrir sur une frontière de mot de code correcte par coïncidence en temps fini, et lorsque cela se produira, il produira un résultat de décodage correct pour les symboles suivants. Il y a eu quelques recherches sur les propriétés (sur le dictionnaire de mots de code et sur le flux binaire) qui garantiraient cette resynchronisation.
rwong
@rwong: Si les données d'origine étaient aléatoires avec une distribution telle que les bits du flux auraient chacun une probabilité indépendante d'être un ou zéro, la probabilité de rester hors de synchronisation pour plus de N symboles diminuerait exponentiellement avec l'augmentation de N. Les données réelles sont plus susceptibles de contenir des modèles qui pourraient empêcher la resynchronisation, mais dans la pratique, il est peu probable qu'une erreur au début d'un fichier texte de 100 Mo corromprait tous les 100 Mo de texte.
supercat
13

Il est utile de l'imaginer comme un arbre. Vous traversez simplement l'arbre jusqu'à ce que vous atteigniez un nœud feuille, puis redémarrez à partir de la racine. De l'algorithme qui fait le codage de Huffman, vous pouvez voir que ce type de structure est créé dans le processus.

https://en.wikipedia.org/wiki/File:HuffmanCodeAlg.png

quietContest
la source
6
L'aspect important ici est que tous les mots de code valides sont des feuilles. Vous auriez également besoin de séparateurs si vous aviez des symboles sur les nœuds internes.
MvG
3

Aucun code autre que E ne commence par 0000. Aucun code autre que i ne commence par 0001. Et ainsi de suite. Dans un cas extrême, aucun code autre que e ne commence par 01. Vous n'avez pas de choses comme E = 0000, espace = 000, où vous ne sauriez pas quoi faire si vous trouvez trois zéros.

Regardez votre chaîne encodée: 0000101100000 ...

Vous lisez le premier zéro. Vous savez que le code est l'un des E, i, y, l, k, virgule ou espace. Le zéro suivant signifie que ce n'est pas k, virgule ou espace, mais E, i, y ou l. Le zéro suivant signifie que c'est E ou i. Le zéro suivant signifie que c'est un E. Lorsque vous savez de quel code il s'agit, vous savez que vous avez analysé tous les bits de ce code.

Ensuite, vous avez 101100000 ... Le 1 signifie que vous avez e, r, s, n ou a. Le bit suivant est 0, donc le code est e. Encore une fois, vous avez terminé avec ce personnage.

gnasher729
la source
-2

Nous ne pouvons pas utiliser le séparateur dans le codage Huffman parce que l'équivalent binaire de chaque lettre ne correspond pas au code préfixé de n'importe quelle lettre, nous pouvons donc nous passer même d'utiliser le séparateur.

Sandeep Das
la source
3
N'ai-je pas déjà dit cela, seulement sans les niveaux déroutants de nombreuses négations imbriquées. (Et, au fait, ce n'est pas que nous ne pouvons pas utiliser un séparateur; juste que nous n'en avons pas besoin .)
David Richerby