Sequitur (oder Nevill-Manning-Witten-Algorithmus ) ist ein rekursiver Algorithmus, der 1997 von Craig Nevill-Manning und Ian H. Witten entwickelt wurde [ 1 ] und aus einer Folge diskreter Symbole eine hierarchische Struktur ( kontextfreie Grammatik ) ableitet. Der Algorithmus benötigt linearen Speicherplatz und lineare Laufzeit. Er kann in Softwareanwendungen zur Datenkomprimierung eingesetzt werden. [ 2 ]

Einschränkungen

Der Sequitur-Algorithmus konstruiert eine Grammatik, indem er wiederkehrende Phrasen in der gegebenen Sequenz durch neue Regeln ersetzt und somit eine prägnante Darstellung der Sequenz erzeugt. Zum Beispiel, wenn die Sequenz lautet:

S→abcab,

Der Algorithmus wird Folgendes erzeugen

S→AcA, A→ab.

Beim Scannen der Eingabesequenz beachtet der Algorithmus zwei Bedingungen für die effiziente Generierung seiner Grammatik: Digramm-Eindeutigkeit und Regel-Nützlichkeit .

Digramm-Eindeutigkeit

Wird ein neues Symbol aus der Sequenz gelesen, wird es mit dem zuletzt gelesenen Symbol zu einem neuen Digramm verknüpft . Existiert dieses Digramm bereits, wird eine neue Regel eingeführt, die beide Vorkommen ersetzt. Dadurch wird sichergestellt, dass kein Digramm in der Grammatik mehrfach vorkommt. In der Sequenz S→abaaba beispielsweise ergeben sich nach dem Lesen der ersten vier Symbole die Digramme ab, ba und aa . Beim Lesen des fünften Symbols entsteht das bereits existierende Digramm 'ab'. Daher werden beide Vorkommen von 'ab' durch eine neue Regel (z. B. A) in S ersetzt . Die Grammatik lautet nun S→AaAa, A→ab , und dieser Prozess wird fortgesetzt, bis kein Digramm mehr doppelt vorkommt.

Regel-Utility

Diese Einschränkung stellt sicher, dass alle Regeln in den rechten Seiten aller Produktionen der Grammatik mehr als einmal verwendet werden. Das heißt, wenn eine Regel nur einmal vorkommt, wird sie aus der Grammatik entfernt und durch die Symbole ersetzt, aus denen sie gebildet wurde. Im obigen Beispiel würde die Grammatik nach dem Scannen des letzten Symbols und der Anwendung der Digramm-Eindeutigkeit auf 'Aa' Folgendes erzeugen: S→BB, A→ab, B→Aa . Da die Regel 'A' in der Grammatik nur einmal in B→Aa vorkommt , wird A entfernt, und die Grammatik lautet schließlich:

S→BB, B→aba .

Diese Einschränkung trägt dazu bei, die Anzahl der Regeln in der Grammatik zu reduzieren.

Methodenübersicht

Der Algorithmus scannt eine Folge von Terminalsymbolen und erstellt eine Liste aller gelesenen Symbolpaare. Sobald ein Paar ein zweites Mal vorkommt, werden die beiden Vorkommen in der Folge durch ein neu erstelltes Nichtterminalsymbol ersetzt . Die Liste der Symbolpaare wird an die neue Folge angepasst, und der Scanvorgang wird fortgesetzt. Wird das Nichtterminalsymbol eines Paares nur in der Definition des neu erstellten Symbols verwendet, wird es durch seine Definition ersetzt und aus der Liste der definierten Nichtterminalsymbole entfernt. Nach Abschluss des Scanvorgangs kann die transformierte Folge als oberste Regel einer Grammatik für die ursprüngliche Folge interpretiert werden. Die Regeldefinitionen für die darin enthaltenen Nichtterminalsymbole finden sich in der Liste der Symbolpaare. Diese Regeldefinitionen können ihrerseits weitere Nichtterminalsymbole enthalten, deren Regeldefinitionen ebenfalls in der Liste der Symbolpaare zu finden sind. [ 3 ]

Siehe auch

Referenzen

  1. ^ Nevill-Manning, CG ; Witten, IH (1997). „Identifizierung hierarchischer Strukturen in Sequenzen: Ein linearer Algorithmus“. arXiv : cs/9709102 . Bibcode : 1997cs........9102N .{{cite journal}}: Zeitschrift zitieren erfordert |journal=( Hilfe )
  2. ^ Nevill-Manning, CG ; Witten, IH (1997). „Lineare, inkrementelle Hierarchieinferenz für die Komprimierung“. Proceedings DCC '97. Data Compression Conference . S.  3–11 . CiteSeerX 10.1.1.30.2305 . doi : 10.1109/DCC.1997.581951 . ISBN  978-0-8186-7761-8. S2CID  14324301 .
  3. ^ GrammarViz 2.0 – Sequitur und parallele Sequitur-Implementierungen in Java, Sequitur-basierte Erkennung von Zeitreihenmustern