Sequitur

Sequitur – algorytm kompresji, który znajduje dla podanego tekstu opisującą go gramatykę bezkontekstową; następnie gramatyka jest kompresowana konwencjonalnymi metodami. Metoda została opracowana w 1996 roku przez Craiga Nevill-Manninga oraz Iana Wittena (patrz sekcja linki zewnętrzne).

Sequitur dla danych tekstowych, charakteryzujących się dużą powtarzalnością umożliwia uzyskanie dobrego stopnia kompresji. Ponadto można ją zaimplementować, tak aby działała w czasie liniowym (liczba operacji wprost proporcjonalna do długości tekstu). Wada: kodowany jest cały tekst, nie ma możliwości kompresowania strumienia danych.

Algorytm kodowania

Na gramatykę nakłada dwa ograniczenia:

  1. żadna para sąsiednich symboli (terminalnych i nieterminalnych) nie występuje więcej niż raz,
  2. każda produkcja wykorzystywana jest co najmniej dwa razy.

Algorytm składa się z dwóch głównych kroków:

  1. rozszerzenie gramatyki – dopisywanie kolejnych symboli wejściowych do produkcji startowej (tu ozn. S {\displaystyle S} ),
  2. modyfikacja gramatyki – jeśli któreś z ograniczeń zostanie złamane.

Po rozszerzeniu gramatyki może zostać złamane pierwsze ograniczenie, co powoduje konieczność dodania nowej produkcji. Np. po dopisaniu symbolu b {\displaystyle b} do produkcji S → a b c d a {\displaystyle S\to abcda} przyjmie ona postać – S → a b _ c d a b _ . {\displaystyle S\to {\underline {\color {Blue}ab}}cd{\underline {\color {Blue}ab}}.} Powtarza się para a b , {\displaystyle ab,} stąd zostaje dodana nowa produkcja A → a b , {\displaystyle A\to ab,} a startowa przyjmuje postać S → A c d A . {\displaystyle S\to AcdA.}

Z kolei drugie ograniczenie może zostać złamane po dodaniu nowej produkcji, gdy zastępuje ona wystąpienia innej produkcji. Np. po dopisaniu symbolu c , {\displaystyle c,} produkcja startowa przyjmuje postać S → A c _ d A c _ , {\displaystyle S\to {\underline {\color {Blue}Ac}}d{\underline {\color {Blue}Ac}},} dodawana jest nowa reguła B → A c . {\displaystyle B\to Ac.} Gramatyka ma teraz postać:

  • S → B d B , {\displaystyle S\to BdB,}
  • A → a b , {\displaystyle \color {Red}A\to ab,}
  • B → A c , {\displaystyle B\to {\color {Red}A}c,}

produkcja druga ( A ) {\displaystyle (A)} jest wykorzystywana tylko raz (w produkcji 3, B {\displaystyle B} ). Po jej usunięciu gramatyka zostaje uproszczona do:

  • S → B d B , {\displaystyle S\to BdB,}
  • B → a b c . {\displaystyle B\to abc.}

Zobacz też

  • LZ78
  • LZW

Linki zewnętrzne

  • Oficjalna strona, zawierająca publikacja i przykładowe aplikacje. [dostęp 2008-09-14]. [zarchiwizowane z tego adresu (2008-10-13)]. (ang.).