在LZW压缩时计数？

Question

注意:这不是LZW压缩的正确用途。我只是在玩它。

问题

在一次传递中，是否也可以更新字典中元素的频率计数？

我的实施

import sys
from collections import defaultdict
import re

# The silliest string!
inputString = "this is the first sentence in this book the first sentence is really the most interesting the first sentence is always first"
inputString = inputString.lower().split()

StringTable = defaultdict(int)
FreqTable = defaultdict(int)

def DoPass():
    global inputString
    global StringTable
    global FreqTable

    print ""
    print "INPUT STRING:"
    print inputString

    CODE = 256

    STRING = inputString[0]

    output = []

    StringTable[STRING] = CODE
    CODE += 1

    total = len(inputString)

    for i in range(1, total):
        WORD = inputString[i]

        if STRING + " " + WORD in StringTable:
            STRING += " " + WORD
        else:
            if STRING in StringTable:
                output.append(str(StringTable[STRING]))
            else:
                output.append(STRING)
            StringTable[STRING + " " + WORD] = CODE
            CODE += 1
            STRING = WORD

    StringTable[STRING] = CODE
    CODE += 1
    output.append(str(StringTable[STRING]))

    print ""
    print "OUTPUT STRING:"
    print output

    print ""
    print "Dictionary Built..."
    for i in sorted(StringTable.keys(), key=lambda x: len(x)):
        print i, StringTable[i]

    print ""
    print "Frequencies:"
    for i in sorted(FreqTable.keys(), key=lambda x: len(x)):
        print i, FreqTable[i]

def main():
    DoPass()

if __name__ == "__main__":
    main()

输出

INPUT STRING:
['this', 'is', 'the', 'first', 'sentence', 'in', 'this', 'book', 'the', 'first', 'sentence', 'is', 'really', 'the', 'most', 'interesting', 'the', 'first', 'sent
ence', 'is', 'always', 'first']

OUTPUT STRING:
['256', 'is', 'the', 'first', 'sentence', 'in', '256', 'book', '259', 'sentence', 'is', 'really', 'the', 'most', 'interesting', '265', 'is', 'always', '275']

Dictionary Built...
this 256
first 275
is the 258
in this 262
this is 257
book the 264
the most 269
this book 263
is always 273
is really 267
the first 259
really the 268
sentence in 261
sentence is 266
always first 274
first sentence 260
interesting the 271
most interesting 270
the first sentence 265
the first sentence is 272

Frequencies:
#### I am trying to fill this

我想用它正在发现的任何模式的频率计数来填充FreqTable。我没有把我的方法放在这里明显的原因-它不工作，它给了我错误的计数。任何关于这是否可能发生的建议都是很好的。

Answer 1

不一定能理解你的问题。如果您只需要一个频率表，那么这应该是简单明了的:每次您找到一个模式时，只需将+1添加到它的频率计数中。所以真正的问题应该是找到模式。

如果您想要保持模式的排序顺序，这也应该非常容易，因为您一直在对表进行排序，因此它最终是一个insert-排序操作，非常快。

现在，找到正确的模式就另当别论了。你需要一棵树，或者一个哈希表，然后是树，或者列表，或者其他什么，才能找到你最好的匹配序列。这使得这样的算法执行起来更加复杂。

显然，对于非常小的数据集，“朴素”搜索(逐个测试所有条目)可以给出一些结果。但随着数据集的扩大，搜索成本将变得难以承受。