Huffmanエンコード紹介
Huffmanエンコーディングは、文字に対応する文字とバイナリのコーディングペアリングの問題を扱います。これは、文字に対応するバイナリデータの長さを圧縮する目的で、エンコードとデコードに分割されます。文字が保存されて転送されると、バイナリ（コンピューターは0/1のみを知っている）であるため、文字とバイナリの間にマッピング関係があることがわかっています。文字はキャラクターセット（Charset）に属します。文字は、エンコードを介してバイナリで保存および送信する必要があります。表示されると、文字にデコードする必要があります。文字セットとエンコーディング方法は、1対多くの関係です（UnicodeはUTF-8、UTF-16などでエンコードできます）。キャラクターのセット、エンコード、デコードを理解した後、空に飛んでいる文字化けコードの問題は簡単に解決できます。英語の手紙の小文字を例にとって、ASCIIエンコードでは、小数は97、バイナリは01100001です。ASCIIの各文字は8ビット（1byte）でエンコードされています。送信する1000文字がある場合は、8000ビットを送信する必要があります。問題は、英語で文字Eを使用する頻度は12.702％、zは0.074％であることです。前者は後者の100倍以上ですが、同じ数字でバイナリを使用しています。より良いことができ、この方法は可変長さのエンコードです。指針は、より短い数字でより高い周波数をエンコードすること、および桁が長い頻度が低いものをエンコードすることです。 Huffmanエンコーディングアルゴリズムは、そのような問題を扱っています。
Javaの実装をエンコードするHuffman
ハフマンエンコードアルゴリズムで主に使用されるデータ構造は、完全なバイナリツリーと優先順位のキューです。後者はjava.util.priorityqueueを使用し、前者はそれ自体を実装します（すべて内部クラスです）。コードは次のとおりです。
静的クラスツリー{プライベートノードルート; public node getRoot（）{return root; } public void setroot（node root）{this.root = root; }} static classノード実装CARMANTABLE <Node> {private string chars = ""; private int frequency = 0;プライベートノードの親;プライベートノード左ノード。プライベートノードRightNode; @Override public int compareto（node n）{return prevuelis -n.frequency; } public boolean isleaf（）{return chars.length（）== 1; } public boolean isroot（）{return parent == null; } public boolean isleftchild（）{return parent！= null && this == parent.leftnode; } public int getFrequence（）{return recurement; } public void setFrequence（int frequence）{this.frequency = frequency; } public string getChars（）{return chars; } public void setchars（string chars）{this.chars = chars; } public node getParent（）{return parent; } public void setParent（node parent）{this.parent = parent; } public node getLeftNode（）{return leftnode; } public void setLeftnode（node leftnode）{this.leftnode = leftnode; } public node getRightNode（）{return regnode; } public void setRightNode（node rightNode）{this.rightNode = rightNode; }}統計
エンコードテーブルは周波数に従って配置する必要があるため、もちろん、周波数の統計情報を取得する必要があります。このような問題に対処する方法を実装しました。すでに統計がある場合は、Map <Character、Integer>に変換します。取得した情報がパーセンテージである場合、100または1000、または10000を掛けます。常に整数に変換できます。たとえば、12.702％に1000を掛けたのは12702であり、Huffmanエンコードはサイズの問題のみを気にします。統計的方法は次のように実装されます。
public static Map <Character、Integer> Statistics（char [] Chararray）{Map <Character、Integer> Map = new Hashmap <Character、Integer>（）; for（charc c：chararray）{文字文字= new文字（c）; if（map.containskey（character））{map.put（character、map.get（character） + 1）; } else {map.put（文字、1）; }}マップを返します。 }木を構築します
ツリーを構築することは、ハフマンエンコードアルゴリズムの中心的なステップです。アイデアは、すべての文字を完全にバイナリツリーの葉のノードに掛けることであり、ページ以外の子ノードの左ノードの周波数は、適切なノードよりも現れません。アルゴリズムは統計をノードに変換し、優先キューに保存します。キューから最小周波数がポップアップする2つのノードが、新しい親ノード（非葉のノード）が構築されるたびに構築されます。文字コンテンツがポップアップする2つのノードの合計、および周波数も合計です。最初のポップアップは左の子ノードとして使用され、次のポップアップは右の子ノードとして使用され、新しく構築された親ノードがキューに配置されます。上記のアクションn-1回を繰り返します。nは異なる文字の数です（キュー内の数は毎回1削減されます）。上記の手順を終了すると、キューにノードが残り、ツリーのルートノードがポップアップします。コードは次のとおりです。
private static Tree buildTree（Map <Character、Integer> Statistics、List <Node> leaves）{Character [] Keys = Statistics.KeySet（）。ToArray（new Character [0]）; PriorityQueue <Node> priorityQueue = new PriorityQueue <Node>（）; for（文字文字：キー）{node node = new node（）; node.chars = character.toString（）; node.frequency = statistics.get（文字）; PriorityQueue.Add（ノード）; leaves.add（ノード）; } int size = priorityqueue.size（）; for（int i = 1; i <= size -1; i ++）{node node1 = priorityqueue.poll（）; node node2 = priorityqueue.poll（）; node sumnode = new node（）; sumnode.chars = node1.chars + node2.chars; sumnode.frequency = node1.fraquence + node2.fraquence; sumnode.leftnode = node1; sumnode.rightnode = node2; node1.parent = sumnode; node2.parent = sumnode; PriorityQueue.Add（sumnode）; }ツリーツリー= new Tree（）; tree.root = priorityqueue.poll（）;ツリーを返します。 }コーディング
キャラクターの対応するエンコードは、文字が配置されている葉のノードから検索することです。文字ノードが親ノードの左ノードである場合、エンコードされた文字の前に0を追加します。文字とバイナリコードのマッピング関係が取得される限り、エンコードは非常に簡単です。コードは次のとおりです。
public static string encode（string originalstr、map <character、integer> statistics）{if（originalstr == null || originalstr.equals（ ""））{return ""; } char [] chararray = originalstr.tochararray（）; List <Node> LeafNodes = new ArrayList <Node>（）; buildtree（統計、葉のノード）; map <文字、string> encodinfo = buildencodinginfo（leafnodes）; stringbuffer buffer = new StringBuffer（）; for（char c：chararray）{文字文字= new Character（c）; buffer.append（encodinfo.get（文字））; } return buffer.toString（）; } private static map <文字、string> buildencodinginfo（list <node> leafnodes）{map <character、string> codewords = new hashmap <character、string>（）; for（node leafnodes：leafnodes）{文字文字= new文字（leafnode.getchars（）。charat（0））;文字列codeword = "";ノードcurrentNode = LeafNode; do {if（currentnode.isleftchild（））{codeword = "0" + codeword; } else {codeword = "1" + codeword; } currentNode = currentNode.Parent; } while（currentNode.Parent！= null）; Codewords.put（Character、Codeword）; } return codewords; }デコード
Huffmanエンコードアルゴリズムは、バイナリコードが別のコードのプレフィックスではないことを確認できるため、デコードは非常に簡単です。バイナリの各ビットを順番に取り出し、ツリールートから1、右、0から左に検索し、葉のノードに到達し（ヒット）、ルートノードに戻り、上記のアクションを繰り返し続けます。コードは次のとおりです。
public static string decode（string binarystr、map <character、integer> statistics）{if（binarystr == null || binarystr.equals（ ""））{return ""; } char [] binarychararray = binarystr.tochararray（）; linkedlist <character> binarylist = new linkedlist <character>（）; int size = binarychararray.length; for（int i = 0; i <size; i ++）{binarylist.addlast（new Character（binaryChararray [i]））; } list <Node> leafnodes = new ArrayList <Node>（）;ツリーツリー= buildtree（統計、リーフノード）; stringbuffer buffer = new StringBuffer（）; while（binarylist.size（）> 0）{node node = tree.root; do {文字c = binarylist.removefirst（）; if（c.charvalue（）== '0'）{node = node.leftnode; } else {node = node.rightnode; }} while（！node.isleaf（））; buffer.append（node.chars）; } return buffer.toString（）; }テストと比較
Huffmanエンコードの正確性に関する次のテスト（最初にエンコードされ、中国語を含むデコードされた後）、およびHuffmanエンコードとの比較バイナリ文字列をエンコードします。コードは次のとおりです。
public static void main（string [] args）{string orist = "huffmanコードデータは非常に効果的にデータを圧縮します。20％から90％の節約は典型的です。 map <文字、integer> statistics = statistics（oristr.tochararray（））; string encodedbinaristr = encode（orist、statistics）; string decodedstr = decode（encodedbinaristr、統計）; system.out.println（ "original string：" + oristr）; system.out.println（ "huffman encoed binary string：" + encodedbinaristr）; System.out.println（ "Binariy Stringからのデコードされた文字列：" + decodedstr）; system.out.println（ "utf-8のバイナリ文字列：" + getStringofbyte（orist、charset.forname（ "utf-8"）））; system.out.println（ "UTF-16のバイナリ文字列：" + getStringofbyte（orist、charset.forname（ "utf-16"）））; system.out.println（ "us-asciiのバイナリ文字列：" + getStringofbyte（orist、charset.forname（ "us-ascii"）））; System.out.println（ "gb2312のバイナリ文字列：" + getStringofbyte（orist、charset.forname（ "gb2312"）））; } public static string getStringofbyte（string str、charset charset）{if（str == null || str.equals（ ""））{return ""; } byte [] bytearray = str.getBytes（charset）; int size = bytearray.length; stringbuffer buffer = new StringBuffer（）; for（int i = 0; i <size; i ++）{byte temp = bytearray [i]; buffer.append（getStringofbyte（temp））; } return buffer.toString（）; } public static string getStringofbyte（byte b）{stringbuffer buffer = new StringBuffer（）; for（int i = 7; i> = 0; i-）{byte temp =（byte）（（b >> i）＆0x1）; buffer.append（string.valueof（temp））; } return buffer.toString（）; }上記はこの記事のすべての内容です。みんなの学習に役立つことを願っています。誰もがwulin.comをもっとサポートすることを願っています。