Sequitur

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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]

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. ),
  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 do produkcji przyjmie ona postać - . Powtarza się para , stąd zostaje dodana nowa produkcja , a startowa przyjmuje postać .

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 , produkcja startowa przyjmuje postać , dodawana jest nowa reguła . Gramatyka ma teraz postać:

  • ,
  • ,
  • ,

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

  • ,
  • .

Zobacz też[edytuj]

Linki zewnętrzne[edytuj]