Sequitur

Sequitur ist ein Algorithmus zur verlustfreien Datenkompression, welcher in der Arbeit „Identifying hierarchical structure in sequences: A linear-time algorithm“ von Craig Nevill-Manning und Ian Witten von der Universität von Waikato (Neuseeland) im Jahr 1997 beschrieben wurde.

Beschreibung

Sequitur ersetzt sich wiederholende Zeichenfolgen in Zeichenketten (z. B. Texten) mit Hilfe von grammatikalischen Regeln. Dieser Vorgang wird rekursiv durchgeführt. Als Ergebnis liefert Sequitur eine hierarchische Darstellung der ursprünglichen Folge, die Einsicht in ihre lexikalische Struktur gibt. Es wird der Umfang der Grammatik reduziert und als „Nebenprodukt“ die Sequenz strukturiert. Der Vorteil von Sequitur liegt in der iterativen Vorgangsweise.

Sequitur erzeugt eine von mehreren möglichen kontextfreien Grammatiken für eine gegebene Zeichenfolge. Diese Grammatik muss nicht zwangsläufig die optimale zum Zweck des Komprimierens sein. Zudem kann Sequitur sehr speicherintensiv sein, weswegen sich dieser Algorithmus nicht so gut zur Komprimierung eignet wie andere gängige Methoden.

Funktionsweise

Mit Hilfe des Sequitur-Algorithmus wird eine Zeichenkette $z\in \Sigma ^{*}$ in eine kontextfreie Grammatik $G$ mit $L(G)=\{z\}$ umgewandelt. Die Grammatik $G$ wird schrittweise aufgebaut. Dafür wird $z$ zeichenweise eingelesen. Tritt in $z$ eine Teilfolge zweimal auf, wird diese Teilfolge durch eine Variable ersetzt, die in ein Wörterbuch eingetragen wird (als Regel der Grammatik). Im Laufe des Aufbaus der Grammatik können nicht nur mehrmals auftretende Teilfolgen der ursprünglichen Zeichenkette, sondern auch (zur Gänze oder zum Teil) aus Variablen bestehende Teilfolgen durch Variablen ersetzt werden und somit Redundanzen entfernt werden.

Als Ergebnis liefert der Sequitur-Algorithmus eine Grammatik, die den Eingabestring mit weniger Symbolen darstellt. Die Kompressionsrate ist abhängig von der Codierung des Ergebnisses (der Grammatik). Hierfür wird beispielsweise die arithmetische Codierung verwendet.

Zeichenketten oder auch Teilstrings werden als „n-Gramme“ bezeichnet. Ein „n-Gramm“ der Länge 2 wird als „Bigramm“ oder „Digramm“ bezeichnet.

Folgende zwingende Regeln des Algorithmus erzeugen die bereits erwähnte, hierarchische Struktur des Ergebnisstrings:

• Digrammeindeutigkeit: Jedes Digramm im zu komprimierenden String darf höchstens einmal vorkommen. Ansonsten erfolgt eine Ersetzung durch eine (bereits bestehende oder neu erzeugte) Variable.

• Variablennützlichkeit: Jede Variable, die einen Teilstring der ursprünglichen Zeichenkette ersetzt, muss mindestens zweimal verwendet werden.

Erzeugung einer Sequitur-Grammatik

1. Es wird mit $G:=(\{S\},\Sigma ,S\rightarrow \varepsilon ,S)$ gestartet (vgl: formale Grammatik).
2. Die Symbole von $z$ werden der Reihe nach an die rechte Seite der zu $S$ gehörigen Produktion (= Zeichenfolge der bisher eingelesenen Zeichen) angehängt.
3. Wenn durch Schritt 2 zwei Symbole $\alpha ,\beta \in V\cup \Sigma$ zu Nachbarn werden, entsteht ein Digramm $\alpha \beta$. Für dieses Digramm bestehen zwei Möglichkeiten:
   1. $\alpha \beta$ ist eindeutig in der so entstandenen Grammatik.
   2. $\alpha \beta$ kommt ohne Überlappung genau ein weiteres Mal vor. Im Fall 2 gibt es wieder zwei Fälle:
      1. $\alpha \beta$ ist rechte Seite einer Produktion $X$ (d. h., es gibt bereits einen Wörterbucheintrag für $\alpha \beta$). Ersetze neu entstandenes $\alpha \beta$ durch bestehende Variable $X$. Springe zu Schritt 4, anschließend nochmal Schritt 3.
      2. $\alpha \beta$ ist nicht rechte Seite einer Produktion. Füge neue Regel $X\rightarrow \alpha \beta$ zu den Produktionen hinzu und ersetze beide Vorkommen von $\alpha \beta$ durch die neue Variable $X$. Springe zu Schritt 4, anschließend nochmal Schritt 3.
