По поводу создания поисковика. Направил меня товарищ, который собирался обеспечивать все железом и программерами – к программеру своему. На Сях.
Я программеру пишу что-то вроде теста:
Ну, пример. Надо организовать быстрый поиск (по точному соответствию слов) многословного запроса, с ограничением по расстоянию (в словах) между любой парой слов в 10 слов между ними. База – 100 млн. документов, средний размер документа (плейнтекст) – 20 Кб или 4000 слов. Результат – список документов.
Твои действия?
Ну и я думал что мне помощь какая-то будет. Я имею в виду, что человек знает, что такое обратный индекс… Но получаю в ответ:
1. Берем i-ый файл, открываем
2. Берем первое слово, ищем в файле -нашлось? да – ищем второе слово, проверяем дистанцию, совпало, тут добавляем в результаты запроса.
переходим к 1. если не совпало, то ищем третье слово, и проверяем дистанцию и так до 10.
если не нашлось дистанций меньше 10, то повторяем то же самое, однако мы как будто смещаемся, так как у нас, допустим слова “булка” может в тексте быть несколько штук.
3. если найдется, то добавляем в результаты(список).
-мдя, создание поисковика наталкивается на непреодолимые препятствия… 🙂
Ну так в повседневных задачах обратный индекс не поиспользуешь.
Хочешь как лучше – сделай сам ;))) или пиши умное ТЗ ;))
и так 100 mio раз 🙂
>или пиши умное ТЗ
-тут может оказаться, что мне Си проще изучить (вспомнить), чем такое ТЗ писать 🙂 Только и остается, действительно, самому…
есть BerkeleyDB а к ней есть интерфейс из перла. Работает быстро. Хотя если положить 100 млн. документов по 3000 слов в одну bdb, то это может положить даже очень быструю машину 🙂
А, может, попробуешь все же человеку показать число документов? 🙂
И рассказать про индексы тоже не помешает.
А лучше ткнуть пальцем в http://openfts.sourceforge.net/ – и просто, и высокотехнологично, и теперь под Windows2k/XP/03 есть 🙂
и PostgreSQL к тому же нужна …
Если человек представляется как программер на Си (дельфи, вб или подобное – выбрать один вариант), то на русский язык:) это переводится – КОДЕР. Т.е. алгоритм надо разжевывать. При этом не факт, что то, что ты запросил, он в состоянии реализовать (закодировать) в принципе.
По крайней мере наиболее навороченный запрос к базе скорее всего этому кодеру будет не по зубам (имеется в виду запрос, результат которого можно дождаться в разумное время). В общем, это мы уже проходили:).
Кстати, а ты уверен, что задачу поставил корректно? И что она вообще имеет разумное решение. По крайней мере мне флаза на счет "расстояния в 10 слов между ЛЮБОЙ парой слов", мне не очень нравится. Ее необходимо уточнять и упрощать, т.к. в лоб оно скорее всего не пойдет.
Gray, ну общий уровень программера это показывает… Я его учить не собираюсь. Времени жалко.
sekir, я, конечно извиняюсь, но Вы как тот вышеупомянутый программист, а если Сей не знаете – то и еще хуже. 🙂
E0LiN, это не наш метод. 🙂 Я так понимаю, там готовые решения для поисковиков? А разве позволяет какой-нибудь из них делать поиск на больших объемах, хотя бы 1/10 Рунета?
Newm, это не задача, а тест.
Кстати, а если не КОДЕР, то кто? Как он должен представляться? 🙂
Блин. Черт побери. Да, вот я знаю о способе оптимизировать поиск по большим базам – обратный индекс. А вот Кодер, положим, не знает.
А ведь есть еще куча вещей в производительности, которые надо разумно оптимизировать – и я их не знаю. И не могу научить или в ТЗ записать. Например, вот у нас есть словарь (для поиска каждого из слов запроса и адреса на диске, по которому лежит список документов, где оно встречается). Я его, положим, хочу в оперативку запихнуть, чтобы быстрее было.
Как это делать? Во-первых, надо решить, возможно ли это вообще, или придется урезанную его часть оставлять в оперативке. Во-вторых, надо наметить, какой род алгоритма (тупой перебор, хеширование – N вариантов, дерево или их комбинации) будет производительнее в каждом из конкретных диапазонов числа слов в словаре. При этом если я хочу учитывать морфологию, возникает доля "несловарных" слов.
Это все творческие задачи. И здесь надо знать, в т.ч., как соотносятся времена работы с оперативкой и с винтом. Это должен решать программер.
Могу поделится своими наработками (на С ) обслуживания инвертированного индекса (примитивы чтение/запись/обновление). Исходники достаточно "сырые" и требуют доработки.
Из особенностей формата – блочная структура записей, возможность частичного обновления без перестройки всего индекса, поддержка компрессии постлистов, раздельное хранение заголовка и текста документа, хранение координат текста и заголовка документов, pagerank’а документа, "termrank’а" слова.
Если интересно, пишите на [email protected].
я в отличие от вышеупомянутого, на этих делах небольшую собаку съел. Болонку.
а что до bdb — то это самое простое и масштабируемое решение. Некоторым нравится:
http://dbpubs.stanford.edu:8090/pub/2000-55
когда прошлый раз писал, не посмотрел на URL блога. Думал, блог на перле. Есть BDB и для php:
http://www.sleepycat.com/docs/ref/ext/php.html
P.S. а если программист знает, как за сублинейное время пересечь несколько инвертированных
индексных блоков,то зачем, я извиняюсь, ему euhenio ?
Если представился просто как "программист" без уточнения языка программирования, то есть шанс, что это искомое:).
По поводу оптимизации и всего прочего…
Если бюджет не предполагает написания своей ОС, то распределение памяти оставь на совесть ОС.
А определение производительности алгоритмов – тут либо привлекай студентов по полной программе – некоторые из них готовы сделать нужный диплом за символическую плату (но время…), либо плати, либо копайся сам.
А вообще для начала лучше ориентироваться на поиск по базе с разумным количеством информации, измеряемом в единицах гигабайт. Отработав качество поиска (и выяснив перспективы), дальше уже тратиться на оптимизацию.
Newm,
>Если бюджет не предполагает написания своей ОС, то распределение памяти оставь на совесть
>измеряемом в единицах гигабайт. Отработав качество поиска (и выяснив перспективы), дальше уже тратиться на оптимизацию
-это, вероятно, очень правильные советы, особенно второй. Но если писать качественный поисковик, в него надо изначально закладывать хорошую полноту поиска – иначе будет страдать качество поиска и мы никогда не выйдем на хорошую посещаемость…
sekir,
Ты точно уверен, что berkeley db поддерживает обратные индексы? и как насчет их объема? Любая узкоспециализированная система, которую делают под конкретные задачи и тип (плюс кол-во и характеристики) данных, эффективнее общей системы.
Так оно поддерживает обр. индекс?
там есть неплохая реализация b-деревьев, на которых строится отображение произвольного бинарного ключа в произвольное бинарное значение. Оба произвольной длины. Миллионов 200 пар ключ-значение в одну базу положить можно. По сравнению с postgress, mysql и прочими SQL-серверами – разница в скорости на порядок, потому как embedded database.
В твоем случае ключ – слово, а значение – или блок координат, или оффсет в файле, где блок координат. Я бы выбрал второе. Строить его (инвертировать) придется самому. Добавлять ключи желательно в лексикографическом порядке, она это делает почти со скоростью записи данных на диск (20-40 мегабайт пар ключей/значений в секунду записать можно).
Я так понимаю, что для словаря эта штука должна работать, но для обратного индекса – т.е., собственно для поиска – не подходит.
А зачем тогда это советовать, тем более что "просто засунуть" все тексты в базу и по ним искать – ненормально? 🙂