Самый быстрый способ поиска слова в неиндексированном текстовом файле - Python

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

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

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

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


python search text-search
person alvas    schedule 08.07.2013    source источник
comment
Я думаю, что использование регулярного выражения может быть очень быстрым. Но поскольку ваш файл очень большой, его нельзя загрузить в ОЗУ для анализа с помощью регулярных выражений. Однако можно читать файл большими фрагментами и анализировать с помощью регулярного выражения каждый фрагмент один за другим. При этом может оказаться, что исследуемая строка может перекрывать два фрагмента, а затем не обнаруживаться. Следовательно, анализ фрагментов должен выполняться определенным образом. Я уже написал такой код и разместил его здесь, на stackoverflow.com. Дай мне поискать.   -  person eyquem    schedule 08.07.2013
comment
Я нашел свой следующий пост (stackoverflow.com/questions/16583591/), в котором код был предназначен для обнаружения строк ROW_DEL в большом файле и замены их более короткими строками. Ваша задача - просто обнаружить закономерность, это проще. Думаю, вы можете взглянуть на цитируемый мной пост, чтобы изучить способ, которым я анализировал фрагмент текста за фрагментом, и адаптировать его принцип к вашим более ограниченным потребностям.   -  person eyquem    schedule 08.07.2013

Ответы (2)


arrow_upward
2
arrow_downward

Существует несколько алгоритмов быстрого поиска (см. wikipedia). Они требуют, чтобы вы собрали слово в некую структуру. Grep использует алгоритм Ахо-Корасика.

Я не видел исходного кода для in python, но либо

  1. word компилируется для каждой строки, что требует времени (я сомневаюсь, что in компилирует что-либо, очевидно, он может скомпилировать это, кэшировать результаты и т. Д.), Или
  2. поиск неэффективен. Подумайте о поиске слова "word" в слове "worword", вы сначала проверяете "worw" и терпите неудачу, затем вы проверяете "o", затем "r" и терпите неудачу и т. Д. Но нет причин проверять "o" или "r", если ты умен. Так, например, алгоритм Кнута – Морриса – Пратта создает таблицу на основе искомого слова, которая сообщает ему, сколько символов можно пропустить при возникновении ошибки.
person Jirka    schedule 08.07.2013

arrow_upward
1
arrow_downward

Я могу порекомендовать установить и использовать the_silver_searcher.

В моем тесте он искал текстовый файл размером ~ 1 ГБ с ~ 29 миллионами строк и нашел сотни найденных словарных статей всего за 00h 00m 00.73s, то есть МЕНЬШЕ секунды!

Вот код Python 3, который использует его для поиска слова и подсчета того, сколько раз оно было найдено:

import subprocess

word = "some"
file = "/path/to/some/file.txt"

command = ["/usr/local/bin/ag", "-wc", word, file]
output = subprocess.Popen(command, stdout=subprocess.PIPE).stdout.read()
print("Found entries:", output.rstrip().decode('ascii'))

Эта версия ищет слово и печатает номера строк + фактический текст, в котором слово было найдено:

import subprocess

word = "some"
file = "/path/to/some/file.txt"

command = ["/usr/local/bin/ag", "-w", word, file]
output = subprocess.Popen(command, stdout=subprocess.PIPE)

for line in output.stdout.readlines():
    print(line.rstrip().decode('ascii'))
person Denis Rasulev    schedule 08.04.2018