Sequitur

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

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[edytuj | edytuj kod]

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

  • S \rightarrow BdB,
  • \color{Red}A \rightarrow ab,
  • B \rightarrow {\color{Red}A}c,

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

  • S \rightarrow BdB,
  • B \rightarrow abc.

Zobacz też[edytuj | edytuj kod]

Linki zewnętrzne[edytuj | edytuj kod]