호프만 암호화

Huffman 암호화는无损 데이터 압축 알고리즘입니다. 이 알고리즘에서는 다른 문자에 대해 변화된 길이의 코드를 배분합니다. 코드 길이는 문자 사용 빈도와 관련이 있습니다. 가장 빈번한 문자는 가장 작은 코드를 가지고 있으며, 더 긴 코드는 가장 빈번하지 않은 문자에 사용됩니다.

주로 두 부분으로 구성됩니다. 첫 번째는 Huffman 트리를 생성하고, 두 번째는 트리를 탐색하여 코드를 찾습니다.

예를 들어, 문자열 'YYYZXXYYX'를 고려해 보면, 문자 Y의 빈도가 X보다 크고, 문자 Z의 빈도가 가장 낮습니다. 따라서 Y의 코드 길이는 X보다 짧고, X의 코드 길이는 Z보다 짧습니다.

• 각 문자의 빈도에 따라 코드를 배분하는 복잡도는 O(n log n)입니다.

입력　-예를 들어, 'ACCEBFFFFAAXXBLKE'와 같은 다른 문자의 문자열.
출력　-다른 문자의 코드:

Data:　K,　Frequency:　1,　Code:　0000
Data:　L,　Frequency:　1,　Code:　0001
Data:　E,　Frequency:　2,　Code:　001
Data:　F,　Frequency:　4,　Code:　01
Data:　B,　Frequency:　2,　Code:　100
Data:　C,　Frequency:　2,　Code:　101
Data:　X,　Frequency:　2,　Code:　110
Data:　A,　Frequency:　3,　Code:　111

알고리즘

huffmanCoding(문자열)

입력-다른 문자의 문자열.

출력-각 문자의 코드.

시작
　　　Huffman 트리를 위해 문자, 빈도, 왼쪽과 오른쪽 자식 노드를 가진 노드를 정의합니다.
　　　각 문자의 빈도를 저장하기 위해 'freq'라고 불리는 목록을 생성합니다. 초기에는 모두 0입니다.
　　　각 문자 c 가 문자열에 있는 경우에 대해
　　　　　　freq 목록에서 문자 ch의 빈도를 증가시킵니다.
　　　완료
　　　모든 유형의 문자 ch를 대상으로
　　　　　　ch의 빈도가 μη zero라면 ch 및 그 빈도를 우선순위 큐 Q의 노드로 추가합니다.
　　　완료
　　　Q가 비어 있지 않다면
　　　　　　Q에서 항목을 제거하고 노드의 왼쪽 자식에 할당합니다
　　　　　　Q에서 항목을 제거하고 노드의 오른쪽 자식에 할당합니다
　　　　　　할당된 코드를 찾기 위해 노드를 탐색합니다
　　　완료
끝

traverseNode(n: 노드, 코드)

입력-호프만 트리의 노드 n 및 이전 호출에서 할당된 코드　

출력-각 문자에 할당된 코드

if left child of node n ≠ φ then
　　　traverseNode(leftChild(n), code+’0’)　//좌측 자식을 탐색합니다
　　　traverseNode(rightChild(n), code+’1’)　//오른쪽 자식을 탐색합니다
else
　　　현재 노드의 문자와 데이터를 표시합니다.

예제

#include<iostream>
#include<queue>
#include<string>
using namespace std;
struct node{
　　　int freq;
　　　char data;
　　　const node　*child0,　*child1;
　　　node(char d, int f =　-1{　//assign values in the node
　　　　　　data = d;
　　　　　　freq = f;
　　　　　　child0 = NULL;
　　　　　　child1　= NULL;
　　　}
　　　node(const node　*c0, const node　*c1{
　　　　　　data = 0;
　　　　　　freq = c0->freq　+　c1->freq;
　　　　　　child0=c0;
　　　　　　child1=c1;
　　　}
　　　bool operator<(const node &a) const {　//< 연산자는 큐에서 우선순위를 찾기 위해 사용됩니다
　　　　　　return freq > a.freq;
　　　}
　　　void traverse(string code = "")const{
　　　　　　if(child0!=NULL){
　　　　　　　　　child0->traverse(code+'0');　//왼쪽 자식으로 코드와 0을 추가하기
　　　　　　　　　child1->traverse(code+'1);　//add　1　오른쪽 자식으로 코드를 추가하기
　　　　　　}else{
　　　　　　　　　cout << "Data: " << data << ", Frequency: " << freq << ", Code: " << code << endl;
　　　　　　}
　　　}
};
void huffmanCoding(string str){
　　　priority_queue<node> qu;
　　　int frequency[256;
　　　for(int i = 0; i<256; i++)
　　　　　　frequency[i] = 0;　//모든 효과를 지우기
　　　for(int i = 0; i<str.size(); i++{
　　　　　　frequency[int(str[i])]++;　//효과를 증가시키기
　　　}
　　　for(int i = 0; i<256; i++{
　　　　　　if(frequency[i]){
　　　　　　　　　qu.push(node(i, frequency[i]));
　　　　　　}
　　　}
　　　while(qu.size() >1{
　　　　　　node　*c0 = new node(qu.top());　//왼쪽 자식을 가져와 큐에서 제거하기
　　　　　　qu.pop();
　　　　　　node　*c1　= new node(qu.top());　//오른쪽 자식을 가져와 큐에서 제거하기
　　　　　　qu.pop();
　　　　　　qu.push(node(c0, c1));　//두 자식의 효과를 추가하고 다시 큐에 추가하기
　　　}
　　　cout << "The Huffman Code: " << endl;
　　　qu.top().traverse();　//트리를 탐색하여 코드를 가져오기
}
main(){
　　　string str = "ACCEBFFFFAAXXBLKE";　//arbitray string to get frequency
　　　huffmanCoding(str);
}

출력 결과

The　Huffman　Code:
Data:　K,　Frequency:　1,　Code:　0000
Data:　L,　Frequency:　1,　Code:　0001
Data:　E,　Frequency:　2,　Code:　001
Data:　F,　Frequency:　4,　Code:　01
Data:　B,　Frequency:　2,　Code:　100
Data:　C,　Frequency:　2,　Code:　101
Data:　X,　Frequency:　2,　Code:　110
Data:　A,　Frequency:　3,　Code:　111