迭代一个大字符串并检查字典性能中子字符串的成员资格

Question

我目前正在python中实现霍夫曼编码，我已经完成了它，但我想让它更有效率。

这是我用来获取原始文件内容的方法

def getDecodedFile(self, text, codes):
        code = ""
        origin = []        
        for ch in text:
            code += ch
            if code in codes:
                origin.append(codes[code])
                code = ""
        bCodes = bytes(origin)
        return bCodes

text大字符串和codes是霍夫曼代码的字典（Key是代码的字符串，值是0到255之间的int）

我尝试使用''.join(somelist)而不是code += ch但结果却慢了。目前使用len(text) = 13972363执行此方法需要3秒钟，最短代码长度为6

数据示例：

text = "0100101110111"

codes = {'0': 65, '100': 66, '101': 67, '110': 68, '111': 69}

这将导致origin = [65,66,67,68,69]

我将不胜感激任何使我的代码有效的建议。

Answer 1

据我所知，你可以做的一件事就是当你这样做时：

code += ch
if code in codes:
    origin.append(codes[code])
code = ""

具体来说，每次修改if code in codes:时都要检查code。例如，对于长度为k的代码，最终将在此处执行O（1 + 2 + 3 + ... + k）= O（0.5 * k * k + 1）= O（k²）运算。相反，你应该通过构建一个霍夫曼树来预处理codes并在树下进行单个O（k）遍历来解码你的代码（从根开始，一次读取一个1或0并沿着相应的子边缘向下移动） ;一旦你写了一个字母，把它输出到解码的消息中并移回你的树的根目录）。这不仅明确地节省了检查if code in codes:的时间复杂度，而且还避免了每次执行code时重建字符串code += ch。

除此之外，我不确定你是否可以进一步优化。我想知道将每个单独的解码字母转换为byte并附加到输出列表是否更快，而不是将字母解码为列表然后通过bytes(origin)转换列表？

Answer 2

最大的性能提升来自使用像trie这样的东西存储你的霍夫曼树。这将允许您一次下降一个级别，这将消除字符串连接或重复检查存在的需要。