Pourquoi le codage Huffman élimine-t-il l'entropie que Lempel-Ziv ne fait pas?

L'algorithme DEFLATE populaire utilise le codage Huffman au-dessus de Lempel-Ziv.

En général, si nous avons une source aléatoire de données (= entropie 1 bit / bit), aucun encodage, y compris Huffman, n'est susceptible de le compresser en moyenne. Si Lempel-Ziv était "parfait" (ce qu'il approche pour la plupart des classes de sources, car la longueur va à l'infini), le post-encodage avec Huffman n'aurait pas aidé. Bien sûr, Lempel-Ziv n'est pas parfait, au moins avec une longueur finie, et il reste donc une certaine redondance.

C'est cette redondance restante que le codage Huffman élimine partiellement et améliore ainsi la compression.

Ma question est: pourquoi cette redondance restante est-elle éliminée avec succès par le codage Huffman et non par LZ? Quelles propriétés de Huffman par rapport à LZ rendent cela possible? Est-ce que le simple fait d'exécuter à nouveau LZ (c'est-à-dire encoder les données compressées LZ avec LZ une deuxième fois) accomplirait quelque chose de similaire? Sinon, pourquoi pas? De même, la compression avec Huffman d'abord et ensuite avec LZ fonctionnerait-elle, et sinon, pourquoi?

MISE À JOUR: Il est clair que même après LZ, une certaine redondance restera. Plusieurs personnes l'ont souligné. Ce qui n'est pas clair, c'est: pourquoi cette redondance restante est-elle mieux traitée par Huffman que LZ? Qu'est-ce qui est unique en contraste avec la redondance d'origine, où LZ fonctionne mieux que Huffman?

C'était à l'origine un commentaire, mais il est devenu trop long.

Si vous regardez DEFLATE, ce qui est compressé par Huffman est la sortie de LZ77; Le LZ77 fonctionne (quand cela prend moins de bits que les données brutes) en envoyant un pointeur plus tôt dans la chaîne en cours de compression, et une longueur de correspondance qui indique le nombre de symboles à prendre après le pointeur. La théorie montre que, même sans compression supplémentaire, cette technique finit par converger vers l'entropie source. Cependant, en compression de données, chaque fois que vous avez une distribution qui n'est pas complètement aléatoire, vous pouvez aussi bien la compresser. Il n'y a aucune raison de croire que la sortie du LZ77 - les pointeurs et les longueurs de correspondance - sont complètement aléatoires. Ils doivent converger vers un caractère aléatoire complet dans la limite asymptotique, car LZ77 est asymptotiquement optimal, mais en pratique, vous n'utilisez qu'un dictionnaire fini, ils restent donc probablement assez loin d'être complètement aléatoires pour que vous gagniez en les compressant davantage. Naturellement, vous utilisez un code Huffman pour les pointeurs et un autre pour les longueurs de correspondance, car ces deux processus ont des statistiques différentes.

Pourquoi utiliser Huffman plutôt que LZ pour le deuxième cycle de compression? Le gros avantage de LZ sur Huffman est de traiter les dépendances entre symboles. En anglais, si une lettre est un «q», la suivante est extrêmement susceptible d'être un «u», etc. Si les symboles sont des événements indépendants, alors Huffman est plus simple et fonctionne aussi bien ou mieux pour les chaînes courtes. Pour la sortie du LZ77, mon intuition est que les symboles devraient être assez indépendants, donc Huffman devrait mieux fonctionner.

La compression des données concerne en réalité deux choses: la modélisation et l'encodage. Les algorithmes de la famille LZ modélisent le texte comme une concaténation de répétitions exactes, ce qui est asymptotiquement optimal pour de nombreuses sources aléatoires et raisonnablement bon pour de nombreux textes réels. Pour certaines entrées, ce modèle peut cependant être assez mauvais. Par exemple, vous ne pouvez pas utiliser LZ pour compresser directement un tableau de suffixes, même si le tableau de suffixes est aussi compressible que le texte d'origine.

$(p, \ell, c)$$p$$\ell$$c$

$\log n$$n$

Donc, en bref, Huffman bat LZ en compressant les tuples, car son modèle (distribution fixe vs répétitions exactes) correspond mieux aux données.

Je crois que la réponse réside dans la taille du dictionnaire de recherche.

Les données ont un sens de la localité (c'est-à-dire que si une donnée a été utilisée, il est probable qu'elle sera à nouveau utilisée bientôt), et l'algorithme LZ en profite dans la construction du dictionnaire de recherche. Il génère un trie avec une quantité finie de nœuds possibles, pour garder les recherches rapides . Quand il atteint la taille limite, il fait un autre trie, "oubliant" le précédent. Il doit donc reconstruire la table de recherche pour les caractères les plus simples, mais si certains mots ne sont plus utilisés, ils ne sont plus conservés en mémoire, donc un encodage plus petit peut être utilisé.

Par conséquent, une sortie LZ peut être encore réduite avec le codage Huffman, car cette redondance dans la création des essais de recherche peut être détectée par une analyse statistique.

Peut-être que je suis hors piste ici, mais l'encodage Huffman examine l'intégralité de l'entrée pour construire sa table d'encodage (arbre), tandis que Lempel-Ziv encode au fur et à mesure. C'est à la fois un avantage et un inconvénient pour Huffman. Le désavantage est évident, à savoir que nous devons voir l'intégralité de l'entrée avant de commencer. L'avantage est que Huffman prendra en compte les statistiques qui se produisent n'importe où dans l'entrée, tandis que Lempel-Ziv doit s'y développer progressivement. Ou pour le dire autrement, Lempel-Ziv a une "direction" que Huffman n'a pas.

Mais tout cela n'est que ma façon naïve d'imaginer comment les choses sont. Nous aurions besoin d'une véritable preuve ici pour voir exactement comment Huffman surpasse Lempel-Ziv.

La réponse courte est, LZ est un algorithme "universel" en ce qu'il n'a pas besoin de connaître la distribution exacte de la source (a juste besoin de l'hypothèse que la source est stationnaire et ergodique). Mais Huffman ne l'est pas; il a besoin de connaître la distribution exacte à partir de laquelle la source est échantillonnée (pour créer l'arbre Huffman). Ces informations supplémentaires permettent à Huffman d'atteindre des garanties de compression strictes. Cependant, pour les algorithmes de compression de fichiers pratiques, Huffman peut être moins favorable car il devra d'abord recueillir des statistiques empiriques du fichier, puis effectuer la compression réelle dans une seconde moitié, tandis que LZ peut être implémenté en ligne.

Plus de détails peuvent être trouvés dans les textes standard de théorie de l'information, par exemple, Elements of Information Theory par Cover et Thomas.