Erweiterter Huffman -Code

Question

Ich habe diese Hausaufgaben: Finden Sie die Codewörter für die Symbole in einem bestimmten Alphabet. Es heißt, ich muss binäres Huffman für Gruppen von drei Symbolen verwenden. Was bedeutet das genau? Verwende ich normales Huffman auf [Alphabet]^3? Wenn ja, wie kann ich dann den Unterschied zwischen den 3 Symbolen in einer Gruppe erkennen?

Answer 1

Ich kann nicht ganz sagen, weil Ihre Beschreibung des Problems nicht so detailliert ist, aber ich würde vermuten, dass sie bedeuten, dass Sie anstatt jedes Symbol in Ihrem Alphabet einzeln zu kodieren, Sie jedes Dreifach von Symbolen als Gruppe betreten sollen .

Also zum Beispiel, wenn Ihr Alphabet besteht a, b, und c, Anstatt eine Codierung für jeden dieser einzeln zu generieren, würden Sie eine Codierung erstellen aaa, aab, aac, usw. Jeder dieser Saiten würde als separates Symbol im Huffman -Algorithmus behandelt; Sie können sie einfach unterscheiden, indem Sie einen String -Vergleich auf ihnen durchführen. Wenn Sie die Eingabe der willkürlichen Länge annehmen müssen, müssen Sie auch in Ihre Alphabet -Symbole einbezogen aabacab, Sie müssten das in die Symbole zerlegen aab, aca, und b.

Beantwortet das Ihre Frage? Ich war mir nicht ganz sicher, wonach Sie suchen. Bitte bearbeiten Sie Ihre Frage oder antworten Sie in einem Kommentar, wenn dies nichts geklärt hat.

Answer 2

Denkfutter: Was ist mit kürzeren Saiten und Permutationen von "Blockgrenzen"? Was ist mit 1 und 2 Charakterzeichenfolgen? Zählen Sie einfach 3, 6, 9, 12, ... Zeichen in Ihren Eingabetxt und dann null pad am Ende ungleiche Längen?

Wenn die Stücke von variabler Größe haben können, wird es wirklich interessant, die beste Passform zu finden. Ich vermute, dass es zu einem reisenden Verkäufer entgespracht wird, aber vielleicht gibt es einen ordentlichen "Theorem" oder ein anderes Tool für solche Dinge.

Versuchen Sie vielleicht alle Permutationen von 3 Chars und sparen Sie die am häufigsten verwendeten und versuchen Sie dann, eine gute Passform für die 1- und 2 -langen Lücken zu finden? Hmm, klingt so, als wäre es sehr langsam, aber mit einer Art rekursiver Kluft und Beratungsansatz machbar: Ziehen Sie die lange Blocklänge N heraus und dann in die Kodierung der Lücken als Länge n - 1.

Mehr Fragen als Antworten, fürchte ich.