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:
- Hozzon létre egy új belső csomópontot.
- A csomópont frekvenciája az azonos frekvenciájú két csomópont frekvenciájának összege lesz.
- 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:
- Huffman kód az összes karakterhez
- Átlagos kódhossz az adott karakterlánchoz
- 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.
| karakter | Frekvencia | Kód | Kód hossza |
|---|---|---|---|
| A | 5 | 0 | 1 |
| B | 2 | 111 | 3 |
| C | 1 | 1100 | 4 |
| D | 1 | 1101 | 4 |
| R | 2 | 10 | 2 |
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 -> 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' 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, '', huffmanCode); //print the Huffman codes for the characters System.out.println('Huffman Codes of the characters are: ' + huffmanCode); //prints the initial data System.out.println('The initial string is: ' + 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('The encoded string is: ' + sb); System.out.print('The decoded string is: '); if (isLeaf(root)) { //special case: For input like a, aa, aaa, etc. while (root.freq-- > 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 : '1'); } encodeData(root.left, str + '0', huffmanCode); encodeData(root.right, str + '1', 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) == '0') ? 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 && root.right == null; } //driver code public static void main(String args[]) { String text = 'javatpoint'; //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