Поисковые алгоритмы.

← →
Pavia © (2010-02-22 23:31) [0]

Во всемирном интернете насчитывается миллионы книг. И прочесть их одному человеку не под силу. Так вот самое лучшее это привлечь поисковые технологии.

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

Коллективный_Разум.Выполнить_Поиск ("Подскажите что почитать про алгоритмы используемые при поиске?") ;

1. Задача. Есть у нас файлы на диске. Вот хочу проиндексировать названия для быстрого поиска. И сделать поиск как ввисте, но только мгновенный. 0.1с и менее меня устроит.

2. Задача номер два как сделать быстрый поиск слов с ошибками. В Word"е используется проверка орфографии и она очень шустро работает.
Находит много слов да и поиск тут явно нечеткий.

Вначале интересует первая задача. Предлагайте алгоритмы или где про них прочитать. Реализация интересует как с использованием СУБД таких как MsSQL или MySQL. Так и целиком ручная реализация.

← →
KilkennyCat © (2010-02-22 23:40) [1]

Фундаментальные алгоритмы и структуры данных в Delphi. Бакнелл Дж.М.
Структуры и методы обработки данных: Практикум в среде Delphi. Зубов В.С. Шевченко И.В.
Искусство программирования, том 3. Сортировка и поиск. Кнут Д.Э.

← →
Kerk © (2010-02-22 23:40) [2]

Что значит "проиндексировать названия"? MySQL умеет индексировать текстовые поля. Может быть тебе и этого хватит?

← →
Игорь Шевченко © (2010-02-22 23:42) [3]

Кнута читать

← →
antonn © (2010-02-22 23:45) [4]

> Kerk © (22.02.10 23:40) [2]
>
> Что значит "проиндексировать названия"?

видимо он в общем, чтобы "индексы" названий лежали в одном месте и поиск велся по ним, не прибегая к пробегу по ФС

← →
Pavia © (2010-02-22 23:49) [5]

> видимо он в общем, чтобы "индексы" названий лежали в одном
> месте и поиск велся по ним, не прибегая к пробегу по ФС

Да именно так.

Кнута я читал не сильно он мне что-то помог.

← →
Kerk © (2010-02-22 23:53) [6]

> antonn © (22.02.10 23:45) [4]
>
> видимо он в общем, чтобы "индексы" названий лежали в одном
> месте и поиск велся по ним, не прибегая к пробегу по ФС

Значит можно засунуть в MySQL, а потом
http://dev.mysql.com/doc/refman/5.1/en/fulltext-query-expansion.html

Ну это конечно если не хочется реализовывать все руками.

← →
Игорь Шевченко © (2010-02-22 23:53) [7]

> Кнута я читал не сильно он мне что-то помог.

Ты хочешь понять или готовый рецепт ?

← →
turbouser © (2010-02-22 23:54) [8]

> Kerk © (22.02.10 23:53) [6]

Можно и в FB - гораздо "легче" уже монструозного Mysql

← →
Kerk © (2010-02-22 23:56) [9]

> turbouser © (22.02.10 23:54) [8]

Наверно можно. Это уже детали. :)

← →
Игорь Шевченко © (2010-02-23 00:04) [10]

> чтобы "индексы" названий лежали в одном месте и поиск велся
> по ним, не прибегая к пробегу по ФС

Это для CD/DVD хорошо, там файловая система реже меняется. Когда-то давно делал похожее на Firebird, потом плюнул, овчинка выделки не стоит, проще снять оглавление в файл и FAR-ом в этих файлах искать

← →
antonn © (2010-02-23 00:11) [11]

Я для папки с музыкой делал когда-то такой каталогизатор, в типизированном бинарном файле (куча record"ов). Ну как бы даже использовал, пару раз :)

а что брать - это уже вопросы реализации, если строк не очень много я бы и sqlite довольстовался (ну тысяч 5-10). Нечеткий поиск тут сильно будет мешать

← →
Pavia © (2010-02-23 01:22) [12]

Задача 1 вроде понятна да и ясно как ускорить ответ принимается.

А вот как вторую решать?

← →
antonn © (2010-02-23 01:32) [13]

Ну если я сам пользовался бы этим, то я бы написал поддержку регулярок/простых масок и пользовался ими :)
Решение в лоб придуманное только что для "однокоренных" слов - завести текстовое поле куда заносить различные написания слов принадлежащих объекту (название файла, теги и тп), делать поиск по этому полю, в качестве поисковой строки так же формировать "много_написаний" (на запрос "привет" ищется "привет", "превед", "медвед" и тп), запрос обычным like или регуляркой сооружается, плюс будет некая релевантность, чем больше совпадений тем лучше ): Осталось найти то, что даст "различные написания" :)

← →
Kerk © (2010-02-23 01:36) [14]

> Pavia © (23.02.10 01:22) [12]
>
> А вот как вторую решать?

