Поиск. Строки и последовательности

Представьте себе, что Вы ищете слово в словаре. Маловероятно, что Вы сначала загляните в середину словаря, затем отступите от начала на 1/4 или 3/4 и т.д, как в бинарном поиске. Если нужное слово начинается с буквы 'А', вы наверное начнете поиск где-то в начале словаря. Когда найдена отправная точка для поиска, ваши дальнейшие действия мало похожи на рассмотренные выше методы.

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

В ставших уже классическими работах Д. Кнута, Н. Вирта, У. Ахо и других авторов приводится ряд алгоритмов, позволяющих проводить эффективный поиск в текстовых документах. Наиболее известны из них алгоритмы Бойера-Мура (Boyer-Moore) и Кнута-Морриса-Пратта (Knuth-Morris-Pratt). При сравнительно малых затратах на предварительную обработку текста, эти алгоритмы обеспечивают достаточно высокую скорость поиска. Однако их применение при работе в Сети чрезвычайно осложняется необходимостью просматривать в поисках образца множество текстов, число которых может достигать сотен миллионов. При этом затраты времени возрастают линейно с ростом количества обрабатываемых документов.

В этом тексте содержится информация о некоторых алгоритмах сортировки и поиска. Описания кратки и апеллируют к интуиции, хотя и включают достаточно теории, чтобы заставить понервничать простого программиста. Предполагается, что читатель знает Си и знаком с такими понятиями, как массивы и указатели.

- RU.ALGORITHMS (2:5061/49.16) ------------------------------- RU.ALGORITHMS - Msg : 29 из 64 From : Aleksey Smirnov 2:5015/107.32 Чтв 18 Hоя 99 20:42 To : Konstantin Osipov Суб 20 Hоя 99 17:00 Subj : Алгоритм поиска подстроки Кнута-Морриса-Прата ------------------------------------------------------------------------------...