itman, спасибо за ответы ;)
Скажите, касательно способа хранения словаря, какие варианты возможны? Или способ б-дерева и есть самый правильный для большого словаря? Как я уже писал выше, я остановился на таком хранении, т.к. подозреваю, что словарь будет очень большим для коллекция в несколько десятков миллионов документов. Но я могу и ошибаться насчет размеров (есть какая-та статистика?). Какие существуют эффективные схемы хранения словаря в памяти?
Кстати, Максим Голубев в одной из тем объяснял необходимость наличия 2х индексов: поисковый (небольшой) и рабочий (полный). При этом критерием включения документа в поисковый индекс является его значимость. Интересно, как можно определить значимость и насколько релевантным будет выдача, сформированная только лишь на основе данных поискового индекса?
С большим интересом прочел эту тему.
Если использование реляционных баз накладно, то как все-таки организовывается индекс в large-scale поисковиках? Тут прозвучало, в plain-файлах, но суть все-равно не ясна для меня.
Например, имеется некоторая коллекция документов, собранная crawler'ом. Данная коллекция обрабатывается индексатором, выделяются отдельные слова, строится прямой индекс, на этапе построения прямого индекса считается TF. Далее строится обратный индекс, после инвертирования легко посчитать IDF. А вот как теперь хранить обратный индекс без использования СУБД?
Я бы сделал так:
- Б-дерево для хранения словаря (или все-таки хранить словарь в памяти отсортированным и искать бинарным поиском? но как быть с тем, что словарь будет содержать большое число терминов в силу нелитературности веба?). Планируется взять готовую реализацию б-дерева, например, Berkeley DB (или глупая затея?). В поле value будет хранится адрес начала пост-листа.
- Пост-листы хранить в отдельном файле. Если индекс некоординатный, то все просто - хранить номера документов, для сжатия - дельта-кодирование (или другие методы разностного кодирования). А вот как быть с координатным? Хранить все в виде пар (документ, позиция) или в виде подчиненных списков? Здесь есть какие-то "правильные" решения? Кстати, релевантность idf*tf думаю хранить в пост-листе для каждого документа.
З.Ы. Еще хотелось бы узнать, где можно почитать насчет способов построения инвертированного индекса, когда нет возможности сделать это целиком в памяти.
Очень благодарен вам за ответ, на самом деле мне просто необходимо понять насколько мои идеи адекватны тому, что существует на сегодяншний день
Цель - исключительно образовательная. Ничего коммерческого. Поиск подразумевается делать по неструктурировнным документам. Насчет супер-пуппер - не знаю, это уже как оплучится ;)
Да но как тогда быть с шумовыми стоп-словами? Ведь они в индексе отсутствуют и соответсвенно запрос "Петя и Вася" не может быть выполнен в силу отсутствия "и" в индексе. Выход - индексировать все слова, включая стоп-слова?
Я задумывался над этим и вряд ли возможным будет хранение всего разнообразия лексем в ОЗУ, т.к. тут будут и числа и разнообразные сокращения, аббревиатуры и проч, как вы правильно написали.
Полное перестроение - это совсем "больно", т.к. лучше уже пользоваться прямым индексом. Т.е хранить оба: прямой и обратный. Прямой позволит определить термины, по которым надо произвести зачистку пост-листа, чтобы удалить документ подлежащий переиндексации.
Но вряд ли это самый лучший способ. Возможно вы сможете посоветовать, где прочитать о лучших? Информационный поиск имеет долгую истории развития и прежде всего развития в плане научных изысканий, а посему существует много публикаций на тему. Я ведь спрашиваю о достаточно базовых вещях, которые вряд ли уж настолько ноу-хау ;)
Ну раз уже занялся - значит надо ;) Кстати, я не в коем случае не прошу вас раскрывать ваши ноу-хау... Только ткнуть носом в уже существующие и доступные публике алгоритмы.
Посмотрел литературу, многое почерпнул ;)
Но все же остались и белые пятна.
Во-первых все тот же поиск подстроки в кавычках. Его можно делать конечно и по индексу, отфильтровуя и оставляя в пост-листе (объединенном по "И" для всех поисковых терминов) только те документы, в которых слова расположены рядом. Это единственный способ? Не будет ли он слишком медленным - просматривать все документы на предмет нахождения слов рядом.
Далее, интересно как же все-таки лучше организовать инвертированный индекс. Можно сделать Б+-деревом, а ведь можно и полностью лексикон (словарь) сохранить в памяти со ссылками на пост-листы для каждого слова лексикона. Что является правильным для поисковика?
Ну и наконец как правильно индексировать изменяющиеся документы. Ведь перед переиндексацией следует удалить все предыдущие ссылки на документ в пост-листах, но т.к. инвертированный индекс предназначен только для поиска по вхождениям терминов - сделать это будет проблематично. Как вариант - держать 2 представления для индексатора и поисковика (прямой и обратный индекс соответственно), но преобразование всего индекса из прямой формы в обратную очень трудоемо и вряд ли подойдет для реальной поисковой системы. Подскажите, как быть?
Во-первых, огромное спасибо за компетентный ответ, а, во-вторых, разрешите задать еще несколько новых вопросов :)
Если можно ссылку на сообщение с рекоммендованной лит-рой, буду очень признателен.
Есть идеи, где можно взять эту книгу в электронном варианте? По приведенной ссылке - только название книги ;)
Кстати, для хранения инверсного индекса ведь можно применит формат хранения BerkleyDB? Кто-то уде так делал или это мои фантазии? ;) Единственно не ояень понятно, как обрабатывать конкурентные запросы (особенно одновременно чтение и модификация)
Спасибо, учту. Насчет ранжирования по релевантности - это тоже к п.1 ?
Нет, поиск - по исходной словоформе - тут как раз все понятно. Меня интересует имеено поиск по фразе.
Кстати, насчет БД. Если есть опят использования СУБД в качестве "сердца" поискавика - поделитесь опытом. Каие ограничения на размер индекса, узкие места в производительности.
