Итерация по строковому слову за раз в 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

Перебор слово за словом по содержимому файла (в моем случае это Wizard of Oz из 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

Answer 2

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

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

Answer 3

Рассматривали ли вы вопрос Natural Language Toolkit . Он включает в себя множество приятных функций для работы с текстовым корпусом, а также имеет классный класс FreqDist, который ведет себя как dict (имеет ключи) и list-like (слайс).

Answer 4

#!/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 +».

Answer 5

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

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

Answer 6

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

Answer 7

Вы можете попробовать сделать это наоборот ... вместо обработки текстового корпуса 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 ... не уверен.

Answer 8

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