ハフマン符号化は、可逆データ圧縮アルゴリズムです。アイデアは、入力文字に可変長コードを割り当てることです。割り当てられるコードの長さは、対応する文字の頻度に基づいています。
入力文字に割り当てられる可変長コードは次のとおりです。 プレフィックスコード , ある文字に割り当てられたコードが他の文字に割り当てられたコードのプレフィックスにならないように、コード (ビット シーケンス) が割り当てられていることを意味します。このようにして、ハフマン コーディングでは、生成されたビットストリームをデコードするときにあいまいさがなくなるようにします。
反例を挙げてプレフィックス コードを理解しましょう。 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++

>   
 
     
 
     
 
  
     
   
  
     
  
     
     
     
  
 
  
  
  
  
  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 によって寄稿されました>>  
  
  
  
  
 
     
 
   
 
     
 
   
 
  
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 チームによってレビューされました。