用字典解码哈夫曼密码

Question

我需要用一个包含ASCII和Huffman位之间转换的文件来解码我用程序编写的Huffman代码。我已经有一本字典在程序中，从“代码”到ASCII，如下所示：

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

我创建了函数：

def huffmanDecode (dictionary, text) :

那需要字典和密码。我试过在字典中搜索文本中的键，并同时使用replace方法表单string和subfromre但它们都无法正确解码消息。 例如，如果代码为：

011111011101110

将其解码为：

By!

但我还没能通过遍历代码并在字典中搜索匹配项来做到这一点！

如何使用字典中的键及其值来解码代码，方法是在文本中找到键并用其值替换它？

任何帮助都非常感谢。

Answer 1

使用^{}模块，您可以免费获得huffman en-/de编码，而且可能比任何其他模块都更高效：

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：向右+向上）；如果你碰到一个结束节点：返回该节点的字符并在根节点重新启动。

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 ""

您还可以从代码中生成regex并使用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

注意：这两种方法都没有正确的错误处理，如果代码与消息不匹配，它们将永远失败或循环，但这应该可以让您开始。