用字典解码霍夫曼代码

Question

我需要使用包含ASCII和Huffman位之间的转换的文件来解码我用我的程序编码的霍夫曼代码.我已经在程序中从"代码"到ASCII这样的字典:

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

我创建了这个函数:

def huffmanDecode (dictionary, text) :

那需要字典和代码.我已经尝试在字典中搜索密钥并使用替换方法表单字符串和来自re的sub,但它们都没有正确地解码消息.例如,如果代码是:

011111011101110

它应该直接解码为:

By!

但我无法通过迭代代码和搜索字典中的匹配来做到这一点!

如何通过查找文本中的键并将其替换为值来使用字典中的键及其值来解码代码？

任何帮助是极大的赞赏.

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:向右+向上); 如果您点击了一个终端节点:返回该节点上的字符并在根节点重新启动.

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

注意：这两个都没有正确的错误处理，如果代码与消息不匹配，就会失败或永远循环，但这应该可以帮助您开始。