大型自然语言单词集的哈希表

Question

我正在用 python 编写一个程序来对电影评论进行一元（最终是二元等）分析。目标是创建特征向量以输入 libsvm。我的特征向量中有 50,000 个奇怪的独特单词（这对我来说似乎相当大，但我相对确定我是对的）。

我使用 python 字典实现作为哈希表来跟踪遇到的新单词，但我注意到在处理前 1000 个奇数文档后速度大幅下降。如果我使用几个较小的哈希表/字典，我的效率会更高（考虑到自然语言的分布）还是会相同/更差？

更多信息：

数据被分成大约 1500 个文档，每个文档大约 500 个单词。每个文档中有 100 到 300 个唯一单词（相对于所有以前的文档）。

我当前的代码：

#processes each individual file, tok == filename, v == predefined class
def processtok(tok, v):
    #n is the number of unique words so far, 
    #reference is the mapping reference in case I want to add new data later
    #hash is the hashtable
    #statlist is the massive feature vector I'm trying to build
    global n
    global reference
    global hash
    global statlist
    cin=open(tok, 'r')
    statlist=[0]*43990
    statlist[0] = v
    lines = cin.readlines()
    for l in lines:
        line = l.split(" ")
        for word in line:
            if word in hash.keys():
                if statlist[hash[word]] == 0:
                    statlist[hash[word]] = 1
            else:
                hash[word]=n
                n+=1
                ref.write('['+str(word)+','+str(n)+']'+'\n')
                statlist[hash[word]] = 1
    cin.close()
    return statlist

另请记住，我的输入数据约为 6mb，输出数据约为 300mb。我只是对这需要多长时间感到惊讶，而且我觉得它不应该在运行时如此显着地减慢速度。

放慢速度：前50个文档大约需要5秒，后50个文档大约需要5分钟。

Answer 1

@ThatGuy 已经修复了，但实际上并没有告诉你这一点：

速度变慢的主要原因是行

if word in hash.keys():

，它费力地制作了所有键的列表到目前为止，然后费力地在该列表中搜索“单词”。所花费的时间与键的数量（即到目前为止找到的唯一单词的数量）成正比。这就是为什么它开始很快，然后变得越来越慢。

您所需要的只是 if word in hash: ，在 99.9999999% 的情况下，它所花费的时间与键的数量无关——这是拥有字典的主要原因之一。

对 statlist[hash[word]] 的花哨也没有帮助。顺便说一下，statlist=[0]*43990 中的固定大小需要解释一下。

更多问题

问题 A：要么 (1) 您的代码在发布时出现缩进失真，要么 (2) hash 永远不会被该函数更新。很简单，如果 word 不在 hash 中，即这是您第一次看到它，则绝对不会发生任何事情。不执行 hash[word] = n 语句（唯一更新 hash 的代码）。因此，hash 中不会出现任何单词。

看起来这段代码需要向左移动 4 列，以便与外部 if 对齐：

else:
    hash[word]=n
    ref.write('['+str(word)+','+str(n)+']'+'\n')
    statlist[hash[word]] = 1

问题 B：根本没有代码可以更新 n （据称到目前为止唯一单词的数量）。

我强烈建议你尽可能多地采纳 @ThatGuy 和我提出的建议，删除所有的全局内容，修复你的代码，在显着的位置插入一些打印语句点，然后运行它，假设 2 个文档，每行 3 行，每行大约 4 个单词。确保其正常工作。然后在您的大数据集上运行它（抑制打印）。在任何情况下，您可能希望定期发布统计数据（例如文档数、行数、单词数、唯一单词数、经过的时间等）。

另一个问题

问题C：我在@ThatGuy的回答的评论中提到了这一点，他同意我的观点，但你没有提到接受它：

>>> line = "foo bar foo\n"
>>> line.split(" ")
['foo', 'bar', 'foo\n']
>>> line.split()
['foo', 'bar', 'foo']
>>>

你使用 .split(" ") 会导致伪造“单词”并扭曲您的统计数据，包括您拥有的唯一单词的数量。您可能会发现需要更改该硬编码的幻数。

我再说一遍：函数中没有更新 n 的代码。执行 hash[word] = n 看起来很奇怪，即使每个文档都更新了 n 。

Answer 2

我不认为 Python 字典与你的速度下降有任何关系。特别是当你说条目大约有 100 个时。我希望你指的是插入和检索，它们在字典中都是 O(1) 的。问题可能是您在创建字典时没有使用迭代器（或一次加载一个键值对），而是将整个单词加载到内存中。在这种情况下，速度减慢是由于内存消耗造成的。

Answer 3

我认为你这里遇到了一些问题。大多数情况下，我不确定您要使用 statlist 完成什么任务。在我看来，它就像是你的字典的糟糕副本。找到所有单词后创建它。

这是我对您想要的内容的猜测：

def processtok(tok, v):
    global n
    global reference
    global hash
    cin=open(tok, 'rb')
    for l in cin:
        line = l.split(" ")
        for word in line:
            if word in hash:
                hash[word] += 1
            else:
                hash[word] = 1
                n += 1
                ref.write('['+str(word)+','+str(n)+']'+'\n')

    cin.close()
    return hash

请注意，这意味着您不再需要“n”，因为您可以通过执行 len(n) 来发现这一点。