Wie erstelle ich einen optimalen Affix-Code?

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?

coding-theory prefix-free-code Anko
quelle

Antworten:

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

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

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 eine Instanz des Problems, dh eine Wahrscheinlichkeitsverteilung auf . $\epsilon>0$ $p$ $[n]$

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

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

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

Konvertieren Sie anschließend in einen fixfreien Code, ohne die Kosten um mehr als a zu erhöhen. $C_0$ $(1+O(\epsilon))$ wie folgt Faktor .

Fügen Sie innerhalb jedes Codeworts in eine zusätzliche '1' in jede (maximale) Gruppe aufeinanderfolgender '1' mit der Länge oder mehr ein. (Dies erhöht die Kosten um höchstens einen Faktor, und der resultierende Code ist immer noch fix-frei, und keine maximale Gruppe aufeinanderfolgender Einsen in einem Codewort hat die Länge ) Dann gilt für jedes Codewort in einer Länge von mehr als , ' 1 gefolgt von einer '0' voranstellen und anhängen $C_0$ $K' = \lceil 1/\epsilon \rceil$ $(1+\epsilon)$ $K$ $K$ $C_0$ $K$ $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 als die Lösung. $1+O(\epsilon)$ $C_1$

Da höchstens mal kostet und die Kosten von eine Untergrenze für die Kosten des optimalen fixfreien Codes sind, hat der fixfreie Code höchstens Kosten mal die Kosten des optimalen fixfreien Codes. $C_1$ $(1+O(\epsilon))$ $C_0$ $C_0$ $C_1$ $(1+O(\epsilon))$

Neal Young
quelle