PPM kompresní algoritmus
Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od
verze recenzované 28. května 2022; ověření vyžaduje
1 úpravu .
PPM ( anglicky Prediction by Partial Matching - predikce částečnou shodou) je adaptivní statistický bezztrátový algoritmus komprese dat založený na kontextovém modelování a predikci. Model PPM využívá kontext, množinu znaků v nekomprimovaném proudu, který předchází danému, k predikci hodnoty znaku na základě statistik. Samotný PPM model pouze předpovídá hodnotu znaku, přímá komprese je prováděna entropickými kódovacími algoritmy , jako je Huffmanův algoritmus , aritmetické kódování .
Délka kontextu, který se používá v predikci, je obvykle velmi omezená. Tato délka je označena n a definuje pořadí PPM modelu, který je označen jako PPM(n) . Neomezené modely také existují a jsou jednoduše označovány jako PPM* . Pokud symbol nelze předpovědět z kontextu n symbolů, pokusí se jej předpovědět pomocí n-1 symbolů. K rekurzivnímu přechodu na modely s nižším řádem dochází, dokud v jednom z modelů nedojde k predikci, nebo když se kontext stane nulovou délkou ( n = 0). Modely stupně 0 a -1 by měly být popsány samostatně. Model nultého řádu je ekvivalentní případu bezkontextového modelování, kdy je pravděpodobnost symbolu určena výhradně z frekvence jeho výskytu v komprimovatelném datovém toku. Tento model se obvykle používá ve spojení s Huffmanovým kódováním. Model −1 řádu je statický model, který přiřazuje jistou pevnou hodnotu pravděpodobnosti symbolu; obvykle jsou všechny znaky, které se mohou vyskytovat v komprimovatelném datovém toku, považovány za stejně pravděpodobné. Chcete-li získat dobrý odhad pravděpodobnosti postavy, je třeba vzít v úvahu kontexty různých délek. PPM je variantou směšovací strategie, kde se odhady pravděpodobnosti provedené na základě kontextů různých délek spojují do jedné společné pravděpodobnosti. Výsledný odhad je zakódován jakýmkoli entropickým kodérem (EC), obvykle nějakým druhem aritmetického kodéru. Ve fázi entropického kódování probíhá vlastní komprese.
Pro algoritmus PPM je velmi důležitý problém manipulace s novými znaky, které se dosud ve vstupním proudu nevyskytovaly. Tento problém se nazývá problém nulové frekvence . Některé implementace PPM nastavují počet nových znaků na pevnou hodnotu, jako je jedna. Jiné implementace, jako je PPM-D, zvyšují pseudopočet nového znaku pokaždé, když se nový znak skutečně objeví v proudu (jinými slovy, PPM-D odhaduje pravděpodobnost nového znaku jako poměr počtu jedinečné znaky k celkovému počtu použitých znaků).
Publikované studie rodiny algoritmů PPM se objevily v polovině 80. let. Softwarové implementace nebyly populární až do 90. let, protože modely PPM vyžadují značné množství paměti RAM . Moderní implementace PPM patří mezi nejlepší mezi bezeztrátovými kompresními algoritmy pro texty v přirozeném jazyce . [1] [2]
Praktické použití
Varianty PPM algoritmu jsou v současné době široce používány, zejména pro kompresi redundantních informací a textových dat. Následující archivátory používají PPM [3] :
- hroznýš, založený na PPMz (Ian Sutton)
- HA , PPM pořadí 4, původní metoda pravděpodobnosti odchodu (Harry Hirvola)
- lgha, založený na kódu archivátoru ha (Yuri Lyapko)
- ppmpacktc, založený na kódu PPMd, PPMz, PPMVC a HA s implementací hsc (Alexander Myasnikov)
- arhangel, založený na ha algoritmech s přidáním sady filtrů pro různá data (Yuri Lyapko)
- PPMd - implementace PPM objednávky-2..16, používá se dědění informací ("blázen" od Dmitrije Shkarina)
- ppmz - implementována metoda Z (Charles Bloom)
- rk - implementace PPMz s bankou filtrů (Malcolm Taylor)
- rkuc - PPM s objednávkami 16-12-8-5-3-2-1-0 (Malcolm Taylor)
- rkive (Malcolm Taylor)
- x1 - implementace LZP a PPM (Stig Valentini)
- RAR (verze 3 a 4) - implementace varianty PPMd, PPMII
- 7-Zip - implementace varianty PPMd
- WinZip (verze 10 a vyšší) - implementace varianty PPMd
Poznámky
- ↑ http://www.maximumcompression.com/algoritms.php Archivováno 13. ledna 2021 na Wayback Machine Nedávné implementace PPM patří mezi nejvýkonnější bezztrátové kompresní programy pro text v přirozeném jazyce.
- ↑ Úvod do komprese dat Archivováno 28. září 2015 na Wayback Machine ISBN 1-55860-558-4 strana 141 „některé z nejvýkonnějších algoritmů komprese textu jsou variantami algoritmu ppm“
- ↑ Úvod do PPM . Získáno 26. května 2008. Archivováno z originálu 9. ledna 2021. (neurčitý)
Literatura
- JG Cleary a IH Witten, Komprese dat pomocí adaptivního kódování a částečné shody řetězců (odkaz není k dispozici) , IEEE Transactions on Communications , sv. 32 (4), str. 396-402, duben 1984.
- A. Moffat, Implementace schématu komprese dat PPM , IEEE Transactions on Communications , sv. 38 (11), str. 1917–1921, listopad 1990.
- JG Cleary, WJ Teahan a IH Witten, Neohraničené délkové kontexty pro PPM, In JA Storer a M. Cohn, editoři, Proceedings DCC-95 , IEEE Computer Society Press, 1995.
- C. Bloom, Řešení problémů kontextového modelování .
- WJ Teahan, Odhad pravděpodobnosti pro PPM .
- T. Schürmann a P. Grassberger, Entropy odhad sekvencí symbolů (odkaz není k dispozici) , Chaos , sv. 6 , str. 414–427, září 1996.