Kodowanie gramatykowe

Kodowanie gramatykowe (ang. grammar-based coding) – nazwa grupy algorytmów kodowania stosowanych w bezstratnej kompresji danych, w których dane wejściowe opisuje się gramatyką bezkontekstową, dąży się przy tym do minimalizacji ilości reguł. Następnie gramatyka jest kompresowana innymi metodami. Kodowanie sprawdza się m.in. w kompresji DNA oraz tekstów naturalnych, w których powtarzają się ciągi liter, ale często też całe słowa, frazy czy zdania.

Idea kodowania gramatykowego wykorzystuje powtórzenia ciągów liter, które są zastępowane specjalnymi symbolami (nieterminalnymi). Np. w tekście „aaabaaacaaadaaae” powtarza się ciąg „aaa”, stąd gramatyka, która go opisuje może składać się z dwóch reguł:

1. $A\to aaa$ – reguła pomocnicza, zapamiętująca powtórzenie;
2. $S\to AbAcAdAe$ – reguła główna, opisująca cały tekst (gdzie $S$ to symbol startowy).

Istnieją dwa podejścia do budowania gramatyki:

1. Kodowanie rozpoczyna się od pustego ciągu, do którego dopisywane są kolejne litery z tekstu i gdy zajdzie potrzeba, tworzone są nowe reguły pomocnicze. Metody działające według tego schematu:
   • LZ78, LZW,
   • Sequitur.
2. Kodowanie rozpoczyna się od wejściowego tekstu i w wyniku jego całościowej analizy podejmowane są decyzje o dodaniu nowych reguł. Metody działające według tego schematu:
   • Multilevel Pattern Matching (MPM),
   • Byte Pair Encoding (BPE),
   • Greedy.

LZ78, LZW

Chociaż metoda LZ78 (i pochodne) jest klasyfikowana jako kodowanie słownikowe, obecnie rozważa się ją także w kategoriach kodowania gramatykowego. Podstawowym krokiem kodowania jest dodawanie do słownika konkatenacji najdłuższego słowa ze słownika pasującego do początku niezakodowanych jeszcze danych oraz kolejnego symbolu; np. jeśli do zakodowania jest słowo „wiki”, a w słowniku istnieje „wik”, to do słownika trafia „wik” + „i”.

Z punktu widzenia kodowania gramatykowego słownik jest tożsamy z listą reguł, zaś jego rozszerzenie z dodaniem nowej; np. jeśli istnieje reguła $A\to wik$ i ma zostać zakodowane „wiki”, wówczas dodawana jest nowa reguła $B\to Ai.$

Multilevel Pattern Matching (MPM)

Uniwersalna metoda MPM została opracowana przez Johna Kieffere, En-hui Yanga, Gregora Nelsona oraz Pamelę Cosman ([MPM2000]). Jednakże jej specjalny przypadek był znany już w latach 70. XX wieku i stosowany w zapisie oraz działaniach na funkcjach boolowskich (binary decision diagrams – BDD); metoda ta była już wówczas traktowana jako pewna forma kompresji danych.

W MPM kodowany tekst jest rekurencyjnie dzielony na podsłowa, następnie wszystkie słowa na tym samym poziomie podziału są zamieniane na reguły mające po prawej stronie słowa z głębszego poziomu. MPM zakłada dowolny podział, na 2, 3, 4 i więcej części.

Na przykład kodowanie tekstu aabbaaabababaaab dla podziałów na 2 części przebiega następująco:

• poziom 0 = $\underbrace {aabbaaabababaaab} _{S},$ produkcje: $S\to T_{1}T_{2},$
• poziom 1 = $\underbrace {aabbaaab} _{T_{1}},\underbrace {ababaaab} _{T_{2}},$ produkcje: $T_{1}\to U_{1}U_{2},T_{2}\to U_{3}U_{2},$
• poziom 2 = $\underbrace {aabb} _{U_{1}}\underbrace {aaab} _{U_{2}}\underbrace {abab} _{U_{3}}\underbrace {aaab} _{U_{2}},$ produkcje: $U_{1}\to V_{1}V_{2},U_{2}\to V_{1}V_{3},U_{3}\to V_{3}V_{3},$
• poziom 3 = $\underbrace {aa} _{V_{1}}\underbrace {bb} _{V_{2}}\underbrace {aa} _{V_{1}}\underbrace {ab} _{V_{3}}\underbrace {ab} _{V_{3}}\underbrace {ab} _{V_{3}}\underbrace {aa} _{V_{1}}\underbrace {ab} _{V_{3}},$ produkcje: $V_{1}\to aa,V_{2}\to bb,V_{3}\to ab.$

Jak widać już przy drugim podziale ujawniają się powtórzenia – zamiast $2^{2}=4$ ciągów, są 3 różne $(U_{1,2,3});$ podobnie na kolejnym – zamiast $2^{3}=8$ ciągów, są zaledwie 3 różne $(V_{1,2,3}).$

Byte Pair Encoding (BPE)

Metoda została opisana w pracy [BPE1999]. Nie daje ona wyraźnie lepszej kompresji danych – współczynniki kompresji, a także czas kompresji są gorsze niż popularnych metod opartych na LZ77 czy LZ78 (np. gzip). Jednak wyszukiwanie wzorców w skompresowanych tekstach jest szybsze i łatwiejsze – nie jest wymagana dekompresja.

Tworzenie gramatyki (kompresowanie) polega na iteracyjnym dodawaniu nowych reguł dla najczęściej powtarzających się par symboli w produkcji startowej.

Np.

1. $S\to {\underline {\color {Blue}ab}}cd{\underline {\color {Blue}ab}}cdac{\underline {\color {Blue}ab}}ad,$
2. $S\to A{\underline {\color {Blue}cd}}A{\underline {\color {Blue}cd}}acAad,$ $A\to ab,$
3. $S\to {\underline {\color {Blue}AB}}{\underline {\color {Blue}AB}}acAad,$ $A\to ab,$ $B\to cd,$
4. $S\to CCacAad,$ $A\to ab,$ $B\to cd,$ $C\to AB.$

Greedy

Pomysłodawcami metody opisanej w [GRE2000] są Aleberto Apostolico oraz Stefano Lonardi. Metoda greedy (zachłanna) rozpoczyna od całego tekstu, następnie wyszukiwany jest ciąg, którego zastąpienie przez wprowadzenie nowej produkcji spowoduje maksymalne skrócenie gramatyki. Zasada działania jest więc dość podobna do opisanej metody BPE, z tą różnicą, że kryteria wyboru ciągu są bardziej złożone.

Eksperymenty autorów wykazały, że metoda daje lepsze współczynniki kompresji niż popularne kompresory gzip, bzip2 i compress.

Zobacz też

• kodowanie słownikowe

Bibliografia

• Eric Lehman: Approximation Algorithms for Grammar-Based Data Compression. luty 2002, s. 37–76. (ang.).
• [BPE1999] Yusuke Shibata, Takuya Kida, Shuichi Fukamachi, Masayuki Takeda, Ayumi Shinohara, Takeshi Shinohara, Setsuo Arikawa: Byte pair encoding: a text compression scheme that accelerates pattern matching. 1999. (ang.).brak strony w książce
• [MPM2000] John Kieffer, En-hui Yang, Gregory Nelson, Pamela Cosman: Universal lossless compression via multilevel pattern matching. 2000. (ang.).brak strony w książce
• [GRE2000] Aleberto Apostolico, Stefano Lonardi: Off-Line Data Compression by Textual Substitution. 2000. (ang.).brak strony w książce