Быстрый поиск в больших базах , Опитимизация поиска, интересная задача кто предлож

[AlexSuv]

Имеется задача обеспечение быстрого поиска в базе (interbase firebird 1.5), размер базы 0,8 ГБ
главная таблица по которой необходимо произвести поиск содержит около 500 тыс. записей.
Поиск нужно производить по полю типа текстовый BLOB, информация в котором сжата gzip-ом.
Размер текстовой информации в одном поле колеблется от 200 байт (в среднем) до 65 кб (максимум).

Поиск должен проводится обязательно по всему контенту.

Мои варианты решения задачи:

1). Создание отдельного несжатого поля в которое будет хранить все слова в одном экземпляре,
содержащиеся в поле соодержащем контент. Затем поиск по этому поля простой функцией like '%фраза%'.

плюсы: неплохая скорость построения полного индекса (около 9 мин.) или 1 мс на одну запись
минусы: достаточнао медленная скорость поиска (т.к. приходится перебирать все записи ибо в interbase по блоб и большим текстовым полям индекса не построишь)
размер индекса около 400 мб.

2). Создание отдельной таблицы для индекса со структурой (WordName varchar(50),Data blob), где
WordName - уникальное слово
Data - блоб поле, содержащее список всех записей, в которых упоминается данное слово

плюсы: скорость поиска - почти мгновенная
минусы: индекс строиться очень долго (около двух часов) и съедает огромное количество памяти

размер индекса около 700 мб!

3). Похожее на 2, только создается две таблицы WordsIndex (Id int,WordName varchar(50)) и TopicIndex (WordId int,TopicNo int), где

WordsIndex:
Id - уникальный номер уникального слова в таблице
WordName - уникальное слово

TopicIndex:
WordId - ссылка на слово в таблице WordsIndex
TopicNo - соответственно номер записи, где это слово встречается

плюсы: минимум использования памяти, скорость поиска - почти мгновенная
минусы: время на создание полного индекса - несколько часов, размер индекса более 1 гб., кол-во записей в таблице TopicIndex - 30 млн. !!!!, со всеми вытекающими отсюда последствиями по скорости добавления следующих данных

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

Оптимальное время поиска, как для меня - не более 10 сек. и размер индекса не более 50% от размера базы

[Romkin]

Третий вариант - самый предпочительный. И что такого, что время большое? Один раз делается, потом пополняется. А что со скоростью добавления? Вообще говоря, она от объема мало зависит, скорее всего ты весь индекс в одной транзакции строил? Вот это тяжко
30 млн - скорее всего меньше, ты, наверно вообще все слова закинул? Надо исключать местоимения (вроде "я" "и" "о") и другие слова, которые есть везде, и искать бессмысленно по ним
Плюс, можно сделать многоуровневый индекс, с хешированием. Это и объем уменьшит.
Вот уже год как на ibase лежит набор процедур полнотекстового поиска, посмотри.

[H.Iglesias II]

Цитата

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

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

[AlexSuv]

Итак задачу решил следующим образом:

Таблица: Index (WordHash integer,WordPos integer)
пробегаем по всем записям определяем все уникальные слова длиннее 3-х букв, затем добавляем в таблицу Index хэш (я взял CRC32), этого слова и номер записи, где это слово встречается. Все оказалось гараздо проще.
Использовал библиотеки TextParser c Некоторыми доработками типа избавления HTML от тэгов и т.п.

Итак: построение полного индекса по 500 тыс записям около 10 мин.+построение двух индексов по полям WordHash и WordPos еще 7 мин.
размер индекса равен 80% от исходной таблицы
Количество записей в таблице Index около 24 млн.
Используемая оперативная память менее 1 мб.
Время поиска от 10 мс до 1 сек.

Недостатки:
1) Поиск точных слов т.е. "ИСКАТЬ " в поИСКАТЬ не найдет, хотя думаю сделать при добавлении слова в поиск добавлять и некоторые морфологические формы.
2) Подозреваю, что CRC32 не дает нужной уникальности, а жаль прийдется использовать другую хэш функцию, хотя все равно прийдется делать
обычный поиск в результататах для поиска словосочетаний.
3) Немаленикий размер индекса.

Спасибо всем кто ответил особенно H.Iglesias II за идею с хэш функцией.

[H.Iglesias II]

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

Цитата

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

enum { MULTIPLIER = 31 };
 /* hash: вычислить
хэш-функцию строки */
 
unsigned long hash(char *str)
{
unsigned long h = 0;
unsigned char *p;
 
 
for (p = (unsigned char *) str; *p != '\0'; p++) h = MULTIPLIER * h + *p;
return h % NHASH;
}

Цитата

В вычислениях символы принимаются неотрицательными принудительно (тем, что используется тип unsigned char), так как ни в С, ни в C++ наличие знака у символов не регламентировано, а мы хотим, чтобы наша хэш-функция оставалась положительной.

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

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