Az adatok tömörítése; es - Aritmus tömörítés; ketyegés

Számtani kódolás

Ez a rész egy veszteségmentes tömörítést vezet be, amelyet aritmetikai kódolásnak neveznek. Először meghatározza az algoritmus érdeklődését, mielőtt bemutatja az ezzel a kódolással végrehajtott tömörítést és dekompressziót

adatok

Leírás

Az aritmetikai kódolás statisztikai kódolás, vagyis minél többet ábrázol egy karakter, annál kevesebb bitre lesz szükség a kódolásához.

A Huffman-kódolás unokatestvére, amely azonban mindig hatékonyabb, mint az utóbbi (kivéve azt a különleges esetet, amikor a Huffman-fa leveleinek/csomópontjainak/gyökereinek minden súlya a 2-es hatvány). Könnyebb megvalósítani is.

Az aritmetikai kódolás előnye a Huffman-kódolással szemben az, hogy ez utóbbi egy karaktert kódol egy egész bitszám fölé (1,5 bitet nem kódolhat), ahol az aritmetikai kódolás képes. Például, ha egy karakter 90% -ban van ábrázolva, akkor a karakterkód optimális mérete 0,15 bit lenne, míg Huffman valószínűleg 1 bitre kódolná ezt a szimbólumot, vagyis hatszor túl sokat.

Ezt a kódolást a gyakorlatban nagyon keveset használják, de továbbra is jelen van, különösen JPEG2000 formátumban.

Tömörítés

A tömörítés bemutatásához használunk egy példát, és leírjuk az egyes tömörítési lépéseket. Kódoljuk az "ESIPE" szót aritmetikai kódolással.

Az első lépés a szó minden betűjének megszámlálása. Tehát van 2 „E”, 1 „S”, 1 „I” és 1 „P”. Ezután generáljuk a szóban való jelenlét valószínűségét, azaz 40% -os esélyt találunk egy E-re és 20% -ot a többi betűre. Az első résznél végrehajtandó művelet minden betűhöz 0 és 1 közötti intervallumot rendelünk az alábbiak szerint:

  • Az "E" betű valószínűsége 40% (vagy 0,4). Intervalluma tehát [0,0,4 [
  • A "P" betű valószínűsége 20% (vagy 0,2). Intervalluma tehát [0,4,0,6 [
  • Stb.