自動完成算法？

Question

我指的是當用戶在Google中輸入搜索詞時，用於提供查詢建議的算法。

我主要興趣在谷歌的算法是如何能夠證明： 1.最重要的結果（最有可能的查詢，而不是任何比賽） 2.匹配子 3.模糊匹配

我知道你可以使用特里或全身線索來尋找匹配，但它不會滿足上述要求...

問

類似的問題早here

Answer 1

有喜歡soundex和工具可用於查找在一定範圍內的模糊匹配。

Soundex找到聽起來相似的單詞，levenshtein距離找到與另一個單詞相距一定編輯距離的單詞。

Answer 2

我認爲一個人可能會更好地構建一個專門的trie，而不是追求完全不同的數據結構。

我可以看到，該功能表現在每個葉子都有一個字段反映其相應單詞搜索頻率的字典中。

搜索查詢方法將顯示具有最大值的後代葉節點，該最大值通過將與每個後代葉節點的距離乘以與每個後代葉節點相關聯的搜索頻率來計算。

Google使用的數據結構（以及算法）可能要複雜得多，可能會考慮到大量其他因素，例如從您自己的特定帳戶（以及一天中的時間...和天氣......季節......和月相......和......）。 然而，我相信通過在每個節點中包含附加字段並在搜索查詢方法中使用這些字段，基本特里樹數據結構可以擴展爲任何類型的專用搜索首選項。

Answer 3

看看Firefox's Awesome bar algorithm

谷歌的建議是有用的，因爲它以百萬計的熱門查詢+你過去的相關查詢的考慮。

它不會有一個很好的完成算法/ UI，但：

1. 沒有做子
2. 似乎是一個相對簡單的字邊界前綴算法。
   例如：嘗試tomcat tut - >正確提示「tomcat tutorial」。現在試試tomcat rial - >沒有建議） - ：
3. 不支持「你的意思是？」 - 在谷歌搜索結果。

Answer 4

對於（港燈）真棒模糊/部分字符串匹配算法，看看該死的冷靜算法：

• 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」，他們很可能會繼續使用「apple」，「apply」。預取數據：例如，一個Web應用程序可以向瀏覽器發送一組較小的結果，足夠小以便在JS中進行蠻力搜索。

Answer 5

我只想說... 這個問題的一個很好的解決方案將包含多於三元搜索樹。 Ngrams和帶狀皰疹（短語）是必要的。還需要檢測字邊界錯誤。 「hell o」應該是「hello」...而「whitesocks」應該是「白色襪子」 - 這些都是預處理步驟。如果您沒有正確預處理數據，您將無法獲得有價值的搜索結果。 三元搜索樹是確定什麼是單詞的有用組件，並且還可用於在輸入的單詞不是索引中的有效單詞時執行相關單詞猜測。

谷歌算法執行短語建議和更正。 谷歌算法也有一些上下文的概念...如果你搜索的第一個詞是天氣相關的，你結合他們「weatherforcst」vs「monsoonfrcst」vs「deskfrcst」 - 我的猜測是幕後排名正在改變基於遇到的第一個單詞的建議 - 預測和天氣都是相關詞，因此預測在Did-You-Mean猜測中得到很高的排名。 （ngrams），短語術語（帶狀皰疹），單詞接近（單詞聚類索引），三元搜索樹（單詞查找）。

Answer 6

谷歌的確切算法是未知的，但it is said通過用戶輸入的統計分析工作。一種不適用於大多數情況的方法。更常見的是自動完成使用下列之一來實現：

• 樹。通過索引樹形結構中的可搜索文本（前綴樹，後綴樹，dawg等），可以以犧牲內存存儲爲代價執行非常快速的搜索。樹遍歷可以適應近似匹配。
• 模式分區。通過將文本劃分爲令牌（ngrams），可以使用簡單的哈希方案執行對模式發生的搜索。
• 篩選。找到一組潛在的匹配，然後應用順序算法檢查每個候選人。

看看completely，這是一個Java自動完成庫，它實現了後面的一些概念。

Answer 7

對於子串和模糊匹配，Levenshtein距離算法對我來說工作得相當好。儘管我承認它似乎不像自動完成/建議的行業實現那樣完美。 Google和Microsoft的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]; 
} 

Answer 8

如果你正在尋找這個問題的整體設計，嘗試https://www.interviewbit.com/problems/search-typeahead/閱讀的內容。

他們首先通過建立自動填充，通過使用一個trie的天真方法，然後建立它。他們還解釋了抽樣和離線更新等優化技術，以滿足特定用例的需求。

爲了保持解決方案的可擴展性，您必須智能地分割您的trie數據。