Algorytm kodowania Huffmana został zaproponowany przez Davida A. Huffmana w 1950 r. Jest to bezstratna kompresja danych mechanizm. Znany jest również jako kodowanie kompresji danych. Jest szeroko stosowany w kompresji obrazu (JPEG lub JPG). W tej części omówimy Kodowanie Huffmana I rozszyfrowanie, a także zaimplementować jego algorytm w programie Java.

Wiemy, że każdy znak jest sekwencją zer i jedynek i jest zapisywany przy użyciu 8 bitów. Mechanizm nazywa się kodowanie o stałej długości ponieważ każdy znak wykorzystuje tę samą liczbę bitów pamięci.

importuj skaner Java

Tutaj nasuwa się pytanie, czy można zmniejszyć ilość miejsca potrzebnego do przechowywania postaci?

Tak, jest to możliwe za pomocą kodowanie o zmiennej długości. W tym mechanizmie wykorzystujemy niektóre postacie, które występują częściej w porównaniu do innych postaci. W tej technice kodowania możemy przedstawić ten sam fragment tekstu lub ciąg znaków, zmniejszając liczbę bitów.

Kodowanie Huffmana

Kodowanie Huffmana obejmuje następujące kroki.

• Przypisuje kod o zmiennej długości do wszystkich podanych znaków.
• Długość kodu znaku zależy od tego, jak często występuje on w danym tekście lub ciągu znaków.
• Postać otrzymuje najmniejszy kod, jeśli zdarza się to często.
• Postać otrzymuje największy kod, jeśli występuje najmniej.

Kodowanie Huffmana następuje a reguła przedrostka co zapobiega dwuznaczności podczas dekodowania. Reguła zapewnia również, że kod przypisany do znaku nie będzie traktowany jako przedrostek kodu przypisanego do innego znaku.

Kodowanie Huffmana składa się z dwóch głównych etapów:

• Najpierw skonstruuj a Drzewo Huffmana z podanego ciągu wejściowego, znaków lub tekstu.
• Przypisz kod Huffmana do każdej postaci, przechodząc przez drzewo.

Krótko opiszmy powyższe dwa kroki.

Drzewo Huffmana

Krok 1: Dla każdego znaku węzła utwórz węzeł liścia. Węzeł liścia znaku zawiera częstotliwość tego znaku.

Krok 2: Ustaw wszystkie węzły w kolejności posortowanej według ich częstotliwości.

pobierz autocad 2019 angielski mediafire

Krok 3: Może zaistnieć sytuacja, w której dwa węzły mogą mieć tę samą częstotliwość. W takim przypadku wykonaj następujące czynności:

1. Utwórz nowy węzeł wewnętrzny.
2. Częstotliwość węzła będzie sumą częstotliwości tych dwóch węzłów, które mają tę samą częstotliwość.
3. Oznacz pierwszy węzeł jako lewy potomek, a drugi węzeł jako prawy potomek nowo utworzonego węzła wewnętrznego.

Krok 4: Powtarzaj kroki 2 i 3, aż cały węzeł utworzy jedno drzewo. W ten sposób otrzymujemy drzewo Huffmana.

Przykład kodowania Huffmana

Załóżmy, że musimy zakodować ciąg Abra Cadabra. Ustal co następuje:

1. Kod Huffmana dla wszystkich znaków
2. Średnia długość kodu dla danego ciągu
3. Długość zakodowanego ciągu

(i) Kod Huffmana dla wszystkich znaków

Aby określić kod dla każdego znaku, najpierw konstruujemy a Drzewo Huffmana.

Krok 1: Utwórz pary znaków i ich częstotliwości.

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

Krok 2: Sortując pary ze względu na częstotliwość otrzymujemy:

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

Krok 3: Wybierz pierwsze dwa znaki i połącz je pod węzłem nadrzędnym.

Zauważamy, że węzeł nadrzędny nie ma częstotliwości, więc musimy mu przypisać częstotliwość. Częstotliwość węzła nadrzędnego będzie sumą jego węzłów podrzędnych (lewego i prawego), tj. 1+1= 2.

pusta lista java

Krok 4: Powtarzaj kroki 2 i 3, aż otrzymamy pojedyncze drzewo.

Obserwujemy, że pary są już posortowane (według kroku 2). Ponownie wybierz dwie pierwsze pary i dołącz do nich.

