Huffmani kodeerimine: erinevus redaktsioonide vahel
P r2.7.2+) (Robot: th:รหัสฮัฟแมน และ รหัสแชนนอน-ฟาโน → th:การเข้ารหัสฮัฟฟ์แมน |
P r2.7.1) (Robot: fa:کدگذاری هافمن → fa:کدگذاری هافمن |
||
99. rida: | 99. rida: | ||
[[en:Huffman coding]] |
[[en:Huffman coding]] |
||
[[es:Codificación Huffman]] |
[[es:Codificación Huffman]] |
||
[[fa: |
[[fa:کدگذاری هافمن]] |
||
[[fr:Codage de Huffman]] |
[[fr:Codage de Huffman]] |
||
[[ko:허프만 부호화]] |
[[ko:허프만 부호화]] |
Redaktsioon: 1. märts 2013, kell 04:09
See artikkel ootab keeletoimetamist. |
Huffmani kodeerimine on prefikskoodide üks liik. Huffmani kodeerimise idee on asendada olemasolev sümboleid kirjeldav bitijada ümber nõnda, et informatsiooni hulgas tihemini esinevad tähemärgid saaksid kirjeldatud lühema bitijadaga. Tulemusena saame informatsiooni kirjeldatud esinemistihedust eelistaval ja minimaalset tähemärkide hulka kasutaval alusel. Informatiooni kirjeldav andmehulk ei pruugi väheneda, eriolukorras võib ta isegi kasvada, kuid tegemist on tihendusalgoritmiga, mis tavateksti kokkupakkimisel saavutab märgatava erinevuse (tihti üle 30%).
Algoritmi rakendamisest
Huffmani kodeerimisalgoritm põhineb konkreetse informatsiooni tähemärkide sageduse põhjal binaarpuu ehitamisel ja sellest tähemärkide bitijada kirjeldava kodeerimistabeli loomisel. Faili tihendamise puhul kirjutatakse väljundfaili puu kirjeldus ja algse sisendfaili sisu, kus tähemärgid on asendatud uue kodeeringuga.
Otsese informatsiooni sisaldava faili tihendamise juures eksisteerib nii mõnedki kitsaskohad, mida tuleb lahendada. Näiteks tuleb realiseerida väljundfaili lõpu tuvastus, sest tõenäolisel ei lõpe fail baidi pealt vaid on mõne bitine ülejääk.
Binaarpuu rakendamiseks kasutatav struktuur
//tüüpiline struktuur programmeerimskeeles C, mida kasutada binaarpuu ehitamisel
typedef struct tree {
int ch; //tähemärgi numbriline kood
int freq; //informatsioonis esinemise tihedus
struct tree *left; //viide sama tüüpi struktuurile
struct tree *right; //2 viide sama tüüpi struktuurile
} tree;
Puu ehitamisel kasutatavad mõisteid
- leht – element, mille tähemärgi numbriline kood on määratud positiivselt, harud jäävad ühendamata (tal pole neid)
- vars – element, mille tähemärgi numbriline kood on vaid algväärtustatud, harud on väärtustatud, esinemistihedus on temast harudes olevate elementide esinemistiheduse summa
- juur – element, mille harusid pidi võib jõuda kõigi lehtedeni
- haru – elemendi viide sama tüüpi elemendile
Puu ehitamise algoritm
- Saadakse lehtede massiiv, milles on tähemärgid ja nende esinemise sagedused
- Massiiv sorditakse esinemise sageduse alusel
- Luuakse uus vars, mille harud ühendatakse kahe väiksema esinemise sagedusega elemendiga massiivis.
- Massiivi lisatakse vars ja eemaldatakse elemendid, mis asetsevad tema harudes
- Lisatud vars saab oma esinemise sageduseks tema harudes olevate elementide summa
- Kui massiivis on järgi vaid üks element, on puu valmis, kui mitte, korratakse punkte alates 2st
Kodeerimistabeli loomise rekursiivne algoritm
- Saadakse viit puu juurele
- Kui tegemist on lehega, lisatakse loodud kood ja koodi pikkus kodeerimstabelisse
- Kui varrel on vasakpoolne (esimene) haru olemas, suurendatakse koodi pikkust ja pöördutakse punkti 1
- Kui varrel on parempoolne (teine) haru olemas, määratakse koodi viimane bitt 1ks, suurendatakse koodi pikkust ja pöördutakse punkti 1
Tõenäoliselt pole raske iteratiivset algoritmi luua, kuid selle vajadus on olematu, sest tähed on üldjuhul kirjeldatud 8 bitiga, mille kõigi kombinatsioonide hulk on 256.
Kodeerimistabeli näide
Kodeerimistabeli element koosneb vormist ja pikkusest, ning kõik elemendid saavad pärast seda algoritmi määratud unikaalsete bitijadadega. Järgneval on toodud infokuvang eelneva ja uue kodeeringu erinevustest, kodeerimistabeli informatsiooniks on sõne "this is an example of a huffman tree", mille kohta eelneval oli juba samaväärne puu näide toodud.
Kodeerimistabel: Tähemärk ' ' nr(32) | binaarkood:00100000 | uus binaarkood:111 Tähemärk 'a' nr(97) | binaarkood:01100001 | uus binaarkood:001 Tähemärk 'e' nr(101) | binaarkood:01100101 | uus binaarkood:000 Tähemärk 'f' nr(102) | binaarkood:01100110 | uus binaarkood:1101 Tähemärk 'h' nr(104) | binaarkood:01101000 | uus binaarkood:1100 Tähemärk 'i' nr(105) | binaarkood:01101001 | uus binaarkood:1001 Tähemärk 'l' nr(108) | binaarkood:01101100 | uus binaarkood:01101 Tähemärk 'm' nr(109) | binaarkood:01101101 | uus binaarkood:1000 Tähemärk 'n' nr(110) | binaarkood:01101110 | uus binaarkood:1011 Tähemärk 'o' nr(111) | binaarkood:01101111 | uus binaarkood:01100 Tähemärk 'p' nr(112) | binaarkood:01110000 | uus binaarkood:01111 Tähemärk 'r' nr(114) | binaarkood:01110010 | uus binaarkood:01110 Tähemärk 's' nr(115) | binaarkood:01110011 | uus binaarkood:1010 Tähemärk 't' nr(116) | binaarkood:01110100 | uus binaarkood:0101 Tähemärk 'u' nr(117) | binaarkood:01110101 | uus binaarkood:01001 Tähemärk 'x' nr(120) | binaarkood:01111000 | uus binaarkood:01000
Vaata ka
Välislingid
Pildid, videod ja helifailid Commonsis: Huffmani kodeerimine |
- Program for explaining the Huffman Coding procedure.
- Huffman Code Applet
- n-ary Huffman Template Algorithm
- Sloane A098950 Minimizing k-ordered sequences of maximum height Huffman tree
- Computing Huffman codes on a Turing Machine
- Mordecai J. Golin, Claire Kenyon, Neal E. Young "Huffman coding with unequal letter costs" (PDF), STOC 2002: 785-791
- Huffman Coding: A CS2 Assignment a good introduction to Huffman coding
- A quick tutorial on generating a Huffman tree
- Pointers to Huffman coding visualizations
- Huffman in C
- Huffman in Java
- Huffman binary algorithm applet
- Implementation approaches to Huffman Decoding