ハフマン符号化アルゴリズムは、によって提案されました。 デビッド・A・ハフマン 1950年に。 可逆データ圧縮 機構。としても知られています データ圧縮エンコーディング。 画像 (JPEG または JPG) 圧縮で広く使用されています。このセクションでは、 ハフマン符号化 そして デコード、 また、そのアルゴリズムを Java プログラムに実装します。
各文字は 0 と 1 のシーケンスであり、8 ビットを使用して格納されることがわかっています。そのメカニズムはと呼ばれます 固定長エンコーディング 各文字が同じ数の固定ビット ストレージを使用するためです。
の Java インスタンス
ここで疑問が生じますが、 キャラクターを保存するために必要なスペースの量を減らすことはできますか?
はい、 を使用することで可能です 可変長エンコーディング。 このメカニズムでは、他の文字と比較してより頻繁に出現するいくつかの文字を利用します。このエンコード技術では、ビット数を減らすことで同じテキストまたは文字列を表現できます。
ハフマン符号化
ハフマン符号化は次の手順を実行します。
- 指定されたすべての文字に可変長コードを割り当てます。
- 文字のコード長は、指定されたテキストまたは文字列内でその文字が出現する頻度によって異なります。
- 文字が頻繁に出現する場合、その文字は最小のコードを取得します。
- 文字が最も少ない場合、その文字は最大のコードを取得します。
ハフマンコーディングは次のようになります。 プレフィックスルール これにより、デコード中のあいまいさが防止されます。このルールは、文字に割り当てられたコードが他の文字に割り当てられたコードのプレフィックスとして扱われないことも保証します。
ハフマンコーディングには次の 2 つの主要な手順が含まれます。
- まず、 ハフマンツリー 指定された入力文字列、文字、またはテキストから。
- ツリーをたどって各文字にハフマン コードを割り当てます。
上記 2 つの手順を簡単に説明します。
ハフマンツリー
ステップ1： ノードの文字ごとに、リーフ ノードを作成します。文字のリーフ ノードには、その文字の頻度が含まれます。
ステップ2： すべてのノードを頻度に従ってソートされた順序で設定します。
ステップ 3: 2 つのノードが同じ周波数を持つ状況が存在する可能性があります。このような場合は、次の操作を行ってください。
- 新しい内部ノードを作成します。
- ノードの周波数は、同じ周波数を持つ 2 つのノードの周波数の合計になります。
- 最初のノードを左の子としてマークし、別のノードを新しく作成した内部ノードの右の子としてマークします。
ステップ 4: すべてのノードが単一のツリーを形成するまで、ステップ 2 と 3 を繰り返します。したがって、ハフマン木が得られます。
ハフマン符号化の例
文字列をエンコードする必要があるとします。 アブラ・カダブラ。 次のことを決定します。
- 全文字のハフマンコード
- 指定された文字列の平均コード長
- エンコードされた文字列の長さ
(i) 全文字のハフマンコード
各文字のコードを決定するために、まず、 ハフマンツリー。
ステップ1： 文字とその頻度のペアを作成します。
(a, 5)、(b, 2)、(c, 1)、(d, 1)、(r, 2)
ステップ2： 頻度に関してペアを並べ替えると、次のようになります。
(c, 1)、(d, 1)、(b, 2) (r, 2)、(a, 5)
javatpoint java
ステップ 3: 最初の 2 文字を選択し、親ノードの下に結合します。
親ノードには周波数がないことがわかります。そのため、親ノードに周波数を割り当てる必要があります。親ノードの頻度は、その子ノード (左と右) の合計、つまり 1+1= になります。 2.
ステップ 4: 単一のツリーが得られるまで、ステップ 2 と 3 を繰り返します。
ペアがすでに (ステップ 2 によって) ソートされていることがわかります。もう一度、最初の 2 つのペアを選択して結合します。
親ノードには周波数がないことがわかります。そのため、親ノードに周波数を割り当てる必要があります。親ノードの頻度は、その子ノード (左と右) の合計、つまり 2+2= になります。 4.
もう一度、ペアがソートされているかどうかを確認します。このステップでは、ペアをソートする必要があります。
ステップ 3 に従って、最初の 2 つのペアを選択して結合すると、次の結果が得られます。
親ノードには周波数がないことがわかります。そのため、親ノードに周波数を割り当てる必要があります。親ノードの頻度は、その子ノード (左と右) の合計、つまり 2+4= になります。 6.
git add --all
もう一度、ペアがソートされているかどうかを確認します。このステップでは、ペアをソートする必要があります。並べ替えると、ツリーは次のようになります。
ステップ 3 に従って、最初の 2 つのペアを選択して結合すると、次の結果が得られます。
親ノードには周波数がないことがわかります。そのため、親ノードに周波数を割り当てる必要があります。親ノードの頻度は、その子ノード (左と右) の合計、つまり 5+6= になります。 十一。
したがって、単一の木が得られます。
最後に、上記のツリーを使用して各文字のコードを見つけます。各エッジに重みを割り当てます。それぞれに注意してください 左端の重み付けは 0 そしてその 右端の重み付けは 1 です。
数学ランダムJava
入力文字は Leave ノードにのみ表示され、内部ノードには null 値があることがわかります。各文字のハフマン コードを見つけるには、コードを見つけたい特定の文字のルート ノードからリーフ ノードまでハフマン ツリーをたどります。次の表に、各文字のコードとコード長を示します。
| キャラクター | 頻度 | コード | コード長 |
|---|---|---|---|
| あ | 5 | 0 | 1 |
| B | 2 | 111 | 3 |
| C | 1 | 1100 | 4 |
| D | 1 | 1101 | 4 |
| R | 2 | 10 | 2 |
最も頻繁に使用される文字は最も短いコード長を取得し、より頻繁に使用されない文字は最大のコード長を取得することがわかります。
これで文字列をエンコードできるようになりました (アブラ・カダブラ) 上で取り上げたものです。
0 111 10 0 1100 0 1101 0 111 10 0
(ii) 文字列の平均コード長
ハフマン木の平均コード長は、次の式で求めることができます。
Average Code Length = ∑ ( frequency × code length ) / ∑ ( frequency )
= { (5 x 1) + (2 x 3) + (1 x 4) + (1 x 4) + (2 x 2) } / (5+2+1+1+2)
= 2.09090909
(iii) エンコードされた文字列の長さ
エンコードされたメッセージの長さは、次の式を使用して決定できます。
length= Total number of characters in the text x Average code length per character
= 11 × 2.09090909
= 23 ビット
ハフマン符号化アルゴリズム
Huffman (C) n=|C| Q=C for i=1 to n-1 do z=allocate_Node() x=left[z]=Extract_Min(Q) y=right[z]=Extract_Min(Q) f[z]=f[x]+f[y] Insert(Q,z) return Extract_Min(Q)
ハフマン アルゴリズムは貪欲なアルゴリズムです。すべての段階で、アルゴリズムは利用可能な最適なオプションを探します。
ハフマン符号化の時間計算量は次のとおりです。 ああ(nlogn)。 ここで、n は指定されたテキストの文字数です。
ハフマンデコード
ハフマン復号化とは、符号化されたデータを初期データに変換する技術です。エンコードで見たように、ハフマン ツリーは入力文字列に対して作成され、文字はツリー内の位置に基づいてデコードされます。デコードプロセスは次のとおりです。
c ブール値
- から木の上をトラバースし始める。 根 ノードを選択して文字を検索します。
- 二分木を左に移動すると、次のように追加します。 0 コードに。
- 二分木内を右に移動すると、次のように追加します。 1 コードに。
子ノードは入力文字を保持します。連続する 0 と 1 で構成されるコードが割り当てられます。文字列をデコードする時間計算量は次のとおりです。 の上）、 ここで、n は文字列の長さです。
ハフマンエンコーディングおよびデコーディング Java プログラム
次のプログラムでは、優先キュー、スタック、ツリーなどのデータ構造を使用して、圧縮および解凍ロジックを設計しました。私たちのユーティリティは、広く使用されているハフマン コーディングのアルゴリズム技術に基づいています。
ハフマンコード.java
import java.util.Comparator; import java.util.HashMap; import java.util.Map; import java.util.PriorityQueue; //defining a class that creates nodes of the tree class Node { //storing character in ch variable of type character Character ch; //storing frequency in freq variable of type int Integer freq; //initially both child (left and right) are null Node left = null; Node right = null; //creating a constructor of the Node class Node(Character ch, Integer freq) { this.ch = ch; this.freq = freq; } //creating a constructor of the Node class public Node(Character ch, Integer freq, Node left, Node right) { this.ch = ch; this.freq = freq; this.left = left; this.right = right; } } //main class public class HuffmanCode { //function to build Huffman tree public static void createHuffmanTree(String text) { //base case: if user does not provides string if (text == null || text.length() == 0) { return; } //count the frequency of appearance of each character and store it in a map //creating an instance of the Map Map freq = new HashMap(); //loop iterates over the string and converts the text into character array for (char c: text.toCharArray()) { //storing character and their frequency into Map by invoking the put() method freq.put(c, freq.getOrDefault(c, 0) + 1); } //create a priority queue that stores current nodes of the Huffman tree. //here a point to note that the highest priority means the lowest frequency PriorityQueue pq = new PriorityQueue(Comparator.comparingInt(l -> l.freq)); //loop iterate over the Map and returns a Set view of the mappings contained in this Map for (var entry: freq.entrySet()) { //creates a leaf node and add it to the queue pq.add(new Node(entry.getKey(), entry.getValue())); } //while loop runs until there is more than one node in the queue while (pq.size() != 1) { //removing the nodes having the highest priority (the lowest frequency) from the queue Node left = pq.poll(); Node right = pq.poll(); //create a new internal node with these two nodes as children and with a frequency equal to the sum of both nodes' frequencies. Add the new node to the priority queue. //sum up the frequency of the nodes (left and right) that we have deleted int sum = left.freq + right.freq; //adding a new internal node (deleted nodes i.e. right and left) to the queue with a frequency that is equal to the sum of both nodes pq.add(new Node(null, sum, left, right)); } //root stores pointer to the root of Huffman Tree Node root = pq.peek(); //trace over the Huffman tree and store the Huffman codes in a map Map huffmanCode = new HashMap(); encodeData(root, '', huffmanCode); //print the Huffman codes for the characters System.out.println('Huffman Codes of the characters are: ' + huffmanCode); //prints the initial data System.out.println('The initial string is: ' + text); //creating an instance of the StringBuilder class StringBuilder sb = new StringBuilder(); //loop iterate over the character array for (char c: text.toCharArray()) { //prints encoded string by getting characters sb.append(huffmanCode.get(c)); } System.out.println('The encoded string is: ' + sb); System.out.print('The decoded string is: '); if (isLeaf(root)) { //special case: For input like a, aa, aaa, etc. while (root.freq-- > 0) { System.out.print(root.ch); } } else { //traverse over the Huffman tree again and this time, decode the encoded string int index = -1; while (index <sb.length() - 1) { index="decodeData(root," index, sb); } traverse the huffman tree and store codes in a map function that encodes data public static void encodedata(node root, string str, huffmancode) if (root="=" null) return; checks node is leaf or not (isleaf(root)) huffmancode.put(root.ch, str.length()> 0 ? str : '1'); } encodeData(root.left, str + '0', huffmanCode); encodeData(root.right, str + '1', huffmanCode); } //traverse the Huffman Tree and decode the encoded string function that decodes the encoded data public static int decodeData(Node root, int index, StringBuilder sb) { //checks if the root node is null or not if (root == null) { return index; } //checks if the node is a leaf node or not if (isLeaf(root)) { System.out.print(root.ch); return index; } index++; root = (sb.charAt(index) == '0') ? root.left : root.right; index = decodeData(root, index, sb); return index; } //function to check if the Huffman Tree contains a single node public static boolean isLeaf(Node root) { //returns true if both conditions return ture return root.left == null && root.right == null; } //driver code public static void main(String args[]) { String text = 'javatpoint'; //function calling createHuffmanTree(text); } } </sb.length()> 出力：
Huffman Codes of the characters are: {p=000, a=110, t=111, v=001, i=010, j=011, n=100, o=101} The initial string is: javatpoint The encoded string is: 011110001110111000101010100111 The decoded string is: javatpoint