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

Это не один алгоритм, а савокупность.
1. Алгоритмы сбора информации
2. Парсинг и сортировка информация
3. Алгоритмы хранения и доступа.

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

Смотри, Когда мне нужно было делать поиск лексем в тексте, я организовал дерево поиска. Вначале завел все лексемы в дерево. Их было около 50 штук. Мегабайтный текст программа просматривала и выделяла лексемы меньше чем за 1 секунду. Есть еше один способ, на каждую лексему считается хэш и по таблице хэшев находятся ссылки на включения в те или иные тексты.

Там используется распараллеливание(надеюсь написал это слово верно ) работы, т.е. поиск ведут сразу несколько машин, поэтому и получается так быстро...
вот тута кратенько но изложено http://logic.pdmi.ras.ru/%7Eyura/modern/5.pdf

Fin, к сожалению, так не пойдет... не представляю как тогда осуществять поиск по большому индексу???

yaja, как бы там нибыло, на самом деле каждый конкретный запрос (ну по меньшей мере на 99%) обрабатывает не так уж и много машин, например как в упрощенном виде это устроено на Рамблере: есть большая сетка обычных компов, их можно прямо на лету включать/выключать, новые добавлять и т.д., нагрузку на них распределяет какой-то можный входной сервер напару с маршрутизаторами циско, компы этой сетки и занимаются поиском данных, это самые обычные ПК, и каждый конкретный запрос (насколько мне известно) обрабатывает лишь один такой ПК, а вот индекс у них хранится в каком-то кластиризированном сервере, но вся фишка в том, что эти ПК не обращаются ко всему индексу. они как-то определяют какая именно его часть им нужна, но все равно, даже те части очень большие и они паразительно быстро как-то проводят там поиск... а много компов используется лишь по той причине, что большая нагрузка на них (много посетителей)
ну это насколько мне известно

ЗЫ: кстати, твоя ссылка битая

Пример:
В запрос пришло слово "Виноград"
Делаем такую структуру.

Строку можно представить ввиде массива

1. Первоначальный указатель на элемент (Otstr *Beg) устанавливаем на начальный элемент дерева,
Указатель на строку устанавливаем на начальный элемент (char *Str) Также вводим еше один
указатель (Otstr *Temp)
2. Бежим по уровню (через Next) пока не находим ch== (*Str)
3. Если находим, то
Temp=Beg;
Beg=Level;
Str++;
Проверяем, что Beg != NULL и *Str != 0 Если нормально переходим к пункту 2
4. Проверяем состояния и говорим индекс в базе, или говорим, что слово не найдено.

Это сообщение отредактировал(а) Fin - 20.1.2006, 20:09

Fin я так понял это ООП? никогда с ним не дружил и последний раз конкретно лет 5 назад сталкивался...
но насколько я понял смысл, тут идет последовательный перебор, пока не будет найден запрос? да? просто если тогда в базе будет 50000000 слов, что тогда? или если запрос типа "виноград это ягода или фрукт", тогда выходит каждое слово по кругу гонять надо? непонятно что-то
спасибо что помогаешь пароль от старого логина забыл, пока не могу плюсики ставить, сорри

Там не важно сколько слов. Тем более словарь Ожогова около 100 тысяч. Оксфордский словарь тоже где то в этих пределах. Первую версию данного алгоритма я делал без применения ООП.
Теперь смотри. Слолько слов у тебя будет на основу "вино-" И они все вместе будут сидеть на одной и той же ветке. Просто отвелетления дальнейшие у них пойдут разными путями. Ну и перебор тоже будет не слишком длинный. Самый максимум перебора 256 * Кол-во_букв_в_слове.

Пардон за ссылку, вот работающая http://logic.pdmi.ras.ru/%7Eyura/modern/05.pdf
PROme2 знаю про гугля. там у них тысяч 10 компов основная часть которых и ведет поск в базе. так вот, МНЕ ГОВОРИЛИ(т.е. я не порверял ) что идет паралельный поиск данных. Т.е. допустим данные хрянятся в виде НЕКОТОРОГО дерева, тогда один комп берет одну его ветвь и осуществляет поиск только в ней, а другой, соответственно, в другой.
Но это в гугле, в остальных конечно будет по другому, хотя мне тоже кажется, что будет распараллелизация

Fin вроде что-то толковое говоришь, но я пока не понимаю
с утра еще раз перечитаю твои посты