http://ru.wikipedia.org/wiki/%D0%A0%D0%B0%D1%81%D1%81%D1%82%D0%BE%D1%8F%D0%BD%D0%B8%D0%B5_%D0%9B%D0%B5%D0%B2%D0%B5%D0%BD%D1%88%D1%82%D0%B5%D0%B9%D0%BD%D0%B0

← →
Kerk © (2010-02-23 01:38) [15]

Предупреждаю вопрос. Поддержку морфологии можно взять здесь: http://aot.ru/

← →
GDI+ (2010-02-23 02:59) [16]

> Pavia © (22.02.10 23:31)

Делал. Сканируются и раскладываются по дереву, где на каждом концевом слове в дереве ID строки в базе. Недостаток, может отожрать до 30-40 Мб ОЗУ если сканировать весь диск. Скорость поиска на современных процессорах(1 ядро) 10-15 мс.

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

← →
Игорь Шевченко © (2010-02-23 03:14) [17]

antonn © (23.02.10 01:32) [13]

Если в слове хлеб сделать 4 ошибки...

← →
Германн © (2010-02-23 03:21) [18]

> Игорь Шевченко © (23.02.10 03:14) [17]
>
> antonn © (23.02.10 01:32) [13]
>
> Если в слове хлеб сделать 4 ошибки...

Опять "пришел поручик Ржевский". :(

"И эти люди запрещают мне ковырять в носу!"
:)

← →
Pavia © (2010-02-23 12:53) [19]

Поповоду Расстояние Левенштейна.
Оно не учитывает длину слова. Если в слове "хлеб" сделать 4 ошибки то это будет другое слово. А вот если взять слово подлиннее "глазовыколупывательница". То 4 ошибки уже не так сильно влияют. А еще если 4 ошибки подряд то это тоже будет другое слово.

Во вторых скорость перебора словарь в среднем содержит около 64 тыс слов. Пусть длина слова в среднем 10. Тогда 10*10*64 000 что долговато.

Как ускорить?

За http://aot.ru/ спасибо посмотрю.

> Pavia © (23.02.10 12:53) [19]
> Во вторых скорость перебора словарь в среднем содержит около
> 64 тыс слов. Пусть длина слова в среднем 10. Тогда 10*10*64
> 000 что долговато.

Ну ты программист или где? :)
Ты хочешь как-то определять ошибки в словах, не проверяя их по словарю?

> Ты хочешь как-то определять ошибки в словах, не проверяя
> их по словарю?

А почему бы, нет? Вон медиану без полной сортировки ищут и что.

Вопрос был в том - как быстро перебирать?

> 1. Задача. Есть у нас файлы на диске. Вот хочу проиндексировать
> названия для быстрого поиска. И сделать поиск как ввисте,
> но только мгновенный. 0.1с и менее меня устроит.

Есть замечательный продукт, который по-моему неплохо справляется со своей задачей:
Microsoft Search Server 2008 Express, используемый совместно с Adobe PDF IFilter 5.0 (либо со своими собственными фильтрами/индексаторами).
ПС. У нас народ супер доволен.
С точки зрения администрирования - несложно, достаточно почитать и разобраться :)

Еще в тему
http://rsdn.ru/article/files/libs/fullsearch.xml

>Pavia © (23.02.10 12:53) [19]
>По поводу Расстояние Левенштейна
Вот есть два слова сон и слон. Во втором слове на одну букву больше - а какая разница!
А вот ещё два слова - дуст и дихлордифенилтрихлорметилметан - во втором слове на двадцать шесть букв больше, а разницы - никакой!

> Pavia © (23.02.10 12:53) [19]

Угу, поэтому считают E-value - число находок с данным или большим весом в рандомизированном тексте с такой же статистикой букв и таким же размером, как у базы. Подробности можно прочитать в книгах по биоинформатике, а именно:

Дурбин. Анализ биологических последовательностей.
Гасфилд. Строки, деревья и последоватлеьности в алгоритмах: информатика и вычислительная биология.
Франк-Каменский. Не помню название.

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

зы. Еще в личку мне снукнитесь.

А вообще, имхо, Google Desktop справится.

> Пусть длина слова в среднем 10. Тогда 10*10*64000

А как же быстрый поиск по отсортированному массиву?

> А как же быстрый поиск по отсортированному массиву?

Так метрика у нас какая!! Бинарный поиск ищет на точное совпадение. А тут нужно на минимальное отличия. Я уверен что бинарный поиск тут просто так работать не будет. Но при этом уверен что можно доработать алгоритм.

> TUser © (24.02.10 10:07) [26]
> А вообще, имхо, Google Desktop справится.

Это не интересно.

Гасфилд. Когда-то читал там у него много решенных частных задач при работе со строками.
В ПМ отписался.

Поисковые алгоритмы. Найти похожие ветки