Adattömörítési tudomány mindenkinek
Ez egy olyan kifejezés, amely könnyen érthető, de amelynek működését nehéz megmagyarázni. Pontosan ilyen jellegű elképzeléseket szeretnék elmagyarázni ebben a blogban.
A számítástechnikában az adattömörítés a következőképpen fogalmazható meg: "A bitek sorozatának átalakítása egy másik kisebb bit sorozatra egy algoritmus segítségével, az információk megtartása mellett, vagyis l" fordított műveletre van szükség "
Veszteségmentes tömörítés
A legkönnyebben veszteségmentes tömörítési algoritmus megértése a RLE kódolás (Run Length Encoding), amely egy karakter (vagy egy kicsit) ismétlésének számlálásából áll.
Példa RLE kódolásra: az "ouuuuuaauuuuuu" szót úgy értelmezik, mint "o", 5 "u", 2 "a" és 6 "u" szekvenciáját, azaz: "o5u2a6u". Ezért 14 karaktert tömörítettünk 7 karakterbe (50% -os tömörítési arány). Nyilvánvaló, hogy ez a típusú kódolás csak akkor releváns, ha nagy karakterláncokat ismételnek meg. Ez a helyzet a faxok kódolásakor a pontok egymás utáni kódolásához
fekete-fehér egy lapon (CCITT kódolás).
Egyéb veszteségmentes tömörítési technikák entrópia tömörítés . Ezek az algoritmusok a tömörítendő információk statisztikai vizsgálatán alapulnak, hogy az ismétlődő karaktereket nagyon kevés bitben kódolják. A leghíresebb entrópia algoritmusok a Huffman és az algoritmus
LZ77.
Huffman algoritmusa
Az algoritmus megértésének legjobb módja, ha példát adunk. Tegyük fel magunknak azt a célt, hogy tömörítsük a "A tudósok intelligensek" mondatot.
A klasszikus ASCII reprezentációban betűre 7 bitre van szükség (összesen 2 ^ 7 = 128 karakter): ez a 35 karakteres mondat tehát 35 * 7 = 245 bit memóriaterületet foglal el.
Most Huffman kódolásával tanulmányozzuk a tömörítendő szöveg egyes betűinek előfordulási számát, hogy kisebb számú bitet rendeljünk a leggyakrabban használt betűkhöz:
- C, F, Q, U, O, G: 1 előfordulás
- L, SPACE: 3 előfordulás
- T, N: 4 előfordulás
- E, S, I: 5 előfordulás
Ezután építünk egy fát, ahol minden levél egy betűt képvisel, súlyával együtt (az előfordulások száma). Ezután vegyük a 2 legkisebb súlyt, hogy csoportosítsuk őket, és kapunk egy csomópontot, amelynek súlya megegyezik a 2 levél összegével, és így tovább, amíg egyetlen csomópontot nem kapunk a végén.
Példánkkal:
- a) Átcsoportosítjuk az "1" súlyú betűket, és hozzáadjuk őket, hogy "2" súlyú csomókat készítsünk (sárga)
- b) A 2 "3" betűt hozzáadjuk a "2" 2 csomóhoz, hogy "5" (zöld) csomókat készítsünk
- c) Hozzáadjuk a 2 "4" súlyú betűt a "2" és az "5" súlyú csomópontokhoz, hogy "6" és "9" súlyú csomópontokat készítsünk (bíborvörös).
- d) Hozzáadjuk a 3 "5" súlyú betűt az "5", "6" és "9" súlyú csomókhoz, hogy "10", "11" és "14" (narancssárga) súlyú csomókat készítsünk.
- e) Addig fejezzük be a fát, amíg nem kapunk közös "35" súlyú csomópontot (piros).
- f) Az egyes betűkhöz bitek sorozatát kell rendelni. Ehhez hozzáadunk egy "0" bitet a bal ágakhoz és egy "1" bitet a jobb ágakhoz, majd megszerezzük a következő fát: