データは、情報を失うことなくサイズを小さくするために、ハフマン コーディング技術を使用して圧縮できます。デビッド・ハフマンの後、最初にそれを作成したのは誰ですか?頻繁に繰り返される文字を含むデータは通常、ハフマン コーディングを使用して圧縮されます。
よく知られている Greedy アルゴリズムは、ハフマン コーディングです。文字に割り当てられるコードのサイズは文字の頻度に依存するため、貪欲なアルゴリズムと呼ばれます。短い長さの可変コードは最も高い頻度の文字に割り当てられ、より低い頻度の文字にはその逆が割り当てられます。可変長エンコーディングを採用しています。これは、提供されたデータ ストリーム内の各文字に異なる可変長コードを与えることを意味します。
プレフィックスルール
基本的に、このルールは、文字に割り当てられるコードが別のコードのプレフィックスであってはいけないことを規定しています。このルールが破られると、作成されたハフマン木をデコードするときにさまざまな曖昧さが現れる可能性があります。
このルールをよりよく理解するために、このルールの図を見てみましょう。文字ごとに、次のようなコードが提供されます。
インターネットを使用して
a - 0 b - 1 c - 01
生成されたビット ストリームが 001 であると仮定すると、コードをデコードすると次のように表現できます。
0 0 1 = aab 0 01 = ac
ハフマン符号化プロセスとは何ですか?
ハフマン コードは、主に 2 つの手順で個別の文字ごとに取得されます。
- まず、提供されたデータ ストリーム内の固有の文字のみを使用してハフマン ツリーを作成します。
- 次に、構築されたハフマン ツリーを処理し、文字にコードを割り当て、それらのコードを使用して提供されたテキストをデコードする必要があります。
ハフマンコーディングの手順
提供された文字を使用してハフマン ツリーを構築するために使用される手順
Input: string str = 'abbcdbccdaabbeeebeab'
この場合、データ圧縮にハフマン符号化が使用される場合、復号化のために次の情報を決定する必要があります。
- 各文字のハフマン コード
- ハフマンエンコードされたメッセージ長 (ビット単位)、平均コード長
- 以下で説明する公式を利用して、最後の 2 つが見つかります。
入力文字からハフマン ツリーを構築するにはどうすればよいですか?
提供された文字列内の各文字の頻度を最初に決定する必要があります。
| キャラクター | 頻度 |
|---|---|
| ある | 4 |
| b | 7 |
| c | 3 |
| d | 2 |
| それは | 4 |
- 文字を頻度順に昇順に並べ替えます。これらは Q/min-heap 優先キューに保持されます。
- データ ストリーム内の個別の文字とその頻度ごとに、リーフ ノードを作成します。
- 最も低い 2 つの周波数を持つ 2 つのノードをノードから削除すると、これらの周波数の合計を使用してツリーの新しいルートが作成されます。
- 最小ヒープから頻度が最も低いノードを抽出しながら、最初に抽出されたノードを左の子にし、2 番目に抽出したノードを右の子にします。
- 最小ヒープにこのノードを追加します。
- ルートの左側には常に最小周波数が含まれている必要があるためです。
- ヒープ上にノードが 1 つだけ残るか、すべての文字がツリー内のノードで表されるまで、手順 3 と 4 を繰り返します。ルートノードだけが残った時点でツリーは完成します。
ハフマンコーディングの例
図を使ってアルゴリズムを説明しましょう。
ハフマン符号化のアルゴリズム
ステップ1： 各ノードが 1 つのノードを持つツリーのルートを表し、5 (提供されたデータ ストリームの一意の文字の数) を保持する最小ヒープを構築します。
ステップ2： ステップ 2 で最小ヒープから 2 つの最小周波数ノードを取得します。 3 番目の内部ノード (周波数 2 + 3 = 5) を追加します。これは、抽出された 2 つのノードを結合することによって作成されます。
- 現在、最小ヒープには 4 つのノードがあり、そのうち 3 つはそれぞれ 1 つの要素を持つツリーのルートであり、そのうちの 1 つは 2 つの要素を持つツリーのルートです。
ステップ 3: ステップ 3 と同様の方法で、ヒープから 2 つの最小周波数ノードを取得します。さらに、抽出された 2 つのノードを結合して形成された新しい内部ノードを追加します。ツリー内の頻度は 4 + 4 = 8 である必要があります。
- 最小ヒープには 3 つのノードがあるため、1 つのノードは 1 つの要素を持つツリーのルートとして機能し、2 つのヒープ ノードは複数のノードを持つツリーのルートとして機能します。
ステップ 4: ステップ 4 で 2 つの最小周波数ノードを取得します。さらに、抽出された 2 つのノードを結合して形成された新しい内部ノードを追加します。ツリー内の頻度は 5 + 7 = 12 になるはずです。
10/60
- ハフマン ツリーを作成するときは、最小値が常に左側にあり、2 番目の値が常に右側にあることを確認する必要があります。現在、以下の画像は形成されたツリーを示しています。
ステップ5: ステップ 5 で、次の 2 つの最小周波数ノードを取得します。さらに、抽出された 2 つのノードを結合して形成される新しい内部ノードを追加します。ツリー内の頻度は 12 + 8 = 20 になるはずです。
すべての個別の文字がツリーに追加されるまで続行します。指定された文字キャストに対して作成されたハフマン ツリーが上の画像に示されています。
ここで、葉以外のノードごとに、左端に 0 を、右端に 1 を割り当てて、各文字のコードを作成します。
エッジの重みを決定するために従うべきルール:
- 左エッジの重みを 0 に設定する場合は、右エッジの重みを 1 に設定する必要があります。
- 左エッジに重み 1 が与えられる場合、右エッジには重み 0 が与えられる必要があります。
- 前述の 2 つの規則のいずれも使用できます。
- ただし、ツリーをデコードするときも同じプロトコルに従います。
重み付けの後、変更されたツリーは次のように表示されます。
コードを理解する
- 結果として得られるハフマン ツリーから各文字のハフマン コードをデコードするには、要素が存在するリーフ ノードに到達するまでハフマン ツリーをたどる必要があります。
- ノード全体の重みはトラバーサル中に記録され、特定のリーフ ノードにある項目に割り当てられる必要があります。
- 次の例は、その意味をさらに説明するのに役立ちます。
- 上の図の各文字のコードを取得するには、ツリー全体を (すべての葉ノードがカバーされるまで) 歩く必要があります。
- その結果、作成されたツリーは、各ノードのコードをデコードするために使用されます。以下は各文字のコードのリストです。
| キャラクター | 頻度・回数 | コード |
|---|---|---|
| ある | 4 | 01 |
| b | 7 | 十一 |
| c | 3 | 101 |
| d | 2 | 100 |
| それは | 4 | 00 |
以下は C プログラミングでの実装です。
// C program for Huffman Coding #include #include // This constant can be avoided by explicitly // calculating height of Huffman Tree #define MAX_TREE_HT 100 // A Huffman tree node struct MinHeapNode { // One of the input characters char data; // Frequency of the character unsigned freq; // Left and right child of this node struct MinHeapNode *left, *right; }; // A Min Heap: Collection of // min-heap (or Huffman tree) nodes struct MinHeap { // Current size of min heap unsigned size; // capacity of min heap unsigned capacity; // Array of minheap node pointers struct MinHeapNode** array; }; // A utility function allocate a new // min heap node with given character // and frequency of the character struct MinHeapNode* newNode(char data, unsigned freq) { struct MinHeapNode* temp = (struct MinHeapNode*)malloc( sizeof(struct MinHeapNode)); temp->left = temp->right = NULL; temp->data = data; temp->freq = freq; return temp; } // A utility function to create // a min heap of given capacity struct MinHeap* createMinHeap(unsigned capacity) { struct MinHeap* minHeap = (struct MinHeap*)malloc(sizeof(struct MinHeap)); // current size is 0 minHeap->size = 0; minHeap->capacity = capacity; minHeap->array = (struct MinHeapNode**)malloc( minHeap->capacity * sizeof(struct MinHeapNode*)); return minHeap; } // A utility function to // swap two min heap nodes void swapMinHeapNode(struct MinHeapNode** a, struct MinHeapNode** b) { struct MinHeapNode* t = *a; *a = *b; *b = t; } // The standard minHeapify function. void minHeapify(struct MinHeap* minHeap, int idx) { int smallest = idx; int left = 2 * idx + 1; int right = 2 * idx + 2; if (left size && minHeap->array[left]->freq array[smallest]->freq) smallest = left; if (right size && minHeap->array[right]->freq array[smallest]->freq) smallest = right; if (smallest != idx) { swapMinHeapNode(&minHeap->array[smallest], &minHeap->array[idx]); minHeapify(minHeap, smallest); } } // A utility function to check // if size of heap is 1 or not int isSizeOne(struct MinHeap* minHeap) { return (minHeap->size == 1); } // A standard function to extract // minimum value node from heap struct MinHeapNode* extractMin(struct MinHeap* minHeap) { struct MinHeapNode* temp = minHeap->array[0]; minHeap->array[0] = minHeap->array[minHeap->size - 1]; --minHeap->size; minHeapify(minHeap, 0); return temp; } // A utility function to insert // a new node to Min Heap void insertMinHeap(struct MinHeap* minHeap, struct MinHeapNode* minHeapNode) { ++minHeap->size; int i = minHeap->size - 1; while (i && minHeapNode->freq array[(i - 1) / 2]->freq) { minHeap->array[i] = minHeap->array[(i - 1) / 2]; i = (i - 1) / 2; } minHeap->array[i] = minHeapNode; } // A standard function to build min heap void buildMinHeap(struct MinHeap* minHeap) { int n = minHeap->size - 1; int i; for (i = (n - 1) / 2; i >= 0; --i) minHeapify(minHeap, i); } // A utility function to print an array of size n void printArr(int arr[], int n) { int i; for (i = 0; i left) && !(root->right); } // Creates a min heap of capacity // equal to size and inserts all character of // data[] in min heap. Initially size of // min heap is equal to capacity struct MinHeap* createAndBuildMinHeap(char data[], int freq[], int size) { struct MinHeap* minHeap = createMinHeap(size); for (int i = 0; i array[i] = newNode(data[i], freq[i]); minHeap->size = size; buildMinHeap(minHeap); return minHeap; } // The main function that builds Huffman tree struct MinHeapNode* buildHuffmanTree(char data[], int freq[], int size) { struct MinHeapNode *left, *right, *top; // Step 1: Create a min heap of capacity // equal to size. Initially, there are // modes equal to size. struct MinHeap* minHeap = createAndBuildMinHeap(data, freq, size); // Iterate while size of heap doesn't become 1 while (!isSizeOne(minHeap)) { // Step 2: Extract the two minimum // freq items from min heap left = extractMin(minHeap); right = extractMin(minHeap); // Step 3: Create a new internal // node with frequency equal to the // sum of the two nodes frequencies. // Make the two extracted node as // left and right children of this new node. // Add this node to the min heap // '$' is a special value for internal nodes, not // used top = newNode('$', left->freq + right->freq); top->left = left; top->right = right; insertMinHeap(minHeap, top); } // Step 4: The remaining node is the // root node and the tree is complete. return extractMin(minHeap); } // Prints huffman codes from the root of Huffman Tree. // It uses arr[] to store codes void printCodes(struct MinHeapNode* root, int arr[], int top) { // Assign 0 to left edge and recur if (root->left) { arr[top] = 0; printCodes(root->left, arr, top + 1); } // Assign 1 to right edge and recur if (root->right) { arr[top] = 1; printCodes(root->right, arr, top + 1); } // If this is a leaf node, then // it contains one of the input // characters, print the character // and its code from arr[] if (isLeaf(root)) { printf('%c: ', root->data); printArr(arr, top); } } // The main function that builds a // Huffman Tree and print codes by traversing // the built Huffman Tree void HuffmanCodes(char data[], int freq[], int size) { // Construct Huffman Tree struct MinHeapNode* root = buildHuffmanTree(data, freq, size); // Print Huffman codes using // the Huffman tree built above int arr[MAX_TREE_HT], top = 0; printCodes(root, arr, top); } // Driver code int main() { char arr[] = { 'a', 'b', 'c', 'd', 'e', 'f' }; int freq[] = { 5, 9, 12, 13, 16, 45 }; int size = sizeof(arr) / sizeof(arr[0]); HuffmanCodes(arr, freq, size); return 0; } 出力
f: 0 c: 100 d: 101 a: 1100 b: 1101 e: 111 …………… Process executed in 1.11 seconds Press any key to continue.
上記のコードの Java 実装:
import java.util.Comparator; import java.util.PriorityQueue; import java.util.Scanner; class Huffman { // recursive function to print the // huffman-code through the tree traversal. // Here s is the huffman - code generated. public static void printCode(HuffmanNode root, String s) { // base case; if the left and right are null // then its a leaf node and we print // the code s generated by traversing the tree. if (root.left == null && root.right == null && Character.isLetter(root.c)) { // c is the character in the node System.out.println(root.c + ':' + s); return; } // if we go to left then add '0' to the code. // if we go to the right add'1' to the code. // recursive calls for left and // right sub-tree of the generated tree. printCode(root.left, s + '0'); printCode(root.right, s + '1'); } // main function public static void main(String[] args) { Scanner s = new Scanner(System.in); // number of characters. int n = 6; char[] charArray = { 'a', 'b', 'c', 'd', 'e', 'f' }; int[] charfreq = { 5, 9, 12, 13, 16, 45 }; // creating a priority queue q. // makes a min-priority queue(min-heap). PriorityQueue q = new PriorityQueue( n, new MyComparator()); for (int i = 0; i <n; i++) { creating a huffman node object and add it to the priority queue. huffmannode hn="new" huffmannode(); hn.c="charArray[i];" hn.data="charfreq[i];" hn.left="null;" hn.right="null;" functions adds q.add(hn); } create root here we will extract two minimum value from heap each time until its size reduces 1, all nodes are extracted. while (q.size()> 1) { // first min extract. HuffmanNode x = q.peek(); q.poll(); // second min extract. HuffmanNode y = q.peek(); q.poll(); // new node f which is equal HuffmanNode f = new HuffmanNode(); // to the sum of the frequency of the two nodes // assigning values to the f node. f.data = x.data + y.data; f.c = '-'; // first extracted node as left child. f.left = x; // second extracted node as the right child. f.right = y; // marking the f node as the root node. root = f; // add this node to the priority-queue. q.add(f); } // print the codes by traversing the tree printCode(root, ''); } } // node class is the basic structure // of each node present in the Huffman - tree. class HuffmanNode { int data; char c; HuffmanNode left; HuffmanNode right; } // comparator class helps to compare the node // on the basis of one of its attribute. // Here we will be compared // on the basis of data values of the nodes. class MyComparator implements Comparator { public int compare(HuffmanNode x, HuffmanNode y) { return x.data - y.data; } } </n;> 出力
f: 0 c: 100 d: 101 a: 1100 b: 1101 e: 111 ………………. Process executed in 1.11 seconds Press any key to continue.
説明：
トラバースすることにより、ハフマン ツリーが作成され、デコードされます。走査中に収集された値は、リーフ ノードにある文字に適用されます。供給されたデータ ストリーム内のすべての一意の文字は、この方法でハフマン コードを使用して識別できます。 O (nlogn) (n は文字の総数) は時間計算量です。 n 個のノードがある場合、ExtractMin() は 2*(n - 1) 回呼び出されます。 extractMin() は minHeapify() を呼び出すため、その実行時間は O (logn) です。したがって、合計の複雑さは O (nlogn) になります。入力配列がソートされている場合は、線形時間アルゴリズムがあります。これについては、今後の記事で詳しく説明します。
ハフマンコーディングの問題
この部分では、ハフマン コーディングの欠点と、それが必ずしも最良の選択肢ではない理由について説明しましょう。
レカ映画女優
- すべての文字の確率または頻度が 2 の負の累乗ではない場合、それは理想的とは見なされません。
- 記号をグループ化してアルファベットを拡張することで理想に近づくこともできますが、ブロック化する方法ではより大きなアルファベットを扱う必要があります。したがって、ハフマン符号化は必ずしも効果的であるとは限りません。
- 各シンボルや文字の頻度をカウントする効果的な方法は数多くありますが、それぞれのツリー全体を再構成するには非常に時間がかかる場合があります。アルファベットが大きく、記号ごとに確率分布が急速に変化する場合、これは一般的に当てはまります。
貪欲なハフマン コード構築アルゴリズム
- ハフマンは、入力データ ストリーム内の個別の文字ごとに、理想的なプレフィックス コードであるハフマン コードを生成する貪欲な手法を開発しました。
- このアプローチでは、毎回最も少ないノードを使用してハフマン ツリーをボトムアップで作成します。
- 各文字は、指定されたデータ ストリーム内での出現頻度に基づいてコード長を受け取るため、この方法は貪欲なアプローチとして知られています。取得されるコードのサイズが小さい場合、これはデータ内に一般的に発生する要素です。
ハフマン符号化の使用
- ここでは、ハフマンコーディングの実際的な使用法について説明します。
- PKZIP、GZIP などの従来の圧縮形式は、通常、ハフマン符号化を使用します。
- ハフマン符号化は、ファイル サイズを最小限に抑え、転送速度を向上させるため、FAX やテキストによるデータ転送に使用されます。
- ハフマン エンコーディング (特にプレフィックス コード) は、JPEG、PNG、MP3 などのいくつかのマルチメディア ストレージ形式でファイルを圧縮するために使用されます。
- ハフマン符号化は主に画像圧縮に使用されます。
- 頻繁に出現する文字列を送信する必要がある場合は、さらに便利です。
結論
- 一般に、ハフマン コーディングは、頻繁に出現する文字を含むデータを圧縮するのに役立ちます。
- 最も頻繁に出現する文字のコードは最も短く、最も出現頻度の低い文字のコードは最大であることがわかります。
- ハフマン コード圧縮技術は、文字または記号ごとにさまざまな量のビットを使用する可変長コーディングを作成するために使用されます。この方法は、使用するメモリが少なく、データをより速く送信できるため、固定長コーディングよりも優れています。
- この記事を読んで、貪欲アルゴリズムについての知識を深めてください。