yaja спасиюо за линк, щас поглядим
по поводу гугла, в прошлом году у него было по разным оценкам примерно от 60 до 80 тыс. компов что еще интересней - у него же уйма датацентров, так сказать куча клонов по всей Земле
по поводу озвученного алгоритма, может быть и так, хотя как по-моему это не рационально
хотя бы потому, что поиск для современного поисковика это ничтожная задача, намного более важная и сложная - определение релевантности результатов, а исходя из озвученного алгоритма, определение релевантности в таком случае будет вызывать очень большую нагрузку на систему, т.к. в данном случае прийдется анализировать все те же объемы данный и плюс некоторые другие, но в совокупности, как единое целое... по крайней мере насколько мне известно / на сколько я догадываюсь :смайлик_делающий_умный_вид:

Чтобы представить, как работает этот алгоритм. Вспомни, как ты ишеш в словаре слово. Сначало ишеш блок начинаюшийся на букву "в". Затем в этом блоке подблок начинаюшийся на "ви" и т.д.
Практически тоже самое происходит и в алгоритме.

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

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

Какая уйма?
Делаем не сложный подсчет: Словарь Ожогова около 100 тысяч слов. Средний размер слова 6-7 букв.
В алгоритме нужно хранить только букву текушего положения + ссылки на следуюший уровень, + ссылку на продолжение ветки. Это где то получается 9 байт служебной информации. Я возьму для всякого пожарного не 100 тысяч, а 1 миллион слов
1 000 000 * 6 * 9 = 54 000 000 байт
Что для современных компов не слишком много. Если учесть, что база данных Oracle требует по минимуму 1 гигабайт оперативной памяти только. Причем заметь, я беру максимальные значения. В реальных условиях это будет намного меньше.

Fin, что-то я совсем запутался, каким образом тогда представляется индекс какого-либо документа???

Что бы было быстро пиши Хеширование, с если еще и место хочешь экономить, то двоичное дерево полюбому.

Опс, не заметил твой вопрос. Извини. Если посмотриш структуру, то увидиш, что я выделил место, куда ты можеш сбрасывать уже твою служебную инфу, независимую от дерева поиска. Как ты дальше распределиш, чтобы это было быстро, тебе решать. Можно давать номер записи в базе данных. И из базы скачивать дальнейшую информацию. Тут самое главное быстро найти этот индекс.

тэкс, народ, наконец выкроил немного времени, по своим сооброжениям и алгоритмам, опираясь на вычитанный материал, разработал структуру индекса БД и методы быстрой выборки в ней, в итоге в тестовой БД на 20ГБ текста, мой рабочий комп выполняет поиск документов (200 тыс мнимых файлов)... ну достаточно быстро, до секунды занимает поиск, для моих целей даже минута не проблема, так что с этим моментом все ясно, спасибо за помощь

сейчас вот осталась только одна маленькая проблемка: поиск производится по каждому слову в отдельности т.е. если в поисковом запросе, например, 5 слов - это 5 независимых поисков по каждому из слов, там выходит очень длинный, но достаточно быстрый sql запрос, который производит выборку соответствующих id документов, в общем он нас не интересует и его можно принять, например, как SELECT id FROM indx WHERE `dat`='bla-bla-bla' так вот проблема в том, что по запросу "слово1 слово2 слово3 слово4 слово5" нужно сортировать документы в порядке убывания количества/порядка слов

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

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

или есть другой путь?

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

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

По каждому слову у тебя будет какой то массив индексов так? Ну в чем же дело. Тут уже алгорит слияния массивов. Сначало отсортировываеш все массивы. потом начиная с первых членов массива, идеш вверх по массивам и смотриш соответствия всех документов.
Например:
В первом запросе получился массив индексов
2 7 25 64 188 269 365
2 8 26 64 189 282 365

Тут не трудно заметить, что в документе под индексов 2 64 365 есть сразу два слова.

Кстати, чтобы быстрее искать слово, можно создать для него автомат и тогда сложность поиска станет O(n)

SoWa, спасибо, с этим уже проблем нет

Fin, по результатам эксперемента по среднему запросу получали массив на 20 тыс элементов
опять же, даже при 5 словах в запросе это уже 5 массивов и нам надо же провести довольно много сравнений: документ входит во все 5 сассивов, в один из 4-х (это уже не одна проверка ;)), 3-х, 2-х и т.д.

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

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

PROme2 Первое. Как ты организовал все таки поиск? Чтобы от этого можно было плясать.
Второе, Когда индексируеш документ, индексы в словах нужно сортировать сразу. Тогда все индексы по слову будут выходить в отсортированном порядке.
Да кстати, есть алгоритм битовой сортировки. Он является самым быстрым алгоритмом сортировки. Единственный недостаток его, нужно все время настраивать его на данные. Когда я эксперементировал с ним, у меня были следуюшие результаты. На Pentium III 850 Мгц, массив из 1 миллиона 32 байтных значений, алгоритм сортировал примерно за 28 секунд. При этом я алгоритм не слишком оптимизировал. Количество полных проходов данного алгоритма по массиву будет равно количеству бит в числе, по которому идет сортировка.