Huffman-kód - studopediya
Definíció 1: Legyen A = 1, A2 ,. , An> - ábécé különböző szimbólumok N, W = 1, W2 ,. , Wn> - egy sor megfelelő pozitív egész súlyok. Ezután egy sor bináris kódok C = 1, c2 ,. , Cn>, oly módon, hogy:
(1) ci egy előtagot CJ. ha i * j
(2) minimál (| ci | ci-kód hossz)
Ez az úgynevezett minimálisan redundáns prefix kód, vagy egy másik kódot Huffman.
1. Az ingatlan (1) az úgynevezett prefix tulajdonság. Meg lehet egyedileg dekódolni változó hosszúságú kódok.
2. Az a mennyiség, az ingatlan (2) lehet kezelni, mint a kódolt adatbitek. A gyakorlatban ez nagyon kényelmes, mert Ez lehetővé teszi számunkra, hogy becsülni az összenyomódás mértékét anélkül, hogy kódolni közvetlenül.
3. Ezt követően annak érdekében, hogy a félreértések elkerülése végett, megértjük kóddal bitsorozat egy bizonyos hosszúságú, és a minimális redundancia Huffman-kódot, vagy - több kód (bitsztringekre) jelöl ki a különleges karaktereket és bizonyos tulajdonságú.
Köztudott, hogy egy bináris kód prefix megfelel egy adott bináris fa.
2. Definíció: Egy bináris fa megfelelő Huffman kódot hívják Huffman fa.
A feladat megépítésének Huffman kód megegyezik a problémát építésének a megfelelő fát. Itt van egy általános rendszer felépítésének Huffman fa:
a betűk vannak elrendezve csökkenő sorrendben valószínűsége. Hajtsuk a valószínűsége, hogy a két utolsó betű és számos átírni újra az új valószínűsége (összeg). Ezután ismételjük meg a műveletet, amíg nem kap 1. Az alsó levél mindig kódolni nulla, és a felső - egységet.
A fordításhoz a kód kombinációk alapján kódfában. Megy a kódfában fentről lefelé, lehet írni minden betű a megfelelő kódszó.
Huffman-kód, valamint Shannon-Fano, egy előtag, azaz ilyen kód kombináció sem nem esik egybe az elején egy játék hosszabb, és ez lehetővé teszi, hogy egy egyértelmű dekódolási bevezetése nélkül elválasztó szimbólumokat.
Átlagos számjegyek száma:
Amint látjuk, az értéke az átlagos bitek számát elég közel az entrópia, ezért is tekinthető hatékony kódot. Ezen túlmenően, az összehasonlítás, ki tudjuk számítani a K értéke az egységes kód:
Tegyük fel, hogy van egy X valószínűségi változó (x1, x2, x3, x4, x5, x6, x7, x8), amelynek nyolc államok valószínűségi eloszlás
Minden betű írásos csökkenő sorrendben a valószínűség, majd csoportokba osztottuk, egyformán valószínű, amelyek kijelölt 0 és 1, majd újra osztva egyformán valószínű csoportok, stb
építeni egy Huffman fa az üzenet S = "A H F B H C E H E H C E A H D C E E H H H C H H H D E G H G G E H C H H".
Tegyük fel, hogy az alábbi táblázatban előtag kódok:
És dekódolja az üzenetet: 00100010000111010101110000110
Megjegyzés. Dekódolás történik ciklikus ismétlődése a következő:
1. vágott az aktuális üzenet, a bal szélső karakter, hogy csatlakozzon a munka kódszó;
2. összehasonlítják az operációs kódszó a kód táblázat; Ha nincs egyezés, menjen a (1);
3. dekódolni dolgozó kódszó, tisztítsa meg;
4. Ellenőrizze, hogy több karakter az üzenet; Ha "igen", menj (1).
Legyen elsődleges ábécé A. álló hat karakter a1 ... a6 az előfordulási valószínűsége az üzenet, illetve 0,3; 0,2; 0,2; 0,15; 0,1; 0,05.
Szerkesszünk egy Huffman-kód
Kódolja a bináris kód a Shannon-Fano együttest álláshelyek = x1, x2. x8, ha minden egyformán kódolt üzeneteket. Itt található az optimális jellegét a kapott kódot.
Határozzuk meg az elemek száma egy kódszóban, ha tudjuk, hogy a kombinációk teljes száma N = 512, és egy bázis 2 kód.
Hány bináris számokat lehet képviselni 7-bites kódot?
Ez adott egy sor szimbólumok x1, x2, x3, x4, rendre a következő statisztikák: 0,28; 0,14; 0,48; 0.10. Kódolás szimbólumok szerinti Shannon-Fano, és hatékonyságának meghatározására a kódot.