Huffman Kodlama Algoritması tarafından önerildi David A.Huffman 1950 yılında. kayıpsız veri sıkıştırma mekanizma. Aynı zamanda şu şekilde de bilinir: veri sıkıştırma kodlaması. Görüntü (JPEG veya JPG) sıkıştırmada yaygın olarak kullanılır. Bu bölümde şunları tartışacağız: Huffman kodlaması Ve kod çözme, ve ayrıca algoritmasını bir Java programında uygulayın.
Her karakterin 0 ve 1'lerden oluşan bir dizi olduğunu ve 8 bit kullanarak saklandığını biliyoruz. Mekanizma denir sabit uzunluklu kodlama çünkü her karakter aynı sayıda sabit bit depolama alanı kullanır.
java int'e kadar uzun
Burada bir soru ortaya çıkıyor, bir karakteri saklamak için gereken alan miktarını azaltmak mümkün mü?
Evet, kullanarak mümkündür değişken uzunluklu kodlama Bu mekanizmada diğer karakterlere göre daha sık ortaya çıkan bazı karakterlerden yararlanırız. Bu kodlama tekniğinde aynı metin veya dizi parçasını bit sayısını azaltarak temsil edebiliriz.
Huffman Kodlaması
Huffman kodlaması aşağıdaki adımları uygular.
- Verilen tüm karakterlere değişken uzunlukta bir kod atar.
- Bir karakterin kod uzunluğu, verilen metin veya dizede ne sıklıkta geçtiğine bağlıdır.
- Bir karakter sık sık ortaya çıkıyorsa en küçük kodu alır.
- Bir karakter en az meydana gelirse en büyük kodu alır.
Huffman kodlaması aşağıdaki gibidir: önek kuralı Bu, kod çözme sırasında belirsizliği önler. Kural aynı zamanda karaktere atanan kodun başka bir karaktere atanan kodun öneki olarak değerlendirilmemesini de sağlar.
Huffman kodlamasında aşağıdaki iki önemli adım vardır:
- İlk önce bir inşa edin Huffman ağacı verilen giriş dizesinden veya karakterlerden veya metinden.
- Ağacın üzerinden geçerek her karaktere bir Huffman kodu atayın.
Yukarıdaki iki adımı kısaca özetleyelim.
Huffman Ağacı
Aşama 1: Düğümün her karakteri için bir yaprak düğüm oluşturun. Bir karakterin yaprak düğümü o karakterin frekansını içerir.
Adım 2: Tüm düğümleri frekanslarına göre sıralanmış şekilde ayarlayın.
Aşama 3: İki düğümün aynı frekansa sahip olabileceği bir durum mevcut olabilir. Böyle bir durumda aşağıdakileri yapın:
- Yeni bir dahili düğüm oluşturun.
- Düğümün frekansı, aynı frekansa sahip iki düğümün frekansının toplamı olacaktır.
- İlk düğümü yeni oluşturulan iç düğümün sol çocuğu ve diğer düğümü sağ çocuğu olarak işaretleyin.
Adım 4: Tüm düğümler tek bir ağaç oluşturana kadar 2. ve 3. adımları tekrarlayın. Böylece bir Huffman ağacı elde ederiz.
Huffman Kodlama Örneği
Diyelim ki dizeyi kodlamamız gerekiyor Abra Kadabra. Aşağıdakileri belirleyin:
b artı ağacı
- Tüm karakterler için Huffman kodu
- Verilen Dize için ortalama kod uzunluğu
- Kodlanmış dizenin uzunluğu
(i) Tüm Karakterler için Huffman Kodu
Her karakterin kodunu belirlemek için öncelikle bir kod oluşturuyoruz. Huffmann ağacı.
Aşama 1: Karakter çiftlerini ve sıklıklarını oluşturun.
(a, 5), (b, 2), (c, 1), (d, 1), (r, 2)
Adım 2: Çiftleri frekansa göre sıralarsak şunu elde ederiz:
(c, 1), (d, 1), (b, 2) (r, 2), (a, 5)
Aşama 3: İlk iki karakteri seçin ve onları bir ana düğüm altında birleştirin.
Bir ebeveyn düğümün frekansı olmadığını gözlemliyoruz, bu yüzden ona bir frekans atamamız gerekiyor. Ana düğüm frekansı, alt düğümlerinin (sol ve sağ) toplamı olacaktır, yani 1+1= 2.
java dize birleştirme
Adım 4: Tek bir ağaç elde edene kadar 2. ve 3. Adımları tekrarlayın.
Çiftlerin zaten (2. adıma göre) sıralanmış bir şekilde olduğunu gözlemliyoruz. Yine ilk iki çifti seçin ve onlara katılın.
Bir ebeveyn düğümün frekansı olmadığını gözlemliyoruz, bu yüzden ona bir frekans atamamız gerekiyor. Ana düğüm frekansı, alt düğümlerinin (sol ve sağ) toplamı olacaktır, yani 2+2= 4.
Yine çiftlerin sıralı olup olmadığını kontrol ediyoruz. Bu adımda çiftleri sıralamamız gerekiyor.
3. adıma göre ilk iki çifti seçin ve onlara katılın, şunu elde ederiz:
Bir ebeveyn düğümün frekansı olmadığını gözlemliyoruz, bu yüzden ona bir frekans atamamız gerekiyor. Ana düğüm frekansı, alt düğümlerinin (sol ve sağ) toplamı olacaktır, yani 2+4= 6.
Yine çiftlerin sıralı olup olmadığını kontrol ediyoruz. Bu adımda çiftleri sıralamamız gerekiyor. Ağaç sıralandıktan sonra aşağıdaki gibi görünür:
3. adıma göre ilk iki çifti seçin ve onlara katılın, şunu elde ederiz:
Bir ebeveyn düğümün frekansı olmadığını gözlemliyoruz, bu yüzden ona bir frekans atamamız gerekiyor. Ana düğüm frekansı, alt düğümlerinin (sol ve sağ) toplamı olacaktır, yani 5+6= on bir.
Bu nedenle tek bir ağaç elde ediyoruz.
java tasarım desenleri
En sonunda yukarıdaki ağaç yardımıyla her karakterin kodunu bulacağız. Her kenara bir ağırlık atayın. Her birinin sol kenar ağırlıklı 0 ve sağ kenar ağırlıklı 1'dir.
Giriş karakterlerinin yalnızca izin düğümlerinde sunulduğunu ve iç düğümlerin boş değerlere sahip olduğunu gözlemliyoruz. Her karakterin Huffman kodunu bulmak için, Huffman ağacı üzerinde, kodunu bulmak istediğimiz karakterin kök düğümünden yaprak düğümüne doğru ilerleyin. Tabloda her karakterin kodu ve kod uzunluğu açıklanmaktadır.
| Karakter | Sıklık | Kod | Kod Uzunluğu |
|---|---|---|---|
| A | 5 | 0 | 1 |
| B | 2 | 111 | 3 |
| C | 1 | 1100 | 4 |
| D | 1 | 1101 | 4 |
| R | 2 | 10 | 2 |
En sık kullanılan karakterin en kısa kod uzunluğunu, daha az sıklıkta kullanılan karakterin ise en büyük kod uzunluğunu aldığını gözlemliyoruz.
Artık dizeyi kodlayabiliriz (Abra Kadabra) yukarıda aldık.
0 111 10 0 1100 0 1101 0 111 10 0
(ii) Dizinin Ortalama Kod Uzunluğu
Huffman ağacının ortalama kod uzunluğu aşağıdaki formül kullanılarak belirlenebilir:
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) Kodlanmış Dizinin Uzunluğu
Kodlanmış mesajın uzunluğu aşağıdaki formül kullanılarak belirlenebilir:
length= Total number of characters in the text x Average code length per character
= 11x2,09090909
= 23 bit
Huffman Kodlama Algoritması
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)
Huffman algoritması açgözlü bir algoritmadır. Çünkü her aşamada algoritma mevcut en iyi seçenekleri arar.
Huffman kodlamasının zaman karmaşıklığı O(nlogn). Burada n, verilen metindeki karakter sayısıdır.
Huffman Kod Çözme
Huffman kod çözme, kodlanmış verileri başlangıç verilerine dönüştüren bir tekniktir. Kodlamada gördüğümüz gibi, Huffman ağacı bir giriş dizesi için yapılmıştır ve karakterlerin kodu, ağaçtaki konumlarına göre çözülür. Kod çözme işlemi aşağıdaki gibidir:
Java döngüleri
- Ağacın üzerinden geçmeye başlayın kök düğüme gidin ve karakteri arayın.
- İkili ağaçta sola gidersek şunu ekleriz: 0 koda.
- İkili ağaçta sağa doğru hareket edersek şunu ekleyin: 1 koda.
Alt düğüm giriş karakterini tutar. Sonraki 0 ve 1'lerin oluşturduğu koda atanır. Bir dizenin kodunu çözmenin zaman karmaşıklığı Açık), burada n dizenin uzunluğudur.
Huffman Java Programını Kodlama ve Kod Çözme
Aşağıdaki programda, bir sıkıştırma ve açma mantığı tasarlamak için öncelik kuyrukları, yığınlar ve ağaçlar gibi veri yapılarını kullandık. Yardımcı programlarımızı Huffman kodlamanın yaygın olarak kullanılan algoritmik tekniğine dayandıracağız.
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()> Çıktı:
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