Eine Anmerkung zum Ziv - Lempel-Modell zur Kompression einzelner Sequenzen (Korrespondenz)

Der Ziv-Lempel-Kompressionsalgorithmus ist ein Ansatz zur Datenkompression, der auf Mustererkennung und Parsing basiert. Das symbolweise Äquivalent für Parsing-Modelle wurde von Rissanen und Langdon definiert und liefert die gleiche ideale Codelänge bei denselben Kosten in Kodierungsparametern. Durch die Beschreibung des Kontexts und der Kodierungsparameter für jedes Symbol wird Einblick gegeben, wie die Ziv-Lempel-Methode Kompression erreicht. Diese Behandlung verwendet keine probabilistische Quelle für den Datenstring. Die Ziv-Lempel-Methode zählt effektiv die Symbolinstanzen innerhalb der analysierten Phrasen. Der Kodierungsparameter für jeden symbolweisen Kontext wird durch kumulative Zählverhältnisse bestimmt. Die Zunahme der Code-String-Länge für ein Symbol y, das auf dem Teilstring s folgt, unter dem symbolweisen Äquivalent ist der Logarithmus des Verhältnisses der Knotenzählungen in den Teilbäumen s und s y des Ziv-Lempel Parsing-Baums. Um das symbolweise Äquivalent des Ziv-Lempel-Algorithmus zu demonstrieren, erweitern wir die Arbeiten von Rissanen und Langdon auf unvollständige Parse-Bäume. Das Ergebnis erfordert die ordnungsgemäße Handhabung des Kommas, wenn eine Phrase das Präfix einer anderen Phrase ist.