2013-07-08 3 views
3

Учитывая текстовый файл в 1,5 миллиона строк и около 50-100 слов в строке.Самый быстрый способ поиска слова в неиндексированном текстовом файле - Python

Чтобы найти строки, которые содержат слово, используя os.popen('grep -w word infile'), кажется, быстрее, чем

for line in infile: 
    if word in line: 
    print line 

Как еще можно искать слово в текстовом файле в Python? Каков самый быстрый способ поиска через этот большой текстовый файл unindex?

+0

Я думаю, что использование регулярного выражения может быть очень быстрым. Но поскольку ваш файл очень большой, он не может быть загружен в оперативную память, чтобы анализировать повторно. Тем не менее, можно прочитать файл большими кусками и проанализировать с регулярным выражением каждый фрагмент один за другим. Это может привести к тому, что исследуемая строка может быть перекрыта по двум кускам, а затем не обнаружена. Следовательно, анализ кусков должен выполняться определенным образом. Я уже написал такой код и разместил его здесь на stackoverflow.com. Позвольте мне найти его. – eyquem

+1

Я нашел следующее сообщение (http://stackoverflow.com/questions/16583591/read-a-very-big-single-line-txt-file-and-split-it), в котором код предназначался для обнаружения строк ROW_DEL в большом файле и заменить их более короткими строками. Ваша проблема заключается только в том, чтобы обнаружить шаблон, это проще. Я думаю, вы можете взглянуть на мой цитируемый пост, чтобы изучить, как я проанализировал кусок текста после куска и адаптировать его принцип к вашим более ограниченным потребностям. – eyquem

ответ

2

Существует несколько алгоритмов быстрого поиска (см. wikipedia). Они требуют, чтобы вы скомпилировали слово в какую-то структуру. Греп использует Aho-Corasick algorithm.

Я не видел исходный код языка Python in но либо

  1. word скомпилирован для каждой линии, которая занимает много времени (я сомневаюсь in компилирует что-нибудь, очевидно, он может скомпилировать его, кэшировать результаты и т.д.), или
  2. поиск неэффективен. Попробуйте найти слово «слово» в «worword», вы сначала проверяете «worw» и терпите неудачу, тогда вы проверяете «o», затем «r» и терпите неудачу и т. Д. Но нет никаких оснований перепроверять «o» или «r», если ты умен. Так, например, Knuth–Morris–Pratt algorithm создает таблицу на основе искомого слова, которое сообщает, сколько символов может быть пропущено при сбое.
Смежные вопросы