3

我有一个巨大的文本文件的字符串缓冲区。我必须在字符串缓冲区中搜索给定的单词/短语。什么是有效的方法？

我尝试使用 re 模块匹配。但是因为我有一个巨大的文本语料库，我必须搜索。这需要大量时间。

给定一个单词和短语字典。

我遍历每个文件，将其读入 string ，搜索字典中的所有单词和短语，如果找到键，则增加字典中的计数。

我们认为的一个小优化是将具有最大单词数的短语/单词字典排序到最低。然后从字符串缓冲区比较每个单词的起始位置并比较单词列表。如果找到一个短语，我们不会搜索其他短语（因为它匹配最长的短语，这就是我们想要的）

有人可以建议如何在字符串缓冲区中逐字进行。（逐字迭代字符串缓冲区）？

另外，还有其他可以做的优化吗？ 

data = str(file_content)
for j in dictionary_entity.keys():
    cnt = data.count(j+" ")
    if cnt != -1:
        dictionary_entity[j] = dictionary_entity[j] + cnt
f.close()
4

8 回答 8

7

通过文件的内容逐字迭代（在我的例子中，来自 Project Gutenberg 的绿野仙踪），三种不同的方式：

from __future__ import with_statement
import time
import re
from cStringIO import StringIO

def word_iter_std(filename):
    start = time.time()
    with open(filename) as f:
        for line in f:
            for word in line.split():
                yield word
    print 'iter_std took %0.6f seconds' % (time.time() - start)

def word_iter_re(filename):
    start = time.time()
    with open(filename) as f:
        txt = f.read()
    for word in re.finditer('\w+', txt):
        yield word
    print 'iter_re took %0.6f seconds' % (time.time() - start)

def word_iter_stringio(filename):
    start = time.time()
    with open(filename) as f:
        io = StringIO(f.read())
    for line in io:
        for word in line.split():
            yield word
    print 'iter_io took %0.6f seconds' % (time.time() - start)

woo = '/tmp/woo.txt'

for word in word_iter_std(woo): pass
for word in word_iter_re(woo): pass
for word in word_iter_stringio(woo): pass

导致：

% python /tmp/junk.py
iter_std took 0.016321 seconds
iter_re took 0.028345 seconds
iter_io took 0.016230 seconds
于 2010-05-04T21:56:40.330 回答
1

这听起来像是尝试真正有用的问题。您可能应该使用某种压缩树，例如Patricia/​​radix trie. 只要您可以在 trie 中找到您要查找的整个单词/短语字典，这将大大降低时间复杂度。它的工作原理是你取一个单词的开头并下降 trie，直到找到最长的匹配并增加该节点中的计数器。这可能意味着如果部分匹配没有成功，您必须提升 trie。然后你会继续到下一个单词的开头，然后再做一次。trie 的优点是，每次搜索都在搜索整个字典（每次查找大约需要 O(m)，其中 m 是字典中单词/短语的平均长度）。

如果您不能将整个字典放入一个 trie，那么您可以将字典分成几个尝试（一个用于所有以 al 开头的单词/短语，一个用于 mz 例如）并扫描整个语料库。特里。

于 2010-05-04T21:06:43.243 回答
0

您可以尝试以另一种方式进行操作...而不是处理文本语料库 2,000,000 次（每个单词一次），只处理一次。对于语料库中的每个单词，增加一个哈希表或类似的表来存储该单词的计数。伪代码中的一个简单示例：

word_counts = new hash<string,int>
for each word in corpus:
  if exists(word_counts[word]):
    word_counts[word]++
  else:
    word_counts[word] = 1

您可以通过使用完整的单词列表提前初始化 word_counts 来加快速度，这不需要 if 语句......不确定。

于 2010-05-04T20:19:52.013 回答
0

正如 xyld 所说，我认为您无法超越 re 模块的速度，尽管如果您发布正则表达式以及可能的代码会有所帮助。我可以添加的只是在优化之前尝试分析。当您看到大部分处理的去向时，您可能会感到非常惊讶。我使用 hotshot 来分析我的代码并且对它非常满意。您可以在http://onlamp.com/pub/a/python/2005/12/15/profiling.html找到关于 python 分析的很好的介绍。

于 2010-05-04T20:21:42.340 回答
0 
#!/usr/bin/env python
import re

s = ''
for i in xrange(0, 100000):
    s = s + 'Hello, this is a sentence. '
    if i == 50000:
        s = s + " my phrase "

s = s + 'AARRGH'

print len(s)

itr = re.compile(r'(my phrase)|(\w+)').finditer(s)
for w in itr:
    if w.group(0) == 'AARRGH':
        print 'Found AARRGH'
    elif w.group(0) == "my phrase":
        print 'Found "my phrase"'

运行这个，我们得到

$ time python itrword.py
2700017
Found "my phrase"
Found AARRGH

real    0m0.616s
user    0m0.573s
sys     0m0.033s

但是，明确添加到正则表达式中的每个“短语”都会对性能产生影响——根据我的粗略测量，以上内容比仅使用“\w+”慢 50%。

于 2010-05-04T21:16:03.730 回答
0

您是否考虑过查看自然语言工具包。它包括许多用于处理文本语料库的好功能，还有一个很酷的 FreqDist 类，其行为类似于 dict（有键）和类似列表（slice）。

于 2010-05-05T00:37:39.547 回答
0

如果 usingre性能不够，您可能正在使用findall(), 或手动一一查找匹配项。使用迭代器可能会使其更快：

>>> for i in re.finditer(r'\w+', 'Hello, this is a sentence.'):
...     print i.group(0)
...     
Hello
this
is
a
sentence
于 2010-05-04T20:23:11.510 回答
0

如果re模块不能快速完成，那么您将很难更快地完成它。无论哪种方式，您都需要阅读整个文件。您可能会考虑修复您的正则表达式（您能提供一个吗？）。也许你也想完成一些背景。

于 2010-05-04T20:14:00.393 回答