Kodowanie gramatykowe

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

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 \rightarrow aaa - reguła pomocnicza, zapamiętująca powtórzenie;
  2. S \rightarrow 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:
  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[edytuj | edytuj kod]

Information icon.svg Osobne artykuły: LZ78LZW.

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 \rightarrow wik i ma zostać zakodowane "wiki", wówczas dodawana jest nowa reguła B \rightarrow Ai.

Sequitur[edytuj | edytuj kod]

Information icon.svg Osobny artykuł: Sequitur.

Multilevel Pattern Matching (MPM)[edytuj | edytuj kod]

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 (BDD - binary decision diagrams); 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 \rightarrow T_1 T_2
  • poziom 1 = \underbrace{aabbaaab}_{T_1}, \underbrace{ababaaab}_{T_2}, produkcje: T_1 \rightarrow U_1 U_2, T_2 \rightarrow 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 \rightarrow V_1 V_2, U_2 \rightarrow V_1 V_2, U_3 \rightarrow 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 \rightarrow ab, V_2 \rightarrow bb, V_3 \rightarrow 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)[edytuj | edytuj kod]

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 \rightarrow \underline{\color{Blue}ab}cd\underline{\color{Blue}ab}cdac\underline{\color{Blue}ab}ad
  2. S \rightarrow A\underline{\color{Blue}cd}A\underline{\color{Blue}cd}acAad, A \rightarrow ab
  3. S \rightarrow \underline{\color{Blue}AB}\underline{\color{Blue}AB}acAad, A \rightarrow ab, B \rightarrow cd
  4. S \rightarrow CCacAad, A \rightarrow ab, B \rightarrow cd, C \rightarrow AB

Greedy[edytuj | edytuj kod]

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[1].

Zobacz też[edytuj | edytuj kod]

Przypisy

Bibliografia[edytuj | edytuj kod]

  • 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.)
  • [MPM2000] John Kieffer, En-hui Yang, Gregory Nelson, Pamela Cosman: Universal lossless compression via multilevel pattern matching. 2000. (ang.)
  • [GRE2000] Aleberto Apostolico, Stefano Lonardi: Off-Line Data Compression by Textual Substitution. 2000. (ang.)