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

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 是编码的字符串，value 是 0 到 255 之间的 int)

我尝试使用 ''.join(somelist) 而不是 code += ch 但结果要慢得多。目前此方法需要 3 秒执行 len(text) = 13972363 最短代码长度为 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:。例如，对于长度为 k 的代码，您最终将执行 O(1 + 2 + 3 + ... + k) = O(0.5 * < em>k * k+1) = O(k²) 运算。相反，您应该预处理 codes，方法是构建一个 Huffman 树并沿着树向下执行一次 O(k) 遍历以解码您的代码(从根开始，然后读取一次单个 1 或 0 并沿着相应的子边缘向下移动；一旦你击中一个字母，将其输出到解码消息中并移回树的根)。这不仅显着节省了检查 if code in codes: 的时间复杂度，而且还避免了每次执行 code + 时都重建字符串 code = ch.

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