TechCodeview

허프만 코딩 알고리즘은 다음과 같이 제안되었습니다. 데이비드 A. 허프만 1950년에. 무손실 데이터 압축 기구. 그것은 또한로 알려져 있습니다 데이터 압축 인코딩. 이미지(JPEG 또는 JPG) 압축에 널리 사용됩니다. 이 섹션에서는 허프만 인코딩 그리고 디코딩, 또한 Java 프로그램에서 알고리즘을 구현합니다.

우리는 각 문자가 0과 1의 시퀀스이며 8비트를 사용하여 저장한다는 것을 알고 있습니다. 메커니즘이 호출됩니다. 고정 길이 인코딩 각 문자는 동일한 수의 고정 비트 저장소를 사용하기 때문입니다.

BFS 대 DFS

여기서 질문이 하나 올라갑니다. 캐릭터를 저장하는 데 필요한 공간을 줄일 수 있나요?

예, 사용하면 가능하다 가변 길이 인코딩. 이 메커니즘에서는 다른 문자에 비해 더 자주 나타나는 일부 문자를 활용합니다. 이 인코딩 기술에서는 비트 수를 줄여 동일한 텍스트나 문자열을 표현할 수 있습니다.

허프만 인코딩

허프만 인코딩은 다음 단계를 구현합니다.

• 주어진 모든 문자에 가변 길이 코드를 할당합니다.
• 문자의 코드 길이는 해당 텍스트나 문자열에서 해당 문자가 얼마나 자주 나타나는지에 따라 달라집니다.
• 문자가 자주 발생하면 가장 작은 코드를 가져옵니다.
• 문자가 가장 적게 발생하면 가장 큰 코드를 얻습니다.

허프만 코딩은 접두사 규칙 디코딩하는 동안 모호성을 방지합니다. 또한 이 규칙은 해당 문자에 할당된 코드가 다른 문자에 할당된 코드의 접두어로 처리되지 않도록 보장합니다.

허프만 코딩에는 다음과 같은 두 가지 주요 단계가 있습니다.

• 먼저, 허프만 트리 주어진 입력 문자열이나 문자 또는 텍스트에서.
• 트리를 탐색하여 각 문자에 허프만 코드를 할당합니다.

위의 두 단계를 간략히 설명하겠습니다.

허프만 트리

1 단계: 노드의 각 문자에 대해 리프 노드를 만듭니다. 문자의 리프 노드에는 해당 문자의 빈도가 포함됩니다.

2 단계: 모든 노드를 빈도에 따라 정렬된 순서로 설정합니다.

3단계: 두 노드가 동일한 주파수를 가질 수 있는 조건이 존재할 수 있습니다. 그러한 경우에는 다음을 수행하십시오.

1. 새 내부 노드를 만듭니다.
2. 노드의 주파수는 동일한 주파수를 갖는 두 노드의 주파수의 합이 됩니다.
3. 첫 번째 노드를 왼쪽 자식으로 표시하고 다른 노드를 새로 생성된 내부 노드의 오른쪽 자식으로 표시합니다.

4단계: 모든 노드가 단일 트리를 형성할 때까지 2단계와 3단계를 반복합니다. 따라서 우리는 허프만 트리를 얻습니다.

허프만 인코딩 예제

문자열을 인코딩해야 한다고 가정해 보겠습니다. 아브라 카다브라. 다음을 결정합니다.

1. 모든 캐릭터에 대한 허프만 코드
2. 주어진 문자열의 평균 코드 길이
3. 인코딩된 문자열의 길이

(i) 모든 캐릭터에 대한 허프만 코드

각 문자의 코드를 결정하기 위해 먼저 허프만 트리.

1 단계: 문자와 해당 빈도의 쌍을 만듭니다.

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

배열 대 배열 목록

2 단계: 빈도에 따라 쌍을 정렬하면 다음과 같은 결과를 얻습니다.

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

3단계: 처음 두 문자를 선택하고 상위 노드 아래에 결합합니다.

부모 노드에는 빈도가 없으므로 여기에 빈도를 할당해야 합니다. 상위 노드 빈도는 하위 노드(왼쪽 및 오른쪽)의 합입니다. 즉, 1+1= 2.

4단계: 단일 트리를 얻을 때까지 2단계와 3단계를 반복합니다.

우리는 쌍이 이미 (2단계에 따라) 정렬된 방식으로 정렬되어 있음을 관찰합니다. 이번에도 처음 두 쌍을 선택하여 결합하세요.

