Вопросы об организаци поиска

читайте литературу - например, рекомендованную И.Сегаловичем.

Сейчас весьма популярны алгоритмы аналогичные описанным Ricardo Baeza-Yates.

не хотите программировать современные схемы - пользуйтесь стандартными базами данных, например, Oracle, где эти проблемы решены до Вас и за Вас

пересекут миллионы документов, проблема с использованием баз данных - тяжело держать много пользователей одновременно

кстати, для действительно многословного запроса не стоит все слова добавлять через "И", если Вас интересует только релевантность

если имеет в виду поиск по одному слову - очевидно - храните и словоформы

если имеется в виду поск по подстроке - см. п.1 - там это есть

Во-первых, огромное спасибо за компетентный ответ, а, во-вторых, разрешите задать еще несколько новых вопросов :)

Если можно ссылку на сообщение с рекоммендованной лит-рой, буду очень признателен.

Есть идеи, где можно взять эту книгу в электронном варианте? По приведенной ссылке - только название книги ;)

Кстати, для хранения инверсного индекса ведь можно применит формат хранения BerkleyDB? Кто-то уде так делал или это мои фантазии? ;) Единственно не ояень понятно, как обрабатывать конкурентные запросы (особенно одновременно чтение и модификация)

Спасибо, учту. Насчет ранжирования по релевантности - это тоже к п.1 ?

Нет, поиск - по исходной словоформе - тут как раз все понятно. Меня интересует имеено поиск по фразе.

Кстати, насчет БД. Если есть опят использования СУБД в качестве "сердца" поискавика - поделитесь опытом. Каие ограничения на размер индекса, узкие места в производительности.

eMule вам поможет. Там вообще много книжек найти можно.

Вам уже Interitus ответил....

Но мой ответ - купить. У Вас какой бюджет? Потратить на нужные книжки 30-300 баксов - обязательно!

Вы чего хотите - сделать что-нибудь или супер-пупер?

Если что-нибудь - хоть контектным поиском по файлам.

Если правильно - как сказано...

См. также статьи Яндекса в РОМИП и статьи М.Губина в RCDL.

ограничений на размер индекса нет.

Узкие места - это универсальные продукты, следовательно несколько хуже в специальных условиях - например, ORACLE любит хапать все ресурсы для "оптимального" ответа на запрос - это плохо для обслуживания большого числа "одновременных" запросов.

Зато есть и преимущества - поисковик это не только "сердце"...

любая БД (хоть на мускуле) вытянет 18 миллионов запросов в сутки(а э

то уже не что нибудь), если конечно железяки с каналом вытянут

да, наверное, для простых запросов, однако, для поиска по нескольким словам, когда надо еще сортировать результаты...

(особенно, при допущении развитого языка запросов со скобками, логическими операторами и т.п., что сильно удлиняет SQL запрос)

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

хотел бы я посмотреть на ОДИН сервер, который сможет помещать и пересекать в оперативной памяти выборки для частотных слов, для базы, скажем на 10 миллионов документов (около 3 Г записей, не менее 30 Гбайт индекса) хранимую в реляционной форме. Важно, что основной индекс не может быть целиком засунут в оперативную память.

(я-то лично сомневаюсь, что кроме Oracle это, вообще, что-нибудь потянет)

поглядев на потолок, беру оттуда формулу для типичного сервера реляционной базы данных:

количество выполняемых (поиск и ранжирование) запросов в день

равно

10*количество долларов стоимости железа

поделить на

количество документов в миллионах

(можно помножить, или поделить на три)

естесственно нагрузку надо распределять. по моему вообще поиск с помощью одной машины ( пусть даже супер пупер) можно производить для каких нибудь локальных целей. конечно оракля нужна, нужно распределять запрос по разным серверам по принципу "ухо-мозг-рот".

Посмотрел литературу, многое почерпнул ;)

Но все же остались и белые пятна.

Во-первых все тот же поиск подстроки в кавычках. Его можно делать конечно и по индексу, отфильтровуя и оставляя в пост-листе (объединенном по "И" для всех поисковых терминов) только те документы, в которых слова расположены рядом. Это единственный способ? Не будет ли он слишком медленным - просматривать все документы на предмет нахождения слов рядом.

