Итерация по строковому слову за раз в Python

Пословный перебор содержимого файла (в моем случае - Волшебник страны Оз из 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

Это похоже на проблему, в которой действительно поможет trie. Вероятно, вам следует использовать какое-то сжатое дерево, например Patricia / radix trie. Если вы можете поместить в дерево весь словарь слов / фраз, которые вы ищете, это значительно снизит временную сложность. Как это будет работать, вы берете начало слова и спускаетесь по дереву, пока не найдете самое длинное совпадение, и увеличиваете счетчик в этом узле. Это может означать, что вам нужно подняться по дереву, если частичное совпадение не удается. Затем вы переходите к началу следующего слова и повторяете это снова. Преимущество trie в том, что вы выполняете поиск по всему словарю при каждом поиске по trie (каждый поиск должен занимать около O (m), где m - средняя длина слова / фразы в вашем словаре).

Если вы не можете вместить весь словарь в одно дерево, вы можете разделить словарь на несколько попыток (одна для всех слов / фраз, начинающихся с al, одна для mz, например) и провести сканирование всего корпуса для каждой три.

Если модуль re не может сделать это быстро, вам будет сложно сделать это быстрее. В любом случае вам нужно прочитать весь файл. Вы можете исправить свое регулярное выражение (можете ли вы его указать?). Может быть, немного предыстории того, чего вы пытаетесь достичь.

Вы можете попробовать сделать это наоборот ... вместо того, чтобы обрабатывать корпус текста 2000000 раз (по одному разу для каждого слова), обрабатывайте его только один раз. Для каждого слова в корпусе увеличивайте хеш-таблицу или что-то подобное, чтобы сохранить счетчик этого слова. Простой пример в псевдокоде:

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 ... не уверен.

Как сказал xyld, я не думаю, что вы можете превзойти скорость модуля re, хотя было бы полезно, если бы вы разместили свои регулярные выражения и, возможно, также код. Все, что я могу добавить, это попробовать профилирование перед оптимизацией. Вы можете быть очень удивлены, когда увидите, на что идет большая часть обработки. Я использую hotshot для профилирования своего кода, и меня это вполне устраивает. Вы можете найти хорошее введение в профилирование Python здесь http://onlamp.com/pub/a/python/2005/12/15/profiling.html.

Если использование re недостаточно производительно, вы, вероятно, используете findall() или находите совпадения одно за другим вручную. Использование итератора может ускорить работу:

>>> for i in re.finditer(r'\w+', 'Hello, this is a sentence.'):
...     print i.group(0)
...     
Hello
this
is
a
sentence

#!/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

Но каждая «фраза», явно добавленная к регулярному выражению, будет сказываться на производительности - по моим грубым измерениям, это на 50% медленнее, чем просто использование «\ w +».

Думали ли вы об использовании набора инструментов для естественного языка. Он включает в себя множество хороших функций для работы с текстовым корпусом, а также имеет классный класс FreqDist, который ведет себя как dict (имеет ключи) и как список (slice).