PPM tömörítési algoritmus

A PPM ( angolul  Prediction by Partial Matching  - prediction by partial match) egy adaptív statisztikai veszteségmentes adattömörítési algoritmus , amely kontextus modellezésen és előrejelzésen alapul. A PPM-modell a szövegkörnyezetet, a tömörítetlen folyam karakterkészletét használja, amely megelőzi az adott karaktert, hogy megjósolja egy karakter értékét statisztikai adatok alapján. Maga a PPM-modell csak egy karakter értékét jelzi előre, a közvetlen tömörítést entrópiakódoló algoritmusok végzik , mint például a Huffman-algoritmus , az aritmetikai kódolás .

Az előrejelzésben használt kontextus hossza általában nagyon korlátozott. Ezt a hosszúságot n - nel jelöljük , és meghatározza a PPM-modell sorrendjét, amelyet PPM(n) -ként jelölünk . Korlátlan számú modell is létezik, és egyszerűen PPM-nek* nevezik őket . Ha egy szimbólumot nem lehet megjósolni egy n szimbólumból álló kontextusból, akkor n-1 szimbólum használatával próbáljuk megjósolni . Az alacsonyabb rendű modellekre való rekurzív átmenet addig történik, amíg az egyik modellben előrejelzés nem történik, vagy amíg a kontextus nulla hosszúságú lesz ( n = 0). A 0 és -1 fokú modelleket külön kell leírni. A nulla rendű modell egyenértékű a környezetfüggetlen modellezés esetével, amikor egy szimbólum valószínűségét kizárólag a tömöríthető adatfolyamban való előfordulásának gyakorisága alapján határozzuk meg. Ezt a modellt általában a Huffman kódolással együtt használják. A −1 rendű modell egy statikus modell, amely egy bizonyos fix értéket rendel egy szimbólum valószínűségéhez; általában minden karakter, amely egy tömöríthető adatfolyamban előfordulhat, egyformán valószínűnek tekinthető. Ahhoz, hogy jó karaktervalószínűségi becslést kapjunk, különböző hosszúságú összefüggéseket kell figyelembe venni. A PPM a keverési stratégia egy olyan változata, ahol a különböző hosszúságú összefüggések alapján készített valószínűségi becsléseket egyetlen közös valószínűségbe vonják össze. A kapott becslést bármilyen entrópia kódoló (EC) kódolja, általában valamilyen aritmetikai kódoló. Az entrópia kódolás szakaszában a tényleges tömörítés megtörténik.

A PPM algoritmus szempontjából nagy jelentőséggel bír az új karakterek kezelésének problémája, amelyekkel még nem találkoztunk a bemeneti adatfolyamban. Ezt a problémát nulla frekvencia problémának nevezik . Egyes PPM-megvalósítások az új karakterszámot rögzített értékre állítják be, például egy. Más megvalósítások, mint például a PPM-D, növelik az új karakterek álszámát minden alkalommal, amikor egy új karakter ténylegesen megjelenik az adatfolyamban (más szóval a PPM-D egy új karakter valószínűségét a karakterek számának arányaként becsüli meg. egyedi karaktereket a felhasznált karakterek teljes számához).

A PPM algoritmuscsaláddal kapcsolatos publikált tanulmányok az 1980-as évek közepén jelentek meg. A szoftvermegvalósítások az 1990-es évekig nem voltak népszerűek, mivel a PPM-modellek jelentős mennyiségű RAM-ot igényelnek . A PPM modern megvalósításai a legjobbak közé tartoznak a természetes nyelvű szövegek veszteségmentes tömörítési algoritmusai között . [1] [2]

Gyakorlati felhasználás

A PPM algoritmus változatait jelenleg széles körben használják, főként redundáns információk és szöveges adatok tömörítésére. A következő archiválók használnak PPM-et [3] :

• boa, PPMz alapján (Ian Sutton)
• HA , PPM sorrend 4, eredeti kilépési valószínűségi módszer (Harry Hirvola)
• lgha, ha archiváló kód alapján (Jurij Ljapko)
• ppmpacktc, PPMd, PPMz, PPMVC és HA kódon alapul hsc implementációval (Alexander Myasnikov)
• arhangel, ha algoritmusokon alapul, különféle adatok szűrőkészletének hozzáadásával (Yuri Lyapko)
• PPMd - a PPM-rendelés végrehajtása-2..16, információs öröklést használnak (Dmitrij Shkarin "bolond")
• ppmz – Z-módszer implementálva (Charles Bloom)
• rk – PPMz megvalósítás szűrőbankkal (Malcolm Taylor)
• rkuc – PPM 16-12-8-5-3-2-1-0 rendelésekkel (Malcolm Taylor)
• rkive (Malcolm Taylor)
• x1 - LZP és PPM megvalósítása (Stig Valentini)
• RAR (3. és 4. verzió) - a PPMd, PPMII változat megvalósítása
• 7-Zip  - a PPMd változat megvalósítása
• WinZip (10-es és újabb verzió) - a PPMd változat megvalósítása

Jegyzetek

1. ↑ http://www.maximumcompression.com/algoritms.php Archiválva : 2021. január 13. a Wayback Machine -nél A legújabb PPM-megvalósítások a természetes nyelvű szövegek legjobban teljesítő veszteségmentes tömörítőprogramjai közé tartoznak.
2. ↑ Bevezetés az adattömörítésbe Archiválva : 2015. szeptember 28., a Wayback Machine ISBN 1-55860-558-4 141. oldal "a legjobban teljesítő szövegtömörítési algoritmusok egy része a ppm algoritmus változatai"
3. ↑ Bevezetés a PPM-be . Letöltve: 2008. május 26. Az eredetiből archiválva : 2021. január 9.. (határozatlan)

Irodalom

• JG Cleary és IH Witten, Adattömörítés adaptív kódolással és részleges karakterlánc-illesztéssel  (hivatkozás nem érhető el) , IEEE Transactions on Communications , 1. kötet. 32. (4), pp. 396-402, 1984. április.
• A. Moffat, Implementing the PPM adattömörítési séma , IEEE Transactions on Communications , Vol. 38. (11), pp. 1917–1921, 1990. november.
• JG Cleary, WJ Teahan és IH Witten, Unbounded long contexts for PPM, In JA Storer és M. Cohn, szerkesztők, Proceedings DCC-95 , IEEE Computer Society Press, 1995.
• C. Bloom, A kontextusmodellezés problémáinak megoldása .
• WJ Teahan, PPM valószínűségbecslés .
• T. Schürmann és P. Grassberger, Entropy estimation of symbol series  (link unavailable) , Chaos , Vol. 6. o. 414–427, 1996. szeptember.