Comments
Чтобы не хранить в каждом узле все id запросов, можно устроить хранение в виде вложенных множеств. Тогда у каждого узла будут храниться левый и правый указатель на границы в списке id-шников запросов всех дочерних элементов. Но это дополнительный шаг адресации, поэтому в случае приоритета скорости над компактностью ииндексов вариант с 5-10 гб конечно будет быстрее.
Да, скорость здесь играет решающую роль. И надо сказать, что именно пересечение posting list'ов в данном алгоритме — самая ресурсоёмкая часть.
Обязательно ли считать префиксами каждое слово в наборе, или только последнее? Это к ситуации запроса «а б», которое генерирует длинные списки id.
Практическая польза видится только в случаях, если человек начал редактировать свой запрос и набирает новое слово в начале Подобные ситуации можно отслеживать и считать префиксом только текущее редактируемое слово, а все остальные слова в запросе — считать набранными до конца.
Вопрос хороший.
На самом деле к задаче можно действительно подходить способом отслеживания позиции курсора и выяснять редактируемое слово, что можно использовать, скажем, при ранжировании.
Но такой способ обладает и рядом недостатков:
  • нам придётся увеличить объём индекса: придётся хранить trie со списками для редактируемых слов, да плюс отдельный индекс для законченных слов;
  • этот способ подразумевает обязательное наличие информации о набираемом слове, что в общем случае не очень гибко — не все сервисы, которые хотят использовать подсказки, способны на такое;
  • в общем случае такой способ даёт меньшую полноту подсказок, чем когда мы представляет каждое слово как обобщённый префикс.

Поэтому рассматривать каждое слово как префикс не обязательно, но в целом экономичнее и выгоднее.
Расскажите еще, как считать f (вес популярности подсказок)? Допустим еще никакой информации от пользователей нет (система только запустилась), и где их брать?
И как из популярности отдельных слов получить популярность собственно всего запроса?
У нас нет весов популярности слов. По крайней мере, в приведённой статье об этом речи не велось.
Ну, либо я не понял Ваш вопрос.
Ну начнём с того, что в таком случае у нас не будет и самих текстов подсказок, потому что мы не знаем даже, что искали пользователи. :)
Но с другой стороны, если разработчик поисковой системы может «налить» пользователей на свой поисковик, то статистика неминуемо появится сама собой, и покупка трафика пользователей будет равносильна «покупке» тех самых весов популярности f и всего остального о поведении пользователей. Так что через какой-то непродолжительный промежуток времени у вас уже что-то да будет.
«Налить» это понятно. А что делать, если «не наливать»? Других способов нет? Это годится может для больших сайтов, где ищут по миллиону раз в день. А если человек мало и ищут редко — статистику копить слишком долго.
В таком случае можно насобирать «offline» фактов и весов этих фактов из тех источников, по которым происходит поиск.
Скажем, если вы делаете поиск по порталу научных статей, и хотите сделать для этого поиска подсказки, тогда можно было бы поступить следующим образом:
  • насобирать заголовков статей — и это были бы тексты подсказок;
  • посчитать рейтинг этих статей каким-либо известным алгоритмом; скажем, PageRank по ссылкам, которые упоминаются в этих статьях — и это был бы вес подсказки.

В любом случае, если у вас нет online-поведенческих данных, вам придётся каким-то образом насобирать их в offline'е. То есть, как в примере выше, количество ссылок на научную статью, по сути и есть её популярность, оценённая авторами других статей, ссылающихся на первую.
В узлах patricia tree можно еще хранить сумму весов узла и его детей и исходя из этой информации при обходе не заходить в тупиковые ветви с низким весом.
Интересная статья, примерно такое спрашивали на собеседовании в Гугл, тут, правда, индексу альтернатив нет, эту тему раскрыть легко, но дьявол кроется в деталях, спасибо.

Вопрос про опечатки — обнаруживаете ли и на каком этапе? Какой метод используется? Самое простое — нагенерировать термов из данных префиксов и в путь — искать в префиксном дереве, видимо )
Спасибо за отзыв.

Про опечатки.
Обнаруживаем сразу после получения черновых результатов, и исправляем; правда, без фанатизма.
То, что вы описали в качестве самого простого — думаю, вполне себе рабочая идея. Но по-хорошему, это тема для отдельной статьи, поэтому в качестве ориентира привёл ссылку на работу ребят из Майкрософт. Продублирую её здесь.
Only those users with full accounts are able to leave comments. Log in, please.