Know-how, előadás, adatkompressziós algoritmusok
Az előadás célja. tanulmányozza az adatok tömörítésének fő típusát és algoritmusait, és megtanulja, hogyan oldja meg a tömörítési problémákat Huffman módszerrel és kódfák használatával.
Az információs tömörítés tudományának alapítója Claude Shannon. Az optimális kódolásról szóló tétele azt mutatja meg, hogy mikor törekedjen az információ kódolására és az információ tömörítésére. Emellett kísérleteket végzett az angol szöveg redundanciájának empirikus értékelésével. Shenon azt javasolta, hogy az emberek találják meg a következő levelet, és értékeljék a helyes találgatás valószínűségét. Számos kísérlet alapján arra a következtetésre jutott, hogy az angol nyelvű információ mennyisége 0,6 és 1,3 bites szimbólumonként. Annak ellenére, hogy a Shannon kutatásainak eredményei csak évtizedekkel később jelentkeztek, nehéz felbecsülni jelentőségüket.
Az adatok tömörítése olyan folyamat, amely csökkenti az adatok mennyiségét a redundancia csökkentésével. Az adatok tömörítése a szabványos méretű adatrészek kompakt felépítésével társul. Az adatok tömörítése két fő típusra osztható:
Az adattömörítés algoritmusa (az archiválás algoritmusa) egy algoritmus. amely megszünteti az adatrögzítés redundanciáját.
Bemutatunk néhány definíciót, amelyeket később az anyag bemutatásakor használunk.
A kód Az ábécé a bemeneti jel minden szimbólumának halmaza. Az angol nyelvű szövegek tömörítése során általában 128 ASCII kódot használ. A képek tömörítése során több pixelérték tartalmazhat 2, 16, 256 vagy más elemszámot.
A kódszimbólum a legkisebb adatcsomag, amelyet tömöríteni kell. Általában egy szimbólum 1 bájt. de lehet egy kicsit, egy trit, vagy valami más.
A kódszó a kódbetűk kódszimbólumainak sorozata. Ha minden szónak ugyanolyan hosszúsága van (a karakterek száma), akkor ezt a kódot egységesnek (rögzített hosszúságnak) hívják. és ha különböző hosszúságú szavak megengedettek, akkor - egyenetlen (változó hosszúságú).
A kód egy teljes szóösszetétel.
A token egy tömörített adatfolyamba írt adategység, amelyet egyes tömörítési algoritmus végez. A token több rögzített vagy változó hosszúságú mezőt tartalmaz.
A kifejezés egy adat, amelyet egy szótárba helyezett a későbbi tömörítéshez.
A kódolás az adatkompresszió folyamata.
A dekódolás a kódolási folyamat inverze, amelyben az adatok visszaállításra kerülnek.
A tömörítési arány az egyik leggyakrabban használt érték, amely a kompressziós eljárás hatékonyságát jelöli.
A 0,6 érték azt jelenti, hogy az adatok az eredeti térfogat 60% -át foglalják el. Az 1-nél nagyobb értékek azt jelentik, hogy a kimeneti áram nagyobb, mint a bemenet (negatív tömörítés vagy bővítés).
A tömörítési arány a tömörítési arány kölcsönössége.
Az 1-nél nagyobb értékek a tömörítést jelentik, és az 1-nél kisebb értékek a bővítést jelölik.
A kódszó átlagos hossza olyan érték, amelyet minden kódszöveg hosszának valószínűségi súlyozott összegeként számítunk ki.
ahol - a kódszavak valószínűsége;
A tömörítés két fő módja.
Statisztikai módszerek - tömörítési technikák és változó hosszúságú kódok a szimbólumok a bemeneti folyam, a rövidebb kódokat rendelt szimbólumok vagy csoportok szimbólumok, amelynek nagyobb a valószínűségét egy bemeneti folyam. A legjobb statisztikai módszerek a Huffman-kódolást alkalmazzák.
A szókincs tömörítése olyan tömörítési módszerek, amelyek adatokat tárolnak a "szótárban" (néhány adatszerkezet). Ha a bemenetre érkező új adatok sorszáma megegyezik a már a szótárban található töredékkel, akkor egy erre a töredékre mutató mutató a kimeneti folyamba kerül. A legjobb szótár módszerek alkalmazzák a Ziva-Lempel módszert.
Tekintsünk néhány ismert algoritmust az adatok tömörítésére részletesebben.
A Huffman módszer
Ezt az információt kódoló algoritmust a D.A. Huffman 1952-ben. A Huffman kódolás (tömörítés) egy széles körben használt tömörítési eljárás, amely a változó hosszúságú kódokat alfabetikus szimbólumokhoz rendelte, ezeknek a szimbólumok megjelenésének valószínűsége alapján.
Az algoritmus ötlete a következő: tudni kell a szimbólumok előfordulásának valószínűségét a forrásszövegben, leírhatjuk a változó hosszúságú kódok készítésének eljárását, amely egy egész számú bitből áll. A karakterek valószínűleg rövidebb kódokat kapnak. Így ebben az eljárásban, amikor az adatokat tömörítjük, minden karakterhez egy optimális előtag kódot rendelünk hozzá. a szövegben való megjelenésének valószínűsége alapján.
Az előtag kód olyan kód, amelyben egyetlen kódszó sem más kódszó előtagja. Ezek a kódok változó hosszúságúak.
Az optimális prefix kód az előtag kód. minimális átlagos hosszúsággal.
A Huffman algoritmus két szakaszra bontható.
- Határozza meg a karakterek megjelenésének valószínűségét a forrás szövegében.
Kezdetben a forrásszöveget teljesen el kell olvasni, és számolni kell a szimbólumok előfordulásának valószínűségét (néha megszámolja, hogy hányszor jelenik meg minden szimbólum). Ha ez figyelembe veszi mind a 256 karaktert, akkor nincs különbség egy szövegfájl vagy más formátumú fájl tömörítésében.
Ezután két a és b szimbólum van, amelyek a legkisebb valószínűséggel előfordulnak, és helyükre egy db dummy szimbólum lép. amely az a és b szimbólumok megjelenésének valószínűségének összegével megegyező előfordulási valószínűséggel rendelkezik. Ezután rekurzívan használva ezt az eljárást, van egy optimális prefix kód egy kisebb szimbólumkészlethez (ahol az a és b szimbólumokat egyetlen karakterrel helyettesítjük). Az eredeti szimbólumkészlet kódját a helyettesítő szimbólumkódokból a csere szimbólumkódja előtt 0 vagy 1 hozzáadásával kapjuk meg, és a két új kódot helyettesítő karakterkódként fogadjuk. Például az a karakter kódja megegyezik az x kóddal, amely a kód előtt hozzáadódik, és a b karakterhez az x karakter kódja előtt az egyik hozzáadódik.
A Huffman kódok egyedi előtagot tartalmaznak. amely lehetővé teszi számukra, hogy egyedülállóan dekódoljanak, annak ellenére, hogy változó hosszúságúak.
1. példa Huffman módszer szoftvereinek megvalósítása.
A Huffman algoritmus univerzális, bármilyen típusú adat tömörítésére használható, de hatástalan a kis méretű fájlok esetében (a szótár mentésének szükségessége miatt). Jelenleg ezt a módszert gyakorlatilag nem használják tiszta formában, általában összetett sémákban a tömörítés egyik szakaszaként használják. Ez az egyetlen algoritmus. ami a legrosszabb esetben nem növeli a forrásadatok méretét (kivéve a konverziós táblázatnak a fájlhoz való eltárolásának szükségességét).