使用字典解码哈夫曼编码

Question

我需要解码一个用程序编码的哈夫曼编码，使用一个包含ASCII和哈夫曼位之间转换的文件进行翻译。我的程序中已经有了从"codes"到ASCII的字典，例如：

{'01110': '!', '01111': 'B', '10100': 'l', '10110': 'q', '10111': 'y'}

我创建了这个函数：

def huffmanDecode (dictionary, text) :

那需要字典和代码。我尝试在字典中搜索关键字，并使用string的replace方法和re的sub方法，但是都不能正确解码消息。 例如，如果代码是：

011111011101110

应该很容易解码为：

By!

但是通过迭代代码并在字典中搜索匹配项，我还没有能够做到这一点！

如何使用字典中的键和它们的值解码代码，通过在文本中找到键并将其替换为其值？

非常感谢您的任何帮助。

- Matt Rest

---

展示你的解码代码。手动：011111011101110 -> 01111 = B，10111 = y，以及 01110 = !，根据你自己的表格都是正确的。 - Jongware

Answer 1

使用bitarray模块，您可以免费获得哈夫曼编码和解码功能，而且可能比其他任何工具都更高效：

from bitarray import bitarray

huffman_dict = {
    '!': bitarray('01110'), 'B': bitarray('01111'),
    'l': bitarray('10100'), 'q': bitarray('10110'),
    'y': bitarray('10111')
}

a = bitarray()
a.encode(huffman_dict, 'Bylly!')
print(a)

dec = bitarray('011111011101110').decode(huffman_dict)
print(dec)
print(''.join(dec))

# # output:
# bitarray('011111011110100101001011101110')
# ['B', 'y', '!']
# By!

如果您不想安装该模块，请阅读下面的部分。

---

这里有一种使用哈夫曼树进行解码的变体 - 程序可以运行，但可能有更好的变体来表示二叉树（我选择了元组）。

当您的编码字不全是相同长度时，这个版本可能更适合。二叉树的另一个好处是，在这里很明显代码是前缀自由的。

您的树形代码如下所示（过度缩进以使树形结构可见）：

huffman_tree = \
    (   # 0
        (   # 00
            None,
            # 01
            (   # 010
                None,
                # 011
                (   # 0110
                    None,
                    # 0111
                    (   # 01110
                        '!',
                        # 01111
                        'B')))),
        # 1
        (   # 10
            (   # 100
                None,
                # 101
                (   # 1010
                    (   # 10100
                        'l',
                        # 10101
                        None
                    ),
                    # 1011
                    (   # 10110
                        'q',
                        # 10111
                        'y'))),
            # 11
            None))

使用它，然后可以解码：

def huffman_decode(strg):
    ret = ''
    cur_node = huffman_tree
    for char in strg:
        cur_node = cur_node[int(char)]
        if cur_node is None:
            raise ValueError
        elif isinstance(cur_node, str):
            ret += cur_node
            cur_node = huffman_tree
    return ret

print(huffman_decode('011111011101110'))

如果解码遇到 None，则会出现错误并引发 ValueError。一旦解码遇到字符串，当前节点 cur_node 就会重置为“根节点”，游戏将从树的开头开始。

只是因为我可以：这里是您（不完整的）哈夫曼树的可视化显示（这可能有助于理解算法的工作原理：每当您遇到一个0时：向右下方移动；每当您遇到一个1时：向右上方移动）。如果您到达了叶节点：返回该节点处的字符并重新从根节点开始。

- hiro protagonist

---

不错，学到了新东西。但是为什么您认为re.match/startswith方法不能用于可变长度的位序列？在我看来似乎很有效。难道哈夫曼编码的理念不是没有编码是其它编码的前缀吗？ - tobias_k

@tobias_k 当然，这些前缀都是不同的。但是如果出现传输错误（并且哈夫曼编码允许重新同步），我发现树方法更适合。但你是对的：从我的答案中删除了“正则表达式不适合”的部分...虽然没有考虑效率。你考虑了吗？ - hiro protagonist

Answer 2

不确定您尝试了什么，但是 re.sub 或者 replace 可能没有起作用，因为它们不一定从字符串开头替换。您需要查看字符串以哪种代码开头，然后替换该代码，并继续处理其余的字符串。

例如，像这样：

def huffmanDecode (dictionary, text):
    res = ""
    while text:
        for k in dictionary:
            if text.startswith(k):
                res += dictionary[k]
                text = text[len(k):]
    return res

或者递归地：

def huffmanDecode (dictionary, text):
    if text:
        k = next(k for k in dictionary if text.startswith(k))
        return dictionary[k] + huffmanDecode(dictionary, text[len(k):])
    return ""

您可以从您的代码中创建一个正则表达式，并使用re.match找到下一个：

import re
def huffmanDecode (dictionary, text):
    p = "|".join(dictionary) # join keys to regex
    res = ""
    while text:
        m = re.match(p, text)
        res += dictionary[m.group()]
        text = text[len(m.group()):]
    return res

注意：这两种方法都没有适当的错误处理，如果代码与消息不匹配，它们将失败或无限循环，但这应该可以帮助你入门。

- tobias_k

---

非常感谢你！！！ 你真是我的救星啊！自从周五开始我就一直在这上面工作，但一直想不通！ 你说得对，我的替换逻辑不合适，关键在于从开头搜索。 - Matt Rest