Mine sisu juurde

Huffmani kodeerimine: erinevus redaktsioonide vahel

Allikas: Vikipeedia
Sirvi ajalugu interaktiivselt
← Vanem muudatus
Eemaldatud sisu Lisatud sisu
VisuaalneVikitekst
M2s17 (arutelu | kaastöö)
1725 muudatust
Monoglott (arutelu | kaastöö)
173 muudatust
Resümee puudub
 
(ei näidata 20 kasutaja 41 vahepealset redaktsiooni)
1. rida: 1. rida:
[[Pilt:Huffman tree 2.svg|thumb|350px|Huffmani puu, mis on genereeritud järgnevast tekstist jutumärkides: "this is an example of a huffman tree". Lehtede puhul on kuvatud esinemissagedus ja tähemärk, varte puhul vaid esinemistihedus. Kodeeritud teksti kogumaht oleks 135 bitti ehk vähem kui 17 tähemärki, arvestamata puu kirjeldamiseks vajaliku ruumi. Teksti algne pikkus on 36 tähemärki]]
{{keeletoimeta}}
'''Huffmani kodeerimine''' on [[prefikskood]]ide üks liik. Huffmani kodeerimise idee on asendada olemasolev sümboleid kirjeldav [[bitt|bitijada]] ümber nõnda, et [[informatsioon]]i hulgas tihemini esinevad tähemärgid saaksid kirjeldatud lühema bitijadaga. Tulemuseks on informatsiooni kirjeldus esinemistihedust eelistaval ja minimaalset tähemärkide hulka kasutaval alusel. Informatsiooni kirjeldav andmehulk ei pruugi väheneda ja võib eriolukorras isegi kasvada, kuid tegemist on tihendusalgoritmiga, mis tavateksti pakkimisel saavutab märgatava erinevuse (tihti üle 30%).
[[Image:Huffman tree 2.svg|right|thumb|350px|Huffman'i puu, mis on genereeritud järgnevast tekstist jutumärkides: "this is an example of a huffman tree". Lehtede puhul on kuvatud esinemissagedus ja tähemärk, varte puhul vaid esinemistihedus. Kodeeritud teksti kogumaht oleks 135 bitt'i ehk vähem kui 17 tähemärki, arvestamata puu kirjeldamiseks vajaliku ruumi. Algne teksti pikkus 36 tähemärki]]
'''Huffmani kodeerimine''' on [[prefikskood]]ide üks liik. Huffmani kodeerimise idee on asendada olemasolev sümboleid kirjeldav [[bitt|bitijada]], ümber nõnda, et [[informatsioon]]i 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%'i).


== Algoritmi implementeerimisest ==
== Algoritmi rakendamine ==
Huffmani kodeerimis[[algoritm]] põhineb konkreetse informatsiooni tähemärkide sageduse põhjal binaarpuu ehitamisel ja sellest tähemärkide bitijada kirjeldava kodeerimistabeli loomisel.
Huffmani kodeerimis[[algoritm]] põhineb konkreetse informatsiooni tähemärkide sageduse põhjal binaarpuu ehitamisel ja sellest tähemärkide bitijada kirjeldava kodeerimistabeli loomisel. Faili tihendamise puhul kirjeldatakse väljundfaili puud ja algse sisendfaili sisu. Tähemärgid asendatakse uue kodeeringuga.

Otsese informatsiooni sisaldava faili tihendamisel on mõned lahendamist vajavad kitsaskohad. Näiteks tuleb teha väljundfaili lõpu tuvastus, sest tõenäoliselt ei lõpe fail [[bait|baidi]] pealt, vaid selles on mõne[[bitt|bitine]] ülejääk.


=== Binaarpuu rakendamiseks kasutatav struktuur ===
=== Binaarpuu rakendamiseks kasutatav struktuur ===
{{peidetud
{{Peida
|pealkiri =[[C_(programmeerimiskeel)|Programmeerimskeel C]]
|päis = [[C (programmeerimiskeel)|Programmeerimskeel C]]
|css = border:1px solid #aaa;
|sisu =
|sisu =
<source lang="c">
<syntaxhighlight lang="c">
//tüüpiline struktuur programmeerimskeeles C, mida kasutada binaarpuu ehitamisel
//tüüpiline struktuur programmeerimskeeles C, mida kasutada binaarpuu ehitamisel
typedef struct tree {
typedef struct tree {
int ch; //tähemärgi numbriline kood
int ch; //tähemärgi numbriline kood
int freq; //informatsioonis esinemise tihedus
int freq; //informatsioonis esinemise tihedus
struct tree *left; //viide samat tüüpi struktuurile
struct tree *left; //viide sama tüüpi struktuurile
struct tree *right; //2 viide samat tüüpi struktuurile
struct tree *right; //2 viide sama tüüpi struktuurile
} tree;
} tree;
</syntaxhighlight>
</source>
}}
}}
{{Peida
|pealkiri =[[Java]]
|sisu =
<source lang="java">
import java.util.Collection;


=== Puu ehitamisel kasutatavad mõisted ===
/**
*'''Leht''' – element, mille tähemärgi numbrikood on määratud positiivselt, harud jäävad ühendamata (tal pole neid).
* tüüpiline klass Java's, mida kasutada objektipõhise binaarpuu ehitamisel
*'''Vars''' – element, mille tähemärgi numbrikood on vaid algväärtustatud, harud on väärtustatud, esinemistihedus on varre harudes olevate elementide esinemistiheduse summa.
*/
*'''Juur''' – element, mille harusid pidi võib jõuda kõigi lehtedeni.
public class tree implements Comparable<tree> {
*'''Haru''' – elemendi viide sama tüüpi elemendile.
private tree left;
private tree right;
private int ch;
private int freq;


=== Puu ehitamise [[algoritm]] ===
/**
# Luuakse lehtede [[Massiiv (programmeerimine)|massiiv]], milles on tähemärgid ja nende esinemissagedused.
* tüüpiline konstruktor lehtede loomiseks
# Massiiv [[Sortimisalgoritm|sorditakse]] esinemissageduse alusel.
*
# Luuakse uus vars, mille harud ühendatakse kahe väiksema esinemissagedusega elemendiga massiivis.
* @param ch
# Massiivi lisatakse vars ja eemaldatakse selle harudes asetsevad elemendid.
* tähemärk
# Lisatud varre esinemissageduseks määratakse selle harudes olevate elementide summa.
* @param freq
# Kui massiivis on järgi vaid üks element, on puu valmis, kui mitte, korratakse algoritmi alates punktist 2.
* esinemise tihedus
*/
public tree(int ch, int freq) {
this.ch = ch;
this.freq = freq;
}


=== Kodeerimistabeli loomise [[Algoritm#Rekrusiivne_algoritm|rekursiivne algoritm]] ===
/**
# Saadakse viit puu juurele.
* /** tüüpiline konstruktor varte loomiseks
# Kui tegemist on lehega, lisatakse kodeerimistabelisse loodud kood ja koodi pikkus.
*
# Kui varrel on vasakpoolne (esimene) haru olemas, pikendatakse koodi ja pöördutakse punkti 1.
* @param left
# Kui varrel on parempoolne (teine) haru olemas, määratakse koodi viimane bitt 1ks, pikendatakse koodi ja pöördutakse punkti 1.
* viide esimesele harule
* @param right
* viide teisele harule
* @param forest
* viide struktuurile, milles antud klasse hoitakse
*/
public tree(tree left, tree right, Collection<tree> forest) {
this.left = left;
this.right = right;
this.freq = left.freq + right.freq;


Tõenäoliselt pole raske iteratiivset algoritmi luua, kuid seda pole vaja, sest tähed on üldjuhul kirjeldatud 8 bitiga, mille kõigi kombinatsioonide hulk on 256.
forest.add(this);
forest.remove(left);
forest.remove(right);
}

/**
* meetod klassi informatsiooni kuvamiseks
*/
public String toString() {
return "ch:" + this.ch + "\tfreq:" + this.ch;
}

public tree getLeft() {
return this.left;
}

public void setLeft(tree left) {
this.left = left;
}

public tree getRight() {
return this.right;
}

public void setRight(tree right) {
this.right = right;
}

public int getCh() {
return this.ch;
}

public void setCh(int ch) {
this.ch = ch;
}

public int getFreq() {
return this.freq;
}

public void setFreq(int freq) {
this.freq = freq;
}

/*
* Meetod, mis võimaldab tree tüüpi elementide kollektsiooni sortimise
*
* @see java.lang.Comparable#compareTo(java.lang.Object)
*/
@Override
public int compareTo(tree o) {
try {
if (o == null) return -1;

return o.getFreq() - this.getFreq();
} catch (Exception e) {
return 0;
}

}
}
</source>
}}

=== Puu ehitamisel kasutatakse mõisteid ===
*'''leht''' - struktuur, mille tähemärgi numbriline kood on määratud positiivselt, harud jäävad ühendamata (tal pole neid)
*'''vars''' - struktuur, mille tähemärgi numbriline kood on vaid algväärtustatud, struktuuri viited on määratud, esinemistihedus on temast otseselt järgnevalt harude varte/lehtede esinemistiheduse summa
*'''juur''' - struktuur, mille harusid pidi võib jõuda kõigi lehtedeni,

=== 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 2 pisiksema esinemise sagedust omava 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 1 element, on puu valmis, kui mitte korratakse punkte alates 2'est

=== Kodeerimistabeli loomise rekursiivne algoritm ===
# Saadake 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 1'eks, 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 bitt'iga mille kogu kombinatsioonide hulk on 256.


=== Kodeerimistabeli näide ===
=== Kodeerimistabeli näide ===
Kodeerimistabeli element koosneb vormist ja pikkusest, ning kõik elemendid saavad pärast seda algoritmi määratud unikaalsete bitt'ijadadega. 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 puu näide toodud.
Kodeerimistabeli element koosneb vormist ja pikkusest ning kõik elemendid saavad pärast seda algoritmi määratud unikaalsete bitijadadega. Allpool on tabel eelneva ja uue kodeeringu erinevustest. Kodeerimistabeli informatsiooniks on sõne "this is an example of a huffman tree".


Kodeerimistabel:
Kodeerimistabel:
171. rida: 68. rida:
==Vaata ka==
==Vaata ka==
*[[Andmete pakkimine]]
*[[Andmete pakkimine]]
*[[LZ77]]
*[[Lempel-Ziv-Welch]]
*[[ASCII]]


==Välislingid==
{{Commons|Category:Huffman coding|Huffmani kodeerimine}}
* [http://www.huffmancoding.com/david/algorithm.html Program for explaining the Huffman Coding procedure.]
* [http://www.cs.sfu.ca/cs/CC/365/li/squeeze Huffman Code Applet]
* [http://alexvn.freeservers.com/s1/huffman_template_algorithm.html n-ary Huffman Template Algorithm]
* [http://www.research.att.com/projects/OEIS?Anum=A098950 Sloane A098950] Minimizing k-ordered sequences of maximum height Huffman tree
* [http://semillon.wpi.edu/~aofa/AofA/msg00040.html Computing Huffman codes on a Turing Machine]
* Mordecai J. Golin, Claire Kenyon, Neal E. Young "[http://www.cs.ust.hk/faculty/golin/pubs/LOP_PTAS_STOC.pdf Huffman coding with unequal letter costs]" (PDF), [http://www.informatik.uni-trier.de/~ley/db/conf/stoc/stoc2002.html STOC 2002]: 785-791
* [http://www.cs.duke.edu/csed/poop/huff/info/ Huffman Coding: A CS2 Assignment] a good introduction to Huffman coding
* [http://www.siggraph.org/education/materials/HyperGraph/video/mpeg/mpegfaq/huffman_tutorial.html A quick tutorial on generating a Huffman tree]
* Pointers to [http://web-cat.cs.vt.edu/AlgovizWiki/HuffmanCodingTrees Huffman coding visualizations]
* [http://huffman.sourceforge.net Huffman in C]
* [http://apollonic.net/code/ Huffman in Java]
* [http://www.informationsuebertragung.ch/indexAlgorithmen.html Huffman binary algorithm applet]
* [http://www.wipro.com/pdf_files/Huffman_Decoding.pdf Implementation approaches to Huffman Decoding]


[[Kategooria:Algoritm]]
[[Kategooria:Algoritmid]]
[[Kategooria:Informaatika]]
[[Kategooria:Programmeerimine]]

[[ar:ترميز هوفمان]]
[[cs:Huffmanovo kódování]]
[[de:Shannon-Fano-Kodierung#Huffman-Code]]
[[el:Κωδικοποίηση Huffman]]
[[en:Huffman coding]]
[[es:Codificación Huffman]]
[[fa:کد‌گذاری هافمن]]
[[fr:Codage de Huffman]]
[[ko:허프만 부호화]]
[[it:Codifica di Huffman]]
[[he:קוד הופמן]]
[[nl:Huffmancodering]]
[[ja:ハフマン符号]]
[[pl:Kodowanie Huffmana]]
[[pt:Codificação de Huffman]]
[[ru:Алгоритм Хаффмана]]
[[fi:Huffmanin koodaus]]
[[sv:Huffmankodning]]
[[th:รหัสฮัฟแมน และ รหัสแชนนอน-ฟาโน]]
[[vi:Mã Huffman]]
[[tr:Huffman kodu]]
[[zh:霍夫曼编码]]

Viimane redaktsioon: 28. jaanuar 2023, kell 20:12

Huffmani puu, mis on genereeritud järgnevast tekstist jutumärkides: "this is an example of a huffman tree". Lehtede puhul on kuvatud esinemissagedus ja tähemärk, varte puhul vaid esinemistihedus. Kodeeritud teksti kogumaht oleks 135 bitti ehk vähem kui 17 tähemärki, arvestamata puu kirjeldamiseks vajaliku ruumi. Teksti algne pikkus on 36 tähemärki

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. Tulemuseks on informatsiooni kirjeldus esinemistihedust eelistaval ja minimaalset tähemärkide hulka kasutaval alusel. Informatsiooni kirjeldav andmehulk ei pruugi väheneda ja võib eriolukorras isegi kasvada, kuid tegemist on tihendusalgoritmiga, mis tavateksti pakkimisel saavutab märgatava erinevuse (tihti üle 30%).

Algoritmi rakendamine

[muuda | muuda lähteteksti]

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 kirjeldatakse väljundfaili puud ja algse sisendfaili sisu. Tähemärgid asendatakse uue kodeeringuga.

Otsese informatsiooni sisaldava faili tihendamisel on mõned lahendamist vajavad kitsaskohad. Näiteks tuleb teha väljundfaili lõpu tuvastus, sest tõenäoliselt ei lõpe fail baidi pealt, vaid selles on mõnebitine ülejääk.

Binaarpuu rakendamiseks kasutatav struktuur

[muuda | muuda lähteteksti]
//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õisted

[muuda | muuda lähteteksti]
  • Leht – element, mille tähemärgi numbrikood on määratud positiivselt, harud jäävad ühendamata (tal pole neid).
  • Vars – element, mille tähemärgi numbrikood on vaid algväärtustatud, harud on väärtustatud, esinemistihedus on varre 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

[muuda | muuda lähteteksti]
  1. Luuakse lehtede massiiv, milles on tähemärgid ja nende esinemissagedused.
  2. Massiiv sorditakse esinemissageduse alusel.
  3. Luuakse uus vars, mille harud ühendatakse kahe väiksema esinemissagedusega elemendiga massiivis.
  4. Massiivi lisatakse vars ja eemaldatakse selle harudes asetsevad elemendid.
  5. Lisatud varre esinemissageduseks määratakse selle harudes olevate elementide summa.
  6. Kui massiivis on järgi vaid üks element, on puu valmis, kui mitte, korratakse algoritmi alates punktist 2.

Kodeerimistabeli loomise rekursiivne algoritm

[muuda | muuda lähteteksti]
  1. Saadakse viit puu juurele.
  2. Kui tegemist on lehega, lisatakse kodeerimistabelisse loodud kood ja koodi pikkus.
  3. Kui varrel on vasakpoolne (esimene) haru olemas, pikendatakse koodi ja pöördutakse punkti 1.
  4. Kui varrel on parempoolne (teine) haru olemas, määratakse koodi viimane bitt 1ks, pikendatakse koodi ja pöördutakse punkti 1.

Tõenäoliselt pole raske iteratiivset algoritmi luua, kuid seda pole vaja, sest tähed on üldjuhul kirjeldatud 8 bitiga, mille kõigi kombinatsioonide hulk on 256.

Kodeerimistabeli näide

[muuda | muuda lähteteksti]

Kodeerimistabeli element koosneb vormist ja pikkusest ning kõik elemendid saavad pärast seda algoritmi määratud unikaalsete bitijadadega. Allpool on tabel eelneva ja uue kodeeringu erinevustest. Kodeerimistabeli informatsiooniks on sõne "this is an example of a huffman tree". 

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

[muuda | muuda lähteteksti]

Välislingid

[muuda | muuda lähteteksti]
Pärit leheküljelt "https://et.wikipedia.org/w/index.php?title=Huffmani_kodeerimine&oldid=6308501"