С такими людьми коммунизма не построить…

По поводу создания поисковика. Направил меня товарищ, который собирался обеспечивать все железом и программерами – к программеру своему. На Сях.
Я программеру пишу что-то вроде теста:

Ну, пример. Надо организовать быстрый поиск (по точному соответствию слов) многословного запроса, с ограничением по расстоянию (в словах) между любой парой слов в 10 слов между ними. База – 100 млн. документов, средний размер документа (плейнтекст) – 20 Кб или 4000 слов. Результат – список документов.
Твои действия?

Ну и я думал что мне помощь какая-то будет. Я имею в виду, что человек знает, что такое обратный индекс… Но получаю в ответ:

1. Берем i-ый файл, открываем
2. Берем первое слово, ищем в файле -нашлось? да – ищем второе слово, проверяем дистанцию, совпало, тут добавляем в результаты запроса.
переходим к 1. если не совпало, то ищем третье слово, и проверяем дистанцию и так до 10.
если не нашлось дистанций меньше 10, то повторяем то же самое, однако мы как будто смещаемся, так как у нас, допустим слова “булка” может в тексте быть несколько штук.
3. если найдется, то добавляем в результаты(список).

-мдя, создание поисковика наталкивается на непреодолимые препятствия… 🙂

С такими людьми коммунизма не построить…: 18 комментариев

  1. Ну так в повседневных задачах обратный индекс не поиспользуешь.

  2. Хочешь как лучше – сделай сам ;))) или пиши умное ТЗ ;))

  3. 1. Берем i-ый файл, открываем…

    и так 100 mio раз 🙂

  4. >или пиши умное ТЗ
    -тут может оказаться, что мне Си проще изучить (вспомнить), чем такое ТЗ писать 🙂 Только и остается, действительно, самому…

  5. есть BerkeleyDB а к ней есть интерфейс из перла. Работает быстро. Хотя если положить 100 млн. документов по 3000 слов в одну bdb, то это может положить даже очень быструю машину 🙂

  6. А, может, попробуешь все же человеку показать число документов? 🙂
    И рассказать про индексы тоже не помешает.

  9. Если человек представляется как программер на Си (дельфи, вб или подобное – выбрать один вариант), то на русский язык:) это переводится – КОДЕР. Т.е. алгоритм надо разжевывать. При этом не факт, что то, что ты запросил, он в состоянии реализовать (закодировать) в принципе.

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

    Кстати, а ты уверен, что задачу поставил корректно? И что она вообще имеет разумное решение. По крайней мере мне флаза на счет "расстояния в 10 слов между ЛЮБОЙ парой слов", мне не очень нравится. Ее необходимо уточнять и упрощать, т.к. в лоб оно скорее всего не пойдет.

  10. Gray, ну общий уровень программера это показывает… Я его учить не собираюсь. Времени жалко.
    sekir, я, конечно извиняюсь, но Вы как тот вышеупомянутый программист, а если Сей не знаете – то и еще хуже. 🙂
    E0LiN, это не наш метод. 🙂 Я так понимаю, там готовые решения для поисковиков? А разве позволяет какой-нибудь из них делать поиск на больших объемах, хотя бы 1/10 Рунета?

  11. Newm, это не задача, а тест.
    Кстати, а если не КОДЕР, то кто? Как он должен представляться? 🙂
    Блин. Черт побери. Да, вот я знаю о способе оптимизировать поиск по большим базам – обратный индекс. А вот Кодер, положим, не знает.
    А ведь есть еще куча вещей в производительности, которые надо разумно оптимизировать – и я их не знаю. И не могу научить или в ТЗ записать. Например, вот у нас есть словарь (для поиска каждого из слов запроса и адреса на диске, по которому лежит список документов, где оно встречается). Я его, положим, хочу в оперативку запихнуть, чтобы быстрее было.
    Как это делать? Во-первых, надо решить, возможно ли это вообще, или придется урезанную его часть оставлять в оперативке. Во-вторых, надо наметить, какой род алгоритма (тупой перебор, хеширование – N вариантов, дерево или их комбинации) будет производительнее в каждом из конкретных диапазонов числа слов в словаре. При этом если я хочу учитывать морфологию, возникает доля "несловарных" слов.
    Это все творческие задачи. И здесь надо знать, в т.ч., как соотносятся времена работы с оперативкой и с винтом. Это должен решать программер.

  12. Могу поделится своими наработками (на С ) обслуживания инвертированного индекса (примитивы чтение/запись/обновление). Исходники достаточно "сырые" и требуют доработки.

    Из особенностей формата – блочная структура записей, возможность частичного обновления без перестройки всего индекса, поддержка компрессии постлистов, раздельное хранение заголовка и текста документа, хранение координат текста и заголовка документов, pagerank’а документа, "termrank’а" слова.

    Если интересно, пишите на [email protected].

  13. я в отличие от вышеупомянутого, на этих делах небольшую собаку съел. Болонку.
    а что до bdb — то это самое простое и масштабируемое решение. Некоторым нравится:

    http://dbpubs.stanford.edu:8090/pub/2000-55

    когда прошлый раз писал, не посмотрел на URL блога. Думал, блог на перле. Есть BDB и для php:

    http://www.sleepycat.com/docs/ref/ext/php.html

    P.S. а если программист знает, как за сублинейное время пересечь несколько инвертированных
    индексных блоков,то зачем, я извиняюсь, ему euhenio ?

  14. Кстати, а если не КОДЕР, то кто? Как он должен представляться? 🙂

    Если представился просто как "программист" без уточнения языка программирования, то есть шанс, что это искомое:).

    По поводу оптимизации и всего прочего…

    Если бюджет не предполагает написания своей ОС, то распределение памяти оставь на совесть ОС.

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

    А вообще для начала лучше ориентироваться на поиск по базе с разумным количеством информации, измеряемом в единицах гигабайт. Отработав качество поиска (и выяснив перспективы), дальше уже тратиться на оптимизацию.

  15. Newm,
    >Если бюджет не предполагает написания своей ОС, то распределение памяти оставь на совесть
    >измеряемом в единицах гигабайт. Отработав качество поиска (и выяснив перспективы), дальше уже тратиться на оптимизацию
    -это, вероятно, очень правильные советы, особенно второй. Но если писать качественный поисковик, в него надо изначально закладывать хорошую полноту поиска – иначе будет страдать качество поиска и мы никогда не выйдем на хорошую посещаемость…

  16. sekir,
    Ты точно уверен, что berkeley db поддерживает обратные индексы? и как насчет их объема? Любая узкоспециализированная система, которую делают под конкретные задачи и тип (плюс кол-во и характеристики) данных, эффективнее общей системы.

    Так оно поддерживает обр. индекс?

  17. там есть неплохая реализация b-деревьев, на которых строится отображение произвольного бинарного ключа в произвольное бинарное значение. Оба произвольной длины. Миллионов 200 пар ключ-значение в одну базу положить можно. По сравнению с postgress, mysql и прочими SQL-серверами – разница в скорости на порядок, потому как embedded database.

    В твоем случае ключ – слово, а значение – или блок координат, или оффсет в файле, где блок координат. Я бы выбрал второе. Строить его (инвертировать) придется самому. Добавлять ключи желательно в лексикографическом порядке, она это делает почти со скоростью записи данных на диск (20-40 мегабайт пар ключей/значений в секунду записать можно).

  18. Я так понимаю, что для словаря эта штука должна работать, но для обратного индекса – т.е., собственно для поиска – не подходит.
    А зачем тогда это советовать, тем более что "просто засунуть" все тексты в базу и по ним искать – ненормально? 🙂

Комментарии запрещены.