Sequitur – Wikipedia, wolna encyklopedia

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.

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. ${\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 ${\displaystyle b}$ do produkcji ${\displaystyle S\to abcda}$ przyjmie ona postać – ${\displaystyle S\to {\underline {\color {Blue}ab}}cd{\underline {\color {Blue}ab}}.}$ Powtarza się para ${\displaystyle ab,}$ stąd zostaje dodana nowa produkcja ${\displaystyle A\to ab,}$ a startowa przyjmuje postać ${\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 ${\displaystyle c,}$ produkcja startowa przyjmuje postać ${\displaystyle S\to {\underline {\color {Blue}Ac}}d{\underline {\color {Blue}Ac}},}$ dodawana jest nowa reguła ${\displaystyle B\to Ac.}$ Gramatyka ma teraz postać:

• ${\displaystyle S\to BdB,}$
• ${\displaystyle \color {Red}A\to ab,}$
• ${\displaystyle B\to {\color {Red}A}c,}$

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

• ${\displaystyle S\to BdB,}$
• ${\displaystyle B\to abc.}$

• LZ78
• LZW

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