自动完成算法？

问题描述 投票：57回答：8

我指的是当用户在Google中键入搜索字词时用于提供查询建议的算法。

我主要感兴趣的是：1。最重要的结果（最有可能是查询而不是匹配的任何东西）2。匹配子串3.模糊匹配

我知道你可以使用Trie或generalized trie来找到匹配，但它不符合上述要求......

类似的问题早先问过here

algorithm autocomplete scalability data-structures autosuggest
8个回答
56
投票

对于（嘿）令人敬畏的模糊/部分字符串匹配算法，请查看Damn Cool算法：

这些不会取代尝试，而是在尝试中防止暴力查找 - 这仍然是一个巨大的胜利。接下来，您可能想要一种限制trie大小的方法：

  • 保持全球使用的最近/前N个词;
  • 对于每个用户，请为该用户保留最近/前N个单词。

最后，您希望尽可能防止查找...

  • 缓存查找结果：如果用户点击任何搜索结果，您可以非常快速地提供服务，然后异步获取完整的部分/模糊查找。
  • 预计算查找结果：如果用户键入了“appl”，则他们可能会继续使用“apple”，“apply”。
  • 预取数据：例如，一个Web应用程序可以向浏览器发送一小组结果，小到可以在JS中进行暴力搜索。
8
投票

我只想说......这个问题的一个很好的解决方案是不仅仅包含三元搜索树。需要Ngrams和Shingles（Phrases）。还需要检测字边界错误。 “地狱o”应该是“你好”......而“whitesocks”应该是“白袜子” - 这些都是预处理步骤。如果您没有正确预处理数据，那么您将无法获得有价值的搜索结果。三元搜索树是确定单词是什么的有用组件，也是当键入的单词不是索引中的有效单词时实现相关单词猜测的有用组件。

谷歌算法执行短语建议和更正。谷歌算法也有一些上下文的概念...如果你搜索的第一个单词是天气相关的，你将它们结合起来“weatherforcst”vs“monsoonfrcst”vs“deskfrcst” - 我的猜测是在幕后排名正在改变基于遇到的第一个单词的建议 - 预测和天气是相关的单词，因此预测得到了在你的平均猜测中的高排名。

word-partials（ngrams），短语 - 术语（shingles），word-proximity（word-clustering-index），三元搜索树（word-lookup）。

5
投票

谷歌的确切算法未知，但it is said通过统计分析用户输入工作。一种不适合大多数情况的方法。更常见的是，使用以下方法之一实现自动完成：

  • 树。通过索引树结构中的可搜索文本（前缀树，后缀树，dawg等），可以以内存存储为代价执行非常快速的搜索。树遍历可以适用于近似匹配。
  • 模式分区。通过将文本划分为标记（ngrams），可以使用简单的散列方案执行模式发生的搜索。
  • 过滤。找到一组潜在的匹配，然后应用顺序算法来检查每个候选。

看看completely，这是一个Java自动完成库，它实现了后面的一些概念。

4
投票

有像soundex和levenshtein distance这样的工具可用于查找在一定范围内的模糊匹配。

Soundex发现听起来相似的单词，levenshtein距离找到与另一个单词在某个编辑距离内的单词。

3
投票

看看Firefox's Awesome bar algorithm

谷歌建议很有用，因为它会考虑数以百万计的流行查询和过去的相关查询。

它虽然没有很好的完成算法/ UI：

  1. 不做子串
  2. 看起来像一个相对简单的词边界前缀算法。 例如：尝试tomcat tut - >正确建议“tomcat教程”。现在尝试tomcat rial - >没有建议） - ：
  3. 不支持“你的意思是？” - 与谷歌搜索结果一样。
2
投票

对于子串和模糊匹配，Levenshtein距离算法对我来说效果相当好。虽然我承认它似乎并不像自动完成/建议的行业实现那样完美。谷歌和微软的Intellisense都做得更好，我认为因为他们已经改进了这个基本算法来衡量匹配不同字符串所需的编辑操作。例如。转置两个字符应该只计为1个操作，而不是2个（插入和删除）。

但即便如此，我发现这已足够接近了。这是它在C＃中的实现......

// This is the traditional Levenshtein Distance algorithem, though I've tweaked it to make
// it more like Google's 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's 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];
}
1
投票

如果您正在寻找问题的整体设计，请尝试阅读https://www.interviewbit.com/problems/search-typeahead/上的内容。

他们首先通过使用trie的天真方法构建自动完成，然后构建它。他们还解释了优化技术，如采样和离线更新，以满足特定用例。

为了保持解决方案的可扩展性，您必须智能地对trie数据进行分片。

0
投票

我认为构建专门的trie可能会更好，而不是追求完全不同的数据结构。

我可以看到这个功能表现在一个特里，其中每个叶子都有一个反映其相应单词搜索频率的字段。

搜索查询方法将显示具有最大值的后代叶节点，该最大值是通过将与每个后代叶节点的距离乘以与每个后代叶节点相关联的搜索频率而计算的。

谷歌使用的数据结构（以及算法）可能要复杂得多，可能会考虑到大量其他因素，例如您自己特定帐户的搜索频率（以及一天中的时间......和天气......季节） ...和月相......和...）。但是，我相信基本的trie数据结构可以扩展到任何类型的专用搜索首选项，方法是在每个节点中包含其他字段，并在搜索查询方法中使用这些字段。

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.