对大自然语言词集的哈希表

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

我觉得你这里有几个问题。主要是，我不太明白你想用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)来获取这个信息。

Answer 2

我觉得Python的字典和你遇到的速度慢没有什么关系。特别是当你说条目大约有100个的时候。我希望你指的是插入和取值，这两者在字典中都是O(1)，也就是很快的意思。问题可能出在你在创建字典时没有使用迭代器（或者是一次加载一个键值对），而是把所有的单词都加载到内存中。这样的话，速度慢的原因就是内存消耗太大了。

Answer 3

@ThatGuy已经修复了问题，但他并没有告诉你这个：

你程序变慢的主要原因是这一行：

if word in hash.keys():

这行代码会费劲地列出所有的键，然后再慢慢地在这个列表里查找`word`。所花的时间和键的数量成正比，也就是你目前找到的独特单词的数量。这就是为什么一开始运行得快，后来越来越慢的原因。

你只需要用 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和我提出的建议，去掉所有的global相关内容，修正你的代码，在关键地方加几个打印语句，然后在两份每份3行、每行大约4个单词的文档上运行它。确保它正常工作。然后再在你的大数据集上运行（打印输出可以关闭）。无论如何，你可能想定期输出一些统计数据（比如文档数量、行数、单词数、独特单词数、耗时等）。

另一个问题

问题C：我在@ThatGuy的回答中提到过这个，他也同意了，但你没有提到要解决这个问题：

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

你使用的.split(" ")会导致一些虚假的“单词”，并且会扭曲你的统计数据，包括你拥有的独特单词数量。你可能需要更改那个硬编码的魔法数字。

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