Алгоритм автозаполнения?

Ответ 1

Для (heh) удивительных алгоритмов с нечеткой/частичной строкой, проверьте алгоритмы Damn Cool:

• http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees
• http://blog.notdot.net/2010/07/Damn-Cool-Algorithms-Levenshtein-Automata

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

• сохранить тройку последних/верхних N слов, используемых глобально;
• для каждого пользователя, сохраняйте три последних слова N для этого пользователя.

Наконец, вы хотите предотвратить поиск по мере возможности...

• Результаты поиска в кэше: если пользователь нажимает на любые результаты поиска, вы можете очень быстро их обслуживать, а затем асинхронно извлекать полный частичный/нечеткий поиск.
• результаты прекомпоптового поиска: если пользователь набрал "appl", они, скорее всего, будут продолжать "яблоко", "применить".
• данные предварительной выборки: например, веб-приложение может отправлять в браузер меньший набор результатов, достаточно маленький, чтобы сделать поиск грубой силы в JS жизнеспособным.

Ответ 2

Я бы просто хотел сказать... Хорошее решение этой проблемы будет включать больше, чем тройное дерево поиска. Ngrams и Shingles (Фразы). Ошибки в текстовых границах также необходимо обнаружить. "ад o" должен быть "привет"... и "whitesocks" должны быть "белыми носками" - это шаги предварительной обработки. Если вы не предварительно обработаете данные правильно, вы не получите ценные результаты поиска. Тройные деревья поиска являются полезным компонентом при определении того, что является словом, а также для реализации угадывания смежных слов, когда введенное слово не является допустимым словом в индексе.

Алгоритм Google выполняет предложение фразы и исправление. Алгоритм Google также имеет некоторую концепцию контекста... если первое слово, которое вы ищете, связано с погодой, и вы объединяете их "weatherforcst" и "monsoonfrcst" против "deskfrcst" - моя догадка за кулисами. Ранжирование меняется в предложение, основанное на первом встреченном слове - прогноз и погода, являются связанными словами, поэтому прогноз получает высокий ранг в предположении Did-You-Mean.

слово-частичные (ngrams), фразовые термины (черепица), word-proximity (word-clustering-index), тройной поиск (поиск слов).

Ответ 3

Есть такие инструменты, как soundex и levenshtein distance, который можно использовать для поиска нечетких совпадений, находящихся в определенном диапазоне.

Soundex находит слова, которые кажутся похожими и levenshtein расстояние находит слова, которые находятся в пределах определенного расстояния редактирования от другого слова.

Ответ 4

Посмотрите Firefox Awesome bar algorithm

Рекомендуемое Google полезно, поскольку оно учитывает миллионы популярных запросов + ваши прошлые связанные запросы.

У него нет хорошего алгоритма завершения /UI:

• Не подстроки
• Похоже, что это довольно простой алгоритм префикса в слово-граница.
  Например: Попробуйте tomcat tut → правильно предложить "Tomcat Tutorial". Теперь попробуйте tomcat rial → никаких предложений) -:
• Не поддерживает "вы имели в виду?" - как в результатах поиска Google.

Ответ 5

Точный алгоритм Google неизвестен, но сказано для работы путем статистического анализа ввода пользователей. Такой подход не подходит для большинства случаев. Чаще всего автоматическое завершение выполняется с использованием одного из следующих действий:

• Деревья. Индексируя текст с возможностью поиска в древовидной структуре (дерево префиксов, дерево суффикса, dawg и т.д.), Можно выполнить очень быстрый поиск за счет хранения памяти. Обход дерева можно адаптировать для приближенного сопоставления.
• Разделение папок. Разделив текст на токены (ngrams), можно выполнить поиск экземпляров шаблонов с помощью простой схемы хэширования.
• Фильтрация. Найдите набор потенциальных совпадений, а затем примените последовательный алгоритм для проверки каждого кандидата.

Посмотрите completely, библиотеку автозаполнения Java, которая реализует некоторые из последних концепций.

