Tömörítő algoritmusok Flashcards
Huffmann algoritmus lépései
- Kiválasszuk milyen karaktereket szeretnénk kódolni és megadjuk ezeknek a gyakoriságát és növekvő sorrendbe rendezzük ez alapján.
- A két legkisebb elemet összeadjuk és helyettesítjük őket.
- Ha két ugyanolyan érték van mindegy melyiket használjuk fel.
- Felrajzolunk egy binfát úgy hogy a bal éle 0 a jobb pedig 1 lesz és a különböző betűkhöz tudunk kódot rendelni a gyökértől a csúcsig az érintett élek alapján.
Huffmann algoritmus tulajdonságai
Optimális prefix kódolást állít elő.
A Huffmann kód optimális.
A Huffmann kód egy offline kódolás, a beérkező jelek gyakoriságát kiszámolja határozzuk meg a valséget. Az online változata folyamatosan változó kódoló fával számol.
LZ77 tulajdonságok
Abraham Lempel és Jacob Ziv fejlesztett ki. Az algoritmus lényege, hogy a bemeneti adatokban található ismétlődő szekvenciákat az előfordulásuk helyével és hosszával helyettesíti.
Online tömörítés, szótár alapú.
Hatékonz és veszteség mentes.
Bonyolult és az ablak megválasztása kulcs fontosságú.
LZ77 menete
A kódolási folyamat menete:
A pozíció beállítása az adatfolyam elejére;
megkeresi a leghosszabb korábbi előfordulást;
kimenetre írja a (B, L) C formulát, ahol B a megtalált karakter távolsága az előretekintő puffertől, az L az egyező karakterek legnagyobb hosszúsága, a C pedig az első nem egyező karakter az előretekintő pufferben;
ha az előretekintő puffer nem üres, akkor eltolja a pozíciót (ablakot) az L+1-el, majd visszaugrik a 2. lépésre.
LZ78 tulajdonságai
A. Lempel, J. Ziv (1978.)
Online tömörítés; szótáras
A karakterekhez előtagokat (prefixeket) rendel, és új szekvenciákat hoz létre a már felfedezett minták alapján.
LZ78 menete
Szótár létrehozása: Az LZ78 algoritmus folyamatosan bővíti a szótárát az eddig találkozott szekvenciák alapján.
Kódolás:
- Minden új karakterhez, amely nem szerepel a szótárban, új bejegyzést adunk hozzá.
- Ha a karakter már szerepel a szótárban, akkor a hozzá tartozó indexet használjuk, majd a következő karaktert adjuk hozzá a már meglévő szekvenciához.
Kódolt kimenet: A kódolt forma egy index (a szótárban található) és az új karakter (ha van) párja
LZW tulajdonságai
Abraham Lempel, Jacob Ziv és Terry Welch fejlesztett ki 1984-ben. Az LZW a bemeneti adatok ismétlődő mintázatait kihasználva tömörít, és a LZ78 algoritmusra épít, de szótárt használ a már feldolgozott adatok tárolására.
LZW menete
A szótárt inicializáljuk az összes 1 hosszú sztringgel
Kikeressük a szótárból a leghosszabb, jelenlegi inputtal összeillő W sztringet
W szótárindexét kiadjuk, és W-t eltávolítjuk az inputról
A W szó és az input következő szimbólumának konkatenációját felvesszük a szótárba
A 2. lépéstől ismételjük
