アルゴリズム学習-ハフマン符号化(c++実装)
5068 ワード
ハフマン符号化
ハフマン符号化は簡単ですが、非常に重要な符号化方式であり、データストレージの非常に重要な問題である圧縮を解決します.その符号化方式は最も優れており,特に画像で非常に多く用いられている.次にその原理を説明します.
コーディングモード
ハフマン符号化の構造は,重み値の大きさに基づいて実現される.まず重み値に基づいてハフマンツリーを構築し,次にハフマンツリーを逆方向に遍歴し,各ノードの符号化方式を見つけた.
例えば、
ハフマンツリーを構築するプロセスは、ウェイト値が最も小さい2つを見つけるたびに、一緒に配置してツリーを構成し、ルートノードがウェイト値の和です.ステップ1:
これで重み値が1の
これで2ステップ目の構造が完了し、4を重みリストに戻し、探し続け、順番に類推します.
結果のハフマンツリー:
はい、これが最終的なハフマンの木です.見ましたか~各葉ノードは、1文字を表しています.1は
そして遍歴して、左が
次の検証結果:ストレージ領域を計算します.
コード実装
ハフマン符号化は簡単ですが、非常に重要な符号化方式であり、データストレージの非常に重要な問題である圧縮を解決します.その符号化方式は最も優れており,特に画像で非常に多く用いられている.次にその原理を説明します.
コーディングモード
ハフマン符号化の構造は,重み値の大きさに基づいて実現される.まず重み値に基づいてハフマンツリーを構築し,次にハフマンツリーを逆方向に遍歴し,各ノードの符号化方式を見つけた.
例えば、
abbcccdddde
これは文字列で、全部で5文字です.各文字の重み値が出現する頻度であり、a
が1、b
重み値が2、c
重み値が3、d
重み値が4、e
重み値が1である.通常の符号化方式では、5文字を表す最低3ビット、すなわち3 bitである.では、この文字列には1*3+2*3+3*3+4*3+1*3=33 bitsが必要です.ハフマンのコードを使うのでしょうか?ハフマンツリーを構築するプロセスは、ウェイト値が最も小さい2つを見つけるたびに、一緒に配置してツリーを構成し、ルートノードがウェイト値の和です.ステップ1:
2
/ \
1 1
これで重み値が1の
a
とe
は既に構築済みです.また,現在の2を重みリストに戻し,以下の最小の2つがこの2とb
の重み2である. 4
/ \
2 2
/ \
1 1
これで2ステップ目の構造が完了し、4を重みリストに戻し、探し続け、順番に類推します.
... ing
結果のハフマンツリー:
11
/ \
7 4
/ \ / \
3 4 2 2
/ \
1 1
はい、これが最終的なハフマンの木です.見ましたか~各葉ノードは、1文字を表しています.1は
a
とe
です.2はb
の順で...省略ingそして遍歴して、左が
0
、右が1
.c
のは00
、d
のは01
、a
のは100
、b
=11
、e
=101
これで成功した.次の検証結果:ストレージ領域を計算します.
a
からe
:3*1+2*2*3+2*4+3*1=24 bits.発見しましたか?9 bitsが少なくなりました.どんな概念ですか?つまり1/3近く圧縮されているのでしょうが、3 Gサイズなら2 Gに圧縮されているのでしょう.こうなった以上、コード実装を添付します.コード実装
<pre name="code" class="cpp">//
// main.cpp
// HuffmanCode
//
// Created by Alps on 14/11/22.
// Copyright (c) 2014 chen. All rights reserved.
//
#include <iostream>
using namespace std;
typedef struct HTNode{
int weight;
int parent;
int lchild;
int rchild;
HTNode(int w, int p, int l, int r):weight(w),parent(p),lchild(l),rchild(r){}
}HTNode, *HuffmanTree;
typedef char** HuffmanCode;
void Select(HuffmanTree HT, int num, int &child1, int &child2);
void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n){
//
int m,i;
int child1,child2;
if (n <= 1) {
return;
}
m = n*2-1;//
HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode));//
for (i = 1; i <= n; i++,w++) {
HT[i] = HTNode(*w, 0, 0, 0);
}
for (; i <= m; i++) {
HT[i] = HTNode(0, 0, 0, 0);
}
for (i = n+1; i <= m; i++) {
Select(HT,i-1,child1,child2);
HT[child1].parent = i;
HT[child2].parent = i;
HT[i].lchild = child1;
HT[i].rchild = child2;
HT[i].weight = HT[child1].weight + HT[child2].weight;
printf("%d==%d
",child1,child2);
}
HC = (char**)malloc((n+1)*sizeof(char *));
char *cd = (char*)malloc(n*sizeof(char));
// memset(cd, '\0', n*sizeof(char));
int c = 0;
int tempParent,count;
for (i = 1; i <= n; i++) {
count = 0;
for (c = i,tempParent = HT[i].parent; tempParent != 0;c=tempParent, tempParent = HT[tempParent].parent) {
if (HT[tempParent].lchild == c) {
cd[count++] = '0';
}else{
cd[count++] = '1';
}
}
cd[count]='\0';
printf("%s~%d
",cd,i);
HC[i] = (char *)malloc((count)*sizeof(char));
for (int j = count; j>=0; j--) {
HC[i][count-j] = cd[j-1];
}
// strcpy(HC[i], cd);
// memset(cd,'\0', n*sizeof(char));//error
}
}
void Select(HuffmanTree HT, int num, int &child1, int &child2){
child1 = 0;
child2 = 0;
int w1 = 0;
int w2 = 0;
for (int i = 1; i <= num; i++) {
if (HT[i].parent == 0) {
if (child1 == 0) {
child1 = i;
w1 = HT[i].weight;
continue;
}
if (child2 == 0) {
child2 = i;
w2 = HT[i].weight;
continue;
}
if (w1 > w2 && w1 > HT[i].weight) {
w1 = HT[i].weight;
child1 = i;
continue;
}
if (w2 > w1 && w2 > HT[i].weight) {
w2 = HT[i].weight;
child2 = i;
continue;
}
}
}
}
int main(int argc, const char * argv[]) {
char a[] = "abcaab";
int i = (int)strlen(a);
printf("%d
",i);
int b[]={1,2,3,4};
HuffmanTree HT;
HuffmanCode HC;
HuffmanCoding(HT, HC, b, 4);
for (i = 1; i <= 7; i++) {
printf("%d-%d
",HT[i].weight,HT[i].parent);
}
for (i = 1; i <=4; i++) {
printf("%s
",HC[i]);
}
return 0;
}