在字典performan中迭代一个大字符串并检查子字符串的成员身份

Question

我目前正在用python实现Huffman编码，我已经完成了它，但是我想让它更高效

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

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是代码字符串，value是0到255之间的整数）

我试着用''.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 = ""

具体来说，每次修改code时都要检查if code in codes:。例如，对于长度为k的代码，您将执行O（1+2+3+…+k）=O（0.5*k*k+1）=O（k²) 在这里操作。相反，您应该预处理codes，方法是构建一个哈夫曼树，并沿树向下遍历一个O（k）来解码代码（从根开始，每次读取一个1或0，然后沿着相应的子边往下走；一旦你找到了一个字母，在解码后的消息中输出它并移回你的树的根）。这不仅显式地节省了检查if code in codes:的时间复杂性，而且还避免了每次执行code += ch时重建字符串code

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

Answer 2

最大的性能提升来自于使用trie之类的工具来存储Huffman树。这将允许您一次降低一个级别，这将消除字符串串联或重复检查是否存在的需要