Несмотря на кажущуюся простоту,
последние 30 лет прямой поиск интенсивно развивается. Было выдвинуто немалое
число идей, сокращающих время поиска в разы. При этом надо учесть, что новые
алгоритмы и их улучшенные варианты появляются постоянно.
Хотя прямой просмотр всех текстов
– довольно медленное занятие, не следует думать, что алгоритмы прямого поиска
не применяются в интернете. Норвежская поисковая система Fast
(www.fastsearch.com) использовала чип, реализующий логику прямого поиска упрощенных
регулярных выражений, и разместила 256 таких чипов на одной плате. Это
позволяло Fast-у обслуживать довольно большое количество запросов в единицу
времени.
Кроме того, есть масса программ,
комбинирующих индексный поиск для нахождения блока текста с дальнейшим прямым
поиском внутри блока. Например, весьма популярный, в том числе и в Рунете,
glimpse.
У прямых алгоритмов есть
положительные черты. Например, неограниченные возможности по приближенному и
нечеткому поиску. Ведь любое индексирование всегда сопряжено с упрощением и
нормализацией терминов, а, следовательно, с потерей информации. Прямой же поиск
работает непосредственно по оригинальным документам безо всяких искажений.
Инвертированный файл
Эта простейшая структура данных.
Первая категория людей знает, что это такое, по «конкордансам» - алфавитно
упорядоченным исчерпывающим спискам слов из одного текста или принадлежащих
одному автору (например «Конкорданс к стихам А. С. Пушкина», «Словарь-конкорданс публицистики Ф. М.
Достоевского»). Вторые имеют дело с той или иной формой инвертированного списка
всякий раз, когда строят или используют «индекс БД по ключевому полю».
Проиллюстрируем
эту структуру при помощи замечательного русского конкорданса - «Симфонии»,
выпущенной московской патриархией по тексту синодального перевода Библии [симфония].
Рис.
1
Перед нами упорядоченный по
алфавиту список слов. Для каждого слова перечислены все «позиции», в которых
это слово встретилось. Поисковый алгоритм состоит в отыскании нужного слова и
загрузке в память уже развернутого списка позиций.
Чтобы сэкономить на дисковом
пространстве и ускорить поиск, обычно прибегают к двум приемам. Во-первых,
подробность самой позиции. Чем подробнее задана такая позиции, например, в
случае с «Симофонией» это «книга+глава+стих», тем больше места потребуется для
хранения инвертированного файла.
В наиподробнейшем варианте в
инвертированном файле можно хранить и номер слова, и смещение в байтах от
начала текста, и цвет и размер шрифта, да много чего еще. Чаще же просто указывают
только номер документа, скажем, книгу Библии, и число употреблений этого слова
в нем. Именно такая упрощенная структура считается основной в классической
теории информационного поиска – Information Retrieval (IR).
Второй (никак не связанный с
первым) способ сжатия: упорядочить позиции для каждого слова по возрастанию
адресов и для каждой позиции хранить не полный ее адрес, а разницу от
предыдущего. Вот как будет выглядеть такой список для нашей странички в
предположении, что мы запоминаем позицию вплоть до номера главы:
