Gültige Huffman Codes?

Question

Ich versuche ein Huffman-Coding-Problem zu lösen, aber ich bin mir nicht ganz sicher, ob ich das Thema vollständig verstehe. Ich versuche, herauszufinden, ob die folgenden sind ein gültiger Huffman-Code ist:

A: 0 
B: 01 
C: 11 
D: 110 
E: 111 

Was ich denke, ist, dass es nicht gültig ist, weil A, oder 1 ist, würde auf B verletzen oder 01. Ich bin aber nicht positiv. Könnte mich jemand aufklären?

Edit: Ich bin traurig, dass ich A als 0 und nicht 1

Answer 1

Nr Eines Huffman-Code ist ein Präfix-Code eingeben sollte, was bedeutet, dass kein Code ein Präfix von jedem anderen Code sein kann. In Ihrem Beispiel ist A ein Präfix von B und C ist ein Präfix von beiden D und E.

Ein gültiger Code Präfix sein würde:

A: 0 
B: 10 
C: 11 

, das so weit ist, wie Sie mit den Codes von gehen Länge 1, 2 und 2. Alle anderen Codes wären ein Präfix von diesen. Es ist nicht möglich 1 einen Präfix-Code mit Längen aufweisen, 2, 2, 3 und 3.

Dies ist ein gültiger Präfix-Code für fünf Symbole:

A: 0 
B: 10 
C: 110 
D: 1110 
E: 1111 

wie folgt aus:

A: 00 
B: 01 
C: 10 
D: 110 
E: 111