English
předchozí hlavní stránka obsah další

PPMC

Základní informace

Historie

Metoda PPM byla vynalezena Johnem Clearym a Ianem Wittenem v roce 1984. V původní práci se hovořilo o PPMA a PPMB. Přípona "A" nebo "B" označuje escape kód použitý v algoritmu, zbytek je prakticky stejný. PPMC bylo prezentované Alistairem Moffatem. V Moffatově práci byla představena také metoda PPM', což je PPMC používající líné vylučování (lazy exclusion). Existují také další varianty jako PPMD, PPMZ, PPM*. Rozdíl mezi PPMC a PPMA(PPMB) je pouze ve způsobu výpočtu pravděpodobnosti escape sekvence.

Popis

PPM je adaptivní statistická technika datové komprese zapožená na kontextovém modelování a predikci. Její název je zkratka z Prediction by Partial Matching. PPM modely používají množinu předcházejících symbolů v nekomprimovaném proudu pro predikci následujícího symbolu.

Predikce jsou obvykle zredukované na pozici symbolu. Počet předcházejících symbolů n udává řád PPM modelu, který je označený PPM(n). Neohraničené varianty, kde kontext nemá délkové omezení, existují také a značí se PPM*. Jestliže není možno udelat žádnou predikci na všech n kontextových symbolech, zkusí se predikce s n-1 symboly. Tento proces se opakuje, dokud není nalezena shoda, nebo v kontextu nezůstanou žádné symboly. V takovém případě se provede fixní predikce. Tento proces je opačným k procesu komprese DMC, která buduje model od nultého řádu.

Vylučování (exclusion): jestliže používáme escape kódy, tak pokud jsme v určitém kontextu, vylučujeme z výpočtu pravděpodobnosti nižších řádů, protože bereme do úvahy pouze pravděpodobnosti současného řádu. Hovoříme pak o líném vylučování (lazy exclusion). Pokud vylučujeme symboly, které se vyskytly ve vyšších řádech, hovoříme o plném vylučování.

Poznámka: změna délky kontextu se projeví po resetování apletu.

Pseudokód


Vstup: A text T = t1t2...t|T|, T patrí S+.
Výstup: PPM(T).
  
 1:  begin
 2:     for (i = 1 to |T|) do
 3:      begin
 4:        j := N {Začni najdlhším kontextom}
 5:  	     while ((j > -1) AND (p(ti|cj) = 0)) do
 6:         begin
 7:           output(code(┬))
 8:           j := j - 1;
 9: 	      end
10: 	     if (j > -1) then
11:           zakóduj ti použitím p(ti|cj);
12: 	     else
13:           zakóduj ti použitím p = 1/|S|;
14:      end
15:  end

p(ti|cj): Pravdepodobnosť znaku ti v kontexte dĺžky j (i.e. ti-j...ti-1|ti)

Výstup: AC(c,x,y) - Aritmetická kompresia znaku c s pravdepodobnostným rozsahom <x,y)

Odkazy

  1. Arturo San Emeterio Campos: Implementing PPMC with hash tables.
  2. PPM compression algorithm. Wikipedia, the free encyclopedia.
  3. T. Bell, J. Cleary, and I. Witten: Data compression using adaptive coding and partial string matching. IEEE Transactions on Communications, Vol. 32 (4), p. 396-402 (University of Waikato, New Zealand)(1984).
  4. A. Moffat: Implementing the PPM data compression scheme. IEEE Transactions on Communications, Vol. 38 (11), p. 1917-1921. (1990)
  5. J. Cleary, W. Teahan, and I. Witten: Unbounded length contexts for PPM. In J.A. Storer and M. Cohn, editors, Proceedings DCC-95. IEEE Computer Society Press (1995).

Ukázka