Huffman-Codierung: Warum ist kein Trennzeichen erforderlich?

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

Original Text:

Unheimliche Augen gesehen nahe See


Codiert : 000010110000011001110001010110110100111110111111000111111110100100101

Warum ist in der Huffman-Codierung kein Trennzeichen erforderlich?

coding-theory encoding-scheme huffman-coding BufBills
quelle
1
Denn wenn Sie einen Binärwert dekodieren, nehmen Sie den Bitblock "von links nach rechts", der zuerst mit dem Wert aus dem Originaltext übereinstimmt. Wie in diesem Fall sehen Sie den am weitesten links stehenden Block (0000), der mit E übereinstimmt. Wenn Ihr Zeichencode ein Symbol mit dem Wert 000 enthält, würden Sie die 000 durch dieses Symbol ersetzen und dann erneut von den verbleibenden Bits in suchen eine "von links nach rechts" Weise. Deshalb brauchen Sie keine Trennung.
Syed Ali Hamza
1
Die Frage impliziert, dass normalerweise Trennzeichen benötigt werden. Sie wissen bereits, dass Sie keine Trennzeichen benötigen Eerie eyes seen near lake(nun, mit Ausnahme des Leerzeichens). Die Zeichen selbst benötigen jedoch keine Trennzeichen. Warum ist das nicht so?
MSalters
versuchen Sie es selbst zu entschlüsseln, es gibt nie eine Mehrdeutigkeit.
njzk2
@MSalters: Bei Wörtern variabler Länge werden normalerweise Trennzeichen benötigt: cat cheat for mice≠ catch eat form ice. Ihre Analogie ist fehlerhaft: Jeder Buchstabe ist atomar; Buchstaben sind einfach zu unterscheiden und in sich trennbar. Eine bessere Analogie wäre "Warum kann man eine kursive (handgeschriebene) Schrift lesen, wenn jedes Wort nur eine lange, sich windende, sich selbst schneidende Linie hat?", Und selbst das ist eine schlechte Analogie, da man sich ein handgeschriebenes Wort ansehen kann ( oder sogar einen Teil von einem) und unterscheiden die einzelnen Buchstaben - während eine Huffman-codierte Zeichenfolge Kauderwelsch ist, wenn Sie den Anfang nicht sehen können.
G-Man sagt, dass Monica am
@MSalters Ich sehe deinen Punkt nicht. Ich benötige keine Trennzeichen für die Zeichen, da wir eine Codierung mit fester Breite verwenden: Jeder nachfolgende Block mit acht Bits entspricht einem Zeichen. Huffman-Codierung ist jedoch keine feste Breite, daher die Frage.
David Richerby

Antworten:

50

Sie benötigen kein Trennzeichen, da Huffman-Codes vorwahlfreie Codes sind (auch "Vorwahlcodes" genannt). Dies bedeutet, dass kein Codewort ein Präfix eines anderen Codeworts ist. Beispielsweise ist das Codewort für "e" in Ihrem Beispiel 10, und Sie können sehen, dass keine anderen Codewörter mit den Ziffern 10 beginnen.

Dies bedeutet, dass Sie gierig decodieren können, indem Sie die codierte Zeichenfolge von links nach rechts lesen und ein Zeichen ausgeben, sobald Sie ein Codewort gesehen haben. Beispielsweise codieren 0, 00 und 000 nichts, sodass Sie weiterhin Bits lesen. Wenn Sie 0000 lesen, das "E" codiert, und weil der Code kein Präfix enthält, wissen Sie, dass es kein anderes Codewort 0000x gibt, sodass Sie jetzt "E" ausgeben und mit dem Lesen des nächsten Codeworts beginnen können. Wieder codiert 1 nichts außer 10 codiert "e". Kein anderes Codewort beginnt mit "10", daher können Sie "e" ausgeben. Und so weiter.

David Richerby
quelle
1
Präfix-Codes werden im Allgemeinen auch als Sofortcodes bezeichnet (siehe z. B. Elements of Information Theory von Cover & Thomas). Ich denke, dass der Begriff Präfix-Code viel häufiger vorkommt als Präfix-freier Code.
Batman
3
Erwähnenswert ist auch, dass zum Decodieren einer Folge verketteter Huffman-Codes zunächst die richtige Codewortgrenze angegeben werden muss. Wenn man versucht, die Sequenz an einer falschen Codewortgrenze zu decodieren, erzeugt der Decodierungsprozess eine falsche Sequenz von Ausgabesymbolen.
RWONG
@rwong: Wenn der Huffman-Code falsch synchronisiert beginnt, werden möglicherweise weiterhin auf unbestimmte Zeit falsche Symbole ausgegeben, aber jedes Mal, wenn die Länge eines Symbols falsch bestimmt wird, wird die Anzahl möglicher falscher Zustände verringert.
Supercat
@supercat Ich denke, ich würde es anders formulieren: Wenn ein Huffman - Decoder anfänglich an einer falschen Codewortgrenze eingestellt ist und mit der Verarbeitung beginnt, gibt es eine Möglichkeit (die Null oder irgendetwas sein kann und sowohl vom Wörterbuch als auch vom abhängt) Bit-Stream-Inhalt), der durch Zufall in endlicher Zeit auf einer korrekten Codewortgrenze landen könnte, und in diesem Fall ein korrektes Decodierungsergebnis für nachfolgende Symbole erzeugt. Es wurden einige Untersuchungen zu den Eigenschaften (im Codewort-Wörterbuch und im Bitstrom) durchgeführt, die diese Neusynchronisation gewährleisten würden.
RWONG
@rwong: Wenn die ursprünglichen Daten mit einer Verteilung zufällig wären, bei der die Bits des Datenstroms jeweils eine unabhängige Wahrscheinlichkeit von eins oder null hätten, würde die Wahrscheinlichkeit, für mehr als N Symbole nicht synchron zu bleiben, mit zunehmendem N exponentiell abfallen. Tatsächliche Daten enthalten mit größerer Wahrscheinlichkeit Muster, die eine erneute Synchronisierung verhindern könnten. In der Praxis ist es jedoch unwahrscheinlich, dass ein Fehler am Anfang einer 100-MB-Textdatei alle 100-MB-Textdateien beschädigt.
Supercat
13

Es ist hilfreich, es sich als Baum vorzustellen. Sie durchlaufen einfach den Baum, bis Sie einen Blattknoten treffen, und starten dann von der Wurzel aus neu. An dem Algorithmus, der Huffman-Codierung ausführt, können Sie erkennen, dass diese Art von Struktur im Prozess erstellt wird.

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

quietContest
quelle
6
Der wichtige Aspekt hierbei ist, dass alle gültigen Codewörter Blätter sind. Sie würden Trennzeichen benötigen, wenn Sie Symbole auch auf inneren Knoten hätten.
MVG
3

Kein anderer Code als E beginnt mit 0000. Kein anderer Code als i beginnt mit 0001. Und so weiter. Im Extremfall beginnt kein anderer Code als e mit 01. Sie haben keine Dinge wie E = 0000, Leerzeichen = 000, bei denen Sie nicht wissen, was zu tun ist, wenn Sie drei Nullen finden.

Sehen Sie sich Ihre codierte Zeichenfolge an: 0000101100000 ...

Sie lesen die erste Null. Sie wissen, dass der Code aus E, i, y, l, k, Komma oder Leerzeichen besteht. Die nächste Null bedeutet, dass es nicht k, Komma oder Leerzeichen ist, sondern E, i, y oder l. Die nächste Null bedeutet, dass es E oder i ist. Die nächste Null bedeutet, dass es ein E ist. Wenn Sie wissen, um welchen Code es sich handelt, wissen Sie, dass Sie alle Bits für diesen Code analysiert haben.

Dann haben Sie 101100000 ... Die 1 bedeutet, Sie haben e, r, s, n oder a. Das nächste Bit ist 0, der Code ist also e. Wieder bist du mit diesem Charakter fertig.

gnasher729
quelle
-2

Wir können bei der Huffman-Codierung kein Trennzeichen verwenden, da das binäre Äquivalent jedes Buchstabens nicht mit dem vorangestellten Code eines Buchstabens übereinstimmt. Daher können wir auch ohne Trennzeichen auskommen.

Sandeep Das
quelle
3
Habe ich das nicht schon gesagt, nur ohne die verwirrenden Ebenen vieler verschachtelter Negationen. (Und, nebenbei gesagt, es ist nicht , dass wir nicht können ein Trennzeichen verwenden, nur , dass wir nicht brauchen , um.)
David Richerby