Структура индексов

InSAn,

Ну, думаю, окончательное ранжирование придется делать на лету - динамически, или держать в кэше запросов. Потому что... :) Ну ведь разные запросы бывают...

Или хранить обалденно большой индекс связей - зачем оно нужно?

Неужели все-же прийдется сначала делать выборку из базы по весам слов, а потом "на лету" дополнительно сортировать по расстояниям?

InSAn,

Ну, можно облегчить себе жизнь тем, скажем, что вы индекс будете упорядочивать не только по идентификаторам слов, а еще и по документам. Мне представляется, что ранжирование результатов не только зависит от удаленности слов друг от друга, а также от количества найденных в документе слов, от их общего веса, от индекса цитируемости сайта.

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

Может подойдет такой вариант - объединить таблицу "саму на себя" и отсортировать в порядке разницы позиций.

Для таблицы index(doc_id, word_id, weight, pos) запрос для двух слов ($word_id1, $word_id2) будет выглядеть так:

select i1.doc_id from index i1, index i2 where i1.doc_id=i2.doc_id and i1.word_id=$word_id1 and i2.word_id=$word_id2 and (i2.pos - i1.pos) > 0 order by (i2.pos - i1.pos)

Если предполагается ранжировать еще и в порядке веса слова в документе дописываем ...order by ((i2.pos - i1.pos) + N * ((i1.weight + i2.weight) / 2))

N - коэфициент "важности" веса слова

weight - чем меньше значение, тем вес выше

По идее можно написать такой запрос для 3-x и более слов. Под каждое количество слов свой запрос.

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

А если правильно строить поисковый индекс, оптимальные положения слов в документе можно найти по алгоритму Дейкстры (нахождение минимального пути, где расстояния между слов - веса узлов графа).

А можно эту же мысль чуть более развернуто?... Как вы предлагаете строить индекс? И что именно будет вычислять алгоритм поиска минимального пути?

Я бы сказал что не совсем верно, задача не вычислить наиболее короткий путь, очевидно что при запросе A B , предпочтительнее последовательность A B , A {X} B , и только потом B A , A {X} B , а при данном подходе будет уравнено. На мой взгляд , нужно брать две отсортированные последовательности , вставлять одну в одну и далее двигаться проверяя заранее подготовленные тест-матрицы. При совпаденнии последовательности присваивать вес данной матрицы , т.е. например AB = 1.00 , BA = 0.5 , и т.д . кои складывать/умножать с другими весами.

Ну можно же тупо взять последовательности позиций каждого из двух слов в документе, слить, и за один проход получить 2 минимальных расстояния - для A {x} B и B {x} A (потом в соответствии с предпочтениями оценить). Если суммарно в документе эти слова встречаются n раз, то всего-то потребуется n вычитаний/сравнений (ну и еще n сравнений на сливание) на документ. Это же мизер, на этапе выборки документов, содержащих оба слова, вполне можно считать.

ну а я что сказал , только предложил не только AB оченивать , но и матрицу других комбинаций. например при AB все понятно , A B , A{x}B , BA , B{x}A , то при трех , словах уже сложенее, при четырех еще сложнее. и важность может меняться, это параметр тюнинга .

фраза "Слова знакомые до боли"

ищем с учетом словообразования "боль знакомая" , "знакомые слова" , "слова о боли" , "слова знакомые до боли". Ясно что :

1. "слова знакомые до боли" ( ABCD )

2. "слова о боли" ( A D )

3. "знакомые слова" (B A)

4. "боль знакомая" ( D B )

Заметно что последовательность имеет значительную роль. И второе что должна существовать матрица более предпочтительных результатов.