序文
データ構造を学んだ友人はハフマンを知っている必要があると思います。この偉大な神は有名な「最適なバイナリツリー」を発明しました。彼を記念するために、私たちはそれを「ハフマンの木」と呼びます。ハフマンの木はハフマンのエンコーディングに使用でき、エンコードの知識は、圧縮、暗号化などのように非常に大きいです。
コンセプト
もちろん、ルーチンの1つは、いくつかの基本的な概念を理解する必要があることです。
1。パス長：ツリー内の1つのノードから別のノードに2つのノードを形成するパス。パス上の枝の数は、パス長と呼ばれます。
2。ツリーパスの長さ：ツリールートから各ノードまでのパス長の合計。完全なバイナリツリーと呼ばれるのは、この種の最短経路長です。
3。ツリーの加重パス長：ツリーの各リーフノードに加重値が割り当てられている場合、ツリーの加重パス長は、ルートノードからすべての葉ノードまでのパス長の積とリーフノードの重量に等しくなります。
では、ツリーが最適なバイナリツリーであるかどうかをどのように判断しますか？次の木を見てみましょう。
彼らのパワーの長さは次のとおりです。
WPL1：7*2+5*2+2*2+4*2 = 36
WPL2：7*3+5*3+2*1+4*2 = 46
WPL3：7*1+5*2+2*3+4*3 = 35
3番目のツリーが最短のウェイトパスを持っていることは明らかです（信じられません、試してみることができます。短いものを見つけることができれば、おそらくチューリング賞を受賞します）。これは、「最適なバイナリツリー（Hafman Tree）」と呼ばれるものです。その構築方法は非常に簡単です。最小の重量でノードを選択し、ツリーの下部に配置し、2つの最小の接続を新しいノードに配置します。形成された新しいノードの重みは、これら2つのノードの重みの合計に等しくなければならないことに注意する必要があります。次に、この新しいノードをノードに戻し、ソートを続けるためにツリーを形成する必要があります。このようにして、Hafmanのツリーに保存されている情報を含むすべてのノードは、葉のノード上にあります。
コンセプトを終えた後、私は少し「不明」になるかもしれません。
それを明確に構築するための例を挙げましょう。
文字列があります：aaaaaaabbbbbbaaaacccccccccccddddddddff
最初のステップでは、最初に各文字が表示される回数をカウントし、それをキャラクターの重量と呼びます。 A 15、B 5、C 8、D 6、F 3。
2番目のステップは、B5とF3が最小の2つのキャラクターを見つけて、ノードを構築することです。
次に、F3とB5、A15、C8、D6、FB8を除去します。
ステップ3、1つのノードのみが残るまで2番目のステップを繰り返します。
現在、DFB14、A15、C8です。
やっと、
さて、私たちのハフマンの木が構築されています。
構築する手順
上記のロジックによれば、それを要約するには、いくつかのステップがあります。
1。統計文字列に表示される文字と文字の数。
2。最初のステップの構造に従ってノードを作成します。
3.ノードの重みを昇順で並べ替えます。
4.最小の重量で2つのノードを取り出し、新しい親ノードを生成します。
5.最小の重みで2つのノードを削除し、リストに親ノードを保存します。
6.ノードが残るまでステップ4または5を繰り返します。
7.最後のノードをルートノードに割り当てます。
Javaコード
原則は終了し、次のステップはコードを実装することです。
まず、データを保存するノードクラスがあります。
パッケージhuffman;/** * node class * @author yuxiu * */public class node {public string code; // hafman node in node public int codesize; //ノードの長さpublic string data;パブリックノードrchild; public node（）{} public node（string data、int count）{this.data = data; this.count = count; } public node（int count、node lchild、node rchild）{this.count = count; this.lchild = lchild; this.rchild = rchild; } public node（string data、int count、node lchild、node rchild）{this.data = data; this.count = count; this.lchild = lchild; this.rchild = rchild; }}次に、実装のプロセスがあります。
パッケージhuffman; import java.io。*; import java.util。*; public class huffman {private string str; //は最初にプライベートストリングnewstr = ""; //プライベートノードルートをエンコードするハフマンによって接続されている文字列;文字は同じ位置の同じ文字ですプライベートアレイリスト<Node> nodeList; charlist = new ArrayList <String>（）; nodeList = new ArrayList <Node>（）; // 1。文字列に表示される文字と文字の数を統計//基本的なアイデアは、ababccdebedなどの順序付けられた文字列をCharlistに入れることです。これは、AA、BBB、CC、DD、EE //です。 //文字flag = trueを取り出します。 for（int j = 0; j <charlist.size（）; j ++）{if（charlist.get（j）.charat（0）== ch）{//同じ文字が見つかった場合、string s = charlist.get（j）+ch; charlist.set（j、s）; flag = false;壊す; }} if（flag）{charlist.add（charlist.size（）、ch + ""）; }} // 2。（int i = 0; i <charlist.size（）; i ++）{string data = charlist.get（i）.charat（0）+"";の最初のステップの構造に従ってノードを作成します。 // charlist int count = charlist.get（i）.length（）で各文字列の最初の文字を取得します。 //リスト内の文字列の長さは、対応する重みノードnode = newノード（data、count）です。 //ノードオブジェクトnodeList.add（i、node）を作成します。 //ノードキューに結合} // 3。sort（nodeList）; while（nodeList.size（）> 1）{//ノードの数が1より大きい場合// 4。最小の重量で2つのノードを取り出し、新しい親ノードを生成します// 5。 node right = nodeList.remove（0）; int parentweight = left.count + right.count; //親ノードの重みは、子ノードノードの重みの合計に等しくなります= newノード（親級、左、右）; nodeList.add（0、親）; //親ノードを最初の位置に置く} //6。4番目と5番目のステップを繰り返し、while loop // 7。最後のノードをルートノードに割り当てます= nodeList.get（0）; } / ** * ascending Order * * @param nodeList * / public void sort（arraylist <node> nodeList）{for（int i = 0; i <nodeList.size（）-1; i ++）{for（int j = i+1; j <nodeList.size（）; j ++）{node tem; if（nodelist.get（i）.count> nodelist.get（j）.count）{temp = nodelist.get（i）; nodeList.set（i、nodeList.get（j））; nodeList.set（j、temp）; }}}}} / ** * traversal * * @param node * node * / public void output（node node）{if（node.lChild！= null）{output（node.lChild）; } system.out.print（node.count + ""）; // in-order traversal if（node.rchild！= null）{output（node.rchild）; }} public void output（）{output（root）; }/** * main method * * @param args */public static void main（string [] args）{huffman huff = new huffman（）; // havalman object huff.creathfmtree（ "sdfassvvvvdfgsfdfsdfs"）; //ツリーの構築}要約します
上記は、Javaに基づいてHuffman Treeを実装することです。この記事がJavaの使用方法を学ぶために誰にとっても役立つことを願っています。ご質問がある場合は、メッセージを残して話し合ってください。