Tudd Intuíció, előadás, adatok tömörítési algoritmusok
Kódfában (fa Huffman, H-fa) - egy bináris fa. ahol:
- levelek jellel megjelölt, amelyre kódolás van kialakulóban;
- csomópontok (beleértve a gyökér) jelölt összege a valószínűségek előfordulásának megfelelő jeleket a levelek a részfa. amelynek gyökér a megfelelő csomópontot.
Huffman módszer kapja meg a bemeneti szimbólum táblázat előfordulási gyakoriság az eredeti szövegben. További alapján E táblázat alapján Huffman kódolás fa.
Egy algoritmust építésére Huffman fa.
1. lépés A bemeneti ábécé szerinti szimbólumok alkotnak listát a szabad csomópontok. Minden lap van súlya. amely lehet azonos a valószínűsége, akár az előfordulások számát egy karaktert a tömörített szöveget.
2. lépés: Válassza ki a két szabad csomópontja a legalacsonyabb súlyokat.
3. lépés: Készítsen szülő tömegű egyenlő a teljes súlyát.
4. lépés: A szülő hozzáadjuk a listát a szabad csomópontok, és a két gyerek eltávolítják a listából.
5. lépéssel egy ív. így a szülő van rendelve egy kicsit 1 és a másik - a bit 0.
6. lépés: Ismételje meg a lépéseket, kezdve a második, amíg a lista a szabad csomópontok nem marad csak egy szabad csomópontot. Úgy tartják a gyökér a fa.
Két módja van, hogy az épület egy kódfában a gyökér a levelek és levelekből a gyökér.
Egy példa az építőiparban a kód fa. Mivel a kezdő karakterek sorozata:
A kiindulási térfogat 20 bájt (160 bit). A közölt ábrán látható. 41,1 adatok (asztal előfordulási valószínűsége szimbólumok, kódfában és egy asztal az optimális prefix kód) kódolt kezdeti szimbólumok sorozatát a következő:
Következésképpen, a térfogata egyenlő 42 bit. A tömörítési arány megközelítőleg egyenlő 3,8.
Ábra. 41.1. Létrehozása egy optimális prefix kód
Classic Huffman van egy jelentős hátránya. Helyreállítani a tartalmát a tömörített szöveg dekódolás során szükséges ismerni a frekvencia táblázatot, melyet a kódoláshoz. Következésképpen a hossza a tömörített szöveg nőtt a hossza a frekvencia táblázatot, amelyet el kell küldeni, megelőzve olyan adatokkal, amelyek semmissé minden erőfeszítés a tömörítés. Továbbá szükség van egy teljes körű statisztikai gyakorisága, mielőtt ténylegesen kódoló szükséges két részeket a szövegben, az egyik modelljének megszerkesztésére a szövegben (a frekvencia asztal és a Huffman fa), a másik az aktuális kódoláshoz.
2. példa szoftver megvalósítása Huffman algoritmus segítségével a kód fa.
Ahhoz, hogy hajtsák végre a dekódoló kell egy kódot fa. amelyet meg kell együtt tárolják a tömörített adatokat. Ez vezet egy bizonyos csekély mennyiségének növekedése a tömörített adatokat. Ők használják a különböző formátumokat, amelyek tárolja a fát. Felhívjuk a figyelmet arra, hogy a kód facsomópontok üresek. Előfordul, hogy egy üzlet nem maga a fa. és a kezdeti adatok a képződéséért, azaz információ a valószínűségek előfordulási szimbólumok vagy számok. Ha ez a dekódolási folyamat előzi építése egy új kódot fa, amely megegyezik a kódoláshoz.
Fontos kifejezések
Az adattömörítés - olyan folyamat, amely biztosítja a csökkentését adatmennyiség csökkentésével redundancia.
Veszteségmentes tömörítés (teljesen reverzibilis) - egy adattömörítési eljárás, amelyben egy része a korábban kódolt adatok helyreáll a kicsomagolás után teljesen módosítás nélkül.
A veszteséges tömörítés - egy adattömörítési eljárás, amelyben, hogy maximalizálja a tömörítési arány az eredeti tömb adat részének az abban közölt adatok eldobjuk.
Az algoritmus az adattömörítés (archiválás algoritmus) - az algoritmus. amely kiküszöböli redundanciát rekordot.
Alphabet kód - egy sor karakterek bemenet.
Kódszimbolummá - a legkisebb egység az adatok tömörítve.
Kódszó - sorozata kódjelkép az ábécé kódot.
Token - egységnyi adat írva, hogy egy tömörített adatfolyamot néhány tömörítési algoritmust.
A kifejezés - ez egy adat, hogy kerül egy szótárban felhasználásra tömörítés.
Coding - egy adattömörítési eljárás.
Decoding - egy fordított kódolási eljárás, amelyben az adat helyreállítás az végre.
Sűrítési arány - olyan érték, hogy jelezze a hatékonysága a tömörítési eljárás, egyenlő az arány a kimeneti adatfolyam mérete a bemeneti adatfolyam.
A tömörítési arány - a reciproka a tömörítési arányt.
Az átlagos hossza egy kódszó - egy értéket, amely súlyozott összege minden valószínűség a kódszavak.
Statisztikai módszerek - ez a tömörítési módszerek rendel 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 Dictionary Compression - egy kompressziós technikák, tárolására darab adatok egy adatstruktúrában úgynevezett szótárban.
Haffmanovskoe kódolás (tömörítés) - tömörítési módszer hozzárendeli a szimbólumok az ábécé változó hosszúságú kódok alapján a valószínűségét a ezeket a karaktereket.
Előhívó - olyan kód, amely kódszó sem prefix egy másik kódszóban.
Optimális prefix kód - egy előtaggal kódot. amelynek legkisebb átlagos hossza.
Kódfában (fa Huffman, H-fa) - egy bináris fa. ahol: a levelek egy szimbólum, amelyre a kódolás fejlesztenek; csomópontok (beleértve a gyökér) jelölt összege a valószínűségek előfordulásának megfelelő jeleket a levelek a részfa. amelynek gyökér a megfelelő csomópontot.
rövid összefoglaló
- Az adattömörítés egy folyamat, amely biztosítja a csökkentését adatmennyiség csökkentésével redundancia.
- Adat tömörítés lehet veszteséges és veszteségmentes.
- Sűrítési arány jellemzi a mértékét adattömörítési.
- Két fő módja rugók: a statisztikai módszerek és szótár tömörítés.
- Huffman algoritmus utal a statisztikai módszerek tömörítés.
- Az az elképzelés, Huffman algoritmus a következő: ismerve a valószínűségét a karakter a forráskódot, akkor lehetséges, hogy ismertesse az eljárást építésének kódok változó hosszúságú, amelyek egy teljes bitek számát.
- Huffman kódok egyediek előtag, amely lehetővé teszi számunkra, hogy egyedi módon dekódolni őket, annak ellenére, hogy a változó hosszúságú.
- Huffman sokoldalú, akkor lehet használni, hogy tömöríteni bármilyen típusú adat, de ez nem túl hatékony a kis fájlméret.
- Klasszikus Huffman algoritmus alapján a kódfában igényel tárolására kódfában, ami növeli a komplexitást.