Le codage Huffman est-il toujours optimal?

9

L'exigence que le codage soit exempt de préfixe se traduit par de grands arbres car l'arbre doit être complet. Existe-t-il un seuil où le stockage de données non codé de longueur fixe serait plus efficace que le codage des données?

information-theory data-compression Kaveh
la source
En général, «non». Pour une donnée moyenne, la fréquence de chaque caractère serait> 1 et il est bon d'utiliser le codage Huffman plutôt que des codes de longueur fixe
@arunmoezhi Pourriez-vous s'il vous plaît citer l'exemple que j'ai donné ci-dessus? La fréquence de chaque caractère est supérieure à 1, mais la longueur fixe est plus optimale.
Cet exemple est intéressant. Mais pouvez-vous fournir un tel scénario avec les probabilités de chaque personnage au lieu de la fréquence et vous assurer que les probabilités de tous les personnages s'ajoutent à 1
@arunmoezhi J'ai inclus les probabilités des personnages et ils s'additionnent à 1.

Réponses:

4

L'entropie H(A)de ce problème est 1.998. Le codage Huffman et le codage à longueur fixe pour ce problème ont une longueur de mot de code moyenne comme 2. Et pour info, le codage que vous avez obtenu en utilisant le codage Huffman est incorrect. Huffman Encoding produit également des codes similaires à une longueur fixe pour ce problème. Il utilise une approche gourmande. Donc, an'obtient pas de code 0mais, à la place, il obtient 00. Retravaillez l'arbre que vous générez à l'aide du codage Huffman. L'arbre que vous devriez obtenir est:entrez la description de l'image ici

arunmoezhi
la source
Merci. Pourriez-vous fournir une sorte de preuve que l'encodage Huffman est toujours plus optimal qu'une longueur fixe, ou du moins m'en référer à une?
1
Vous pouvez vous référer à Introduction to Algorithmspar CLRS. Dans le chapitre qui parle, greedy algorithmsvous pouvez obtenir la preuve formelle de Huffman algorithm. C'est une longue preuve et a besoin de patience pour lire.
8

Le codage de Huffman rapproche la distribution de la population avec des puissances à deux probabilités. Si la vraie distribution se compose de puissances à deux probabilités (et que les symboles d'entrée sont complètement non corrélés), le codage de Huffman est optimal. Sinon, vous pouvez faire mieux avec l'encodage de plage. Il est cependant optimal parmi tous les codages qui affectent des ensembles spécifiques de bits à des symboles spécifiques en entrée.

Antimoine
la source
Qu'entendez-vous par «approximation de la répartition de la population»?
3
Il existe une véritable distribution théorique du message qui pourrait hypothétiquement être envoyée. Idéalement, chaque message devrait être codé de manière proportionnelle au journal de sa probabilité, mais puisque les codes Huffman sont un nombre entier de bits, cela correspond implicitement à des probabilités qui sont des puissances de deux. D'où une approximation. Recherchez le théorème de codage de Shannons.
8

Oui, c'est toujours optimal.

Non, il n'y a pas de seuil où il utiliserait moins d'espace pour utiliser des données non codées de longueur fixe.

J'ai trouvé un certain nombre de preuves sur le Web, mais il y a suffisamment de discussion dans l'article de Wikipedia sur le codage Huffman .

Cela couvre également d'autres techniques qui atteignent une compression plus élevée (travaillant en dehors de l'espace pour lequel le code Huffman est optimal).

Cade Roux
la source