Algoritm de compresie PPM

PPM ( Predicție în limba engleză  prin potrivire parțială  - predicție prin potrivire parțială) este un algoritm de comprimare a datelor statistică adaptiv, fără pierderi, bazat pe modelarea și predicția contextului. Modelul PPM folosește contextul, setul de caractere din fluxul necomprimat care îl precede pe cel dat, pentru a prezice valoarea unui caracter pe baza statisticilor. Modelul PPM în sine prezice doar valoarea unui caracter, compresia directă este efectuată de algoritmi de codare entropică , cum ar fi algoritmul Huffman , codarea aritmetică .

Lungimea contextului care este utilizat în predicție este de obicei foarte limitată. Această lungime este notată n și definește ordinea modelului PPM, care este notat cu PPM(n) . Există și modele nelimitate și sunt pur și simplu denumite PPM* . Dacă un simbol nu poate fi prezis dintr-un context de n simboluri, atunci se încearcă să-l prezică folosind n-1 simboluri. O tranziție recursivă la modele cu un ordin inferior are loc până când apare o predicție într-unul dintre modele sau când contextul devine lungime zero ( n = 0). Modelele de gradul 0 și -1 ar trebui descrise separat. Modelul de ordin zero este echivalent cu cazul modelării fără context, când probabilitatea unui simbol este determinată numai din frecvența apariției acestuia într-un flux de date compresibil. Acest model este de obicei folosit împreună cu codarea Huffman. Modelul ordinului −1 este un model static care atribuie o anumită valoare fixă ​​probabilității unui simbol; de obicei, toate caracterele care pot apărea într-un flux de date compresibil sunt considerate la fel de probabile. Pentru a obține o estimare bună a probabilității caracterului, trebuie luate în considerare contexte de diferite lungimi. PPM este o variantă a strategiei de amestecare, în care estimările de probabilitate făcute pe baza unor contexte de lungimi diferite sunt combinate într-o probabilitate comună. Estimarea rezultată este codificată de orice codificator de entropie (EC), de obicei un fel de codificator aritmetic. În etapa de codificare a entropiei are loc compresia reală.

De mare importanță pentru algoritmul PPM este problema manipulării caracterelor noi care nu au fost încă întâlnite în fluxul de intrare. Această problemă se numește problema frecvenței zero . Unele implementări PPM setează noul număr de caractere la o valoare fixă, cum ar fi una. Alte implementări, cum ar fi PPM-D, măresc pseudonumărul unui nou caracter de fiecare dată când un nou caracter apare efectiv în flux (cu alte cuvinte, PPM-D estimează probabilitatea unui nou caracter ca raport dintre numărul de caractere unice la numărul total de caractere utilizate).

Studiile publicate ale familiei de algoritmi PPM au apărut la mijlocul anilor 1980. Implementările software nu au fost populare până în anii 1990, deoarece modelele PPM necesită o cantitate semnificativă de memorie RAM . Implementările moderne ale PPM sunt printre cele mai bune dintre algoritmii de compresie fără pierderi pentru textele în limbaj natural . [1] [2]

Utilizare practică

Variante ale algoritmului PPM sunt utilizate în prezent pe scară largă, în principal pentru comprimarea informațiilor redundante și a datelor textuale. Următoarele arhivare folosesc PPM [3] :

• boa, bazat pe PPMz (Ian Sutton)
• HA , ordinul PPM 4, metoda probabilității de ieșire inițială (Harry Hirvola)
• lgha, bazat pe codul de arhivare ha (Yuri Lyapko)
• ppmpacktc, bazat pe codul PPMd, PPMz, PPMVC și HA cu implementare hsc (Alexander Myasnikov)
• arhangel, bazat pe algoritmi ha cu adăugarea unui set de filtre pentru diverse date (Yuri Lyapko)
• PPMd - implementarea ordinului PPM-2..16, moștenirea informațiilor este folosită ("prost" de Dmitry Shkarin)
• ppmz - Metoda Z implementată (Charles Bloom)
• rk - implementare PPMz cu banc de filtre (Malcolm Taylor)
• rkuc - PPM cu comenzi 16-12-8-5-3-2-1-0 (Malcolm Taylor)
• rkive (Malcolm Taylor)
• x1 - implementarea LZP și PPM (Stig Valentini)
• RAR (versiunile 3 și 4) - implementarea variantei PPMd, PPMII
• 7-Zip  - implementarea variantei PPMd
• WinZip (versiunea 10 și mai sus) - implementarea variantei PPMd

Note

1. ↑ http://www.maximumcompression.com/algoritms.php Arhivat 13 ianuarie 2021 la Wayback Machine Implementările recente PPM sunt printre cele mai performante programe de compresie fără pierderi pentru text în limbaj natural.
2. ↑ Introducere în compresia datelor Arhivat 28 septembrie 2015 la Wayback Machine ISBN 1-55860-558-4 pagina 141 „unii dintre cei mai performanti algoritmi de compresie a textului sunt variante ale algoritmului ppm”
3. ↑ Introducere în PPM . Preluat la 26 mai 2008. Arhivat din original la 9 ianuarie 2021. (nedefinit)

Literatură

• JG Cleary și IH Witten, Comprimarea datelor utilizând codarea adaptivă și potrivirea parțială a șirurilor  (link indisponibil) , IEEE Transactions on Communications , Vol. 32 (4), pp. 396-402, aprilie 1984.
• A. Moffat, Implementarea schemei de compresie a datelor PPM , IEEE Transactions on Communications , Vol. 38 (11), pp. 1917–1921, noiembrie 1990.
• JG Cleary, WJ Teahan și IH Witten, Unbounded length contexts for PPM, În JA Storer și M. Cohn, editori, Proceedings DCC-95 , IEEE Computer Society Press, 1995.
• C. Bloom, Rezolvarea problemelor modelării contextului .
• WJ Teahan, Estimarea probabilității pentru PPM .
• T. Schürmann și P. Grassberger, Estimarea entropiei a secvențelor de simbol  (link indisponibil) , Chaos , voi. 6 , pp. 414–427, septembrie 1996.