A Huffman kódolási algoritmust javasolta David A. Huffman 1950-ben. Ez a veszteségmentes adattömörítés gépezet. Úgy is ismert, mint adattömörítési kódolás. Széles körben használják képtömörítésben (JPEG vagy JPG). Ebben a részben a Huffman kódolás és dekódolás, és annak algoritmusát is implementálja egy Java programban.

Tudjuk, hogy minden karakter 0-ból és 1-ből álló sorozat, és 8 bitet használ. A mechanizmus az ún fix hosszúságú kódolás mert minden karakter ugyanannyi fix bites tárhelyet használ.

string.formátum java-ban

Itt felvetődik egy kérdés, lehet csökkenteni a karakter tárolásához szükséges helyet?

Igen, használatával lehetséges változó hosszúságú kódolás. Ebben a mechanizmusban kihasználunk néhány olyan karaktert, amelyek gyakrabban fordulnak elő más karakterekhez képest. Ennél a kódolási technikánál a bitek számának csökkentésével ugyanazt a szövegrészt vagy karakterláncot ábrázolhatjuk.

Huffman kódolás

A Huffman-kódolás a következő lépéseket hajtja végre.

• Az összes megadott karakterhez változó hosszúságú kódot rendel.
• Egy karakter kód hossza attól függ, hogy milyen gyakran fordul elő az adott szövegben vagy karakterláncban.
• Egy karakter akkor kapja meg a legkisebb kódot, ha gyakran előfordul.
• Egy karakter akkor kapja a legnagyobb kódot, ha a legkevésbé fordul elő.

A Huffman kódolás követi a előtag szabály amely megakadályozza a kétértelműséget a dekódolás során. A szabály azt is biztosítja, hogy a karakterhez rendelt kód ne legyen más karakterhez rendelt kód előtagjaként kezelve.

A Huffman-kódolásnak a következő két fő lépése van:

• Először készítsünk a Huffman fa a megadott beviteli karakterláncból vagy karakterekből vagy szövegből.
• Minden karakterhez rendeljen egy Huffman-kódot a fán való áthaladással.

Foglaljuk össze röviden a fenti két lépést.

Huffman fa

1. lépés: A csomópont minden karakteréhez hozzon létre egy levél csomópontot. Egy karakter levélcsomópontja tartalmazza az adott karakter gyakoriságát.

2. lépés: Állítsa be az összes csomópontot gyakoriságuk szerint rendezett sorrendbe.

3. lépés: Előfordulhat olyan állapot, amelyben két csomópont azonos frekvenciájú. Ilyen esetben tegye a következőket:

1. Hozzon létre egy új belső csomópontot.
2. A csomópont frekvenciája az azonos frekvenciájú két csomópont frekvenciájának összege lesz.
3. Jelölje meg az első csomópontot az újonnan létrehozott belső csomópont bal gyermekeként, egy másik csomópontot pedig jobb gyermekeként.

4. lépés: Ismételje meg a 2. és 3. lépést, amíg az összes csomópont egyetlen fát nem alkot. Így kapunk egy Huffman fát.

államok listája

Huffman kódolási példa

Tegyük fel, hogy kódolnunk kell egy karakterláncot Abra Cadabra. Határozza meg a következőket:

1. Huffman kód az összes karakterhez
2. Átlagos kódhossz az adott karakterlánchoz
3. A kódolt karakterlánc hossza

(i) Huffman kód az összes karakterhez

Az egyes karakterek kódjának meghatározásához először összeállítjuk a Huffman fa.

1. lépés: Készíts pár karaktert és azok gyakoriságát.

(a, 5), (b, 2), (c, 1), (d, 1), (r, 2)

2. lépés: A párokat gyakoriság szerint rendezve kapjuk:

(c, 1), (d, 1), (b, 2) (r, 2), (a, 5)

3. lépés: Válassza ki az első két karaktert, és csatlakoztassa őket egy szülőcsomópont alá.

Megfigyeljük, hogy egy szülőcsomópontnak nincs frekvenciája, ezért frekvenciát kell hozzá rendelnünk. A szülőcsomópont-frekvencia a gyermekcsomópontok (bal és jobb) összege lesz, azaz 1+1= 2.

4. lépés: Ismételje meg a 2. és 3. lépést, amíg egyetlen fát nem kapunk.

Megfigyeljük, hogy a párok már rendezve vannak (2. lépés szerint). Ismét válassza ki az első két párt, és csatlakozzon hozzájuk.

Megfigyeljük, hogy egy szülőcsomópontnak nincs frekvenciája, ezért frekvenciát kell hozzá rendelnünk. A szülőcsomópont frekvenciája a gyermekcsomópontok (bal és jobb) összege lesz, azaz 2+2= 4.

