PPM-komprimeringsalgoritm

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 28 maj 2022; verifiering kräver 1 redigering .

PPM ( engelsk  Prediction by Partial Matching  - prediction by partial matching) är en adaptiv statistisk förlustfri datakomprimeringsalgoritm baserad på kontextmodellering och förutsägelse. PPM-modellen använder sammanhanget, uppsättningen tecken i den okomprimerade strömmen som föregår den givna, för att förutsäga värdet av ett tecken baserat på statistik. PPM-modellen i sig förutsäger bara värdet av ett tecken, direkt komprimering utförs av entropikodningsalgoritmer , såsom Huffman-algoritmen , aritmetisk kodning .

Längden på sammanhanget som används i förutsägelsen är vanligtvis mycket begränsad. Denna längd betecknas n och definierar ordningen för PPM-modellen, som betecknas som PPM(n) . Obegränsade modeller finns också och kallas helt enkelt PPM* . Om en symbol inte kan förutsägas utifrån ett sammanhang med n symboler, görs ett försök att förutsäga den med n-1 symboler. En rekursiv övergång till modeller med lägre ordning sker tills en förutsägelse inträffar i en av modellerna, eller när kontexten blir noll längd ( n = 0). Grad 0 och −1 modeller ska beskrivas separat. Nollordningens modellen är ekvivalent med fallet med kontextfri modellering, när sannolikheten för en symbol bestäms enbart från frekvensen av dess förekomst i en komprimerbar dataström. Denna modell används vanligtvis i samband med Huffman-kodning. Ordningsmodellen −1 är en statisk modell som tilldelar ett visst fast värde till sannolikheten för en symbol; vanligtvis anses alla tecken som kan förekomma i en komprimerbar dataström vara lika sannolika. För att få en bra karaktärssannolikhetsuppskattning måste sammanhang av olika längd beaktas. PPM är en variant av blandningsstrategin, där de sannolikhetsuppskattningar som gjorts utifrån sammanhang av olika längd kombineras till en gemensam sannolikhet. Den resulterande uppskattningen kodas av valfri entropikodare (EC), vanligtvis någon form av aritmetisk kodare. Vid entropikodningsstadiet sker den faktiska komprimeringen.

Av stor betydelse för PPM-algoritmen är problemet med att hantera nya karaktärer som ännu inte har påträffats i ingångsströmmen. Detta problem kallas nollfrekvensproblemet . Vissa PPM-implementeringar ställer in det nya teckenantalet till ett fast värde, till exempel ett. Andra implementeringar, såsom PPM-D, ökar pseudo-antalet för ett nytt tecken varje gång ett nytt tecken faktiskt dyker upp i strömmen (med andra ord, PPM-D uppskattar sannolikheten för ett nytt tecken som förhållandet mellan antalet unika tecken till det totala antalet tecken som används).

Publicerade studier av PPM-familjen av algoritmer dök upp i mitten av 1980-talet. Mjukvaruimplementationer var inte populära förrän på 1990-talet eftersom PPM-modeller kräver en betydande mängd RAM . Moderna implementeringar av PPM är bland de bästa bland förlustfria komprimeringsalgoritmer för naturliga språktexter . [1] [2]

Praktisk användning

Varianter av PPM-algoritmen används för närvarande i stor utsträckning, främst för att komprimera redundant information och textdata. Följande arkiverare använder PPM [3] :

Anteckningar

  1. ↑ http://www.maximumcompression.com/algoritms.php Arkiverad 13 januari 2021 på Wayback Machine . De senaste PPM-implementeringarna är bland de bäst presterande förlustfria komprimeringsprogrammen för text på naturligt språk.
  2. ↑ Introduktion till datakomprimering Arkiverad 28 september 2015 på Wayback Machine ISBN 1-55860-558-4 sida 141 "några av de bäst presterande textkomprimeringsalgoritmerna är varianter av ppm-algoritmen"
  3. ↑ Introduktion till PPM . Hämtad 26 maj 2008. Arkiverad från originalet 9 januari 2021.

Litteratur

 Kompressionsmetoder _
Teori
Information
Enheter
Förlust mindre
Entropikompression
Ordboksmetoder
Övrig
Audio
Teori
Metoder
Övrig
Bilder
Villkor
Metoder
Övrig
Video
Villkor
Metoder
Övrig