![]() |
|
![]() ![]() ![]() |
|
PROme2 |
|
|||
Шустрый ![]() Профиль Группа: Участник Сообщений: 76 Регистрация: 4.1.2006 Репутация: нет Всего: нет |
Очень интересует любая информация или ее источники по алгоритмам поиска информации, в идеале - подобие алгоритмам поисковых вэб систем. Буду благодарен за любую помощь. Спасибо.
|
|||
|
||||
Fin |
|
|||
![]() Дракон->Спать(); ![]() ![]() Профиль Группа: Участник Сообщений: 687 Регистрация: 4.1.2006 Репутация: 1 Всего: 10 |
Это не один алгоритм, а савокупность.
1. Алгоритмы сбора информации 2. Парсинг и сортировка информация 3. Алгоритмы хранения и доступа. -------------------- Пролетал мимо. |
|||
|
||||
PROme2 |
|
|||
Шустрый ![]() Профиль Группа: Участник Сообщений: 76 Регистрация: 4.1.2006 Репутация: нет Всего: нет |
да, немного неточно выразился
меня интересует любая инфа по организации хранения данных и сам алгоритм поиска, с какой-то там его базовой релевантностью я прекрасно понимаю, что даже у того же Яндекса, все это очень сложно устроено, в частности алгоритм подсчета релевантности, он основан далеко не на одном контенте, но ведь базовый алгоритм поиска информации в базе, ее организация, это явно какой-то из общеизвестных алгоритмов, просто мне самому сложно представить как организовать даже маленькую, например, 10гб базу данных и осуществлять в ней поиск текстовых данных за доли секунд ![]() |
|||
|
||||
Fin |
|
|||
![]() Дракон->Спать(); ![]() ![]() Профиль Группа: Участник Сообщений: 687 Регистрация: 4.1.2006 Репутация: 1 Всего: 10 |
Смотри, Когда мне нужно было делать поиск лексем в тексте, я организовал дерево поиска. Вначале завел все лексемы в дерево. Их было около 50 штук. Мегабайтный текст программа просматривала и выделяла лексемы меньше чем за 1 секунду. Есть еше один способ, на каждую лексему считается хэш и по таблице хэшев находятся ссылки на включения в те или иные тексты.
-------------------- Пролетал мимо. |
|||
|
||||
yaja |
|
|||
Шустрый ![]() Профиль Группа: Участник Сообщений: 98 Регистрация: 30.3.2005 Где: Санкт-Петербург Репутация: нет Всего: 1 |
Там используется распараллеливание(надеюсь написал это слово верно ![]() вот тута кратенько но изложено http://logic.pdmi.ras.ru/%7Eyura/modern/5.pdf |
|||
|
||||
PROme2 |
|
|||
Шустрый ![]() Профиль Группа: Участник Сообщений: 76 Регистрация: 4.1.2006 Репутация: нет Всего: нет |
Fin, к сожалению, так не пойдет... не представляю как тогда осуществять поиск по большому индексу???
![]() yaja, как бы там нибыло, на самом деле каждый конкретный запрос (ну по меньшей мере на 99%) обрабатывает не так уж и много машин, например как в упрощенном виде это устроено на Рамблере: есть большая сетка обычных компов, их можно прямо на лету включать/выключать, новые добавлять и т.д., нагрузку на них распределяет какой-то можный входной сервер напару с маршрутизаторами циско, компы этой сетки и занимаются поиском данных, это самые обычные ПК, и каждый конкретный запрос (насколько мне известно) обрабатывает лишь один такой ПК, а вот индекс у них хранится в каком-то кластиризированном сервере, но вся фишка в том, что эти ПК не обращаются ко всему индексу. они как-то определяют какая именно его часть им нужна, но все равно, даже те части очень большие и они паразительно быстро как-то проводят там поиск... ![]() ну это насколько мне известно ЗЫ: кстати, твоя ссылка битая ![]() |
|||
|
||||
Fin |
|
|||
![]() Дракон->Спать(); ![]() ![]() Профиль Группа: Участник Сообщений: 687 Регистрация: 4.1.2006 Репутация: 1 Всего: 10 |
Пример:
В запрос пришло слово "Виноград" Делаем такую структуру.
Строку можно представить ввиде массива 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 -------------------- Пролетал мимо. |
|||
|
||||
PROme2 |
|
|||
Шустрый ![]() Профиль Группа: Участник Сообщений: 76 Регистрация: 4.1.2006 Репутация: нет Всего: нет |
Fin я так понял это ООП? никогда с ним не дружил и последний раз конкретно лет 5 назад сталкивался...
![]() но насколько я понял смысл, тут идет последовательный перебор, пока не будет найден запрос? да? просто если тогда в базе будет 50000000 слов, что тогда? или если запрос типа "виноград это ягода или фрукт", тогда выходит каждое слово по кругу гонять надо? ![]() ![]() ![]() ![]() спасибо что помогаешь ![]() ![]() |
|||
|
||||
Fin |
|
|||
![]() Дракон->Спать(); ![]() ![]() Профиль Группа: Участник Сообщений: 687 Регистрация: 4.1.2006 Репутация: 1 Всего: 10 |
Там не важно сколько слов. Тем более словарь Ожогова около 100 тысяч. Оксфордский словарь тоже где то в этих пределах. Первую версию данного алгоритма я делал без применения ООП.
Теперь смотри. Слолько слов у тебя будет на основу "вино-" И они все вместе будут сидеть на одной и той же ветке. Просто отвелетления дальнейшие у них пойдут разными путями. Ну и перебор тоже будет не слишком длинный. Самый максимум перебора 256 * Кол-во_букв_в_слове. -------------------- Пролетал мимо. |
|||
|
||||
yaja |
|
|||
Шустрый ![]() Профиль Группа: Участник Сообщений: 98 Регистрация: 30.3.2005 Где: Санкт-Петербург Репутация: нет Всего: 1 |
Пардон за ссылку, вот работающая http://logic.pdmi.ras.ru/%7Eyura/modern/05.pdf
PROme2 знаю про гугля. там у них тысяч 10 компов основная часть которых и ведет поск в базе. так вот, МНЕ ГОВОРИЛИ(т.е. я не порверял ![]() Но это в гугле, в остальных конечно будет по другому, хотя мне тоже кажется, что будет распараллелизация ![]() |
|||
|
||||
PROme2 |
|
|||
Шустрый ![]() Профиль Группа: Участник Сообщений: 76 Регистрация: 4.1.2006 Репутация: нет Всего: нет |
Fin вроде что-то толковое говоришь, но я пока не понимаю
с утра еще раз перечитаю твои посты ![]() yaja спасиюо за линк, щас поглядим по поводу гугла, в прошлом году у него было по разным оценкам примерно от 60 до 80 тыс. компов ![]() ![]() по поводу озвученного алгоритма, может быть и так, хотя как по-моему это не рационально хотя бы потому, что поиск для современного поисковика это ничтожная задача, намного более важная и сложная - определение релевантности результатов, а исходя из озвученного алгоритма, определение релевантности в таком случае будет вызывать очень большую нагрузку на систему, т.к. в данном случае прийдется анализировать все те же объемы данный и плюс некоторые другие, но в совокупности, как единое целое... по крайней мере насколько мне известно / на сколько я догадываюсь :смайлик_делающий_умный_вид: ![]() |
|||
|
||||
Fin |
|
|||
![]() Дракон->Спать(); ![]() ![]() Профиль Группа: Участник Сообщений: 687 Регистрация: 4.1.2006 Репутация: 1 Всего: 10 |
Чтобы представить, как работает этот алгоритм. Вспомни, как ты ишеш в словаре слово. Сначало ишеш блок начинаюшийся на букву "в". Затем в этом блоке подблок начинаюшийся на "ви" и т.д.
Практически тоже самое происходит и в алгоритме. -------------------- Пролетал мимо. |
|||
|
||||
PROme2 |
|
|||
Шустрый ![]() Профиль Группа: Участник Сообщений: 76 Регистрация: 4.1.2006 Репутация: нет Всего: нет |
Fin ну уже ясней все
немного только непонятно как это хранить, в каком виде и какой смысл? (я вот не понимаю, как это может ускорить поиск? разве что если сгенерировать и хранить полное дерево... но это же уйма места потребуется), пока еще перевариваю ![]() |
|||
|
||||
podval |
|
|||
![]() Где я? Кто я? ![]() ![]() ![]() ![]() Профиль Группа: Экс. модератор Сообщений: 3094 Регистрация: 25.3.2002 Где: СПб Репутация: 18 Всего: 62 |
||||
|
||||
Fin |
|
|||
![]() Дракон->Спать(); ![]() ![]() Профиль Группа: Участник Сообщений: 687 Регистрация: 4.1.2006 Репутация: 1 Всего: 10 |
Какая уйма?
Делаем не сложный подсчет: Словарь Ожогова около 100 тысяч слов. Средний размер слова 6-7 букв. В алгоритме нужно хранить только букву текушего положения + ссылки на следуюший уровень, + ссылку на продолжение ветки. Это где то получается 9 байт служебной информации. Я возьму для всякого пожарного не 100 тысяч, а 1 миллион слов 1 000 000 * 6 * 9 = 54 000 000 байт Что для современных компов не слишком много. Если учесть, что база данных Oracle требует по минимуму 1 гигабайт оперативной памяти только. Причем заметь, я беру максимальные значения. В реальных условиях это будет намного меньше. -------------------- Пролетал мимо. |
|||
|
||||
![]() ![]() ![]() |
Правила форума "Алгоритмы" | |
|
Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000. |
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей) | |
0 Пользователей: | |
« Предыдущая тема | Алгоритмы | Следующая тема » |
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |