Ugrás a tartalomhoz

arithmetic coding

A Wikiszótárból, a nyitott szótárból

Angol


Főnév

arithmetic coding (tsz. arithmetic codings)

  1. (informatika) Az aritmetikai kódolás (arithmetic coding) egy hatékony veszteségmentes tömörítési eljárás, amely az információelmélet területén használatos, különösen adattömörítéshez és kódoláshoz.


Mi az az aritmetikai kódolás?

Az aritmetikai kódolás nem a szimbólumokat egyenként helyettesíti kódokkal (mint például a Huffman-kód), hanem az egész bemeneti szöveget vagy adatfolyamot egyetlen tizedestört számként ábrázolja egy [0,1) intervallumon belül. Ez a szám az adott szimbólumsorozatot reprezentálja.


Hogyan működik?

  1. Valószínűségek hozzárendelése: Minden lehetséges szimbólumnak van egy valószínűsége vagy relatív gyakorisága.
  2. Intervallum felosztása: Az egész [0,1) intervallumot felosztjuk részintervallumokra a szimbólumok valószínűségeinek megfelelő arányban.
  3. Szimbólumok feldolgozása sorban: A kódolás során a bemeneti szimbólumsorozatot egyre szűkülő intervallumokra bontjuk:
    • Az első szimbólum kiválasztja a megfelelő részintervallumot az egész [0,1) intervallumon belül.
    • A második szimbólum tovább szűkíti ezt az intervallumot a saját valószínűségi eloszlása alapján, és így tovább.
  4. Végső kód: A teljes szimbólumsorozatot reprezentáló szám bármely értéke az utolsó szűkített intervallumban megfelelő kód lesz. Ez a szám lesz az aritmetikai kód.


Példa leegyszerűsítve

Tegyük fel, hogy az ábécénk csak három szimbólumból áll: {A, B, C}, és a valószínűségek:

  • A: 0.5
  • B: 0.3
  • C: 0.2

Az intervallum felosztása:

  • A: [0.0, 0.5)
  • B: [0.5, 0.8)
  • C: [0.8, 1.0)

Ha a kódolandó szöveg: “AB”

  • Az első szimbólum (‘A’) kiválasztja az [0.0, 0.5) intervallumot.
  • Ezen intervallumot tovább osztjuk a második szimbólum (‘B’) valószínűségei alapján:
    • A részintervallumok most [0.0, 0.25), [0.25, 0.4), [0.4, 0.5), mert 0.5 * 0.5 = 0.25 stb.
  • ‘B’ kiválasztja a [0.25, 0.4) intervallumot.

A végső kód bármely szám lehet ebben az intervallumban, például 0.3.


Miért előnyös az aritmetikai kódolás?

  • Közel optimális tömörítés: Jobban kihasználja a szimbólumok valószínűségi eloszlását, mint a Huffman-kód, főleg ha a valószínűségek nem hatványai 2-nek.
  • Tetszőleges valószínűségekhez jól alkalmazható: Nem szükséges egész számú bit kódhossz.
  • Alkalmas folyamatos adatfolyamok kódolására.


Hátrányok

  • Számítási bonyolultság: pontos lebegőpontos műveleteket igényel.
  • Implementációja bonyolultabb.
  • Néhány esetben lassabb lehet.


További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=arithmetic_coding&oldid=3497770”