В основном для полнотекстового поиска по большим корпусам используются два метода: размещение списков и суффиксных массивов.
Список проводок - это список пар (term, document_id), необязательно с позицией в документе. Если вы сортируете или хешируете по термину, у вас есть эффективный для поиска полнотекстовый индекс.
Существуют различные способы сделать списки рассылки меньше, быстрее получать доступ, быстрее обновлять и более гибкие, некоторые за счет точности. Lucene, вероятно, является лучшим из доступных на сегодняшний день текстовых индексаторов на основе списков публикаций, и (в отличие от ваших предыдущих комментариев) может индексировать текст, найденный в файлах PDF, Microsoft Word и т. Д. Проект Lucene.net , связанный Томасом Майерхофером, выглядит довольно разумным портом, хотя, конечно, вы всегда будете немного отстать от переднего края того, что происходит в версии Java.
Для корпуса, который намного больше, чем память, вы в значительной степени должны хранить список сообщений на диске. Это препятствует использованию простого бинарного дерева поиска для доступа к нему: если у вас есть сто тысяч документов по десять тысяч слов каждый, у вас есть миллиард сообщений, что означает, что ваше двоичное дерево поиска имеет минимальную глубину 30. Проблема в том, что что 30 узлов на пути от корня дерева к листу, как правило, будут расположены в разных частях вашего диска - поэтому диск должен искать 30 раз, чтобы найти записи для одного термина! Это примерно 2,5 секунды, что слишком медленно.
Однако существует модифицированная версия структуры данных бинарного дерева, называемая «B-деревом», которая может работать. Lucene использует простую структуру данных, которая очень похожа на B-дерево, но гораздо легче поддерживает масштабные обновления. Я написал очень простую версию этой же структуры данных в своем собственном проекте dumbfts , в котором реализован механизм полнотекстового поиска для моей электронной почты на нескольких страницах Python. Я использую его каждый день, это бесплатное программное обеспечение, и оно работает довольно хорошо для того, для чего я его использую, но это не совсем система поиска мирового класса, как Lucene.
В качестве примера уменьшения списков рассылки за счет точности книга Managing Gigabytes (и проект mg4j ) имеет структуру данных, называемую «подписанная минимальная совершенная хеш-таблица», которая не на самом деле хранятся индексируемые термины - только их хеши. Таким образом, существует небольшая вероятность ложного положительного результата - вам нужно извлечь документы, которые предположительно содержат термин, чтобы подтвердить, что они действительно есть.
Суффиксные массивы, которые являются гораздо более компактной и немного более медленной версией радикальных деревьев (то есть попыток), реализованы GLIMPSE и несколькими другими программами, но в настоящее время они в основном перестали использоваться. Они обладают некоторой гибкостью, отсутствующей в структуре данных списка публикаций - например, они позволяют осуществлять поиск по регулярному выражению и поиск с ошибками, но они не такие быстрые. Недавно была проведена работа с преобразованием Барроуза-Уилера, которое основано на массивах суффиксов и предоставляет алгоритм сжатия, в котором сжатый файл представляет собой полнотекстовый индекс! Лучше всего документированная версия называется FM-index , хотя я слышал, что существуют более старые версии этой техники, возможно, неопубликованные. В отличие от других методов, описанных выше, однако, я думаю, что это на самом деле не работает, когда документы представляют собой PDF-файлы или что-то в этом роде - вы все равно можете использовать тот же подход для извлечения текстовой версии каждой страницы и индексации, но вы этого не делаете получит преимущество сжатия оригинального документа.
Мой знакомый Тим написал действительно хорошую вводную серию публикаций в блогах о поиске еще в 2003 году, которые все еще довольно хороши. Они охватывают этот материал (за исключением недавних разработок) гораздо глубже.
Рави: Это та информация, которую вы ищете?
Редактировать: спасибо за исправление моего форматирования, Мартин!