Ismét ellenőrizzük, hogy a párok rendezettek-e vagy sem. Ebben a lépésben rendeznünk kell a párokat.

A 3. lépés szerint válassza ki az első két párt, és csatlakoztassa őket, így kapjuk:

Megfigyeljük, hogy egy szülőcsomópontnak nincs frekvenciája, ezért frekvenciát kell hozzá rendelnünk. A szülőcsomópont-frekvencia a gyermek csomópontjainak (bal és jobb) összege lesz, azaz 2+4= 6.

tömb karakterlánca c

Ismét ellenőrizzük, hogy a párok rendezettek-e vagy sem. Ebben a lépésben rendeznünk kell a párokat. A fa válogatás után a következőképpen néz ki:

A 3. lépés szerint válassza ki az első két párt, és csatlakoztassa őket, így kapjuk:

Sridevi

Megfigyeljük, hogy egy szülőcsomópontnak nincs frekvenciája, ezért frekvenciát kell hozzá rendelnünk. A szülőcsomópont-frekvencia a gyermekcsomópontok (bal és jobb) összege lesz, azaz 5+6= tizenegy.

Ezért egyetlen fát kapunk.

Végül minden karakterhez megtaláljuk a kódot a fenti fa segítségével. Minden élhez rendeljen súlyt. Vegye figyelembe, hogy mindegyik A bal éllel súlyozott 0 és a a jobb éllel súlyozott 1.

Megfigyeltük, hogy a bemeneti karakterek csak a kilépő csomópontokban jelennek meg, és a belső csomópontok null értékkel rendelkeznek. Annak érdekében, hogy minden karakterhez megtaláljuk a Huffman-kódot, menjünk át a Huffman-fán a gyökércsomóponttól annak a karakternek a levélcsomópontjáig, amelynek kódját szeretnénk megtalálni. A táblázat leírja az egyes karakterek kódját és kódhosszát.

Megfigyeltük, hogy a leggyakrabban előforduló karakter kapja a legrövidebb kódot, és a ritkább karakter a legnagyobb kódhosszt.

Most már kódolhatjuk a karakterláncot (Abra Cadabra) amit fentebb vettünk.

 0 111 10 0 1100 0 1101 0 111 10 0 

(ii) A karakterlánc átlagos kódhossza

A Huffman-fa átlagos kódhossza az alábbi képlettel határozható meg:

 Average Code Length = ∑ ( frequency × code length ) / ∑ ( frequency ) 

= { (5 x 1) + (2 x 3) + (1 x 4) + (1 x 4) + (2 x 2) } / (5+2+1+1+2)

= 2,09090909

(iii) A kódolt karakterlánc hossza

A kódolt üzenet hossza a következő képlettel határozható meg:

 length= Total number of characters in the text x Average code length per character 

= 11 x 2,09090909

= 23 bit

Huffman kódolási algoritmus

 Huffman (C) n=|C| Q=C for i=1 to n-1 do z=allocate_Node() x=left[z]=Extract_Min(Q) y=right[z]=Extract_Min(Q) f[z]=f[x]+f[y] Insert(Q,z) return Extract_Min(Q) 

A Huffman-algoritmus egy mohó algoritmus. Mivel az algoritmus minden szakaszban a legjobb elérhető lehetőségeket keresi.

A Huffman-kódolás időbeli összetettsége az O(nlogn). Ahol n a karakterek száma az adott szövegben.

Huffman dekódolás

A Huffman-dekódolás egy olyan technika, amely a kódolt adatokat kezdeti adatokká alakítja. Ahogy a kódolásnál láttuk, a Huffman-fa egy bemeneti karakterlánchoz készült, és a karakterek dekódolása a fában elfoglalt helyük alapján történik. A dekódolási folyamat a következő:

karakterláncban tartalmazza

• Kezdje el áthaladni a fán a gyökér csomópontot, és keresse meg a karaktert.
• Ha balra mozgunk a bináris fában, adjuk hozzá 0 a kódhoz.
• Ha jobbra mozgunk a bináris fában, adjuk hozzá 1 a kódhoz.

A gyermek csomópont tartalmazza a bemeneti karaktert. A kódot a következő 0-k és 1-ek alkotják. Egy karakterlánc dekódolásának időbonyolultsága az Tovább), ahol n a karakterlánc hossza.

Huffman kódoló és dekódoló Java program

A következő programban adatstruktúrákat, például prioritási sorokat, veremeket és fákat használtunk a tömörítési és kitömörítési logika megtervezéséhez. Segédprogramjainkat a Huffman kódolás széles körben használt algoritmikus technikájára alapozzuk.

