이전 Huffman 코드 문제에서는 빈도가 정렬되지 않았습니다. 빈도 목록을 정렬된 순서로 제공하면 코드 할당 작업이 더 효율적입니다.
이 문제에서는 두 개의 빈 큐를 사용합니다. 그런 다음 고유한 각 문자에 대한 리프 노드를 만들고 빈도가 높은 순서로 대기열에 삽입합니다.
이 접근 방식에서 알고리즘의 복잡성은 O(n)입니다.
입력 및 출력
Input: Different letters and their frequency in sorted order Letters: {L, K, X, C, E, B, A, F} Frequency: {1, 1, 2, 2, 2, 2, 3, 4} Output: Codes for the letters L: 0000 K: 0001 X: 001 C: 010 E: 011 F: 10 B: 110 A: 111
알고리즘
huffman 코드 (dataList, freqList, n)
입력: 데이터 목록 및 빈도 목록, 목록의 데이터 수 n.
출력 - 코드에 할당된 문자.
Begin root := huffmanTree(dataList, freqList, n) //create root of Huffman tree create an array to store codes, and top pointer for that array. call getCodes(root, array, top) to find codes for each character. End
getCode (루트:노드, 배열, 상단)
입력: 루트 노드, 코드를 저장할 배열, 배열의 맨 위.
출력 - 각 문자에 대한 코드
Begin if leftChild(root) ≠φ then array[top] := 0 getCodes(leftChild(root), array, top) if rightChild(root) ≠φ then array[top] = 1 getCode(rightChild(root), array, top) if leftChild(root) = φ AND rightChild(root) = φ then display the character ch of root for all entries of the array do display the code in array[i] for character ch done End에 대한 array[i]의 코드를 표시합니다.
huffmanTree(dataList, freqList, n)
입력 - 데이터 목록 및 빈도 목록, 목록의 데이터 수 n.
출력 - 허프만 트리 생성
Begin for all different character ch do add node with ch and frequency of ch into queue q1 done while q1 is not empty OR size of q2 ≠ 1 do find two minimum node using q1 and q2 and add them as left and right child of a new node. add new node in q2 done delete node from q2 and return that node. End
예
#include<iostream> #include<queue> using namespace std; struct node { char data; int freq; node *child0, *child1; }; node *getNode(char d, int f) { node *newNode = new node; newNode->data = d; newNode->freq = f; newNode->child0 = NULL; newNode->child1 = NULL; return newNode; } node *findMinNode(queue<node*>&q1, queue<node*>&q2) { node *minNode; if(q1.empty()) { //if first queue is empty, delete and return node from second queue minNode = q2.front(); q2.pop(); return minNode; } if(q2.empty()) { //if second queue is empty, delete and return node from first queue minNode = q1.front(); q1.pop(); return minNode; } if((q1.front()->freq) < (q2.front()->freq)) { //find smaller from two queues minNode = q1.front(); q1.pop(); return minNode; }else { minNode = q2.front(); q2.pop(); return minNode; } } node *huffmanTree(char data[], int frequency[], int n) { node *c0, *c1, *par; node *newNode; queue<node*> qu1, qu2; for(int i = 0; i<n; i++) { //add all node to queue 1 newNode = getNode(data[i], frequency[i]); qu1.push(newNode); } while(!(qu1.empty() && (qu2.size() == 1))) { c0 = findMinNode(qu1, qu2); //find two minimum as two child c1 = findMinNode(qu1, qu2); node *newNode = getNode('#', c0->freq+c1->freq); //intermediate node holds special character par = newNode; par->child0 = c0; par->child1 = c1; qu2.push(par); //add sub tree into queue 2 } node *retNode = qu2.front(); qu2.pop(); return retNode; } void getCodes(node *rootNode, int array[], int n) { //array to store the code if(rootNode->child0 != NULL) { array[n] = 0; getCodes(rootNode->child0, array, n+1); } if(rootNode->child1 != NULL) { array[n] = 1; getCodes(rootNode->child1, array, n+1); } if(rootNode->child0 == NULL && rootNode->child1 == NULL) { // when root is leaf node cout << rootNode->data << ": "; for(int i = 0; i<n; i++) cout << array[i]; cout << endl; } } void huffmanCodes(char data[], int frequency[], int n) { node *rootNode = huffmanTree(data, frequency, n); int array[50], top = 0; getCodes(rootNode, array, top); } int main() { char data[] = {'L', 'K', 'X', 'C', 'E', 'B', 'A', 'F'}; int frequency[] = {1, 1, 2, 2, 2, 2, 3, 4}; int n = sizeof(data)/sizeof(data[0]); huffmanCodes(data, frequency, n); }
출력
L: 0000 K: 0001 X: 001 C: 010 E: 011 F: 10 B: 110 A: 111