Shoda komprimovaného vzoru - Compressed pattern matching

v počítačová věda, komprimované porovnávání vzorů (ve zkratce CPM) je proces hledání vzorů v komprimovaných datech s malou nebo žádnou dekompresí. Hledání v komprimovaném řetězci je rychlejší než hledání nekomprimovaného řetězce a vyžaduje méně místa.

Problém s komprimovanou shodou

Pokud stlačený soubor používá kódování s proměnnou šířkou může to představovat problém: například „100“ nechť je kódové slovo pro A a kódovým slovem nechť „110100“ b. Pokud hledáme výskyt A v textu bychom mohli získat jako výsledek také výskyt, který je v rámci kódového slova b: tuto událost nazýváme falešná shoda. Musíme tedy ověřit, zda je zjištěný výskyt skutečně zarovnán na hranici kódového slova. Vždy jsme však mohli dekódovat celý text a poté použít klasiku algoritmus shody řetězců, ale to obvykle vyžaduje více prostoru a času a často to není možné, například pokud je komprimovaný soubor hostován online. Tento problém ověřování shody vrácené komprimovaným algoritmem porovnávání vzorů je pravdivá nebo nepravdivá shoda spolu s nemožností dekódování celého textu se nazývá problém s komprimovanou shodou.

Strategie

Existuje mnoho strategií, jak najít hranice kódových slov a vyhnout se úplné dekompresi textu, například:

  • Seznam indexů prvního bitu každého kódového slova, kde můžeme použít binární vyhledávání;
  • Seznam indexů prvního bitu každého kódového slova s ​​diferenciálním kódováním, abychom mohli v souboru zabrat méně místa;
  • Bitová maska, kde bit 1 označuje počáteční bit každého kódového slova;
  • Členění v blocích, pro částečnou a cílenou dekompresi.

Reference

externí odkazy

  • Msgstr "Téměř optimální plně přizpůsobené vzory komprimované LZW". CiteSeerX  10.1.1.44.5521. Citovat deník vyžaduje | deník = (Pomoc)
  • Algoritmus pro komprimovaný vzor založený na slovníku (PDF), archivovány z originál (PDF) 13. března 2003
  • Msgstr "Sjednocující rámec pro komprimované porovnávání vzorů". CiteSeerX  10.1.1.50.1745. Citovat deník vyžaduje | deník = (Pomoc)
  • „Urychlení shody řetězcových vzorů pomocí komprese textu: úsvit nové éry“ (PDF). Archivovány od originál (PDF) dne 8. 8. 2007. Citováno 2009-03-22. Citovat deník vyžaduje | deník = (Pomoc)
  • "Shift a přístup k porovnávání vzorů v komprimovaném textu LZW". CiteSeerX  10.1.1.15.4609. Citovat deník vyžaduje | deník = (Pomoc)
  • „Algoritmus LZW“ (PDF). Citovat deník vyžaduje | deník = (Pomoc)