Как искать несколько строк в текстовом файле

Question

Я работаю в текстовых файлах.Я хочу реализовать алгоритм поиска в Java.У меня есть текстовые файлы, которые мне нужно искать.

Если я хочу найти одно слово, я могу сделать это, просто поместив весь текст в hashmap и сохранив вхождение каждого слова.Но есть ли алгоритм, если я хочу найти две строки (или может быть больше)?Должен ли я хэшировать строки в паре из двух?

Answer 1

Многое зависит от размера текстового файла. Обычно следует рассмотреть несколько случаев:

1. Лот запросов к очень коротким документам (веб-страницам, текстам эссе и т. Д.). Распределение текста как нормальный язык. Простой O (n ^ 2) алгоритм в порядке. Для запроса длины n просто возьмите окно длины n и сдвиньте его. Сравните и переместите окно, пока не найдете совпадение. Этот алгоритм не заботится о словах, поэтому вы просто видите весь поиск как большую строку (включая пробелы). Это, вероятно, то, что делает большинство браузеров. KMP или Бойер Мур не стоят усилий, поскольку случай O (n ^ 2) очень редок.

2. Лот запросов на один большой документ. Предварительно обработайте ваш документ и сохраните его предварительно обработанным. Распространенными вариантами хранения являются суффиксные деревья и инвертированные списки. Если у вас есть несколько документов, вы можете создать один документ с того момента, когда объедините их и сохраните конец документов отдельно. Это путь для баз данных документов, где коллекция почти постоянна.

3. Если у вас есть несколько документов с высокой избыточностью и ваши коллекции часто меняются, используйте KMP или Boyer Moore. Например, если вы хотите найти определенные последовательности в данных ДНК, и вы часто получаете новые последовательности, чтобы найти также новую ДНК из экспериментов, O (n ^ 2) часть наивного алгоритма убьет ваше время.

Вероятно, существует множество других возможностей, которые требуют различных алгоритмов и структур данных, поэтому вам следует выяснить, какой из них является лучшим в вашем случае.

Answer 2

Требуются дополнительные подробности, прежде чем предлагать подход:

Вы ищете только целые слова или какую-либо подстроку?

Собираетесь ли вы искать много разных слов в одном и том же неизменном файле?

Знаете ли вы слова, которые вы хотите найти все сразу?

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

http://en.wikipedia.org/wiki/String_searching_algorithm

Одна простая идея - использовать хеш скользящего окна с окном того же размера, что и строка поиска. Затем за один проход вы можете быстро проверить, где хеш окна соответствует хешу вашей строки поиска. Где оно совпадает, проверьте дважды, есть ли у вас реальное совпадение.