Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Алгоритмы поиска информации 
:(
    Опции темы
PROme2
Дата 19.1.2006, 20:30 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 76
Регистрация: 4.1.2006

Репутация: нет
Всего: нет



Очень интересует любая информация или ее источники по алгоритмам поиска информации, в идеале - подобие алгоритмам поисковых вэб систем. Буду благодарен за любую помощь. Спасибо.
PM MAIL   Вверх
Fin
Дата 19.1.2006, 23:21 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Дракон->Спать();
**


Профиль
Группа: Участник
Сообщений: 687
Регистрация: 4.1.2006

Репутация: 1
Всего: 10



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


--------------------
Пролетал мимо.
PM MAIL   Вверх
PROme2
Дата 19.1.2006, 23:53 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 76
Регистрация: 4.1.2006

Репутация: нет
Всего: нет



да, немного неточно выразился
меня интересует любая инфа по организации хранения данных и сам алгоритм поиска, с какой-то там его базовой релевантностью
я прекрасно понимаю, что даже у того же Яндекса, все это очень сложно устроено, в частности алгоритм подсчета релевантности, он основан далеко не на одном контенте, но ведь базовый алгоритм поиска информации в базе, ее организация, это явно какой-то из общеизвестных алгоритмов, просто мне самому сложно представить как организовать даже маленькую, например, 10гб базу данных и осуществлять в ней поиск текстовых данных за доли секунд smile
PM MAIL   Вверх
Fin
Дата 20.1.2006, 00:06 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Дракон->Спать();
**


Профиль
Группа: Участник
Сообщений: 687
Регистрация: 4.1.2006

Репутация: 1
Всего: 10



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


--------------------
Пролетал мимо.
PM MAIL   Вверх
yaja
Дата 20.1.2006, 12:51 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 98
Регистрация: 30.3.2005
Где: Санкт-Петербург

Репутация: нет
Всего: 1



Цитата(PROme2 @ 19.1.2006, 23:53 Найти цитируемый пост)

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

Там используется распараллеливание(надеюсь написал это слово верно smile ) работы, т.е. поиск ведут сразу несколько машин, поэтому и получается так быстро...
вот тута кратенько но изложено http://logic.pdmi.ras.ru/%7Eyura/modern/5.pdf
PM MAIL   Вверх
PROme2
Дата 20.1.2006, 18:20 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 76
Регистрация: 4.1.2006

Репутация: нет
Всего: нет



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

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

ЗЫ: кстати, твоя ссылка битая smile
PM MAIL   Вверх
Fin
Дата 20.1.2006, 20:08 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Дракон->Спать();
**


Профиль
Группа: Участник
Сообщений: 687
Регистрация: 4.1.2006

Репутация: 1
Всего: 10



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

typedef struct Otstr {
   Otstr *Next;                                         //Ссылка на следуюший элемент в данной ветке
   Otstr *Level;                                        //Ссылка на следуюший уровень
   char ch;                                                //Код символа, которой соответствует данный элемент
   int  hesh;                                             //С этого момента можно ставить служебную инфу
};

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

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


--------------------
Пролетал мимо.
PM MAIL   Вверх
PROme2
Дата 20.1.2006, 20:20 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 76
Регистрация: 4.1.2006

Репутация: нет
Всего: нет



Fin я так понял это ООП? никогда с ним не дружил и последний раз конкретно лет 5 назад сталкивался... smile
но насколько я понял смысл, тут идет последовательный перебор, пока не будет найден запрос? да? просто если тогда в базе будет 50000000 слов, что тогда? или если запрос типа "виноград это ягода или фрукт", тогда выходит каждое слово по кругу гонять надо? smile непонятно что-то smile smile smile
спасибо что помогаешь smile пароль от старого логина забыл, пока не могу плюсики ставить, сорри smile
PM MAIL   Вверх
Fin
Дата 20.1.2006, 20:30 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Дракон->Спать();
**


Профиль
Группа: Участник
Сообщений: 687
Регистрация: 4.1.2006

Репутация: 1
Всего: 10



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


--------------------
Пролетал мимо.
PM MAIL   Вверх
yaja
Дата 20.1.2006, 23:43 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 98
Регистрация: 30.3.2005
Где: Санкт-Петербург

Репутация: нет
Всего: 1



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


Шустрый
*


Профиль
Группа: Участник
Сообщений: 76
Регистрация: 4.1.2006

Репутация: нет
Всего: нет



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

yaja спасиюо за линк, щас поглядим
по поводу гугла, в прошлом году у него было по разным оценкам примерно от 60 до 80 тыс. компов smile что еще интересней - у него же уйма датацентров, так сказать куча клонов по всей Земле smile
по поводу озвученного алгоритма, может быть и так, хотя как по-моему это не рационально
хотя бы потому, что поиск для современного поисковика это ничтожная задача, намного более важная и сложная - определение релевантности результатов, а исходя из озвученного алгоритма, определение релевантности в таком случае будет вызывать очень большую нагрузку на систему, т.к. в данном случае прийдется анализировать все те же объемы данный и плюс некоторые другие, но в совокупности, как единое целое... по крайней мере насколько мне известно / на сколько я догадываюсь :смайлик_делающий_умный_вид: smile
PM MAIL   Вверх
Fin
Дата 21.1.2006, 10:22 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Дракон->Спать();
**


Профиль
Группа: Участник
Сообщений: 687
Регистрация: 4.1.2006

Репутация: 1
Всего: 10



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


--------------------
Пролетал мимо.
PM MAIL   Вверх
PROme2
Дата 21.1.2006, 13:27 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 76
Регистрация: 4.1.2006

Репутация: нет
Всего: нет



Fin ну уже ясней все
немного только непонятно как это хранить, в каком виде и какой смысл? (я вот не понимаю, как это может ускорить поиск? разве что если сгенерировать и хранить полное дерево... но это же уйма места потребуется), пока еще перевариваю smile
PM MAIL   Вверх
podval
Дата 21.1.2006, 15:39 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Где я? Кто я?
****


Профиль
Группа: Экс. модератор
Сообщений: 3094
Регистрация: 25.3.2002
Где: СПб

Репутация: 18
Всего: 62



Цитата(PROme2 @ 21.1.2006, 13:27 Найти цитируемый пост)

разве что если сгенерировать и хранить полное дерево... но это же уйма места потребуется

Уйма еста - это плата за скорость. Думай, что тебе важнее и ищи компромисс.
PM WWW ICQ   Вверх
Fin
Дата 21.1.2006, 18:16 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Дракон->Спать();
**


Профиль
Группа: Участник
Сообщений: 687
Регистрация: 4.1.2006

Репутация: 1
Всего: 10



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


--------------------
Пролетал мимо.
PM MAIL   Вверх
Ответ в темуСоздание новой темы Создание опроса
Правила форума "Алгоритмы"

maxim1000

Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.


Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000.

 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Алгоритмы | Следующая тема »


 




[ Время генерации скрипта: 0.0910 ]   [ Использовано запросов: 21 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.