Grundlegendes zur Komprimierung / Codierung in linearer Zeit

Ich lese den Artikel NJ Larsson, A. Moffat: Offline Dictionary-Based Compression , der einen Komprimierungsalgorithmus beschreibt, der, wenn ich ihn richtig verstehe, der Bytepaar-Codierung ziemlich ähnlich ist .

Bei einer Zeichenfolge der Länge versuche ich zu verstehen, wie man sie mit dieser Komprimierungsmethode in linearer Zeit ( komprimieren kann. Wie genau wird das gemacht? Ich habe die Zeitung gelesen, aber ich verstehe immer noch nicht, wie sie eine lineare Zeit erreichen. Vielleicht würde ich sie auf eine andere Weise erklären. $S$ $n$ $\mathcal O (n)$

Meine erste Verwirrung entsteht im ersten Schritt des Algorithmus, wo wir das häufigste Paar finden, z. B. wenn abcababcabcdas häufigste Paar abbeispielsweise durch ein neues Symbol ersetzt wird XcXXcXc. Ich verstehe nicht, wie wir das häufigste Paar schnell genug finden können. Mein naiver Ansatz wäre, zuerst das erste Paar zu betrachten abund dann die Anzahl der Vorkommen zu zählen, dann das nächste Paar zu betrachten bcund die Anzahl der Vorkommen usw. zu zählen. Dies würde jedoch bereits nur für geben einmal das häufigste Paar finden . $\mathcal O (n^2)$

Als nächstes, selbst wenn ich verstanden habe, wie man das häufigste Paar in Zeit findet. Mein nächstes Problem ist, dass wir nicht das häufigste Paar bis zu mal finden müssen? Und daher würde dies eine Gesamtzeit von ? $\mathcal O(n)$ $\mathcal O(n)$ $\mathcal O(n^2)$

algorithms algorithm-analysis runtime-analysis data-compression encoding-scheme Eff
quelle

Sie sollten eine spezifischere Frage stellen. Das Wiederholen eines Papiers in anderen Worten scheint für diese Site zu weit gefasst zu sein. Wo in der Zeitung verlieren dich die Autoren?

AdrianN

@adrianN Ich habe ein bisschen mehr darüber geschrieben, worüber ich konkret verwirrt bin.

Eff

Das Papier ging davon aus, dass eine Hash-Tabelle verwendet wird, und zählte sie als . In diesem Fall könnte wlog durch den Suffixbaum . Ich habe gerade den Text überflogen, Ihre Frage ist immer noch sehr anspruchsvoll, aber ich verstehe nicht wirklich, warum Sie nur für einen Artikel ausgeben würden .

O (n)

$\mathcal O(n)$

O (n)

$\mathcal O(n)$

O (n^{2})

$\mathcal O(n^2)$

Evil

@Evil Sie sagen also, dass man einen Suffixbaum von in -Zeit erstellen könnte (Übrigens verstehe ich immer noch nicht, wann es möglich ist, einen Suffixbaum in linearer Zeit zu erstellen und wann ). Dann finden wir die häufigste Teilzeichenfolge im Suffixbaum in -Zeit. Richtig?

S

$S$

Θ (n)

$\Theta (n)$

O (n \log n)

$\mathcal O (n\log n)$

Θ (n)

$\Theta (n)$

Eff

Mir? Nein, aber Ukkonen hat ein paar Worte darüber gesagt. für Alphabet konstanter Größe und im Allgemeinen. Dann können wir nach Frequenzen in sortieren oder sogar kleine natürliche Zahlen zum Zählen der Sortierung verwenden. Ich bin nicht sicher, ob etwas 1 ~ n , sorry, keine Antwort für diesen Teil.

O (n)

$\mathcal O(n)$

O (n \log n)

$\mathcal O(n\log n)$

O (n \log n)

$\mathcal O(n\log n)$

Θ (n)

$\Theta(n)$

Evil

Antworten:

Ich habe den Code überprüft, das Papier erneut gelesen und es scheint, dass der Algorithmus in nicht so funktioniert, wie Sie es beschrieben haben. Die rekursiven Aufrufe zum Finden von Paaren funktionieren in $\mathcal O(n)$
$\mathcal O(n \log n)$ geteilt durch konstant, wenn Sie es bis zum Ende packen möchten. Tatsächlich behält die darunter liegende Struktur Zeiger auf das erste Auftreten von Paaren bei, teilt die Warteschlange von Paaren nach Vorkommen auf, um sie effizient, aber dennoch loglinear zu machen. Auf der anderen Seite durch Analyse des von Ph.D. Schüler des Autors Ich habe mehrere Tricks entdeckt - die Länge der Paare (der ursprüngliche Name) wird als Parameter angegeben (Standard ist 2) und die Wiederholung wird durch Parameter begrenzt, die weitere Aufrufe verwerfen können (Standard ist ungefähr 5 Ebenen), mit Fähigkeit, nur einen Durchgang zu machen oder bis zum Ende zu schieben. Der Standardcode wird in , führt jedoch nicht zu einer optimalen Komprimierung. Es gibt auch Schalter, um Speicher, Zeit oder Neutralität zu bevorzugen. $\mathcal O(n)$

Das Papier und der Code zeigen die Verwendung der Hash-Tabelle, die nur in der erwarteten konstanten Zeit ausgeführt wird, aber die angegebene Funktion funktioniert sehr gut mit Zeichen. Außerdem begrenzt der Code die Eingabelänge durch konstante Hardcodierung.

Das Ändern der Hashtabelle in einen Suffixbaum und das Umschreiben des Teils der Wiederholung in Teilpaare der Buchhaltung kann zu besseren Ergebnissen führen. Ich bin mir nicht sicher, ob dies möglich ist, um zu erstellen. Dies wäre wahrscheinlich eine andere Frage. $\mathcal O(n)$

Es wird auch ein Trick verwendet, um das Durchlaufen des leeren Raums zu verhindern - der Beginn eines leeren Blocks zeigt auf das erste nicht leere Zeichen, dies beschleunigt jedoch nur das Durchlaufen, immer noch mit loglinearer Zeit. Der Teil, der für dieses Verhalten verantwortlich ist, ersetzt Paare bei jeder Iteration durch das neue Zeichen. Es wäre schneller, nur die Regeln für das Umschreiben beizubehalten und sie zu bearbeiten. Der Zugriff auf die Überprüfung, ob neue Paare eingeführt wurden, würde jedoch erfordern, die Regeln für das Umschreiben mit den neuen Regeln zu vergleichen. In dem Fall erstellen wir einen vollständigen Binärbaum mit Paaren an den Blättern, so dass wir nach dem Ersetzen des Paares durch ein neues Zeichen und der Abstimmung mit dem Elternteil neue Paare an den Blättern bis zur Wurzel erhalten - es gibt Chatacters, dann Paare, dann , $n$ $\frac{n}{2}$ $\frac{n}{4}$ $\frac{n}{8}$ , ... sehen Sie das Muster, gibt es Paare, sondern nach Algorithmusbeschreibung Diese yelds Zeitnahme nur Eingangsdurchläufe. $\frac{n}{16}$ $2n$ $\mathcal O(n\log n + n)$

Böse
quelle