Ответ 6

Для подстрок и нечетких совпадений алгоритм расстояния Левенштейна работал достаточно хорошо для меня. Хотя я признаю, что это не кажется таким прекрасным, как отраслевые реализации автозаполнения/предложения. Думаю, что и Google, и Microsoft Intellisense работают лучше, потому что они усовершенствовали этот базовый алгоритм, чтобы взвесить такие операции редактирования, которые требуются для соответствия разнородным строкам. Например. перенос двух символов, вероятно, должен учитываться только как 1 операция, а не 2 (вставка и удаление).

Но даже я считаю, что это достаточно близко. Вот реализация в С#...

// This is the traditional Levenshtein Distance algorithem, though I've tweaked it to make
// it more like Google autocomplete/suggest.  It returns the number of operations 
// (insert/delete/substitute) required to change one string into another, with the 
// expectation that userTyped is only a partial version of fullEntry.
// Gives us a measurement of how similar the two strings are.
public static int EditDistance(string userTyped, string fullEntry)
{
    if (userTyped.Length == 0) // all entries are assumed to be fully legit possibilities 
        return 0; // at this point, because the user hasn't typed anything.

    var inx = fullEntry.IndexOf(userTyped[0]);
    if (inx < 0) // If the 1st character doesn't exist anywhere in the entry, it not
        return Int32.MaxValue; // a possible match.

    var lastInx = inx;
    var lastMatchCount = 0;
TryAgain:
    // Is there a better starting point?
    var len = fullEntry.Length - inx;
    var matchCount = 1;
    var k = 1;
    for (; k < len; k++)
    {
        if (k == userTyped.Length || userTyped[k] != fullEntry[k + inx])
        {
            if (matchCount > lastMatchCount)
            {
                lastMatchCount = matchCount;
                lastInx = inx;
            }
            inx = fullEntry.IndexOf(userTyped[0], inx + 1);
            matchCount = 0;
            if (inx > 0)
                goto TryAgain;
            else
                break;
        }
        else
            matchCount++;
    }
    if (k == len && matchCount > lastMatchCount)
        lastInx = inx;

    if (lastInx > 0)
        fullEntry = fullEntry.Substring(lastInx); // Jump to 1st character match, ignoring previous values 

    // The start of the Levenshtein Distance algorithem.
    var m = userTyped.Length;
    var n = Math.Min(m, fullEntry.Length);

    int[,] d = new int[m + 1, n + 1]; // "distance" - meaning number of operations.

    for (var i = 0; i <= m; i++)
        d[i, 0] = i; // the distance of any first string to an empty second string
    for (var j = 0; j <= n; j++)
        d[0, j] = j; // the distance of any second string to an empty first string

    for (var j = 1; j <= n; j++)
        for (var i = 1; i <= m; i++)
            if (userTyped[i - 1] == fullEntry[j - 1])
                d[i, j] = d[i - 1, j - 1];       // no operation required
            else
                d[i, j] = Math.Min
                           (
                             d[i - 1, j] + 1,  // a deletion
                             Math.Min(
                             d[i, j - 1] + 1,  // an insertion
                             d[i - 1, j - 1] + 1 // a substitution
                             )
                           );

    return d[m, n];
}

Ответ 7

Я думаю, что было бы лучше построить специализированное trie, а не преследовать совершенно другую структуру данных.

Я мог видеть, что функциональность проявилась в три, в которой каждый лист имел поле, которое отражало частоту поисков соответствующего слова.

В методе поискового запроса будут отображаться узлы листьев потомков с наибольшими значениями, рассчитанными путем умножения расстояния до каждого листа потомка node на частоту поиска, связанную с каждым потоком потомка node.

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

Ответ 8

Если вы ищете общий дизайн проблемы, попробуйте прочитать содержимое https://www.interviewbit.com/problems/search-typeahead/.

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

Чтобы обеспечить масштабируемость решения, вы должны грамотно делиться своими данными.