Кто-то разбирается в поисковых алгоритмах? Нужна помощь.

rst, ну по сути это то же самое что писала Sadie

теперь непонятно как поступать:

- просто резать материал на слова в исходной форме и забивать их в таблицу с адресом файла? глупо - тогда количество строк будет равно количеству слов индекса, не знаю какая БД такое потянит

- добавлять новое слово с адресом файла только в том случае, если слова там нет? и добавлять новый адрес файла к слову, если оно там уже есть? ну, а как быть если это не стоповое слово и оно есть в большенстве документов? и таких слов будет мноого, ставить на них до 400000 и более указателей? это грубо говоря по 30-40мб информации о файлах на каждое такое слово + это же еще и парсить прийдется, не просто тянуть как ношу, нам ведь надо будет определить набор документов

я в замешательстве :(

Мне кажется, что в подобном случая (учитывая специфику Вашей задачи) подобное слово можно и занести в разряд стоповых. Например, к подобным словам можно отнести те, которые встречаются во всех проиндексированных документах.

да в том то и дело, что будет много таких слов, которые бы к стоповым отнести... но нельзя, например, "закон", "постановление", "Конституция", "суд" и т.д., каждое из этих слов будет встречаться в уйме доков, но далеко не во всех 🙄

ЗЫ: ладно, отвлекусь пока немного, пойду на Яндекс поищу учебник по русскому языку, почитаем... 😂

+++

так, немного почухав свою сонную репу, я все же пришел к выводу что и этот алгоритм не подойдет, объясняю почему: мало того, что хранить даже пусть не 200000-300000, а всего даже 1000 ссылок на файлы к каждому слову будет оочень накладно по объемам, так еще если нам надо осуществить поиск по запросу "слово1 слово2", нам прийдется обломаться т.к. данный алгоритм не представляет никаких данных о последовательности слов в документах, лишь о их наличии... вариант когда идет просто [слово - документ - порядковый номер в документе] не подходит т.к. даже при скромных подсчетах (количество файлов*примерное количество слов в каждом файле=количество строк в бд): 400000*2500=1 000 000 000, а то и более 😮

ну что, я сделал все что мог? 🍾

Не так.

размер базы (кстати, а кто сказал что это база должна быть (об этом позже) = количество общеупотребимых слов в языке + количество терминов предметной области. А это не больше 500000 слов, а реально это порядка 30000.

Т.к. если слово в документе встречается 10 раз, то в таблице ссылка-то должна быть одна.

Не так ли?

А касательно организации ссылок. Ну в худшем случае мы занесем в базу слово "в", которое будет встречаться в любом документе. То получим 400000 ссылок. Это не так уж и много кстати. Всего 12 мегабайт информации (заметь - это максимальный размер одной записи в таблице, в вашем случае).

Так вот. Для хранения я предлагаю использовать древовидную структуру файлов в файловой системе. Т.е. делим слово на буквы, и буквы будут являться путем к файлу с ссылками. К примеру слово "статья". Допустим индекс будет иметь уровень вложенности 2, соответственно файл с ссылками на документы по слову "статья" будет находиться по пути :

/с/т/статья

Уловили суть? Вы получаете доступ к любому файлу за 3 операции (два открытия каталога + открытие файла). При этом избегаете перегрузки структуры каталогов (на каждом уровне будет не больше 32 объектов). Это кстати очень важно. ибо , к примеру в линуксе 8192 объекта в каталоге - критическое количество для комфортной работы. (при большем кол-ве rm -f * не будет работать к примеру, или ls ... )

ну и касательно более низкого уровня - рекомендую использовать файловую XFS от SGI - она лучше всех справляется с большим количеством файлов.

Да, вы считаете что это будет медленно. Да. Это будет медленно. Но с таким объемом информации быстро не будет. Либо очень дорогое железо нужно.

Но здесь придет на помощь кеш серпов, как я уже писал в первом посте. Вы имеете серп по запросу : "статья 241", сохраните его в отдельное хранилище, и перед тем, как делать полнотекстовый поиск по документам, и вообще обращаться к базе - посмотрите, а вдруг это уже запрашивали. В качестве методики организации кеша - можно использовать мое предложение по организации в FS.

ну да, точно :d

ну да, а кто спорит?

всего 12 мегабайт 😮 😂 и то там вложенность файловой структуры такая, что я думаю, скорее все 24 МБ выйдет в результате... ;)

а теперь попробуем посмотреть на алгоритм, как все это будет работать для средненького запроса "слово1 слово2 слово3", предположим что каждое из слов встречается всего в 1% файлов - по 4000 ссылок на каждое из слов, что нам надо сделать? берем файл с адресами файлов для "слово1", разбиваем его на подстроки - 4000 адресов и ДЛЯ КАЖДОГО 😮 ищем вхождение подстроки в файлы с адресами для "слово2" и "слово3", а если вдруг еще понадобится проверка частичного вхождения, прийдется со ствигом +1 проверять все файлы попарно, пока не останется одна пара

в общем это огромная нагрузка явно будет, но я щас все же устрою тест

по поводу хранения в файлах - есть свои "+" и "-", не думаю, что это хорошая идея, удобная, но не надежная и значительно более тормознутая

+++

результаты теста: проверка наличия 4000 адресов в одном файле с 400000 адресами занимает... 40-45 минут :D (само чтение файла примерно 0.03 сек)

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

У вас не вполне верное представление об устройстве Линукса. В частности, о том как работает rm -f *. :)

