DMC (komprimeringsalgoritme)

DMC ( dynamisk Markov-komprimering ,  dynamisk Markov-komprimering [1] ) er en tabsfri datakomprimeringsalgoritme udviklet af Gordon Cormack og Nigel Horspool [2] . Metoden er bygget på samme måde som PPM- metoden : selve algoritmen er en prædiktor (beregner sandsynligheden for symboler), og direkte komprimering udføres af en entropi-koder . I modsætning til PPM fungerer DMC-metoden generelt på bitniveau, mens PPM fungerer på byteniveau. DMC giver sammenlignelige komprimeringsniveauer og behandlingshastighed til PPM, men kræver mere hukommelse og er ikke så almindelig som PPM. Nogle af de moderne implementeringer er: krogkompressoren af ​​Nania Francesco Antonio, ocamyd- kompressoren af ​​Frank Schwellinger, og DMC bruges som en af ​​modellerne i Matt Mahoneys paq8l-kompressor . Alle anførte kompressorer er baseret på den originale 1993 C-implementering af Gordon Cormack.

Algoritme

DMC forudsiger og koder en bit pr. logisk operationstrin. Det adskiller sig fra PPM ved, at det fungerer på niveauet af bit, ikke bytes. Forskellen fra kontekstblandingsmetoder (såsom PAQ ) er, at DMC bygger og bruger én enkelt kildemodel. Direkte komprimering udføres ved hjælp af aritmetisk kodning .

Model

Kildemodellen forudsiger den næste bit baseret på den aktuelle kontekst. Modellen kan repræsenteres som en graf, hvor hver knude indeholder to tællere: n 0 og n 1 , hvor n 0 er en bittæller med værdien 0, og n 1 er en bittæller med værdien 1. En af noderne er altid den nuværende. En af tællerne i det aktuelle knudepunkt øges, når en bit med den tilsvarende værdi stødes på i de originale data. Noden har også to kanter, der forbinder den med andre noder eller til sig selv. En af kanterne bruges, når 0 forekommer i kildedataene, den anden, når 1. I det simpleste tilfælde består modellen af ​​en enkelt node, der refererer til sig selv. I denne konfiguration kan modellen kun læse forholdet mellem antallet af bits med en værdi på 0 og antallet af bits med en værdi på 1 i de originale data. Når der er mere end én node i modellen, så kan der ved behandling af den næste bit ske en overgang til en anden node, samt dannelsen af ​​en ny node.

Den næste bit forudsiges ved at beregne sandsynligheden for 0 ved hjælp af formlen p 0 = n 0 / n = n 0 /( n 0 + n 1 ) og følgelig for 1 ved hjælp af formlen p 1 = 1 − p 0 = n 1 / n . Hver knude inkarnerer således en separat tilstand af modellen, hvor den foretager forskellige forudsigelser. Konteksten i DMC-modellen huskes ikke eksplicit, men den tages i betragtning af modellen som følge af overgange mellem knudepunkterne i tilstandsgrafen.

Simulering udføres på samme måde for både kompression og dekompression.

Noter

1. ↑ Vatolin D. Metoder til datakomprimering. Enheden til arkivering, billed- og videokomprimering .. - M . : Dialog-MEPhI, 1993. - S. 9. - ISBN 5-86404-170-x .
2. ↑ Gordon Cormack og Nigel Horspool, "Data Compression using Dynamic Markov Modeling", Computer Journal 30:6 (december 1987)