Wie erstelle ich einen optimalen Affix-Code?

8

Ein Affix-Code ist ein Code, der gleichzeitig Präfix- und Suffix-Code ist. Das heißt, kein Codewort ist weder das Präfix noch das Suffix eines anderen Codeworts. Affix-Codes können sofort in beide Richtungen (vorwärts und rückwärts) dekodiert werden .

Ich möchte eine erstellen, die eine bestimmte Verteilung der Eingabesymbole bei einer Reihe von Ausgabesymbolen optimal komprimiert.

Der Huffman-Algorithmus (der Präfixcodes erstellt) kommt dem am nächsten, scheint jedoch aufgrund seiner gierigen Strategie für eine Änderung dieses Zwecks ungeeignet zu sein.

Wie können optimale Affix-Codes gefunden werden?

Anko
quelle

Antworten:

4

Ich glaube wirklich nicht, dass es einen bekannten Algorithmus gibt, der optimal ist. Tatsächlich gibt es eine große Vermutung darüber, wie effektiv eine Reihe von Codewörtern sein kann, siehe: http://arxiv.org/abs/0709.2598 (der Name, den ich für den Zusatzcode kannte, ist fixfreier Code). Wenn sich ein Algorithmus als optimal herausstellen würde, würde er höchstwahrscheinlich auch diese Vermutung lösen (oder widerlegen).

domotorp
quelle
Diese Antworten scheinen darauf hinzudeuten, dass der Huffman-Algorithmus unter vernünftigen Bedingungen optimale Codes erzeugt.
Anko
Ich verstehe nicht, wie diese Antworten mit Ihrem Problem zusammenhängen. Wenn Sie nur einen Algorithmus verwenden, können Sie Huffman verwenden und dann einige schlechte Wörter erweitern.
Domotorp
Ich mache nur den Punkt, dass einige Codes als optimal erwiesen werden können. Das Erweitern der Codewörter eines Huffman-Codes würde ihn wahrscheinlich unoptimal machen, da jede Erweiterung dazu führt, dass er sich einer Blockcodierung nähert. Dies könnte jedoch ein Ausgangspunkt sein!
Anko
1
Aber Huffman ist für Präfix-frei, für die wir die Kraft-Ungleichung kennen ( en.wikipedia.org/wiki/Kraft%27s_inequality ). Wenn wir einen Beweis für die Optimalität haben, folgt eine kraftähnliche Ungleichung. Für fixfreie Codes gilt jedoch die resp. Ungleichheit ist eine Vermutung, daher kann es keinen Beweis geben.
Domotorp
Auf Seite 8 unten werden mehrere fixfreie Codes für Englisch beschrieben, und es wird erwähnt, dass sich keiner der zu ihrer Erstellung verwendeten Algorithmen als optimal erwiesen hat. Es ist also vermutlich kein effizienter Algorithmus bekannt.
Yuval Filmus
2

FWIW, es scheint mir wahrscheinlich, dass es ein PTAS für das Problem gibt, das der Grundidee in diesem Artikel folgt . (Dies beantwortet Ihre Frage nicht genau, aber ich werde das PTAS hier im Antwortbereich trotzdem beschreiben, da es zu lang ist, um in einen Kommentar zu passen.)

Fixiere jede Konstante . Sei p eine Instanz des Problems, dh eine Wahrscheinlichkeitsverteilung auf [ n ] .ϵ>0p[n]]

Angenommen , ein Code (eine Reihe von Codewörtern) ist fix-frei,K. wenn kein Codewort im Code mit der Länge oder wenigerK. ein Präfix oder Suffix eines anderen Codeworts ist.

Fix . Berechnen Sie einen K- Fix-freien Code mit minimalen Kosten für p im Zeitpolynom in n wie folgt. Betrachten Sie für jede der (konstant vielen) Teilmengen S von Zeichenfolgen mit einer Länge von höchstens K den K- fixfreien Code C ( S ) , der durch Zuweisen von | gebildet wird S | größte Wahrscheinlichkeiten in p , Codewörter von S (Übereinstimmung kleinerer Codewörter mit größeren Wahrscheinlichkeiten), dann Aufzählung (in der Reihenfolge zunehmender Länge) der nK.=1/.ϵ2K.pnS.K.K.C.(S.)|S.|pS.Zeichenfolgen mit einer Länge größer als K , die kein Präfix oder Suffix in S haben , und Zuweisen dieser n - | S | Zeichenfolgen als Codewörter für die verbleibenden n - | S | Wahrscheinlichkeiten (in der Reihenfolge abnehmender Wahrscheinlichkeit). Jede Teilmenge S gibt einen Code C ( S ) ; Nehmen Sie C 0 als einen der minimalen Kosten (indem Sie alle Auswahlmöglichkeiten für S auflisten). C 0 ist ein kostengünstiger K- fix-freier Code für pn- -|S.|K.S.n- -|S.|n- -|S.|S.C.(S.)C.0S.C.0K.p.

Es ist zu beachten, dass die Kosten von eine Untergrenze für die Kosten des optimalen fixfreien Codes für p sind , da der optimale fixfreie Code auch ein K istC.0pK. fixfreien fixfreie fixfreier Code ist.

Konvertieren Sie anschließend in einen fixfreien Code, ohne die Kosten um mehr als a ( 1 + O ( ϵ ) ) zu erhöhen.C.0(1+Ö(ϵ)) wie folgt Faktor .

Fügen Sie innerhalb jedes Codeworts in eine zusätzliche '1' in jede (maximale) Gruppe aufeinanderfolgender '1' mit der Länge K ' = 1 / ϵ oder mehr ein. (Dies erhöht die Kosten um höchstens einen ( 1 + ϵ ) Faktor, und der resultierende Code ist immer noch K- fix-frei, und keine maximale Gruppe aufeinanderfolgender Einsen in einem Codewort hat die Länge K. ) Dann gilt für jedes Codewort in C 0 mit einer Länge von mehr als K , K ' ' 1 gefolgt von einer '0' voranstellen und K anhängenC.0K.'=1/.ϵ(1+ϵ)K.K.C.0K.K.'K.'Vor '1' steht eine '0'. (Diese Änderung markiert eindeutig den Anfang und das Ende jedes Codeworts, wodurch der Code vollständig fixfrei ist. Die Modifikation erhöht die Kosten insgesamt um höchstens einen -Faktor.) Nehmen Sie den resultierenden fixfreien Code C 1 als die Lösung.1+Ö(ϵ)C.1

Da höchstens ( 1 + O ( ϵ ) ) mal C 0 kostet und die Kosten von C 0 eine Untergrenze für die Kosten des optimalen fixfreien Codes sind, hat der fixfreie Code C 1 höchstens Kosten ( 1 + O ( ϵ ) ) mal die Kosten des optimalen fixfreien Codes.C.1(1+Ö(ϵ))C.0C.0C.1(1+Ö(ϵ))

Neal Young
quelle