ハフマン符号化詳細(C言語実装)
5292 ワード
問題を解決する:情報伝送、データ圧縮の問題の中で、私たちはいつも1種の符号化を見つけて処理するデータをできるだけ短く圧縮することができることを望んでいます.このような問題に対して,ハフマン符号化を用いて解決することができる.
問題を解決する方法:ハフマンツリーを構築することによってハフマン符号化を得ることができる.
アルゴリズムについては,アルゴリズムの論理構造,アルゴリズムの記憶構造,およびアルゴリズム自体を考慮するとともに,時間と空間の複雑さを考慮する必要があり,ハフマン符号化については,このいくつかの面でこの問題を解析しようと試みた.
ろんりこうぞう
我々はツリーという論理構造を用いて解決した.
理由:ツリーのルートと左右のノード間の経路が一意に決定されるため、ルートノードから各リーフノードへの経路が一意に決定され、ルートノードから複数の異なるリーフノードに到達できるため、ツリーという論理構造を用いてハフマン符号化を実現する.
ハフマンツリーを作成する過程で、一般的な符号化は0と1で構成されているため、私たちが作成したハフマンツリーは二叉木で、左右の2人の子供のノードしかありません.
きおくこうぞう
静的チェーンテーブルを用いてハフマンツリーを格納した.
理由:何度も削除したり、新しいノードを挿入したりするので、操作を容易にするためにチェーンストレージで保存しています.しかし、ノードの数を指定すれば、追加のスペースを簡単に計算できるので、静的チェーンテーブルで保存することができます.また、新しく作成したノードに子供のノードを追加し、子供のノードに両親を追加する必要があります.このように、余分なポインタを使用して、このような操作が正しいことを保証する必要があります.理解を簡略化し,容易にするために,一般に静的三叉鎖表を用いてハフマンツリーを格納する
静的三叉チェーンテーブルの構成部分
二叉木という論理構造を使用しているので,左右の子供ドメイン,LChild,RChildを持ち,ノードの両親が誰であるかを明らかにするために,両親ノードを格納するParentドメインを持つ.ハフマン符号化により生成される符号化は不等長符号化であるため,各文字の出現頻度に応じて異なる符号化が生成され,周波数の大きい符号化は短く,周波数の小さい符号化は長い.したがって、各符号化の周波数を表すWeightドメイン、重みドメインが追加されます.各文字の名前に名前ドメインを付けることもできます.
チェーンテーブルのノードの構成部分がどのようなものかを知り、これらの部分を格納するためにこのような構造体を構築することができます.
アルゴリズム#アルゴリズム#
ハフマンツリーの作成は一般ツリーの作成とは異なり、ツリーの作成は一般的にルートノードから始まり、上下の順序で各ノードが作成されます.しかしハフマンツリーは異なり、ハフマンツリーは異なり、ハフマンツリーは下から上への順に作成されています(ルートノードの左右の2つのノードが何なのか分からないので、ハフマンツリーの葉のノードまでしかありません)
このため,ハフマンツリーの作成過程において,最も長い2つのノードを新しいサブツリーの左右の子供として符号化した(符号化が最も長いのは必ずツリーの一番下の位置を表すため),符号化の長さは文字の重み(周波数)を表すためである.
したがって,操作では,mMinとsMinと表記する最小と2つの重み値を持つノードを先に得た.この2つのノードで新しいノードを作成します(サブツリーが構築されています).
その後、このノードを既存のノードに追加し、前の最小、サブノードをノードから削除します.
その後、上記の操作を繰り返します.
既存のノード(以前に追加した新しいノードを含むが、前回の最小値、マイナー値は削除されたため、既存のノードではない)に最小、マイナー2つのノードを見つけ、新しいサブツリーを構成して既存のノードに追加し、前の最小、マイナーノードをノードから削除...
このようにして、最後に1つのノードしか残っていない(N個のノード、N−1回の操作を行う.最後のノードは別のノードを見つけることができないので、NのノードはN−1個の新しいツリー、すなわちN−1回の操作を行う)まで操作を続ける.
これでハフマンの木が完成しました
注意:
上記のコードは、最小、サブ小のノードの部分を削除していません.配列の削除が不便なため、最小、サブ小のノードの両親が修正されているため、最小を検索します.サブ小値の判断条件に、ノードの両親ドメインが0ではない(初期化時、すべてのノードの両親、子供ドメインが0)という条件を追加します.0でなければ、ノードが削除されたことを示します
同様に、既存のノードに新しいノードを追加していません.len(グローバル変数、配列の長さを表す)を定義しているため、最小になります.セカンダリ・オペレーションの範囲は1からlen(個人的な習慣、配列の下のラベルは1から)に規定されています.lenは最初は入力したノード数NodeNumに等しく、新しいノードの作成に伴ってlenの値も増加します.新しいノードを追加する操作をlenで表します
ハフマン符号化
ハフマンツリーが得られたが,各文字のハフマン符号化は得られなかったので,ハフマンツリーからハフマン符号化を得る必要がある.
一般的には左0右1がデフォルトですが、注意が必要です.左0は左の子供を歩く経路です.同じように右1は右の子供を歩く経路を表します.つまり、符号化された0と1はノードではなく経路を指します.これは間違いありません.
私たちはまずルートから1回ハフマンツリーを巡り、まずハフマンツリーのルートを見つけます.新しく追加されたノードはlenの位置にあるので、最後に追加されたノードもlenの位置(配列の下に1から、len=2*N-1、Nは文字数)です.ルートノードを見つけた後、ツリーの遍歴に従って、左のノードから、左のノードを歩くため、0を保存する必要があります.ハフマン符号化を格納するスペースが必要です.どのようなストレージを使用しますか?
ハフマン符号化を格納するためにスタックを使用することができますが、なぜキューを使用しないのですか?
1つのノードの左のノードがループし終わると、ノード自体に戻る前にそのパスを表す0がスタックを出ます(なぜ戻る前にスタックを出て後で説明するのか)、右のノードをループするときにスタックに1を入れるとこの操作が完了します.
しかし、現在のノードがエンコードが必要な文字ノードであるとどのように判断しますか?符号化する文字はすべてハフマンツリーのルートノードに相当するため、現在のノードに左の子供がいるか右の子供がいるか(すなわち、左の子供ドメインまたは右の子供ドメインが0であるか)に基づいて
構造内に符号化名が定義されている場合は、現在の文字に名前があるかどうかを判断できます(初期化は名前を一緒に0と定義し、入力するときに変更できます).
1つのサブツリーノードは必ず2つのノードからなるので、1つのノードのうちの1つが空で、もう1つのドメインが空ではないという状況は起こり得ないので、再判断の過程でノードの左の子供ドメインが空であるか右の子供ドメインが空であるかのどちらかを判断するだけでよい
ノードが符号化文字であるかどうかをどのように判断するかを知った後、符号化文字のハフマン符号化をどのように出力すればいいのでしょうか.スタックで格納された符号化なので、スタック内の値のみを順番に出力します(スタックを出るのではなく出力するだけで、スタックを出ると残りのノードの符号化が破壊されます)
出力後、戻る前にスタックアウト操作を実行します.前のノードに戻ることを示します.また、このパスが終了したことを示します.
0は左のパスを表し、1は右のパスを表し、スタックを出なければ、左のパスのすべての符号化ノードを歩いて、前のノードに戻り、右のパスのすべての符号化ノードにアクセスすると、前のノードに戻った後、前のノードの左のパスがスタックに残っているため、右のパスの符号化がすべてエラーになります.
一連の符号化にコンパイル後の結果の出力を要求する
ハフマンツリーの各リーフノードが符号化ノードを表していることを知っています.したがって、0に従って左に進み、1に会って右に進み、ルートノードからリーフノードまで歩き、リーフノードの符号化名を出力し、ルートノードから再開すればいいだけです.
問題を解決する方法:ハフマンツリーを構築することによってハフマン符号化を得ることができる.
アルゴリズムについては,アルゴリズムの論理構造,アルゴリズムの記憶構造,およびアルゴリズム自体を考慮するとともに,時間と空間の複雑さを考慮する必要があり,ハフマン符号化については,このいくつかの面でこの問題を解析しようと試みた.
ろんりこうぞう
我々はツリーという論理構造を用いて解決した.
理由:ツリーのルートと左右のノード間の経路が一意に決定されるため、ルートノードから各リーフノードへの経路が一意に決定され、ルートノードから複数の異なるリーフノードに到達できるため、ツリーという論理構造を用いてハフマン符号化を実現する.
ハフマンツリーを作成する過程で、一般的な符号化は0と1で構成されているため、私たちが作成したハフマンツリーは二叉木で、左右の2人の子供のノードしかありません.
きおくこうぞう
静的チェーンテーブルを用いてハフマンツリーを格納した.
理由:何度も削除したり、新しいノードを挿入したりするので、操作を容易にするためにチェーンストレージで保存しています.しかし、ノードの数を指定すれば、追加のスペースを簡単に計算できるので、静的チェーンテーブルで保存することができます.また、新しく作成したノードに子供のノードを追加し、子供のノードに両親を追加する必要があります.このように、余分なポインタを使用して、このような操作が正しいことを保証する必要があります.理解を簡略化し,容易にするために,一般に静的三叉鎖表を用いてハフマンツリーを格納する
静的三叉チェーンテーブルの構成部分
二叉木という論理構造を使用しているので,左右の子供ドメイン,LChild,RChildを持ち,ノードの両親が誰であるかを明らかにするために,両親ノードを格納するParentドメインを持つ.ハフマン符号化により生成される符号化は不等長符号化であるため,各文字の出現頻度に応じて異なる符号化が生成され,周波数の大きい符号化は短く,周波数の小さい符号化は長い.したがって、各符号化の周波数を表すWeightドメイン、重みドメインが追加されます.各文字の名前に名前ドメインを付けることもできます.
チェーンテーブルのノードの構成部分がどのようなものかを知り、これらの部分を格納するためにこのような構造体を構築することができます.
//
typedef struct
{
//char code; //
int Weight;
int Parent;
int LChild;
int RChild;
}HuffmanTree[MAXSIZE+1],TreeNode;
アルゴリズム#アルゴリズム#
ハフマンツリーの作成は一般ツリーの作成とは異なり、ツリーの作成は一般的にルートノードから始まり、上下の順序で各ノードが作成されます.しかしハフマンツリーは異なり、ハフマンツリーは異なり、ハフマンツリーは下から上への順に作成されています(ルートノードの左右の2つのノードが何なのか分からないので、ハフマンツリーの葉のノードまでしかありません)
このため,ハフマンツリーの作成過程において,最も長い2つのノードを新しいサブツリーの左右の子供として符号化した(符号化が最も長いのは必ずツリーの一番下の位置を表すため),符号化の長さは文字の重み(周波数)を表すためである.
したがって,操作では,mMinとsMinと表記する最小と2つの重み値を持つノードを先に得た.この2つのノードで新しいノードを作成します(サブツリーが構築されています).
その後、このノードを既存のノードに追加し、前の最小、サブノードをノードから削除します.
その後、上記の操作を繰り返します.
既存のノード(以前に追加した新しいノードを含むが、前回の最小値、マイナー値は削除されたため、既存のノードではない)に最小、マイナー2つのノードを見つけ、新しいサブツリーを構成して既存のノードに追加し、前の最小、マイナーノードをノードから削除...
このようにして、最後に1つのノードしか残っていない(N個のノード、N−1回の操作を行う.最後のノードは別のノードを見つけることができないので、NのノードはN−1個の新しいツリー、すなわちN−1回の操作を行う)まで操作を続ける.
これでハフマンの木が完成しました
//
void CreatHuffmanTree(TreeNode *ht) //
{
int MNum,SNum;
InitHuffmanTree(ht); //
InputWeight(ht); // （ ）
for(int i=1;i注意:
上記のコードは、最小、サブ小のノードの部分を削除していません.配列の削除が不便なため、最小、サブ小のノードの両親が修正されているため、最小を検索します.サブ小値の判断条件に、ノードの両親ドメインが0ではない(初期化時、すべてのノードの両親、子供ドメインが0)という条件を追加します.0でなければ、ノードが削除されたことを示します
同様に、既存のノードに新しいノードを追加していません.len(グローバル変数、配列の長さを表す)を定義しているため、最小になります.セカンダリ・オペレーションの範囲は1からlen(個人的な習慣、配列の下のラベルは1から)に規定されています.lenは最初は入力したノード数NodeNumに等しく、新しいノードの作成に伴ってlenの値も増加します.新しいノードを追加する操作をlenで表します
ハフマン符号化
ハフマンツリーが得られたが,各文字のハフマン符号化は得られなかったので,ハフマンツリーからハフマン符号化を得る必要がある.
一般的には左0右1がデフォルトですが、注意が必要です.左0は左の子供を歩く経路です.同じように右1は右の子供を歩く経路を表します.つまり、符号化された0と1はノードではなく経路を指します.これは間違いありません.
私たちはまずルートから1回ハフマンツリーを巡り、まずハフマンツリーのルートを見つけます.新しく追加されたノードはlenの位置にあるので、最後に追加されたノードもlenの位置(配列の下に1から、len=2*N-1、Nは文字数)です.ルートノードを見つけた後、ツリーの遍歴に従って、左のノードから、左のノードを歩くため、0を保存する必要があります.ハフマン符号化を格納するスペースが必要です.どのようなストレージを使用しますか?
ハフマン符号化を格納するためにスタックを使用することができますが、なぜキューを使用しないのですか?
1つのノードの左のノードがループし終わると、ノード自体に戻る前にそのパスを表す0がスタックを出ます(なぜ戻る前にスタックを出て後で説明するのか)、右のノードをループするときにスタックに1を入れるとこの操作が完了します.
しかし、現在のノードがエンコードが必要な文字ノードであるとどのように判断しますか?符号化する文字はすべてハフマンツリーのルートノードに相当するため、現在のノードに左の子供がいるか右の子供がいるか(すなわち、左の子供ドメインまたは右の子供ドメインが0であるか)に基づいて
構造内に符号化名が定義されている場合は、現在の文字に名前があるかどうかを判断できます(初期化は名前を一緒に0と定義し、入力するときに変更できます).
1つのサブツリーノードは必ず2つのノードからなるので、1つのノードのうちの1つが空で、もう1つのドメインが空ではないという状況は起こり得ないので、再判断の過程でノードの左の子供ドメインが空であるか右の子供ドメインが空であるかのどちらかを判断するだけでよい
ノードが符号化文字であるかどうかをどのように判断するかを知った後、符号化文字のハフマン符号化をどのように出力すればいいのでしょうか.スタックで格納された符号化なので、スタック内の値のみを順番に出力します(スタックを出るのではなく出力するだけで、スタックを出ると残りのノードの符号化が破壊されます)
出力後、戻る前にスタックアウト操作を実行します.前のノードに戻ることを示します.また、このパスが終了したことを示します.
0は左のパスを表し、1は右のパスを表し、スタックを出なければ、左のパスのすべての符号化ノードを歩いて、前のノードに戻り、右のパスのすべての符号化ノードにアクセスすると、前のノードに戻った後、前のノードの左のパスがスタックに残っているため、右のパスの符号化がすべてエラーになります.
void PrintHuffmanTree(TreeNode *ht,int root) //
{
int data;
if(ht[root].code!=0) // ， ， ， ， code 0,
{
printf("%c:",ht[root].code); //
PrintStack(); //
PushStack(); // ， ， ，
return ;
}
PopStack(0); // 0. 1
PrintHuffmanTree(ht,ht[root].LChild);
PopStack(1); // ， 1
PrintHuffmanTree(ht,ht[root].RChild);
PushStack(); // ， ，
return ;
}
void PrintStack(void) // ，
{
for(int i=0;i一連の符号化にコンパイル後の結果の出力を要求する
ハフマンツリーの各リーフノードが符号化ノードを表していることを知っています.したがって、0に従って左に進み、1に会って右に進み、ルートノードからリーフノードまで歩き、リーフノードの符号化名を出力し、ルートノードから再開すればいいだけです.
void Translate(TreeNode *ht)
{
char ch[80];
int i=0,j=len;
printf(" ：");
gets(ch);
while(ch[i])
{
if(ch[i]=='0') // ， ，
{
j=ht[j].LChild; // 0，
}
if(ch[i]=='1') // 1，
{
j=ht[j].RChild;
}
if(ht[j].code!=0) // ， ， code
{
printf("%c",ht[j].code);
j=len; // ， ，
}
i++; //i
}
}