Entrópia kódolás
Entrópia kódolás - egy értéksorozat kódolása az egyértelmű helyreállítás lehetőségével az adatmennyiség (a sorozat hossza) csökkentése érdekében a kódolt szekvencia elemeinek előfordulási valószínűségének átlagolásával.
Feltételezzük, hogy a kódolás előtt a sorozat egyes elemei eltérő előfordulási valószínűséggel rendelkeznek. A kapott szekvenciában történő kódolás után az egyes karakterek előfordulási valószínűsége közel azonos ( a karakterenkénti entrópia maximális).
Számos kódopció létezik:
- A forrássorozat egyes elemeinek párosítása a kapott sorozat különböző számú elemével. Minél nagyobb az eredeti elem előfordulási valószínűsége, annál rövidebb a megfelelő eredő sorozat. Ilyen például a Shannon-Fano kód , a Huffman kód ,
- A forrássorozat több elemének egyeztetése a végső sorozat rögzített számú elemével. Példa erre a Tunstall kód .
- Más szerkezeti kódok, amelyek egy karaktersorozaton alapuló műveleteken alapulnak. Példa erre a futáshosszúságú kódolás .
- Ha az adatfolyam hozzávetőleges entrópiajellemzői előre ismertek, hasznos lehet egy egyszerűbb statikus kód, például az unáris kódolás , az Elias-gamma-kód , a Fibonacci -kód , a Golomb-kód vagy a Rice-kódolás .
Shannon tétele szerint van egy veszteségmentes tömörítési határ a forrás entrópiájától függően. Minél kiszámíthatóbbak az adatok, annál jobban tömöríthetők. Egy véletlenszerű független kiegyenlíthető sorozat nem tömöríthető veszteség nélkül.
Lásd még
Irodalom