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

• $S\to BdB,$
• $A\to ab,$
• $B\to Ac,$

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

• $S\to BdB,$
• $B\to abc.$

Zobacz też

• LZ78
• LZW

Linki zewnętrzne

• Szablon:Cytuj stronę