Далее, интересно как же все-таки лучше организовать инвертированный индекс. Можно сделать Б+-деревом, а ведь можно и полностью лексикон (словарь) сохранить в памяти со ссылками на пост-листы для каждого слова лексикона. Что является правильным для поисковика?

Ну и наконец как правильно индексировать изменяющиеся документы. Ведь перед переиндексацией следует удалить все предыдущие ссылки на документ в пост-листах, но т.к. инвертированный индекс предназначен только для поиска по вхождениям терминов - сделать это будет проблематично. Как вариант - держать 2 представления для индексатора и поисковика (прямой и обратный индекс соответственно), но преобразование всего индекса из прямой формы в обратную очень трудоемо и вряд ли подойдет для реальной поисковой системы. Подскажите, как быть?

1. Вы так и не сказали цели Ваших изысканий (построение супер-поисковика по неструктурированным документам, просто образование, решение корпоративной задачи и т.д.) В зависимости от посылок ответы совершенно разные.

2. По сути вопросов:

(a) обязательно читать Дональда Кнута (Вам будет интересен 3 том, но без остальных - никуда :)

(б) По поводу "кавычек" (почему именно кавычек? синтаксис запроса может быть любым... но однозначным) в индексе неструктурированных документов хранится и координатная информация, отнесенная к каждому термину. В процессе выполнения логических операций в этом же месте производится сравнение ближайшего расстояния. Для кавычек оно должно быть 1. Координатка может быть устроена совсем просто (типа номер вхождения), а может и сложно (типа номер абзаца-номер предложения-номер во фразе-позиция во фразе 🚬 )

(с) инверсный индекс организовать можно и так и так - все зависит от разработчика и задач. Надо помнить, что существует масса "несловарных" терминов типа КТ315, ММВБ, 666 (шайтан :) , многие авторы специально каверкают слова) и пр.

вы будете обязаны их по образу и подобию занести в свои листы знаний.

(д) как обновляется индекс - у каждого свое ноу-хау. Простейший прием - полное перестроение по сырым документам. Для большого интернет-енджина непреемлимо. Инкриментальность у каждого своя.

(е) подумайте - а оно Вам надо. Подход типа: расскажите мне, как сделать, а я уж напрограммирую - неприемлим т.к. рассказ - это 90% успеха (ничего личного)

Очень благодарен вам за ответ, на самом деле мне просто необходимо понять насколько мои идеи адекватны тому, что существует на сегодяншний день

Цель - исключительно образовательная. Ничего коммерческого. Поиск подразумевается делать по неструктурировнным документам. Насчет супер-пуппер - не знаю, это уже как оплучится ;)

Да но как тогда быть с шумовыми стоп-словами? Ведь они в индексе отсутствуют и соответсвенно запрос "Петя и Вася" не может быть выполнен в силу отсутствия "и" в индексе. Выход - индексировать все слова, включая стоп-слова?

Я задумывался над этим и вряд ли возможным будет хранение всего разнообразия лексем в ОЗУ, т.к. тут будут и числа и разнообразные сокращения, аббревиатуры и проч, как вы правильно написали.

Полное перестроение - это совсем "больно", т.к. лучше уже пользоваться прямым индексом. Т.е хранить оба: прямой и обратный. Прямой позволит определить термины, по которым надо произвести зачистку пост-листа, чтобы удалить документ подлежащий переиндексации.

Но вряд ли это самый лучший способ. Возможно вы сможете посоветовать, где прочитать о лучших? Информационный поиск имеет долгую истории развития и прежде всего развития в плане научных изысканий, а посему существует много публикаций на тему. Я ведь спрашиваю о достаточно базовых вещях, которые вряд ли уж настолько ноу-хау ;)

Ну раз уже занялся - значит надо ;) Кстати, я не в коем случае не прошу вас раскрывать ваши ноу-хау... Только ткнуть носом в уже существующие и доступные публике алгоритмы.