HuffmanCode.java

 import java.util.Comparator; import java.util.HashMap; import java.util.Map; import java.util.PriorityQueue; //defining a class that creates nodes of the tree class Node { //storing character in ch variable of type character Character ch; //storing frequency in freq variable of type int Integer freq; //initially both child (left and right) are null Node left = null; Node right = null; //creating a constructor of the Node class Node(Character ch, Integer freq) { this.ch = ch; this.freq = freq; } //creating a constructor of the Node class public Node(Character ch, Integer freq, Node left, Node right) { this.ch = ch; this.freq = freq; this.left = left; this.right = right; } } //main class public class HuffmanCode { //function to build Huffman tree public static void createHuffmanTree(String text) { //base case: if user does not provides string if (text == null || text.length() == 0) { return; } //count the frequency of appearance of each character and store it in a map //creating an instance of the Map Map freq = new HashMap(); //loop iterates over the string and converts the text into character array for (char c: text.toCharArray()) { //storing character and their frequency into Map by invoking the put() method freq.put(c, freq.getOrDefault(c, 0) + 1); } //create a priority queue that stores current nodes of the Huffman tree. //here a point to note that the highest priority means the lowest frequency PriorityQueue pq = new PriorityQueue(Comparator.comparingInt(l -&gt; l.freq)); //loop iterate over the Map and returns a Set view of the mappings contained in this Map for (var entry: freq.entrySet()) { //creates a leaf node and add it to the queue pq.add(new Node(entry.getKey(), entry.getValue())); } //while loop runs until there is more than one node in the queue while (pq.size() != 1) { //removing the nodes having the highest priority (the lowest frequency) from the queue Node left = pq.poll(); Node right = pq.poll(); //create a new internal node with these two nodes as children and with a frequency equal to the sum of both nodes&apos; frequencies. Add the new node to the priority queue. //sum up the frequency of the nodes (left and right) that we have deleted int sum = left.freq + right.freq; //adding a new internal node (deleted nodes i.e. right and left) to the queue with a frequency that is equal to the sum of both nodes pq.add(new Node(null, sum, left, right)); } //root stores pointer to the root of Huffman Tree Node root = pq.peek(); //trace over the Huffman tree and store the Huffman codes in a map Map huffmanCode = new HashMap(); encodeData(root, &apos;&apos;, huffmanCode); //print the Huffman codes for the characters System.out.println(&apos;Huffman Codes of the characters are: &apos; + huffmanCode); //prints the initial data System.out.println(&apos;The initial string is: &apos; + text); //creating an instance of the StringBuilder class StringBuilder sb = new StringBuilder(); //loop iterate over the character array for (char c: text.toCharArray()) { //prints encoded string by getting characters sb.append(huffmanCode.get(c)); } System.out.println(&apos;The encoded string is: &apos; + sb); System.out.print(&apos;The decoded string is: &apos;); if (isLeaf(root)) { //special case: For input like a, aa, aaa, etc. while (root.freq-- &gt; 0) { System.out.print(root.ch); } } else { //traverse over the Huffman tree again and this time, decode the encoded string int index = -1; while (index <sb.length() - 1) { index="decodeData(root," index, sb); } traverse the huffman tree and store codes in a map function that encodes data public static void encodedata(node root, string str, huffmancode) if (root="=" null) return; checks node is leaf or not (isleaf(root)) huffmancode.put(root.ch, str.length()> 0 ? str : &apos;1&apos;); } encodeData(root.left, str + &apos;0&apos;, huffmanCode); encodeData(root.right, str + &apos;1&apos;, huffmanCode); } //traverse the Huffman Tree and decode the encoded string function that decodes the encoded data public static int decodeData(Node root, int index, StringBuilder sb) { //checks if the root node is null or not if (root == null) { return index; } //checks if the node is a leaf node or not if (isLeaf(root)) { System.out.print(root.ch); return index; } index++; root = (sb.charAt(index) == &apos;0&apos;) ? root.left : root.right; index = decodeData(root, index, sb); return index; } //function to check if the Huffman Tree contains a single node public static boolean isLeaf(Node root) { //returns true if both conditions return ture return root.left == null &amp;&amp; root.right == null; } //driver code public static void main(String args[]) { String text = &apos;javatpoint&apos;; //function calling createHuffmanTree(text); } } </sb.length()>

Kimenet:

 Huffman Codes of the characters are: {p=000, a=110, t=111, v=001, i=010, j=011, n=100, o=101} The initial string is: javatpoint The encoded string is: 011110001110111000101010100111 The decoded string is: javatpoint