ハフマン符号化は、可逆データ圧縮アルゴリズムです。アイデアは、入力文字に可変長コードを割り当てることです。割り当てられるコードの長さは、対応する文字の頻度に基づいています。
入力文字に割り当てられる可変長コードは次のとおりです。 プレフィックスコード , ある文字に割り当てられたコードが他の文字に割り当てられたコードのプレフィックスにならないように、コード (ビット シーケンス) が割り当てられていることを意味します。このようにして、ハフマン コーディングでは、生成されたビットストリームをデコードするときにあいまいさがなくなるようにします。
反例を挙げてプレフィックス コードを理解しましょう。 4 つの文字 a、b、c、d があり、それらに対応する可変長コードが 00、01、0、1 であるとします。c に割り当てられたコードは、a と b に割り当てられたコードのプレフィックスであるため、このコーディングではあいまいさが生じます。圧縮されたビット ストリームが 0001 の場合、解凍された出力は cccd、ccb、acd、または ab になります。
見る これ ハフマンコーディングのアプリケーション向け。
ハフマンコーディングには主に 2 つの主要な部分があります

1. 入力文字からハフマン ツリーを構築します。
2. ハフマン ツリーをたどって、文字にコードを割り当てます。

アルゴリズム：

最適なプレフィックス コードを構築するために使用されるメソッドは、と呼ばれます。 ハフマン符号化 。

このアルゴリズムはボトムアップ方式でツリーを構築します。この木は次のように表すことができます。 T

|c| としましょう。葉の数になる

|c| -1 は、ノードをマージするために必要な操作の数です。 Q は、バイナリ ヒープの構築中に使用できる優先キューになります。

Algorithm Huffman (c) { n= |c| Q = c for i<-1 to n-1 do { temp <- get node () left (temp] Get_min (Q) right [temp] Get Min (Q) a = left [templ b = right [temp] F [temp]<- f[a] + [b] insert (Q, temp) } return Get_min (0) }>

ハフマンツリーを構築する手順
入力は一意の文字の配列とその出現頻度であり、出力はハフマン ツリーです。

1. 一意の文字ごとにリーフ ノードを作成し、すべてのリーフ ノードの最小ヒープを構築します (最小ヒープは優先キューとして使用されます。頻度フィールドの値は、最小ヒープ内の 2 つのノードを比較するために使用されます。最初は、最も頻度の低い文字は次のとおりです)根）
2. 最小ヒープから最小頻度の 2 つのノードを抽出します。
   
3. 2 つのノードの周波数の合計に等しい周波数を持つ新しい内部ノードを作成します。最初に抽出されたノードをその左の子として作成し、もう一方の抽出されたノードをその右の子として作成します。このノードを最小ヒープに追加します。
4. ヒープにノードが 1 つだけ含まれるまで、手順 2 と 3 を繰り返します。残りのノードはルート ノードであり、ツリーが完成します。
   例を挙げてアルゴリズムを理解しましょう。

character Frequency a 5 b 9 c 12 d 13 e 16 f 45>

ステップ1。 6 つのノードを含む最小ヒープを構築します。各ノードは単一ノードのツリーのルートを表します。
ステップ2 最小ヒープから 2 つの最小周波数ノードを抽出します。周波数 5 + 9 = 14 の新しい内部ノードを追加します。

ステップ 2 の図

最小ヒープには 5 つのノードが含まれます。そのうち 4 つのノードはそれぞれ 1 つの要素を持つツリーのルートであり、1 つのヒープ ノードは 3 つの要素を持つツリーのルートです。

コート

character Frequency c 12 d 13 Internal Node 14 e 16 f 45>

ステップ 3: ヒープから 2 つの最小周波数ノードを抽出します。周波数 12 + 13 = 25 の新しい内部ノードを追加します。

ステップ 3 の図

最小ヒープには 4 つのノードが含まれます。そのうち 2 つのノードはそれぞれ 1 つの要素を持つツリーのルートであり、2 つのヒープ ノードは複数のノードを持つツリーのルートです。

character Frequency Internal Node 14 e 16 Internal Node 25 f 45>

ステップ 4: 2 つの最小周波数ノードを抽出します。周波数 14 + 16 = 30 の新しい内部ノードを追加します。

ステップ 4 の図

現在、最小ヒープには 3 つのノードが含まれています。

character Frequency Internal Node 25 Internal Node 30 f 45>

ステップ5: 2 つの最小周波数ノードを抽出します。周波数 25 + 30 = 55 の新しい内部ノードを追加します。

ステップ5の図

現在、最小ヒープには 2 つのノードが含まれています。

character Frequency f 45 Internal Node 55>

ステップ6: 2 つの最小周波数ノードを抽出します。周波数 45 + 55 = 100 の新しい内部ノードを追加します。

ステップ6の図

現在、最小ヒープにはノードが 1 つだけ含まれています。

character Frequency Internal Node 100>

ヒープにはノードが 1 つしか含まれていないため、アルゴリズムはここで停止します。

ハフマン ツリーからコードを出力する手順:
ルートから開始して形成されたツリーを横断します。補助配列を維持します。左側の子に移動しながら、配列に 0 を書き込みます。右側の子に移動しながら、配列に 1 を書き込みます。リーフノードが見つかったときに配列を出力します。

HuffmanTree からコードを出力する手順

コードは次のとおりです。

character code-word f 0 c 100 d 101 a 1100 b 1101 e 111>

上記のアプローチの実装を以下に示します。

C

>

>

C++

>

>

C++

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     // 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;     // add functions adds   // the huffman node to the queue.   q.add(hn);   }     // create a root node   HuffmanNode root = null;     // Here we will extract the two minimum value   // from the heap each time until   // its size reduces to 1, extract until   // all the nodes are extracted.   while (q.size()>1) { // 最初の部分を抽出します。   HuffmanNode x = q.peek();   q.poll();     // 2 番目の分を抽出します。   HuffmanNode y = q.peek();   q.poll();     // HuffmanNode と等しい新しいノード f = new HuffmanNode();     // 2 つのノードの周波数の合計に // 値を f ノードに割り当てます。   f.データ = x.データ + y.データ;   f.c = '-';     // 最初にノードを左の子として抽出します。   f.left = x;     // 2 番目に右側の子として抽出されたノード。   f.right = y;     // f ノードをルート ノードとしてマークします。   ルート = f;     // このノードを優先キューに追加します。   q.add(f);   } // ツリーをたどってコードを出力します printCode(root, '');   } } // ノード クラスは、ハフマン ツリーに存在する // 各ノードの基本構造です。  クラス HuffmanNode { int データ;   文字c;     ハフマンノードは去りました。   ハフマンノード右。  } // コンパレータ クラスは、 // 属性の 1 つに基づいてノードを比較するのに役立ちます。  // ここでは、 // ノードのデータ値に基づいて比較されます。  class MyComparator は Comparator { public int Compare(HuffmanNode x, HuffmanNode y) { return x.data - y.data; を実装します。   } } // このコードは Kunwar Desh Deepak Singh によって寄稿されました>>
 
 
 
 
    
 
>
 
    
 
>
 
.tif ファイル
 
Python3
    
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 # A Huffman Tree Node> import> heapq> > > class> node:> >def> __init__(>self>, freq, symbol, left>=>None>, right>=>None>):> ># frequency of symbol> >self>.freq>=> freq> > ># symbol name (character)> >self>.symbol>=> symbol> > ># node left of current node> >self>.left>=> left> > ># node right of current node> >self>.right>=> right> > ># tree direction (0/1)> >self>.huff>=> ''> > >def> __lt__(>self>, nxt):> >return> self>.freq      # utility function to print huffman  # codes for all symbols in the newly  # created Huffman tree  def printNodes(node, val=''):     # huffman code for current node   newVal = val + str(node.huff)     # if node is not an edge node   # then traverse inside it   if(node.left):   printNodes(node.left, newVal)   if(node.right):   printNodes(node.right, newVal)     # if node is edge node then   # display its huffman code   if(not node.left and not node.right):   print(f'{node.symbol} ->{newVal}') # ハフマン ツリー文字の文字数 = ['a', 'b', 'c', 'd', 'e', 'f'] # 文字の頻度 freq = [5, 9, 12, 13, 16, 45] # 未使用のノードを含むリスト nodes = [] # 文字と頻度を # ハフマンツリーノードに変換 for x in range(len(chars)): heapq .heappush(nodes, node(freq[x], chars[x])) while len(nodes)> 1: # すべてのノードを昇順に並べ替えます # 周波数に基づいて left = heapq.heappop(nodes) right = heapq .heappop(nodes) # これらのノードに方向の値を割り当てます left.huff = 0 right.huff = 1 # 2 つの最小ノードを結合して、 # 新しいノードを親として作成します newNode = node(left.freq+right.freq, left. symbol+right.symbol, left, right) heapq.heappush(nodes, newNode) # ハフマン ツリーの準備ができました。  printNodes(nodes[0])>>
 
 
 
 
    
 
>
 
    
 
>
 
 
JavaScript
    
 
     
  
から助ける
 
    
 
     
     
    
 
 
 
 
 
 > > // node class is the basic structure> // of each node present in the Huffman - tree.> class HuffmanNode> {> >constructor()> >{> >this>.data = 0;> >this>.c =>''>;> >this>.left =>this>.right =>null>;> >}> }> > // recursive function to print the> >// huffman-code through the tree traversal.> >// Here s is the huffman - code generated.> >function> printCode(root,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> >&& (root.c).toLowerCase() != (root.c).toUpperCase()) {> > >// c is the character in the node> >document.write(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> // number of characters.> >let n = 6;> >let charArray = [>'a'>,>'b'>,>'c'>,>'d'>,>'e'>,>'f'> ];> >let charfreq = [ 5, 9, 12, 13, 16, 45 ];> > >// creating a priority queue q.> >// makes a min-priority queue(min-heap).> >let q = [];> > >for> (let i = 0; i     // creating a Huffman node object   // and add it to the priority queue.   let hn = new HuffmanNode();     hn.c = charArray[i];   hn.data = charfreq[i];     hn.left = null;   hn.right = null;     // add functions adds   // the huffman node to the queue.   q.push(hn);   }     // create a root node   let root = null;   q.sort(function(a,b){return a.data-b.data;});     // Here we will extract the two minimum value   // from the heap each time until   // its size reduces to 1, extract until   // all the nodes are extracted.   while (q.length>1) { // 最初の部分を抽出します。   x = q[0] とします。   q.shift();     // 2 番目の分を抽出します。   y = q[0] とします。   q.shift();     // 等しい新しいノード f let f = new HuffmanNode();     // 2 つのノードの周波数の合計に // 値を f ノードに割り当てます。   f.データ = x.データ + y.データ;   f.c = '-';     // 最初にノードを左の子として抽出します。   f.left = x;     // 2 番目に右側の子として抽出されたノード。   f.right = y;     // f ノードをルート ノードとしてマークします。   ルート = f;     // このノードを優先キューに追加します。   q.push(f);   q.sort(function(a,b){return a.data-b.data;});   } // ツリーをたどってコードを出力します printCode(root, '');    // このコードは avanitrachhadiya2155 によって寄稿されました>>
 
 
 
 
    
 
>
 
    
 
>
 
 
C#
    
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 // C# program for the above approach> > using> System;> using> System.Collections.Generic;> > // A Huffman tree node> public> class> MinHeapNode> {> >// One of the input characters> >public> char> data;> > >// Frequency of the character> >public> uint> freq;> > >// Left and right child> >public> MinHeapNode left, right;> > >public> MinHeapNode(>char> data,>uint> freq)> >{> >left = right =>null>;> >this>.data = data;> >this>.freq = freq;> >}> }> > // For comparison of two heap nodes (needed in min heap)> public> class> CompareMinHeapNode : IComparer> {> >public> int> Compare(MinHeapNode x, MinHeapNode y)> >{> >return> x.freq.CompareTo(y.freq);> >}> }> > class> Program> {> >// Prints huffman codes from the root of Huffman Tree.> >static> void> printCodes(MinHeapNode root,>string> str)> >{> >if> (root ==>null>)> >return>;> > >if> (root.data !=>'$'>)> >Console.WriteLine(root.data +>': '> + str);> > >printCodes(root.left, str +>'0'>);> >printCodes(root.right, str +>'1'>);> >}> > >// The main function that builds a Huffman Tree and> >// print codes by traversing the built Huffman Tree> >static> void> HuffmanCodes(>char>[] data,>uint>[] freq,>int> size)> >{> >MinHeapNode left, right, top;> > >// Create a min heap & inserts all characters of data[]> >var> minHeap =>new> SortedSet(>new> CompareMinHeapNode());> > >for> (>int> i = 0; i   minHeap.Add(new MinHeapNode(data[i], freq[i]));     // Iterate while size of heap doesn't become 1   while (minHeap.Count != 1)   {   // Extract the two minimum freq items from min heap   left = minHeap.Min;   minHeap.Remove(left);     right = minHeap.Min;   minHeap.Remove(right);     // 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 = new MinHeapNode('$', left.freq + right.freq);     top.left = left;   top.right = right;     minHeap.Add(top);   }     // Print Huffman codes using the Huffman tree built above   printCodes(minHeap.Min, '');   }     // Driver Code   static void Main()   {   char[] arr = { 'a', 'b', 'c', 'd', 'e', 'f' };   uint[] freq = { 5, 9, 12, 13, 16, 45 };     int size = arr.Length;     HuffmanCodes(arr, freq, size);   }  }    // This code is contributed by sdeadityasharma>
 
 
 
 
    
 
>
 
    
 
>
 
  出力  
 
f: 0 c: 100 d: 101 a: 1100 b: 1101 e: 111>
 
  時間計算量: O(nlogn) ここで、n は一意の文字の数です。 n 個のノードがある場合、extractMin() は 2*(n – 1) 回呼び出されます。 extractMin() は minHeapify() を呼び出すため、O(logn) 時間がかかります。したがって、全体的な複雑さは O(nlogn) です。 
入力配列がソートされている場合、線形時間アルゴリズムが存在します。これについては、次回の投稿ですぐに説明します。
 
  空間の複雑さ :- O(N)  
 
ハフマン符号化の応用:
 
 
ファックスやテキストの送信に使用されます。
 
これらは、PKZIP、GZIP などの従来の圧縮形式で使用されます。
 
JPEG、PNG、MP3 などのマルチメディア コーデックは、ハフマン エンコーディング (より正確にはプレフィックス コード) を使用します。
 
 
頻繁に出現する文字が連続する場合に便利です。
 
    参照：     
  http://en.wikipedia.org/wiki/Huffman_coding   
この記事は Aashish Barnwal によって編集され、techcodeview.com チームによってレビューされました。