Лучший алгоритм поиска строк

Question

У меня есть код, в котором я сравниваю большие данные, скажем, источник веб-страницы с некоторыми словами в файле. Какой алгоритм лучше всего использовать?

Может быть 2 сценария:

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

2. У меня есть только пара слов в файле, и нормальный поиск строки будет в порядке, но все равно необходимо максимально сократить время.

Какой алгоритм лучше? Я знаю про Бойера-Мура, а также алгоритмы поиска Рабина-Карпа. Хотя поиск Бойера-Мура кажется быстрым, я также хотел бы назвать имена других алгоритмов и их сравнения.

Answer 1

Обратите внимание, что Бойер-Мур должен искать текст ( несколько слов) в тексте.

Если все, что вам нужно, это определить отдельные слова, тогда гораздо проще:

• положить каждое найденное слово в структуру словаря (чем бы оно ни было)
• поиск каждого слова в словаре

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

Что касается структурысловаря, я бы порекомендовал простую хеш-таблицу.Прекрасно работает с памятью по сравнению с древовидными структурами.

Answer 2

В обоих случаях, я думаю, вы, вероятно, захотите построить патрицию (также называемую основанием)Самое важное, что время поиска будет O (k), где k - максимальная длина строки в дереве.