Wie kann man die optimalen Parameter zu einem Start-Schritt-Stop-Codierungsschema berechnen?

Question

Ein Start-Schritt-Stop-Code ist eine Datenkomprimierungstechnik, die verwendet wird, die Anzahl zu komprimieren, relativ klein sind.

Der Code funktioniert wie folgt: Es hat drei Parameter, Start, Schritt und stoppen. Starten Sie bestimmt die Menge an Bits verwendet, um die ersten paar Zahlen zu berechnen. Schritt bestimmt, wie viele Bits der Codierung hinzuzufügen, wenn wir laufen und Anschlag bestimmt die maximale Menge an Bits verwendet, um eine Zahl zu kodieren.

So ist die Länge einer Codierung von l = Start + Schritt gegeben ist * i.

Der „i“ Wert eines bestimmten Codes verwendet einstellige codiert. Das heißt, eine Anzahl von 1-Bits durch einen Abschluss 0 Bit folgt. Wenn wir Anschlag erreicht haben, dann können wir den abschließenden 0-Bit löschen. Wenn i Null ist nur wir den 0-Bit schreiben.

So a (1, 2, 5) Start-Schritt-Stop-Code funktionieren würde, wie folgt:

Der Wert 0, codiert als: 0 0
Wert 1, codiert als: 0 1 | Wert 2, codiert als: 10 000
Wert 9, codiert als: 10 111
Wert 10, codiert als: 11 00000
Wert 41, codiert als: 11 11111

So, da eine Datei mehrere Nummern enthalten, wie können wir die optimalen Start-Schritt-Stop-Codes für diese Datei zu berechnen? Die optimalen Parameter werden als solche definiert, die in dem größten Verdichtungsverhältnis führen werden.

Answer 1

Diese "Start-Schritt-stop" Codes sieht aus wie eine andere Art und Weise Huffman-Codes . Sehen Sie sich die Grundtechnik für einen Umriss des Pseudo-Code für sie berechnet werden.

Im Wesentlichen ist es das, was der Algorithmus tut:

Bevor Sie die Huffman starten kodieren Sie die Statistiken jedes Symbols sammeln müssen Sie komprimiert werden, werden (ihre Gesamthäufigkeit in der Datei zu komprimieren).

Nachdem Sie, dass Sie ein Binärbaum , dass Informationen mit, so dass die am häufigsten Verwendete Symbole sind an der Spitze des Baumes (und somit weniger Bits verwenden) und derart, dass keine Codierung Präfix Code . Da, wenn eine Codierung einen gemeinsamen Präfix hat könnte es Zweideutigkeiten sein dekomprimieren.

Am Ende der Huffman-Kodierung des Startwertes wird Tiefe des flachsten Blattknoten sein, wird Ihr Schritt immer 1 (logisch dies Sinn macht, warum sollen Sie mehr Bits zwingen, als Sie benötigen, fügen Sie einfach einen nach dem anderen ,) und Ihr Stop-Wert wird die Tiefe des tiefstenen Blattknoten sein.

Wenn die Frequenz-Statistik nicht sortiert wird es O (n log n) nehmen zu tun, wenn sie nach Häufigkeit sortiert werden, können sie in O erfolgen (n).

Huffman-Codes sind garantiert die beste durchschnittliche Komprimierung für diese Art der Codierung haben:

  

Huffman war in der Lage, die meisten zu entwerfen   effizientes Komprimierungsverfahren dieser   Typ: keine andere Zuordnung einzelner   Source-Symbole, um einzigartige Saiten   Bits einen kleineren Durchschnitt produzieren   Ausgangsgröße, wenn das tatsächliche Symbol   Frequenzen stimmen die mit verwendet   Erstellen Sie den Code.

Dies sollte Ihnen die ideale Lösung für Ihr Problem bei der Implementierung.

Edit: Obwohl ähnlich, das ist nicht das, was die OP war auf der Suche nach

.

Das wissenschaftliche Arbeit vom Schöpfer dieser Codes beschreibt eine Verallgemeinerung von Start-Schritt-Stop-Codes, Codes Start-Stopp. Allerdings beschreibt der Autor kurz, wie kurz vor dem Ende des Abschnitts optimale Start-Schritt-stop bekommen 2. eine statistische Zufallsvariable beinhaltet die Verwendung oder Brute-Force-Finanzierung die beste Kombination. Ohne vorherige Kenntnis der Datei ist, der Algorithmus O ((log n) ^ 3).

Hope, das hilft.

Answer 2

Der verwendete Ansatz war ich eine einfache Brute-Force-Lösung. Der Algorithmus folgt diesen grundlegenden Schritten:

1. Zählen Sie die Frequenz jeder Zahl in der Datei. Im gleichen Pass die Gesamtmenge der Zahlen in der Datei berechnen und die größte Anzahl als maxNumber bestimmen.

2. Berechne die Wahrscheinlichkeit jeder Nummer als seine Frequenz durch die Gesamtmenge von Zahlen in der Datei geteilt.

3. Sie fest, "optimalStop" als gleich log2 (maxNumber). Dies ist die ideale Anzahl von Bits, die verwendet werden sollten maxNumber wie in Shannon Informationstheorie und damit eine vernünftige Schätzung der optimalen maximalen Menge an Bits bei der Codierung einer bestimmten Zahl.

verwendet darzustellen

4. Für jeden "Start" Wert von 1 bis "optimalStop" Wiederholen Sie Schritt 5 bis 7:

5. Für jeden "Schritt" Wert von 1 bis ( "optimalStop" - "Start") / 2, wiederholen Sie Schritt 6 und 7:

6. Berechnen Sie den Wert "Stop" am nächsten "optimalStop" das genügt stoppen = start + Schritt * i für eine ganze Zahl i.

7. Berechnen Sie die durchschnittliche Anzahl von Bits, die von dieser Codierung verwendet werden würde. Dies kann als jede Zahl der Wahrscheinlichkeit durch seine Bit-Länge in der gegebenen Codierung.

multipliziert berechnet werden

8. Pick die Codierung mit der niedrigsten durchschnittlichen Anzahl von Bits.