在Python中逐个单词迭代字符串

Question

我有一个很大的文本文件，内容存储在一个字符串缓冲区里。我需要在这个字符串缓冲区中搜索一些特定的单词或短语。有什么高效的方法可以做到这一点呢？

我尝试过使用正则表达式模块来匹配。但是因为我的文本量非常大，所以搜索的时间很长。

我有一个单词和短语的字典。

我会遍历每个文件，把内容读入字符串中，然后在字典里搜索所有的单词和短语，如果找到，就在字典中把计数加一。

我们想到的一个小优化方法是，把字典中的短语/单词按字数从多到少排序。然后从字符串缓冲区中比较每个单词的起始位置，看看是否能找到这些单词。如果找到一个短语，就不再搜索其他短语了，因为我们已经找到了最长的短语，这正是我们想要的。

有没有人能建议我如何在字符串缓冲区中逐个单词地进行搜索？（逐个单词遍历字符串缓冲区）

另外，还有没有其他可以优化的方法呢？

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()

Answer 1

正如xyld所说，我觉得你很难超越re模块的速度，不过如果你能分享一下你的正则表达式和代码，那可能会有帮助。我想补充的是，在优化之前，先进行性能分析是个好主意。你可能会对大部分处理时间花在哪里感到惊讶。我使用hotshot来分析我的代码，效果不错。你可以在这里找到一个关于Python性能分析的好介绍 http://onlamp.com/pub/a/python/2005/12/15/profiling.html。

Answer 2

这个问题听起来很适合用一种叫做字典树的结构来解决。你可能需要使用一种压缩的字典树，比如Patricia树/基数树。只要你能把你要查找的所有单词和短语都放进这个字典树里，就能大大减少查找的时间。它的工作原理是，你从一个单词的开头开始，沿着字典树向下查找，直到找到最长的匹配，然后在那个节点上增加计数。如果部分匹配没有成功，你可能需要向上回溯字典树。接着，你再从下一个单词的开头开始，重复这个过程。字典树的好处是，每次查找时，你都在整个字典里搜索（每次查找大约需要O(m)的时间，其中m是字典里单词或短语的平均长度）。

如果你不能把整个字典放进一个字典树里，那你可以把字典分成几个字典树（比如一个存放以a-l开头的单词/短语，另一个存放以m-z开头的），然后对每个字典树进行一次全面的查找。

Answer 3

逐字遍历一个文件的内容（在我的例子中是《绿野仙踪》，来自古腾堡计划），有三种不同的方法：

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