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

Question

我正在用python编写一个程序来对电影评论做一个unigram(以及最终的bigram等)分析.目标是创建要提供给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和我所做的那些建议,删掉所有的global东西,修改你的代码,在显着的点上查看几个打印语句,然后运行它说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为每个文档更新,这样做似乎也很奇怪.