Поиск словосочетаний

Весь вопрос в том, что такое "словосочетание". Если имеется в виду слова стоящие рядом, то инвертированный файл при правильной организации дает время поиска не хуже (а реально лучше) O(n), где n - число слов запроса. Что, в принципе, не плохо :).

Для того, чтобы получить лучшее время нужно использовать структуры типа NextWord, см. например http://citeseer.ist.psu.edu/bahle02efficient.html ну или скромную мою работу http://rcdl2002.jinr.ru/Reports/Vol_2/vol2_26-37.pdf

Иногда может быть и наоборот - чем больше слов в запросе, тем короче список результатов поиска, а значит и меньше времени потребуется на ранжирование. При большом количестве слов в запросе производительность, как мне кажется, будет больше "упираться" на объединение списков документов соответствующих каждому слову запроса. Подробне про объединение упорядоченных последовательностях можно посмотреть: Интерполяционный поиск, Hwang-Lin merging, binary merging algorithm

А как насчет неравномерного индекса, основанного на частоте запросов к тем или иным словам или частоте в языке тех или иных слов?

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

eshum,

Есть еще один выход хранить где-то прямой индекс. При разумной структуре обратного слишком много изменений производить не придется.

При "правильной" организации инвертированного файла, конечно нет. Все зависит от приоритетов при разработке поисковой структуры - скорость поиска или обновления, насколько критична компактность и т.д.

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

Согласен, если требуется бысто обновить произвольный документ, лучше хранить постлист кусочками. Правда есть спорные моменты: что делать если после обновления блок становится больше по размеру, переносить данные в новый? Или как быть с фрагментацией таких блоков которая возникнет после некоторого количества обновлений? Если таких блоков будет много в постлисте и они не будут располагаться подряд, упадет производительность поиска т.к. подвод головки винчестера к началу блока (diskseek) не самая быстрая опрерация.

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

Такая проблема есть в любой динамической индексной структуре. Простое и, обычно, хорошее решение предложил в 60-х г-н Bayer для листов Б-дерева.

Честно не слышал о таком решении. Во всех известных мне вариантах кластерного решения информация об одном документе помещалась на одном узле. Это естественно вытекает из более простой реализации индексации и поиска.

Судя по всему так работал Рамблер предыдущей версии и .Turtle

Да, я это читал, когда-то давным-давно, но забыл. Им, конечно, виднее :). С точки зрения частичной пересмотройки, поиска фраз (о чем мы говорили), масштабируемости и устойчивости к потерям узлов кластера это решение не очень.