부모 노드에는 빈도가 없으므로 여기에 빈도를 할당해야 합니다. 상위 노드 빈도는 하위 노드(왼쪽 및 오른쪽)의 합입니다. 즉, 2+2= 4.

sqrt 자바 수학

다시 한번, 쌍이 정렬된 방식으로 되어 있는지 확인합니다. 이 단계에서는 쌍을 정렬해야 합니다.

3단계에 따라 처음 두 쌍을 선택하고 결합하면 다음과 같은 결과를 얻습니다.

부모 노드에는 빈도가 없으므로 여기에 빈도를 할당해야 합니다. 상위 노드 빈도는 하위 노드(왼쪽 및 오른쪽)의 합입니다. 즉, 2+4= 6.

다시 한번, 쌍이 정렬된 방식으로 되어 있는지 확인합니다. 이 단계에서는 쌍을 정렬해야 합니다. 정렬 후 트리는 다음과 같습니다.

3단계에 따라 처음 두 쌍을 선택하고 결합하면 다음과 같은 결과를 얻습니다.

부모 노드에는 빈도가 없으므로 여기에 빈도를 할당해야 합니다. 상위 노드 빈도는 하위 노드(왼쪽 및 오른쪽)의 합입니다. 즉, 5+6= 열하나.

숫자로 백만

따라서 우리는 단일 트리를 얻습니다.

마지막으로 위 트리의 도움을 받아 각 문자에 대한 코드를 찾을 수 있습니다. 각 모서리에 가중치를 할당합니다. 각 왼쪽 가장자리 가중치는 0입니다. 그리고 오른쪽 가장자리 가중치는 1입니다.

입력 문자는 탈퇴 노드에만 표시되고 내부 노드에는 null 값이 있음을 관찰합니다. 각 문자에 대한 허프만 코드를 찾으려면 루트 노드에서 코드를 찾으려는 특정 문자의 리프 노드까지 허프만 트리를 탐색합니다. 표에는 각 문자의 코드와 코드 길이가 설명되어 있습니다.

우리는 가장 빈번한 문자가 가장 짧은 코드 길이를 얻고 덜 빈번한 문자가 가장 큰 코드 길이를 얻는다는 것을 관찰했습니다.

이제 문자열을 인코딩할 수 있습니다. (아브라 카다브라) 우리가 위에서 찍은 것입니다.

 0 111 10 0 1100 0 1101 0 111 10 0 

(ii) 문자열의 평균 코드 길이

허프만 트리의 평균 코드 길이는 아래 공식을 사용하여 결정할 수 있습니다.

 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) 인코딩된 문자열의 길이

인코딩된 메시지의 길이는 다음 공식을 사용하여 결정할 수 있습니다.

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

= 11 x 2.09090909

= 23비트

허프만 인코딩 알고리즘

 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) 

허프만 알고리즘은 그리디 알고리즘이다. 모든 단계에서 알고리즘은 사용 가능한 최상의 옵션을 찾습니다.

허프만 인코딩의 시간 복잡도는 다음과 같습니다. O(n로그인). 여기서 n은 주어진 텍스트의 문자 수입니다.

허프만 디코딩

허프만 디코딩은 인코딩된 데이터를 초기 데이터로 변환하는 기술이다. 인코딩에서 본 것처럼 허프만 트리는 입력 문자열에 대해 만들어지고 문자는 트리에서의 위치에 따라 디코딩됩니다. 디코딩 과정은 다음과 같습니다.

자바 제네릭

• 에서 트리 위로 횡단을 시작합니다. 뿌리 노드를 클릭하고 캐릭터를 검색하세요.
• 이진 트리에서 왼쪽으로 이동하면 다음을 추가합니다. 0 코드에.
• 이진 트리에서 오른쪽으로 이동하면 다음을 추가합니다. 1 코드에.

하위 노드는 입력 문자를 보유합니다. 이후 0과 1로 구성된 코드가 할당됩니다. 문자열을 디코딩하는 데 걸리는 시간 복잡도는 다음과 같습니다. 에), 여기서 n은 문자열의 길이입니다.

허프만 인코딩 및 디코딩 Java 프로그램

다음 프로그램에서는 우선순위 큐, 스택, 트리와 같은 데이터 구조를 사용하여 압축 및 압축 해제 논리를 설계했습니다. 우리는 널리 사용되는 허프만 코딩 알고리즘 기술을 기반으로 유틸리티를 기반으로 할 것입니다.

허프만코드.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()>

산출:

 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