Online számológép Huffman-kód
Egy kis részlet a Wikipedia.
Huffman algoritmus - adaptív optimális mohó algoritmus prefix kódoló ábécé minimális redundancia. Úgy alakult, 1952-ben egy végzős hallgató a Massachusetts Institute of Technology David Huffman írásban idejük papírt. Ez a jelenleg használt számos adattömörítési programokat.
Ez a módszer a kódolás két fő lépésből áll:
Az optimális kódfában.
Építése a leképezés kódjel alapján az épített fa.
Az ötlet az algoritmus a következő: ismerve a valószínűsége karakter az üzenet, akkor lehetséges, hogy ismertesse az eljárást építésének változó hosszúságú kódok, amelyek egy teljes bitek számát. Szimbólumok nagyobb valószínűséggel társított rövidebb kódokat. Huffman kódok tulajdonát előtag (t. E. Nem kódszó egy másiknak előtagja), amely lehetővé teszi számukra, hogy dekódolni egyértelműen.
Klasszikus Huffman algoritmus bemeneti vett szimbólum táblázat előfordulási gyakoriság egy nyilatkozatában. További alapján E táblázat kialakítva Huffman-kódolás fa (fa-H).
- bemeneti ábécé szimbólumot alkotnak egy listát az elérhető csomópontokat. Minden lap tömege, amely lehet azonos a valószínűsége, akár az előfordulások számát egy karakter egy üzenet leeresztett.
- Válogatott két szabad csomópontja a legalacsonyabb súlyokat.
- Hoz létre a szülő egy tömege azonos a teljes súlyt.
- Szülő hozzá a listát a szabad csomópontok, és két utódai eltávolítják a listából.
- Egy ív terjedő szülő, társított bit 1 és a másik - a bit 0.
- A lépések kezdve a második mindaddig ismételjük, amíg a lista a szabad csomópontok nem marad csak egy szabad csomópontot. Úgy tartják a gyökér a fa.
Ez a folyamat is képviselteti magát az építkezés egy fa, melynek gyökere - jelképe az összeget a valószínűségek kombinált szimbólumok elő, hogy a szimbólumok az utolsó lépés, az ő leszármazottai n0 - karakterek az előző lépésben, és így tovább ..
Ahhoz, hogy meghatározzuk a kódot minden karakter szerepel az üzenetben, meg kell menni egészen a gyökér a levél a fa megfelelő aktuális szimbólum, tárolására bitet, amit mozoghat a fa ágain (az első ág a pálya megfelel a legkisebb helyi értékű bit). Az így kapott egy bitsorozatot a kód szimbólumot, írva a fordított sorrendben.