Ich habe diese Hausaufgabe: Finde die Codewörter für die Symbole in einem bestimmten Alphabet. Es heißt, ich soll binäre Huffman-Verfahren für Gruppen von drei Symbolen verwenden. Was bedeutet das genau? Benutze ich reguläres Huffman für [Alphabet]^3? Wenn ja, wie kann ich dann den Unterschied zwischen den 3 Symbolen in einer Gruppe erkennen?
Antworten
Zu viele Anzeigen?
Ich kann es nicht genau sagen, weil Ihre Beschreibung des Problems nicht sehr detailliert ist, aber ich würde vermuten, dass sie meinen, dass Sie jedes Symbol in Ihrem Alphabet nicht einzeln kodieren, sondern jedes Symboltripel als eine Gruppe behandeln sollen.
Wenn Ihr Alphabet zum Beispiel aus folgenden Elementen besteht a , b y c zu erstellen, würden Sie, anstatt für jede einzelne eine Kodierung zu erzeugen, eine Kodierung für aaa , aab , aac , usw. Jede dieser Zeichenketten würde im Huffman-Algorithmus als separates Symbol behandelt werden; man kann sie einfach durch einen Zeichenkettenvergleich unterscheiden. Wenn Sie Eingaben beliebiger Länge akzeptieren müssen, müssen Sie auch Symbole in Ihr Alphabet aufnehmen, die Zeichenketten der Länge 1 oder 2 sind. Wenn Sie zum Beispiel die Zeichenkette aabacab müssen Sie das in die folgenden Symbole aufschlüsseln aab , aca y b .
Hilft das bei der Beantwortung Ihrer Frage? Ich war mir nicht ganz sicher, wonach Sie suchen. Bitte editieren Sie Ihre Frage oder antworten Sie in einem Kommentar, falls dies nicht zur Klärung beigetragen hat.
Roboprog
Punkte
2954
Denkanstoß: Was ist mit kürzeren Zeichenketten und Permutationen von "Blockgrenzen"? Wie sieht es mit 1- und 2-stelligen Zeichenketten aus? Zählen Sie einfach 3, 6, 9, 12, ... Zeichen in Ihren Eingabetext ab und fügen dann ungerade Längen am Ende mit Null auf?
Wenn die Stücke eine variable Größe haben können, wird es wirklich interessant, die beste Lösung zu finden. Ich vermute, dass dies zu einer Art Handelsreisenden-Problem ausartet, aber vielleicht gibt es ja ein nettes "Theorem" oder ein anderes Tool für diese Art von Problemen.
Vielleicht sollten Sie alle Kombinationen von 3 Zeichen ausprobieren, die am häufigsten verwendeten speichern und dann versuchen, eine gute Lösung für die 1 und 2 Zeichen langen Lücken zu finden? Hmm, hört sich an, als wäre es sehr langsam, aber machbar mit einer Art rekursivem Divide-and-Counquer-Ansatz: Ziehen Sie die lange Zeichenkette der Blocklänge N, dann rekursiv in die Codierung der Lücken als Länge N - 1.
Mehr Fragen als Antworten, fürchte ich.
