Google нечеткий поиск (a.k.a "предложения" ): какой метод используется?

Я реализую функции поиска в своем веб-приложении и смотрю на существующие реализации используемых методов.

Кажется, что большинство основных сайтов (Amazon, Bing и т.д.) реализуют нечеткий поиск следующим образом:

Tokenize search string in to terms
processingSearchStringSet = {}
For each term
    if exact term is NOT in index
        Get possible terms (fuzzyTerms) from levenshtein(term, 1 (or 2))
        For each term in fuzzyTerms
            if term is in index
                processingSearchStringSet.intersect(stringsIndexedByTermsSet)
    else
        processingSearchStringSet.intersect(stringsIndexedByTermsSet)

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

Реализация Google, с другой стороны, немного отличается от этого.

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

Интересно, что:

  • Проведение поиска Левенштейна с порогом 5 по всему для каждого термина в пользовательской строке было бы безумно дорогой
  • Даже если № 1 - это то, что сделано, оно все равно не объяснит отсутствие ошибочные предложения

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

Вот пример, иллюстрирующий мои выводы:

Example term: "Fiftyyyy shades of grey"

Amazon suggestions: none 
(if the error count exceeds 1 on any term, the search fails)

Bing suggestions: none
(if the error count exceeds 2 on any term, the search fails)

Google suggestions: 10 (max) 
(breaking the search would require 5 or more errors on any single term, 
or multiple errors on multiple terms)

Мой вопрос: какой тип колдовства здесь работает? Они просто используют поиск Levenshtein с огромным допуском при допущении ошибки или используют другую технику, о которой я не знаю?

Ответы