Tekst źródłowy strony Sequitur

'''Sequitur''' – [[kodowanie gramatykowe|algorytm kompresji]], który znajduje dla podanego tekstu opisującą go [[gramatyka bezkontekstowa|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|linki zewnętrzne]]).

Sequitur dla danych tekstowych, charakteryzujących się dużą powtarzalnością umożliwia uzyskanie dobrego [[stopień kompresji|stopnia kompresji]]. Ponadto można ją zaimplementować, tak aby działała w [[złożoność obliczeniowa|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:
# żadna para sąsiednich symboli ([[Gramatyka formalna|terminalnych]] i [[Gramatyka formalna|nieterminalnych]]) nie występuje więcej niż raz,
# każda [[Gramatyka formalna|produkcja]] wykorzystywana jest co najmniej dwa razy.

Algorytm składa się z dwóch głównych kroków:
# '''rozszerzenie gramatyki''' – dopisywanie kolejnych symboli wejściowych do [[symbol startowy|produkcji startowej]] (tu ozn. <math>S</math>),
# '''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 <math>b</math> do produkcji <math>S \to abcda</math> przyjmie ona postać – <math>S \to \underline{\color{Blue}ab}cd\underline{\color{Blue}ab}.</math> Powtarza się para <math>ab,</math> stąd zostaje dodana nowa produkcja <math>A \to ab,</math> a startowa przyjmuje postać <math>S \to AcdA.</math>

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 <math>c,</math> produkcja startowa przyjmuje postać <math>S \to \underline{\color{Blue}Ac}d\underline{\color{Blue}Ac},</math> dodawana jest nowa reguła <math>B \to Ac.</math> Gramatyka ma teraz postać:
* <math>S \to BdB,</math>
* <math>\color{Red}A \to ab,</math>
* <math>B \to {\color{Red}A}c,</math>

produkcja druga <math>(A)</math> jest wykorzystywana tylko raz (w produkcji 3, <math>B</math>). Po jej usunięciu gramatyka zostaje uproszczona do:
* <math>S \to BdB,</math>
* <math>B \to abc.</math>

== Zobacz też ==
* [[LZ78]]
* [[LZW]]

== Linki zewnętrzne ==
* {{cytuj stronę |url = http://sequitur.info/ |tytuł = Oficjalna strona, zawierająca publikacja i przykładowe aplikacje |język = en |archiwum = https://web.archive.org/web/20081013024323/http://www.sequitur.info/ |zarchiwizowano = 2008-10-13 |data dostępu = 2008-09-14}}

[[Kategoria:Algorytmy kompresji bezstratnej]]