Gramatický kód - Grammar-based code

Rovná gramatika (se symbolem začátku ß) pro druhou větu Deklarace nezávislosti Spojených států. Každý modrý znak označuje a neterminální symbol; byly získány od a gzip -komprese věty.

Gramatické kódy nebo Gramatická komprese jsou komprese algoritmy založené na myšlence konstrukce a bezkontextová gramatika (CFG) pro řetězec, který má být komprimován. Mezi příklady patří univerzální bezztrátová komprese dat algoritmy.[1] Komprese datové sekvence se kód založený na gramatice transformuje do bezkontextové gramatiky Problém najít nejmenší gramatiku pro vstupní sekvenci (nejmenší gramatická úloha ) je známo, že je NP-tvrdý,[2] tolik algoritmů pro transformaci gramatiky je navrženo z teoretického i praktického hlediska. Obecně platí, že vytvořená gramatika je dále komprimován statistickými kodéry jako aritmetické kódování.

Příklady a charakteristiky

Třída kódů založených na gramatice je velmi široká. To zahrnuje blokové kódy, variace přírůstkové analýzy Kód Lempel-Ziv,[3] algoritmus víceúrovňového porovnávání vzorů (MPM),[4] a mnoho dalších nových univerzálních bezztrátových kompresních algoritmů. Kódy založené na gramatice jsou univerzální v tom smyslu, že mohou dosáhnout asymptoticky míra entropie jakéhokoli stacionárního, ergodický zdroj s konečnou abecedou.

Praktické algoritmy

Následující programy pro kompresi jsou k dispozici z externích odkazů.

  • Sequitur[5] je klasický algoritmus komprese gramatiky, který postupně překládá vstupní text do CFG a potom je vytvořený CFG kódován aritmetickým kodérem.
  • Opravit[6] je chamtivý algoritmus využívající strategii substituce nejčastější první. Kompresní výkon je vysoký, i když je hlavní paměťový prostor velmi velký.
  • GLZA,[7] který konstruuje gramatiku, která může být redukovatelná, tj. obsahuje opakování, kde náklady na entropické kódování „hláskování“ opakování jsou menší než náklady na vytváření a entropické kódování pravidla k jejich zachycení. (Obecně platí, že SLG s optimální kompresí není neredukovatelná a problém s nejmenší gramatikou se liší od skutečného problému s kompresí SLG.)

Viz také

Reference

  1. ^ Kieffer, J. C .; Yang, E.-H. (2000), "Gramatické kódy: Nová třída univerzálních bezztrátových zdrojových kódů", IEEE Trans. Inf. Teorie, 46 (3): 737–754, doi:10.1109/18.841160
  2. ^ Charikar, M .; Lehman, E .; Liu, D .; Panigrahy, R .; Prabharakan, M .; Sahai, A .; Shelat, A. (2005), „Nejmenší gramatický problém“, IEEE Trans. Inf. Teorie, 51 (7): 2554–2576, doi:10.1109 / tit.2005.850116
  3. ^ Kieffer, J. C .; Yang, E.-H .; Nelson, G .; Cosman, P. (2000), „Univerzální bezztrátová komprese pomocí víceúrovňového porovnávání vzorů“, IEEE Trans. Inf. Teorie, 46 (4): 1227–1245, doi:10.1109/18.850665
  4. ^ Ziv, J .; Lempel, A. (1978), "Komprese jednotlivých sekvencí pomocí kódování s proměnnou rychlostí", IEEE Trans. Inf. Teorie, 24 (5): 530–536, doi:10.1109 / TIT.1978.1055934, hdl:10338.dmlcz / 142945
  5. ^ Nevill-Manning, C. G .; Witten, I. H. (1997), „Identifikace hierarchické struktury v sekvencích: algoritmus lineárního času“, Journal of Artificial Intelligence Research, 7 (4): 67–82, arXiv:cs / 9709102, doi:10.1613 / jair.374, hdl:10289/1186
  6. ^ Larsson, N.J .; Moffat, A. (2000), „Offline slovníková komprese“ (PDF), Sborník IEEE, 88 (11): 1722–1732, doi:10.1109/5.892708
  7. ^ Conrad, Kennon J .; Wilson, Paul R. (2016), „Grammatical Ziv-Lempel Compression: Achievinging PPM-Class Text Compression Ratios with LZ-Class Decompression Speed“, Konference IEEE pro kompresi dat: 586, doi:10.1109 / DCC.2016.119, ISBN  978-1-5090-1853-6

externí odkazy