01-Tömörítés-jegyzet (1) PDF

Veszteségmentes tömörítés Bevezetés: adattömörítés, kódolás általában Informatikában a kódoláselmélet adatok különböző reprezentációjával és azok közötti átalakításokkal foglalkozik. Legtöbb esetben a cél egy adott mennyiségű információ legkevesebb adattal való tárolása, vagyis a rövid reprezentáci...

Veszteségmentes tömörítés Bevezetés: adattömörítés, kódolás általában Informatikában a kódoláselmélet adatok különböző reprezentációjával és azok közötti átalakításokkal foglalkozik. Legtöbb esetben a cél egy adott mennyiségű információ legkevesebb adattal való tárolása, vagyis a rövid reprezentáció: információ- vagy adattömörítés. A kódolás során fontos kérdés, hogy az adat teljes egészében visszaállítható-e. Tömörítés esetében ennek megfelelően használhatunk veszteségmentes vagy veszteséggel járó eljárásokat (pl. JPEG, MPEG, MP3,... ). Mi csak az előbbivel foglalkozunk. A kódoláselméletnél meg kell adnunk az információ alapegységét, azaz azt, mennyi információtartalma van az atomi „tárolási egységnek”. Mivel a jelenlegi számítógépek bináris elven működnek, ez r = 2 és így a kódszavaink a T ′ = 0, 1 ′ ′ ′ ábécé ("lehetséges karakterek halmaza") feletti szavak lesznek. Kódnak nevezzük a T feletti véges szavak ("T betűiből alkotott sztringek") (kódszavak) egy tetszőleges nem üres halmazát. Egy kód szemléletesebb ábrázolásához elkészíthetjük annak kódfáját. Ebben a fában a fa csúcsai szavak (nem feltétlenül kódszavak), az éleit pedig a kódszavak lehetséges karaktereivel címkézzük. A fa gyökerében az üres szó szerepel és egy szóhoz tartozó csúcs leszármazottai azok a szavak, amelyeket úgy kapunk, hogy a szó után írjuk az élen szereplő karaktert. A kódhoz tartozó kódfa az a legkevesebb csúcsot tartalmazó ilyen tulajdonságú fa, ami tartalmazza az összes kódszót. A kódfa szemléltetés mellett más szempontból is hasznos lehet. Egyrészt a fa tulajdonságaiból következtethetünk a kód tulajdonságaira, másrészt a kódfa segítségével egy bitsorozat hatékonyan dekódolható: A gyökérből indulva a bitek szekvenciájának megfelelően járjuk be a fát, az élek mentén kódszót keresve és találat esetén ismételve a bejárást megkapjuk a dekódolt adatot. (Ha a dekódolás lehetséges és egyértelmű.) A kódolást betűnkénti kódolásnak nevezzük, ha az eredeti ∑ ábécé feletti adatot betűnként egy ∑ → C ⊂ T ∗ kölcsönösen egyértelmű (bijektív) leképezéssel készítjük el. Például az ASCII kódolás is ilyen, hiszen a megfelelő táblázat alapján betűnként történik a kódolt adat kiszámolása. A kódolandó állományokat karaktersorozatnak tekintjük, és a tömörítés célja az adatok kisebb helyen történő tárolásának biztosítása. A kód prefix, ha a kódszavak mind különbözőek és egyik kódszó sem folytatása a másiknak. Az állandó kódhosszú kód mindig prefix, ha a kódszavai különbözőek. Naiv kódolás (/naiv módszer) Fogalmak A kódot egyenletes kódnak nevezzük, ha a kód szavainak hossza egyenlő. A naiv módszer egyenletes kódot használó betűnkénti kódolás: tömörítendő szöveget karakterenként (betűnként), fix hosszúságú bitsorozatokkal kódoljuk. ∑ = ⟨σ1, σ2, … , σd⟩ az ábécé, tehát d az ábécé hossza/elemszáma/betűinek számossága. Ez alapján egy-egy karakter ⌈log2d⌉ bittel kódolható, ugyanis ⌈log2d⌉ biten 2 ⌈log2d⌉ különböző bináris kód ábrázolható, és 2 ⌈log2d⌉ ≥ d > 2 , azaz ⌈log2d⌉ biten ábrázolható d-féle különböző ⌈log2d⌉−1 kód, de eggyel kevesebb biten már nem. Tehát ha meg akarjuk határozni, hogy milyen hosszú kódszavakra lesz szükségünk, megnézzük, hogy hány eleme van az ábécének/tömörítendő szövegnek, kiválasztjuk az ennél nem kisebb legkisebb kettőhatványt, és ennek a kitevője lesz a kódszavak hossza. Kódolás 1. Meghatározzuk az ábécé elemszámát (d), vagyis a tömörítendő szó különböző karaktereit. 2. Ebből meghatározzuk a kódszavak hosszát. 3. Minden karakterhez rendelünk egy kódot ⇒ kódtáblázat. 4. Ezzel kódoljuk az eredeti szót úgy, hogy a karakterekhez tartozó kódokat egymás után írjuk (elválasztójelek nélkül). Kitömörítés A kódot feldaraboljuk és a kapott kódtábla segítségével visszafejtjük az eredeti szöveget. Megjegyzések A tömörített fájl tartalmazza a kódtáblázatot is. A lehetséges kódok tetszőlegesen kioszthatók a karaktereknek. Gyakorlatban, ha a tömörítés nem igazán fontos szempont, egyszerűsége miatt sok helyen alkalmazzák, például a 8 bit hosszúságú kódszavakat használó ASCII kód is ilyen. Csak hosszabb szövegeket érdemes így tömöríteni a kódtáblázat mérete miatt. Példa 1 Szöveg: ABRAKADABRA Kódtáblázat (lehet, de lehetne más is): karakter kód A 000 B 001 D 010 K 011 R 100 A fenti kódtáblázattal a tömörített kód a következő lesz: 000001100000011000010000001100000 Tömörített kód hossza: d = 5 és n = 11 (n a szöveg hossza) ⟹ 11 ∗ ⌈log5⌉ = 11 ∗ 3 = 33 bit (+ kódtábla) Példa 2 Szöveg: ERRE_ARRA_MERRE_ARRA Kódtábla: karakter kód E 000 R 001 _ 010 A 011 M 100 Tömörített kód: 000|001|001000010... (Note: a | jelek csak szemléltetés céljából vannak ott, illetve a... helyére mindenki be tudja helyettesíteni a megoldás maradékát.) Kódhossz: 20 ∗ 3 = 60 bit (+kódtábla) Huffman-kód Ezt az algoritmust Davi A. Huffman (1925-1999) írta le először egy vizsgadolgozatban, és 1952- ben publikálta. A Huffman-kód nagyon hatékony módszer az adatállományok tömörítésére. A megtakarítás 20%- tól 90%-ig terjedhet, a tömörítendő adatállomány sajátosságai alapján. A mohó algoritmus egy táblázatot használ az egyes karakterek előfordulási gyakoriságára, hogy meghatározza, hogyan lehet a karaktereket optimálisan ábrázolni bináris jelsorozattal. Betűnkénti kódolás esetén akkor kapunk rövidebb kódolt adatot, ha a gyakori betűkhöz rövid kódszót, a ritkákhoz pedig hosszabbakat rendelünk. A Huffman-kódolás egy betűnkénti optimális kódolás, az ilyen kódolások között szinte a legjobb tömörítés érhető el vele adott adat esetén. Ezt úgy érjük el, hogy a kódhoz tartozó kódfát alulról felfelé építjük az eredeti szöveg karaktereinek gyakorisága alapján. Kódolás 1. Olvassuk végig a szöveget és határozzuk meg az egyes karakterekhez tartozó gyakoriságokat. 2. Hozzunk létre minden karakterhez egy csúcsot és helyezzük el azokat egy (min) prioritásos sorban a gyakoriság, mint kulcs segítségével. 3. Kódfa építése a) Vegyünk ki két csúcsot a prioritásos sorból és hozzunk létre számukra egy szülő csúcsot. b) A szülő-gyerek éleket címkézzük nullával és eggyel a gyakoriságnak megfelelő sorrendben (legyen mondjuk mindig a bal gyerek felé a 0). c) Helyezzük el a szülő csúcsot a prioritásos sorba gyerekei gyakoriságának összegét használva kulcsként. 4. Ismételjük meg az előző pontot, ha több mint egy csúcs szerepel a sorban. 5. Olvassuk ki a karakterekhez tartozó kódszavakat a kódfából. (Gyökérből indulva, a levélig tartó út címkéi – szokták a levél szelektorának is nevezni.) 6. Olvassuk végig újra a bemenetet és kódoljuk azt karakterenként. Kódfa felépítésének algoritmusa A kódfa csúcsai Hnode típusúak legyenek, ahol a freq tárolja a gyakoriságot a ch levelek esetén a betűt (belső pontokban nem használjuk a ch -t)  A prioritásos sorban Hnode -ra mutató pointerek lesznek; freq adja a prioritást. Feltesszük, hogy az ábécét már meghatároztuk és a gyakoriságokat már megszámoltuk; ez a lépés könnyen megvalósítható programozási tételek segítségével, így nem részletezzük. Dekódolás A kitömörítést is karakterenként végezzük. A kódolt szöveget bitenként dolgozzuk fel a következőképpen: 1. Álljunk a kódfa gyökerére. 2. Olvassunk egy bitet, lépjünk ennek megfelelően a jobb vagy bal gyerekre. Folytassuk addig, amíg egy levélcsúcshoz nem érünk. 3. Levélhez érve olvassuk ki, milyen betűt tartalmaz a levél és írjuk ki a kimenetre. 4. Ismételjük az 1. lépéstől, amíg el nem fogynak a kódolt szöveg bitjei. Megjegyzések A naivhoz képest két optimalizáció:  nincsenek benne unáris ágak a ritkábban előforduló betűk lejjebb vannak a fában "Problémák": A kódoláshoz a tömörítendő fájlt, illetve szöveget kétszer olvassa végig. Betűnként tömörít, ami nem optimális pl. képekhez, amik hosszú mintákat tartalmaznak. A kódolt adathoz a kódfát is csatolnunk kell, ami ront a tömörítési arányon. A kódfa szigorúan bináris fa. A dekódoláshoz használhatnánk a betűk kódjait tartalmazó kódtáblát is, de az abban való keresgélés időigényesebb lenne, mint a kódfa alapján történő dekódolás, így nem ezt használják a gyakorlatban. Általában a Huffman-kódolás nem egyértelmű. Egyrészt, ha több azonos gyakoriság van, akkor bármelyiket választva Huffman-kódolást kapunk; másrészt a 0 és 1 szerepe felcserélhető. De bárhogy is választunk ilyen esetekben, ugyanakkora kódhosszt fog eredményezni. Mivel a kódolás minden adathoz különböző, a dekódoló oldalon is ismertnek kell lennie. Ez gyakorlatban azt jelenti, hogy a kódfát vagy kódtáblát is csatolnunk kell a kódolt adathoz (ami ront a tömörítési arányon), vagy a Huffman-kódot általánosított adathoz készítjük el. Emiatt a gyakorlatban Huffman-kódolással is csak hosszabb szövegeket érdemes tömöríteni. Prefix-kód A Huffman-kód mindig egyértelműen dekódolható a kódfa segítségével, mivel prefix-kód. Prefix- kód (vagy prefixmentes kód) esetén a kódszavak halmaza prefix mentes, a kódszavakra igaz, hogy egyik sem kezdőszelete (valódi prefixe) bármelyik másiknak. A kódolás minden bináris karakterkódra egyszerű: csak egymás után kell írni az egyes karakterek bináris kódját, nincs szükség elválasztó karakterekre. Mikor nem prefixmentes a kódolás és hogy áll összefüggésben a kódfával? A Huffman-kódolásnál a kódfájában a betűk a levelek, vagyis ha bármelyiktől a gyökérig tartó út során nem ütközünk bele másik betűbe. Ha így lenne, vagyis belső csúcsban is lenne betű, akkor már nem lenne prefixmentes a kód (lásd példa ábra fent). Példa 1 Szöveg: AZABBRAKADABRAA karakter gyakoriság kód A 7 0 B 3 111 D 1 1100 K 1 1101 R 2 101 Z 1 100 Prioritásos minimumsorba hozzáadjuk a címkéket, hogy ennek segítségével felrajzolhassuk a kódfát.