霍夫曼算法

霍夫曼编码 (Huffman coding)

• Huffman Algorithm was developed by David Huffman in 1951.

  Huffman算法由David Huffman在1951年开发。

• This is a technique which is used in a data compression or it can be said that it is a coding technique which is used for encoding data.

  这是用于数据压缩的技术，或者可以说是用于编码数据的编码技术。

• This technique is a mother of all data compression scheme.

  该技术是所有数据压缩方案的基础。

• This idea is basically dependent upon the frequency, i.e. the frequency of the corresponding character which needs to be compressed, and by that frequency, only Huffman code will be generated.

  该思想基本上取决于频率，即，需要压缩的相应字符的频率，并且根据该频率，将仅生成霍夫曼码。

• In case of Huffman coding, the most generated character will get the small code and least generated character will get the large code.

  对于霍夫曼编码，生成最多的字符将获得小代码，生成最少的字符将获得大代码。

• Huffman tree is a specific method of representing each symbol.

  霍夫曼树是表示每个符号的一种特定方法。

• This technique produces a code in such a manner that no codeword is a prefix of some other code word. These codes are called as prefix code.

  该技术以这样的方式产生代码：没有代码字是某个其他代码字的前缀。 这些代码称为前缀代码。

霍夫曼编码算法 (Algorithm for Huffman code)

    1.	Input:-Number of message with frequency count.
    2.	Output: - Huffman merge tree.
    3.	Begin
    4.	Let Q be the priority queue,
    5.	Q= {initialize priority queue with frequencies of all symbol or message}
    6.	Repeat n-1 times 
    7.	Create a new node Z 
    8.	X=extract_min(Q)
    9.	Y=extract_min(Q)
    10.	Frequency(Z) =Frequency(X) +Frequency(y);
    11.	Insert (Z, Q)
    12.	End repeat 
    13.	Return (extract_min(Q))
    14.	End.

Example:

例：

Let obtain a set of Huffman code for the message (m1.....m7) with relative frequencies (q1.....q7) = (4,5,7,8,10,12,20). Let us draw the Huffman tree for the given set of codes.

让我们为消息(m1 ..... m7)获得一组霍夫曼代码，其相对频率(q1 ..... q7)=(4,5,7,8,10,12,20) 。 让我们为给定的代码集绘制霍夫曼树。

Step 1) Arrange the data in ascending order in a table.

步骤1)在表中按升序排列数据。

4,5,7,8,10,12,20

4,5,7,8,10,12,20

Step 2) Combine first two entries of a table and by this create a parent node.

步骤2)合并表的前两个条目，并由此创建一个父节点。

Step 3)

步骤3)

A) Remove the entries 4 and 5 from the table and inert 9 at its appropriate position. 7,8,9,10,12,20

A)从表中删除条目4和5，并在适当位置插入9。 7,8,9,10,12,20

Combine minimum value of table and create a parent node.

合并表的最小值并创建一个父节点。

B) Now remove the entries 7 and 8 from the table and insert 15 at its appropriate position. 9,10,12,15,20

B)现在从表中删除条目7和8，并在其适当位置插入15。 9,10,12,15,20

Combine minimum value of two blocks and create a parent node.

合并两个块的最小值并创建一个父节点。

C) Remove the entries 9 and 10 from the table and insert 19 at its proper position. 12,15,19,20.

C)从表中删除条目9和10，并在其适当位置插入19。 12,15,19,20。

Combine minimum value of two blocks and create parent node.

合并两个块的最小值并创建父节点。

D) Remove the entries 15 and 12 from the table and insert 27 at its appropriate position. 19,20,27

D)从桌子上取下入口15和12，并在其适当位置插入27。 19,20,27

Combine minimum value of two blocks and create parent node.

合并两个块的最小值并创建父节点。

E) Remove the entries 19 and 20 from the table and insert 39 in the table. 27,39

E)从表中删除条目19和20，然后在表中插入39。 27,39

Combine minimum value of two blocks and create parent node.

合并两个块的最小值并创建父节点。

Step 4) Now assign left child as 0 and right child as 1 to encode the frequencies.

步骤4)现在将左子级分配为0，右子级分配为1以对频率进行编码。

Now, codes for the given frequencies are given below:

现在，给定频率的代码如下：

时间复杂度： (Time complexity:)

O(nlogn) is the overall time complexity. Where n is the number of characters.

O(nlogn)是整体时间复杂度。 其中n是字符数。

翻译自: https://www.includehelp.com/algorithms/huffman-coding-algorithm-example-and-time-complexity.aspx

霍夫曼算法