Хэширование слов

Sparrow,

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

Пока тестирование такого индекса на поиск дает неплохой результат.

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

Как правило, id документов в списке хранят в порядке возрастания их идентификаторов. Причин такого вида хранения несколько:

1) Возможность бысторого слияния (к примеру бинарным методом) нескольких таких отсортированых списков для многословных запросов.

2) Такие списки эфективно компрессируются. Алгоритмы компрессии (Elias gamma или delta, Variable byte и еще добрый десяток) целых положительных чисел (которымы являются идентификаторы документов) дают лучшую степень сжатия для малых чисел. А в отсортированных списках как раз есть возможность хранить не абсолютные идентификаторы а относительные, т.е хранить разницу от предыдущего значения, например список id документов: 910, 912, 915, 920, 921 хранится как: 910, 2, 3, 5, 1.

eshum,

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

Первичным же ключом поиска так или иначе остаются идентификаторы слов. Так что здесь хэширование тоже не лишне.

Проблема остается проблемой - дайте мне идеальную функцию хэширования :)

На этапе поиска можно обойтись и без идентификаторов слов. Сегмент индекса можно сделать состоящим из двух файлов:

Файл смещений - файл для поиска начала и длины постлиста в индексе. Ключем для в этом файле будет слово в "в текстовом виде", и будет иметь переменную длину. Значением - абсолютное смещение начала постлиста в индексе и его длина. Для такого файла подойдет база BerkeleyDB, в ней есть поддержка ключей переменной длины.

Файл индекса - собствено инвертированный индекс, где хранятся списки документов соответствущих словам.

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

eshum,

То есть вы хотите отказаться от нормальных форм слов?!! Какой смысл хранить его в текстовом виде?

А почему бы и нет? :)

Подумайте как работает морфология mail.ru поверх Гугла. А ведь Гугл ничего не знает о русской морфологии.

А смысл в таком хранении - отсутстивие возможности децентрализованно назначать словам идентификаторы.

eshum,

Если разбирать морфологию, то найдете не только "функцию chmod" а и "функция chmod".

Не только "лечь", но - "лег", "лежать"...

О том, имеет ли это смысл, уж сколько было сказано. И думаю, что имеет. Хотя бы стемминг, чесслово...

А уж релевантнее ли слова именно заданной формы - вопрос совсем таки десятый.

Верно, но можно перетранслировать запрос в форму ((функция || функцию) && chmod). Видимо и Яндекс хранит "не нормальную форму слова", т.к. позволяет искать точное соответствие без подключения морфолигии (такая возможность описана в синтаксисе запросов расширенного поиска).

eshum,

Да пусть ищет, но зачем полный перебор всех форм? Вы видите в этом оптимизацию? Если да, то какую?..

Устроить проверку и отсеивание результатов по совпадению, наверное, куда легче...

Мой взгляд...

Но мы скатываемся в другую тему.