使用 Python 进行霍夫曼编码

霍夫曼编码是一种基于文本中字符频率的无损压缩和编码文本的方法。在信息论和计算机科学研究中，霍夫曼码是一种特殊类型的最优前缀码，通常用于无损数据压缩。

在下面的教程中，我们将了解霍夫曼编码的理论及其使用Python编程语言的实现。在此之前，让我们简要了解一下霍夫曼编码。

理解霍夫曼编码

霍夫曼编码是一种用于数据压缩的无损压缩算法。它是由David A. Huffman在他作为麻省理工学院 (MIT) 的理学博士生时开发的算法，于1952年发表在论文“一种构造最小冗余码的方法”中。它是他计算机编程研究的一部分，通常可以在C、C++、Python、Java、JavaScript、Ruby等编程语言中找到。霍夫曼编码背后的思想如下：

频繁出现的字母或符号使用较短的代码表示，而不频繁出现的字母或符号使用较长的代码表示。

这种思想使得字符的表示更高效，需要更少的内存来存储。因此，我们可以得出结论，我们可以使用霍夫曼编码作为数据压缩方法。

现在让我们了解霍夫曼编码的理论。

理解霍夫曼编码的理论

我们知道文件以二进制代码存储在计算机上，并且文件中的每个字符都被分配了一个二进制字符，并且字符代码通常对于不同的字符具有固定长度。霍夫曼编码是根据文件中每个字符出现的频率以及数据结构中频率为零 (0) 的字符数建立的。典型文本文件的霍夫曼编码可以节省实际数据大小的约40%。因此，像编译后的可执行文件一样，霍夫曼二进制代码也将具有独特的空间节省。其中ASCII字符以0.5的频率编码的二进制文件将具有与其ASCII等效文件非常不同的频率和分布。

为了使用字符序列压缩文件，我们需要一个表格，该表格提供每个字符使用的位序列。该表格生成一个编码树，该树利用根/叶路径来创建编码字符的位序列。我们可以沿着根和叶来创建具有编码字符最大位长度和出现次数的字符列表。

我们可以使用贪婪算法来构建最优树。霍夫曼编码树返回用于压缩数据的最短字符编码。树中的节点表示字符出现的频率。根节点表示字符串的长度，遍历树可以得到指定给字符的编码。一旦树构建完成，遍历树就可以得到每个符号的相应代码。

完成后的最优树如以下表格和图片所示

现在让我们在下一节中开发和实现一个使用霍夫曼编码的程序。

使用Python实现霍夫曼编码

我们将从创建一个名为Nodes的类开始，它指的是二叉霍夫曼树的节点。本质上，每个节点都包含一个符号和相关的概率变量、左和右子节点以及代码变量。根据我们在遍历霍夫曼树时选择的侧（左为0，右为1），代码变量将是0或1。

让我们看下面的代码片段来说明这一点：

示例

说明

在上面的代码片段中，我们定义了一个名为Nodes的类，并初始化了一些参数，如概率、符号、左和右。我们最初将左和右变量的值设置为None，因为方向尚未定义。最后，我们还初始化了代码变量。

现在，我们将添加一些支持函数。第一个函数是计算给定数据中符号的概率。第二个函数是获取符号的编码，我们将在拥有霍夫曼树后使用它。最后一个函数是获取结果（编码数据）。

示例

说明

在上面的代码片段中，我们定义了三个不同的辅助函数，用于计算给定数据中符号的概率、获取符号的编码以及获取结果。

对于第一个函数，我们定义了一个字典名为the_symbols，并使用for循环遍历给定数据中的项，并将它们插入字典中。我们还使用了if-else条件语句来检查数据是否包含某些元素并相应地执行操作。

对于第二个函数，我们定义了另一个字典名为the_codes。在函数中，我们分配了一个变量来存储当前节点的霍夫曼代码，并使用if条件语句将节点添加到当前节点的左侧和右侧，并返回符号编码。

对于最后一个函数，我们创建了一个空数组。然后我们使用for循环遍历数据中的字符，并使用append()函数将数据添加到数组中。然后我们使用join()函数将数组中的元素连接到字符串中并返回字符串。

此外，我们还将定义另一个名为TotalGain的函数，它接受初始数据和来自CalculateCode的字典，其中包含符号及其代码。该函数将帮助我们计算压缩数据和未压缩数据的位大小之间的差异。

让我们看下面的代码片段来说明这一点：

示例

说明

在上面的代码片段中，我们定义了该函数。我们计算了压缩前存储数据所需的总比特空间。然后我们定义了一个变量来存储数据压缩后的比特空间大小并将其设置为零。然后我们遍历了来自CalculateCode函数字典的键并计算了它们的出现次数。然后我们计算了压缩后存储数据所需的比特空间。

我们将使用HuffmanEncoding函数，它只接受数据作为参数，并使用上述所有函数返回结果编码和总增益。

让我们通过以下代码片段来理解这一点：

示例

说明

在上面的代码片段中，我们使用了数据参数，使用CalculateProbability函数计算了符号的概率，并将结果数据存储在一个变量中。然后我们提取了符号（键）和概率（值）并打印给用户。然后我们定义了一个数组名为the_nodes，并将符号和概率转换为霍夫曼树的节点。我们使用for循环遍历符号并将它们附加到数组中。我们还使用了while循环来根据它们的概率按升序对节点进行排序。我们选择了两个最小的节点并将它们组合成一个新节点。我们从数组中删除了最小的节点并添加了新节点。然后我们使用了CalculateCodes函数来计算霍夫曼编码的代码并打印带有代码的符号给用户。我们还使用了TotalGain函数，提供所需的参数来计算压缩数据和未压缩数据的位空间之间的差异。最后，我们打印了结果并返回了encodedOutput和数组的第零个索引。

现在，我们将定义一个函数来解码霍夫曼编码数据，以再次获得初始的未压缩数据，这是一个非常简单的过程。

让我们考虑以下代码片段，它演示了霍夫曼编码数据的解码过程。

示例

说明

在上面的代码片段中，我们定义了一个名为HuffmanDecoding的函数，它接受两个参数：encodedData和huffmanTree。然后我们将huffmanTree变量分配给另一个变量。我们还定义了一个空数组名为decodedOutput。然后我们使用for循环遍历编码数据中的元素。在循环中，我们使用了if-elif-else条件语句和try-exception方法来解码编码数据并将每个解码元素附加以生成解码输出。最后，我们创建了一个字符串并返回该字符串供用户使用。

现在，让我们初始化字符串数据并打印结果。

示例

说明

在上面的代码片段中，我们定义了字符串数据并将其打印给用户。我们将此数据传递给HuffmanEncoding函数，并将值存储在encoding和the_tree变量中。然后我们将编码结果打印给用户。最后，我们将编码数据传递给HuffmanDecoding函数并打印解码后的字符串。

现在，让我们在执行前查看完整的项目。

完整的项目代码

让我们看看霍夫曼编码的完整Python项目代码。

文件: huffmanAlgo.py

输出

AAAAAAABBCCCCCCDDDEEEEEEEEE
symbols:  dict_keys(['A', 'B', 'C', 'D', 'E'])
probabilities:  dict_values([7, 2, 6, 3, 9])
symbols with codes {'E': '00', 'A': '01', 'C': '10', 'D': '110', 'B': '111'}
Space usage before compression (in bits): 216
Space usage after compression (in bits): 59
Encoded output 01010101010101111111101010101010110110110000000000000000000
Decoded Output AAAAAAABBCCCCCCDDDEEEEEEEEE