Betűrendben egyenetlen bináris kódolás
Betűrendben egyenetlen bináris kódolás - kódoló, amelyben a kód ábécé elsődleges kódolt bináris kombinációi alfanumerikus karakterek (azaz 0 és 1), azzal jellemezve, a kód hossza, és ennek megfelelően, a időtartama egyetlen kód átviteli változhat.
Az előhívó Kódelméleti - a kódszó változó hosszúságú, hogy ilyen tulajdonság (teljesítmény Fano körülmények): ha a kódszó tartalmaz, akkor minden nem üres sor b ab szava a kód nem létezik. Bár az előhívó áll a szavak különböző hosszúságú, ezeket a szavakat lehet rögzíteni anélkül, hogy a határoló.
Például egy kód, amely szavak 0, 10 és 11, egy előtag és az üzenet lehet osztani 01001101110 szava egyedülálló módon:
0 10 0 11 0 11 10
A kódszó tagjai 0, 10, 11 és 100, nem egy előtagot, ugyanazt az üzenetet is lehet értelmezni több szempontból is.
0 10 0 11 0 11 10
0 100 11 0 11 10
Az ötlet alapjául szolgáló Huffman, alapuló előfordulási gyakorisága a karakter a szekvenciában. A szimbólum, amely megtalálható a sorozatban gyakran kap egy új, nagyon kevés kódot, és a karakter fordul elő, hogy legritkábban kap, épp ellenkezőleg, nagyon hosszú kódot. Erre azért van szükség, mert szeretnénk, ha az általunk feldolgozott összes bemenet, a leggyakoribb jel elfoglalt kevésbé az egész hely (és kevésbé, hogy mit csinálnak az eredetiben), és a legritkább - egy kicsit több (de mivel azok ritkák, hogy nem számít ). Ebben a cikkben, úgy döntöttem, hogy a karakter hosszúságú lesz 8 bit, azaz megfelel karaktereket.
Tegyük fel, hogy egy string «sípoló boop sört!», Amelyekhez a jelenlegi formájában, minden karakter tölt egy bájt. Ez azt jelenti, hogy az egész sort vesz fel az egész 15 * 8 = 120 bit memória. Kódolás után sorban fogja elfoglalni 40 bit.
Ahhoz, hogy a kódot minden karakterhez «sípoló boop sört!», Alapozva gyakorisága, meg kell építeni egy bináris fa úgy, hogy minden levél a fán fog tartalmazni egy karakter (nyomtatható karaktert a string). Fa épül majd a levelek, hogy a gyökér, abban az értelemben, hogy a karakterek kisebb gyakorisággal lesz távolabb a gyökér, mint a karaktereket. Hamarosan látni, hogy ez miért van szükség.
Építeni a fa, fogjuk használni egy kissé módosított prioritású sorba - ez lesz az első a kivont elemeket a legalacsonyabb prioritású, és nem is a legnagyobb. Meg kell építeni egy fa a levelek, hogy a gyökér.
Megkezdéséhez számítani a frekvenciát az összes karakter:
Kiszámítása után a frekvencia, akkor hozzon létre egy bináris fa csomópontok minden karaktert, és helyezze el őket a sorban frekvenciát használva prioritásként:
Elérjük most mi vagyunk az első két elem a sorból, és kösse őket, ami egy új csomópont a fa, amelyet mindketten leszármazottai, és a prioritás az új csomópont lesz egyenlő az összeg a prioritásokat. Ezt követően adjuk hozzá a kapott új összeállítás helyére.
Mi ismételje meg a fenti, és egymás után kapjuk:
Nos, miután társítjuk az utolsó két elem, hogy az utolsó fát:
Most, hogy a kódot minden egyes karakter, akkor csak meg kell járni a fa, és minden átmenet hozzátéve 0, ha megyünk a bal oldalon, és 1 - ha a jobb:
Ha így teszünk, megkapjuk a következő kódokat a karakterek:
Megfejteni a kódolt szöveg, van, illetve csak megy fa, fordult a megfelelő bit mindkét oldalán, amíg el nem érjük a lap. Például, ha van egy vonal „101 11 101 11„és a fát, akkor egy sor «pepe».
Fontos szem előtt tartani, hogy minden kód egy prefix egy másik karakter kódját. Példánkban, ha a 00 - az a kód, a „b”, a 000 nem lehet valaki másnak a kódját, mert különben kap egy konfliktus. Mi soha nem érte el ezt a szimbólumot a fán, mert megszűnne egy „b”.