4. Wenn ein Digramm $\alpha \beta$ durch eine Variable ersetzt wird gibt es wieder zwei Möglichkeiten:
   1. $\alpha \in \Sigma \land \beta \in \Sigma$ ($\alpha$ und $\beta$ beinhalten keine Variablen)
   2. $\alpha \in V\lor \beta \in V$ ($\alpha$ oder $\beta$ oder $\alpha$ und $\beta$ beinhalten bereits Variablen). Unterscheide für alle Variablen $\gamma \in \{\alpha ,\beta \}$ (Variablen die in $\alpha$ oder $\beta$ enthalten sind) zwei Fälle:
      1. Variable $\gamma$ kommt noch an anderen Stellen vor.
      2. Variable $\gamma$ kommt sonst nicht mehr vor. Entferne die Regel $\gamma \rightarrow r\gamma$ aus den Produktionen und ersetze das einzige Vorkommen von $\gamma$ durch rechte Seite $r\gamma$ (also durch den Wörterbucheintrag für die entsprechende Variable). Springe zu Schritt 3.

Die gelb hinterlegten Stellen symbolisieren Ersetzungsvorgänge und bewirken daher immer einen Aufruf von Schritt 4. Kommt eine bisher benutzte Variable nämlich durch einen dieser Vorgänge nicht mehr länger vor, so muss die geforderte Variablennützlichkeit wiederhergestellt werden.

Alle drei farblich markierten Stellen bewirken rekursive Aufrufe von Schritt 3, da ein Ersetzungsvorgang immer bewirkt, dass neue Digramme entstehen. Es muss daher immer überprüft werden, ob die geforderte Digrammeindeutigkeit noch gegeben ist, bzw. muss diese gegebenenfalls wiederhergestellt werden.

Beispiel

Die folgende Tabelle zeigt anhand eines einfachen Beispiels, wie der Sequitur-Algorithmus funktioniert. Im Beispiel wird der Eingabestring „abcdbcabcd“ mit Hilfe des Sequitur-Algorithmus verlustfrei komprimiert. Es wird Schritt für Schritt gezeigt, wie der Eingabestring durchlaufen und dabei die neue Grammatik erzeugt wird.

Nummer	Bisheriger String	Grammatik	Anmerkung
1	a	S=a
2	ab	S=ab
3	abc	S=abc
4	abcd	S=abcd
5	abcdb	S=abcdb
6	abcdbc	S=abcdbc	bc doppelt
	abcdbc	S=aAdA A=bc	Digrammeindeutigkeit herstellen
7	abcdbca	S=aAdAa A=bc
8	abcdbcab	S=aAdAab A=bc
9	abcdbcabc	S=aAdAabc A=bc	bc doppelt
		S=aAdAaA A=bc	Digrammeindeutigkeit herstellen aA doppelt
		S=BdAB A=bc B=aA	Digrammeindeutigkeit herstellen
10	abcdbcabcd	S=BdABd A=bc B=aA	Bd doppelt
		S=CAC A=bc B=aA C=Bd	Digrammeindeutigkeit herstellen B wird nur mehr einmal verwendet
		S=CAC A=bc C=aAd	Variablennützlichkeit hergestellt

Der String „abcdbcabcd“ wird zeichenweise eingelesen und durchlaufen. Zu Beginn wird also nur das Zeichen „a“ betrachtet. Da der überprüfte String zu diesem Zeitpunkt nur aus einem Zeichen besteht, kann es hier natürlich auch noch keine Wiederholungen geben, es kann also noch keine Ersetzung durch eine Variable stattfinden.

String a
Wörterbuch (leer)

