PPM-pakkausalgoritmi

PPM ( englanniksi  Prediction by Partial Matching  - ennustus osittaisella täsmäämällä) on adaptiivinen tilastollinen häviötön tietojen pakkausalgoritmi , joka perustuu kontekstin mallintamiseen ja ennustukseen. PPM-malli käyttää kontekstia, annettua edeltävää pakkaamattoman virran merkkijoukkoa ennustaakseen merkin arvon tilastojen perusteella. PPM-malli itsessään ennustaa vainmerkin arvon, suora pakkaus suoritetaan entropiakoodausalgoritmeilla , kuten Huffman-algoritmilla , aritmeettisella koodauksella .

Ennustuksessa käytetyn kontekstin pituus on yleensä hyvin rajallinen. Tämä pituus on merkitty n :llä ja se määrittää PPM-mallin järjestyksen, jota merkitään PPM(n) . Myös malleja on rajattomasti, ja niistä käytetään yksinkertaisesti nimitystä PPM* . Jos symbolia ei voida ennustaa n symbolin kontekstista, se yritetään ennustaa käyttämällä n-1 symbolia. Rekursiivinen siirtyminen alemman kertaluvun malleihin tapahtuu, kunnes jossakin malleista tapahtuu ennuste tai kun kontekstista tulee nollapituus ( n = 0). Asteen 0 ja −1 mallit tulee kuvata erikseen. Nollakertainen malli vastaa yhteydettömän mallinnuksen tapausta, jolloin symbolin todennäköisyys määritetään pelkästään sen esiintymistiheydestä pakattavassa tietovirrassa. Tätä mallia käytetään yleensä yhdessä Huffman-koodauksen kanssa. −1-asteen malli on staattinen malli, joka antaa tietyn kiinteän arvon symbolin todennäköisyydelle; yleensä kaikkia merkkejä, jotka voivat esiintyä pakattavassa tietovirrassa, pidetään yhtä todennäköisinä. Hyvän merkkitodennäköisyysestimaatin saamiseksi on otettava huomioon eripituiset kontekstit. PPM on muunnos sekoitusstrategiasta, jossa eripituisten kontekstien perusteella tehdyt todennäköisyysarviot yhdistetään yhdeksi yhteiseksi todennäköisyydeksi. Tuloksena oleva arvio koodataan millä tahansa entropiakooderilla (EC), yleensä jonkinlaisella aritmeettisella kooderilla. Entropiakoodauksen vaiheessa varsinainen pakkaus tapahtuu.

Erittäin tärkeä PPM-algoritmille on uusien merkkien käsittelyongelma, joita ei ole vielä tavattu syöttövirrassa. Tätä ongelmaa kutsutaan nollataajuusongelmaksi . Jotkin PPM-toteutukset asettavat uuden merkkimäärän kiinteään arvoon, kuten yhdeksi. Muut toteutukset, kuten PPM-D, lisäävät uuden merkin pseudomäärää aina, kun uusi merkki todella ilmestyy virrassa (toisin sanoen PPM-D arvioi uuden merkin todennäköisyyden suhteeksi yksilöiviä merkkejä käytettyjen merkkien kokonaismäärään).

Julkaistut tutkimukset PPM-algoritmeista ilmestyivät 1980-luvun puolivälissä. Ohjelmistototeutukset olivat suosittuja vasta 1990-luvulla, koska PPM-mallit vaativat huomattavan määrän RAM-muistia . Nykyaikaiset PPM-toteutukset ovat parhaita luonnollisen kielen tekstien häviöttömistä pakkausalgoritmeista . [1] [2]

Käytännön käyttö

PPM-algoritmin muunnelmia käytetään tällä hetkellä laajalti, pääasiassa redundantin tiedon ja tekstidatan pakkaamiseen. Seuraavat arkistaattorit käyttävät PPM :ää [3] :

• boa, perustuu PPMz:ään (Ian Sutton)
• HA , PPM järjestys 4, alkuperäinen poistumistodennäköisyysmenetelmä (Harry Hirvola)
• lgha, perustuu ha-arkistointikoodiin (Juri Lyapko)
• ppmpacktc, joka perustuu PPMd-, PPMz-, PPMVC- ja HA-koodiin hsc-toteutuksen kanssa (Alexander Myasnikov)
• arhangel, perustuu ha-algoritmeihin, joihin on lisätty joukko suodattimia erilaisille tiedoille (Juri Lyapko)
• PPMd - PPM-järjestyksen-2..16 toteutus, tiedon periytymistä käytetään (Dmitri Shkarinin "tyhmä")
• ppmz - Z-menetelmä otettu käyttöön (Charles Bloom)
• rk - PPMz-toteutus suodatinpankilla (Malcolm Taylor)
• rkuc - PPM tilauksilla 16-12-8-5-3-2-1-0 (Malcolm Taylor)
• rkive (Malcolm Taylor)
• x1 - LZP:n ja PPM:n toteutus (Stig Valentini)
• RAR (versiot 3 ja 4) - PPMd-, PPMII-version toteutus
• 7-Zip  - PPMd-version toteutus
• WinZip (versio 10 ja uudemmat) - PPMd-version toteutus

Muistiinpanot

1. ↑ http://www.maximumcompression.com/algoritms.php Arkistoitu 13. tammikuuta 2021 Wayback Machinessa Viimeaikaiset PPM-toteutukset ovat tehokkaimpia luonnollisen kielen tekstin häviöttömiä pakkausohjelmia.
2. ↑ Tietojen pakkaamisen esittely Arkistoitu 28. syyskuuta 2015 Wayback Machinessa ISBN 1-55860-558-4 sivu 141 "jotkut parhaiten suoriutuvista tekstinpakkausalgoritmeista ovat muunnelmia ppm-algoritmista"
3. ↑ Johdatus PPM:ään . Haettu 26. toukokuuta 2008. Arkistoitu alkuperäisestä 9. tammikuuta 2021. (määrätön)

Kirjallisuus

• JG Cleary ja IH Witten, Tietojen pakkaus mukautuvalla koodauksella ja osittaisella merkkijonojen sovituksella  (linkki ei ole käytettävissä) , IEEE Transactions on Communications , Voi. 32 (4), s. 396-402, huhtikuu 1984.
• A. Moffat, Implementing the PPM-tietojen pakkausmenetelmä , IEEE Transactions on Communications , Voi. 38 (11), s. 1917–1921, marraskuu 1990.
• JG Cleary, WJ Teahan ja IH Witten, Rajattomat pituuskontekstit PPM:lle, julkaisussa JA Storer ja M. Cohn, toimittajat, Proceedings DCC-95 , IEEE Computer Society Press, 1995.
• C. Bloom, Kontekstimallinnuksen ongelmien ratkaiseminen .
• WJ Teahan, PPM :n todennäköisyysestimaatti .
• T. Schürmann ja P. Grassberger, Symbolisekvenssien entropiaestimointi  (linkki ei ole käytettävissä) , Chaos , Voi. 6 , s. 414–427, syyskuu 1996.