XFS на большом количестве мелких файлов пожрет уж очень много места.

Немного не так. В каждом файле храните отсортированный список документов, в котором слово встречается. Тогда при запросе "слово1 слово2 слово3" вы открываете одновременно 3 файла, и последовательно их сканируете. В итоге получение списка документов выполняется за время, необходимое для последовательного чтения с диска трех файлов. Даже если там они объемом 15 мегабайт - это на обычном винте 7200 оборотов - меньше секунды. А еще же не забывайте что кешируется всё, и для популярных слов читать не надо будет. Плюс ещё если файлы открывать mmap'ом - параллельные запросы памяти жрать лишней не будут.

каких доменов? :)

потом я же специально подчеркнул - файл считывается примерно за 0.03 сек, время занимает лишь чисто поиск

конечно, я юзал самый простой алгоритм, сортировка хорошая идея, но практика показала - это в любом случае не в какие ворота не лезит 😒

ладно, это не так все просто, спасибо за помощь, пусть сами думают че делать...

У меня очень хорошее представление об устройстве линукса, поверьте. :)

[root@host315 huge]# ls | wc

  66001   66001  384900

[root@host315 huge]# rm -f *

bash: /bin/rm: Argument list too long

А какие предложения? Чтоб быстро было. Reiser? Не смешите.

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

И не забывайте - вначале вам нужно всего первые 10 результатов. Соответственно вам нужно просмотреть только первые 10 файлов из результатов пересечения (грубо говоря). И дать знать, что есть еще результаты, которые вы начнете анализировать по нажатии на кнопочку Next results.

И еще немного дополнений : очень большое значение имеет алгоритм текстового поиска. Скорость может отличаться в десятки раз в разных алгоритмах.

И еще немаловажное значение имеет аппаратная платформа.

Простой пример :

Текстовая база на 3 миллиона статей, на моем домашнем сервере для тестов с конфигурацией :

AMD Athlon(tm) 64 X2 Dual Core Processor 4800+

Cache 1024kb

4GB Dual-Channel Ram

дисковая подсистема : два SATA-2 диска, организованных в страйп.

импортируется за 3 часа.

Это парсинг 3 гигового XML файла + инсерты, инсерты и еще раз инерты в мускуль.

да, тестовая машина крутится на виртуальной машине (VMware) , которая собственно и живет на вышеприведенной конфигурации.

А теперь посмотрим на ту же самую работу, но уже на другой конфигурации :

Intel(R) Pentium(R) 4 CPU 2.80GHz

cache 1024 kb

1GB RAM

SCSI диск без страйпа.

база импортируется на _реальной_ машине , а не под VMWare-гостевой уже больше 12 часов.

Как видите - разница в скорости _очень_ существенна.

Ну так как раз если списки отсортированы - то их слияние выполняется мгновенно, за время, необходимое на чтение.

Очень непохоже, судя по высказываниям "в линуксе 8192 объекта в каталоге - критическое количество для комфортной работы". rm к вашему сведению ругается на длину командной строки, к количеству обрабатываемых объектов это не имеет отношения.

Да тот же ext3 вполне себе быстро работает на десятках тысяч файлов. Если древние ядра не юзать.

или я Вас не так понял, или именно это я и делал на протяжении 1.5 часов ;)

сорри, глупости :)

я бы сказал _вполне_ ожидаема 🙄

ааа... вы имеете в виду, что для каждого запроса надо формировать ПОЛНЫЙ список адресов? утопия какая-то... или я снова ниче не понял? 😂

ЗЫ: блин, аж самому интересно, как это всякие вэб поисковики могут так работать? там особых мощностей им не надо - все их мощностя вынуждены лишь большим количество запросов, а тут если сотня за сутки будет - уже хорошо...