PPM-komprimeringsalgoritme

PPM ( engelsk  Prediction by Partial Matching  - forudsigelse ved delvis match) er en adaptiv statistisk tabsfri datakomprimeringsalgoritme baseret på kontekstmodellering og forudsigelse. PPM-modellen bruger konteksten, det sæt af tegn i den ukomprimerede strøm, der går forud for den givne, til at forudsige værdien af ​​et tegn baseret på statistik. Selve PPM-modellen forudsiger kun værdien af ​​et tegn, direkte komprimering udføres af entropi-kodningsalgoritmer , såsom Huffman-algoritmen , aritmetisk kodning .

Længden af ​​konteksten, der bruges i forudsigelsen, er normalt meget begrænset. Denne længde er betegnet n og definerer rækkefølgen af ​​PPM-modellen, som er betegnet som PPM(n) . Der findes også ubegrænsede modeller, og de kaldes blot PPM* . Hvis et symbol ikke kan forudsiges ud fra en kontekst med n symboler, så forsøges det at forudsige det ved hjælp af n-1 symboler. En rekursiv overgang til modeller med en lavere orden sker, indtil der sker en forudsigelse i en af ​​modellerne, eller når konteksten bliver nul længde ( n = 0). Grad 0 og -1 modeller bør beskrives separat. Nulordensmodellen svarer til tilfældet med kontekstfri modellering, når sandsynligheden for et symbol udelukkende bestemmes ud fra hyppigheden af ​​dets forekomst i en komprimerbar datastrøm. Denne model bruges normalt i forbindelse med Huffman-kodning. −1 ordensmodellen er en statisk model, der tildeler en bestemt fast værdi til sandsynligheden for et symbol; normalt anses alle tegn, der kan forekomme i en komprimerbar datastrøm, lige sandsynlige. For at få et godt karaktersandsynlighedsestimat skal kontekster af forskellig længde tages i betragtning. PPM er en variant af blandingsstrategien, hvor sandsynlighedsestimaterne lavet på baggrund af sammenhænge af forskellig længde kombineres til én fælles sandsynlighed. Det resulterende estimat kodes af en hvilken som helst entropikoder (EC), normalt en slags aritmetisk encoder. På stadiet med entropikodning finder selve komprimeringen sted.

Af stor betydning for PPM-algoritmen er problemet med at håndtere nye karakterer, der endnu ikke er stødt på i inputstrømmen. Dette problem kaldes nulfrekvensproblemet . Nogle PPM-implementeringer sætter det nye tegnantal til en fast værdi, f.eks. en. Andre implementeringer, såsom PPM-D, øger pseudo-tallet for et nyt tegn, hver gang et nyt tegn faktisk vises i strømmen (med andre ord, PPM-D estimerer sandsynligheden for et nyt tegn som forholdet mellem antallet af unikke tegn til det samlede antal anvendte tegn).

Publicerede undersøgelser af PPM-familien af ​​algoritmer dukkede op i midten af ​​1980'erne. Softwareimplementeringer var ikke populære før i 1990'erne, fordi PPM-modeller kræver en betydelig mængde RAM . Moderne implementeringer af PPM er blandt de bedste blandt tabsfri komprimeringsalgoritmer til naturlige sprogtekster . [1] [2]

Praktisk brug

Varianter af PPM-algoritmen er for tiden meget brugt, hovedsageligt til at komprimere overflødig information og tekstdata. Følgende arkivere bruger PPM [3] :

• boa, baseret på PPMz (Ian Sutton)
• HA , PPM ordre 4, original udgangssandsynlighedsmetode (Harry Hirvola)
• lgha, baseret på ha arkiveringskode (Yuri Lyapko)
• ppmpacktc, baseret på PPMd, PPMz, PPMVC og HA kode med hsc implementering (Alexander Myasnikov)
• arhangel, baseret på ha-algoritmer med tilføjelse af et sæt filtre til forskellige data (Yuri Lyapko)
• PPMd - implementering af PPM-ordre-2..16, informationsarv bruges ("narre" af Dmitry Shkarin)
• ppmz - Z-metode implementeret (Charles Bloom)
• rk - PPMz implementering med filterbank (Malcolm Taylor)
• rkuc - PPM med ordrer 16-12-8-5-3-2-1-0 (Malcolm Taylor)
• rkive (Malcolm Taylor)
• x1 - implementering af LZP og PPM (Stig Valentini)
• RAR (version 3 og 4) - implementering af PPMd, PPMII varianten
• 7-Zip  - implementering af PPMd-varianten
• WinZip (version 10 og nyere) - implementering af PPMd-varianten

Noter

1. ↑ http://www.maximumcompression.com/algoritms.php Arkiveret 13. januar 2021 på Wayback Machine . Nylige PPM-implementeringer er blandt de bedst ydende tabsfri komprimeringsprogrammer til tekst på naturligt sprog.
2. ↑ Introduktion til datakomprimering Arkiveret 28. september 2015 på Wayback Machine ISBN 1-55860-558-4 side 141 "nogle af de bedst ydende tekstkomprimeringsalgoritmer er varianter af ppm-algoritmen"
3. ↑ Introduktion til PPM . Hentet 26. maj 2008. Arkiveret fra originalen 9. januar 2021. (ubestemt)

Litteratur

• JG Cleary og IH Witten, Datakomprimering ved hjælp af adaptiv kodning og delvis strengmatchning  (link utilgængeligt) , IEEE Transactions on Communications , Vol. 32 (4), s. 396-402, april 1984.
• A. Moffat, Implementering af PPM-datakomprimeringsskemaet , IEEE Transactions on Communications , Vol. 38 (11), s. 1917–1921, november 1990.
• JG Cleary, WJ Teahan og IH Witten, Unbounded length contexts for PPM, In JA Storer og M. Cohn, redaktører, Proceedings DCC-95 , IEEE Computer Society Press, 1995.
• C. Bloom, Løsning af problemerne med kontekstmodellering .
• WJ Teahan, Sandsynlighedsvurdering for PPM .
• T. Schürmann og P. Grassberger, Entropi-estimering af symbolsekvenser  (link utilgængeligt) , Chaos , Vol. 6 , s. 414-427, september 1996.