Ist die Huffman-Codierung immer optimal?

  • Das Erfordernis der Kodierung, Präfix-frei zu sein, führt dazu, dass große Bäume vorhanden sind, da der Baum abgeschlossen sein muss. Gibt es eine Schwelle, bei der eine nicht kodierte Speicherung von Daten mit fester Länge effizienter ist als die Kodierung der Daten?

    14 August 2012
    Kaveh
3 answers
  • Ja, es ist immer optimal.

    Nein, es gibt keinen Schwellenwert, bei dem weniger Platz für die Verwendung nicht kodierter Daten mit fester Länge benötigt würde.

    Ich habe im Internet eine Reihe von Beweisen gefunden, aber in der Wikipedia-Artikel Huffman-Codierung .

    Dies gilt auch für andere Techniken, die eine höhere Komprimierung erzielen (außerhalb des Speicherbereichs, für den der Huffman-Code gilt ist optimal).

    14 August 2012
    Michael Haren
  • Die Huffman-Codierung approximiert die Bevölkerungsverteilung mit zwei Potenzen. Wenn die wahre Verteilung aus Potenzen zweier Wahrscheinlichkeit besteht (und die Eingabesymbole völlig unkorreliert sind), ist die Huffman-Codierung optimal. Wenn nicht, können Sie die Bereichskodierung verbessern. Es ist jedoch optimal für alle Kodierungen, die bestimmten Symbolen in der Eingabe bestimmte Bitsätze zuweisen.

    07 August 2012
    mattdm
  • Die Entropie H(A) für dieses Problem ist 1.998. Sowohl die Huffman-Codierung als auch die Codierung mit fester Länge für dieses Problem hat eine durchschnittliche Codewortlänge als 2. Und zu Ihrer Information, die Kodierung, die Sie mit Huffman-Kodierung erhalten haben, ist falsch. Huffman Encoding erzeugt für dieses Problem auch Codes, die der festen Länge ähneln. Es verwendet einen gierigen Ansatz. a erhält also keinen Code als 0, sondern stattdessen 00. Überarbeiten Sie den Baum, den Sie mit Huffman-Codierung erstellen. Der Baum, den Sie erhalten sollten, lautet: Ist die Huffman-Codierung immer optimal?

    10 August 2012
    arunmoezhi