Danach wird das Zeichen „b“ hinzugefügt. Im String „ab“ kommt noch immer keine Zeichenfolge mindestens zweimal vor, daher ist auch hier noch keine Ersetzung möglich. Das Gleiche gilt für die Strings „abc“, „abcd“ und „abcdb“.

String ab, abc, abcd, abcdb
Wörterbuch (leer)

Nach dem Einlesen des 6. Zeichens entsteht der String „abcdbc“. In diesem String tritt die Zeichenfolge „bc“ zweimal auf („abcdbc“). Das Digramm „bc“ wird nun durch das Zeichen „A“ ersetzt. Es wird also eine neue Variable „A → bc“ erzeugt, und der String „abcdbc“ als „aAdA“ gespeichert.

String aAdA
Wörterbuch {A → bc}

Nun wird das Zeichen „a“ dazu eingelesen. Es entsteht der String „aAdAa“. In diesem String tritt keine neue Zeichenfolge doppelt auf.

String aAdAa
Wörterbuch {A → bc}

Nach dem Einlesen des 8. Zeichens entsteht der String „aAdAab“. Auch hier tritt noch keine neue Zeichenfolge mindestens zweimal auf.

String aAdAab
Wörterbuch {A → bc}

Nun wird das Zeichen „c“ dazu eingelesen. Es entsteht der String „aAdAabc“. In diesem String ist die bereits im Wörterbuch als Variable „A“ eingetragene Zeichenfolge „bc“ enthalten. Sie wird nun durch die Variable ersetzt. Es entsteht der neue String „aAdAaA“. Das Digramm „aA“ tritt nun zweimal auf und wird durch das Zeichen „B“ ersetzt. Es wird ein Wörterbucheintrag „B → aA“ erzeugt. Die Variable „B“ steht nun also für die Zeichenfolge „abc“. Der String wird als „BdAB“ gespeichert.

String BdAB
Wörterbuch {A → bc}, {B → aA}

Zum Schluss wird das letzte Zeichen „d“ eingelesen. Es entsteht der String „BdABd“. In diesem String tritt die Zeichenfolge „Bd“ zweimal auf. Für diese Zeichenfolge wird die neue Variable C (C → Bd) definiert. Die Zeichenfolge „Bd“ wird durch die Variable C ersetzt. Es entsteht der neue String „CAC“. Die Variable „B“ kommt in diesem String gar nicht mehr, und im Wörterbuch nur einmal vor. Die Bedingung der Variablennützlichkeit (r2) ist also nicht mehr erfüllt. Die Variable „B“ wird daher gelöscht. Die Variable „C“, die bisher als „Bd“ gespeichert war, wird durch den Wegfall der Variable „B“ in „aAd“ geändert (dadurch entsteht also ein längerer Wörterbucheintrag).

String CAC
Wörterbuch {A → bc}, {C → aAd}

Die mit Sequitur verlustfrei komprimierte Version der Zeichenfolge „abcdbcabcd“ lautet daher „CAC“ mit dem Wörterbuch {A → bc}, {C → aAd}.

Komprimierte Zeichenfolge: CAC

Wörterbucheinträge: A → bc C → aAd

Rekonstruierter Originalstring: abcdbcabcd

Analyse

Um die einzelnen Ersetzungsvorgänge schneller realisieren zu können, wenn ein Digramm mehrfach auftritt, werden die Produktionen der Grammatik als verkettete Listen gespeichert. Diese Listen sind ebenfalls untereinander verkettet. Dadurch kann, ausgehend von der Einsatzstelle der Variablen, schnell die Definition der Variablen (also der Wörterbucheintrag) gefunden werden. Zusätzlich wird ein Digramm-Index verwaltet. Dieser ermöglicht die schnelle Überprüfung, ob ein Digramm bereits einmal existiert. Der Index wird als Hashtabelle abgespeichert. Dadurch ist es möglich, in konstanter Zeit zu einem gesuchten Digramm die Positionen sämtlicher Vorkommen in den Produktionen zu finden. Bei einer wie hier beschriebenen Implementierung des Sequitur-Algorithmus sind Laufzeit und benötigter Speicher linear von der Länge des Ausgangsstrings abhängig. Das Laufzeitverhalten entspricht also $O(n),$ mit $n=$ Länge von $z.$

Weblinks

• Offizielle Homepage für Sequitur