Zauważamy, że węzeł nadrzędny nie ma częstotliwości, więc musimy mu przypisać częstotliwość. Częstotliwość węzła nadrzędnego będzie sumą jego węzłów podrzędnych (lewego i prawego), tj. 2+2= 4.

Ponownie sprawdzamy, czy pary są posortowane, czy nie. Na tym etapie musimy posortować pary.

Zgodnie z krokiem 3, wybierz dwie pierwsze pary i połącz je, otrzymamy:

Zauważamy, że węzeł nadrzędny nie ma częstotliwości, więc musimy mu przypisać częstotliwość. Częstotliwość węzła nadrzędnego będzie sumą jego węzłów podrzędnych (lewego i prawego), tj. 2+4= 6.

Ponownie sprawdzamy, czy pary są posortowane, czy nie. Na tym etapie musimy posortować pary. Po posortowaniu drzewo wygląda następująco:

Zgodnie z krokiem 3, wybierz dwie pierwsze pary i połącz je, otrzymamy:

Zauważamy, że węzeł nadrzędny nie ma częstotliwości, więc musimy mu przypisać częstotliwość. Częstotliwość węzła nadrzędnego będzie sumą jego węzłów podrzędnych (lewego i prawego), tj. 5+6= jedenaście.

Dlatego otrzymujemy jedno drzewo.

W końcu znajdziemy kod dla każdego znaku za pomocą powyższego drzewa. Przypisz wagę do każdej krawędzi. Pamiętaj, że każdy ważona lewą krawędzią wynosi 0 i ważona prawą krawędzią wynosi 1.

Zauważamy, że znaki wejściowe są prezentowane tylko w węzłach opuszczających, a węzły wewnętrzne mają wartości null. Aby znaleźć kod Huffmana dla każdego znaku, przejdź przez drzewo Huffmana od węzła głównego do węzła liścia tego konkretnego znaku, dla którego chcemy znaleźć kod. Tabela opisuje kod i długość kodu dla każdego znaku.

Obserwujemy, że najczęstszy znak otrzymuje najkrótszą długość kodu, a rzadszy znak – największą długość kodu.

dopełnianie CSS

Teraz możemy zakodować ciąg (Abra Kadabra) które podjęliśmy powyżej.

 0 111 10 0 1100 0 1101 0 111 10 0 

(ii) Średnia długość kodu dla ciągu

Średnią długość kodu drzewa Huffmana można wyznaczyć korzystając ze wzoru podanego poniżej:

 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) Długość zakodowanego ciągu

Długość zakodowanej wiadomości można określić korzystając ze wzoru:

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

= 11 x 2,09090909

= 23 bity

Algorytm kodowania Huffmana

 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) 

Algorytm Huffmana jest algorytmem zachłannym. Ponieważ na każdym etapie algorytm szuka najlepszych dostępnych opcji.

Złożoność czasowa kodowania Huffmana wynosi O(nlogn). Gdzie n jest liczbą znaków w podanym tekście.

Dekodowanie Huffmana

Dekodowanie Huffmana to technika konwertująca zakodowane dane na dane początkowe. Jak widzieliśmy podczas kodowania, drzewo Huffmana tworzone jest dla ciągu wejściowego, a znaki są dekodowane na podstawie ich pozycji w drzewie. Proces dekodowania wygląda następująco:

aktorka filmowa Rekha

• Rozpocznij przechodzenie po drzewie od źródło węzeł i wyszukaj znak.
• Jeśli przesuniemy się w lewo w drzewie binarnym, dodaj 0 do kodu.
• Jeśli przejdziemy w prawo w drzewie binarnym, dodaj 1 do kodu.

Węzeł podrzędny przechowuje znak wejściowy. Przypisany jest do niego kod utworzony z kolejnych zer i jedynek. Złożoność czasowa dekodowania ciągu wynosi NA), gdzie n jest długością łańcucha.

Huffman Kodowanie i dekodowanie programu Java

W poniższym programie wykorzystaliśmy struktury danych, takie jak kolejki priorytetowe, stosy i drzewa, do zaprojektowania logiki kompresji i dekompresji. Nasze narzędzia będziemy opierać na szeroko stosowanej technice algorytmicznej kodowania Huffmana.

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()>

Wyjście:

 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