執行模糊搜索建議/單詞完成

Question

我有一堆短語的列表。由於這是一個相當長的列表，我還有一個文本框，用戶可以將其作爲搜索欄輸入。截至目前，搜索欄中的字母不完全包含的條款將被濾除。然而，我想讓它列出一些關於這個詞可能是什麼的建議。

注：我不是在尋找像那些here或here或here（雖然this image從第一環節似乎不錯）一個「你的意思是......」或拼寫檢查算法;我想要一個算法，能夠建議不完整的單詞或短語的最佳匹配;例如單詞"bat"應該是單詞"battery"比單詞"car"更好的匹配。

使用Google返回以（大致）相同的字母開頭的最常見的字符串的方法也是不切實際的，因爲據我所知，列表中的每個元素都是相同的和其他人一樣。我想在Java（8）中做到這一點;然而，其他語言答案是可以接受的，只要他們不使用Java沒有的同等功能的內置函數。如果它有用，我寫了一個Levenshtein距離的修改版本（見下文），它填充搜索字符串時用星號表示「任何字符」。這適用於單個單詞，例如"mud"與完美匹配，但在考慮人們可能使用"car"來搜索"race car"時不夠好。

/** 
* <ul> 
* <b><i>searchDistance</i></b><br> 
* <br> 
* <code>&nbsp;public static int searchDistance(String key, String match)</code><br> 
* <br> 
* Gets the Levenshtein distance between <code>key</code> and <code>match</code>. <br> 
* If <code>useAsterisk</code> is true, then the follwing applies: If <code>key</code> is shorter than <code>match</code>, the asterisk <code>'*'</code> is appended to it until the lengths are equal. Asterisks can be used in <code>key</code> to signify 'any character.' 
* @param key - The text to search for 
* @param match - The text to compare <code>key</code> against 
* @param useAsterisk - Whether or not to use asterisks for the purpose described above 
* @return the Levenshtein distance between <code>key</code> and <code>match</code>. 
*   </ul> 
*/ 
public static int searchDistance(String key, String match, boolean useAsterisk) { 
    while (key.length() < match.length()) { 
     key = key + "*"; 
    } 

    int[][] matrix = new int[key.length() + 1][match.length() + 1]; 

    for (int i = 0; i < matrix.length; i++) { 
     matrix[i][0] = i; 
    } 

    for (int i = 0; i < matrix[0].length; i++) { 
     matrix[0][i] = i; 
    } 

    for (int a = 1; a < matrix.length; a++) { 
     for (int b = 1; b < matrix[0].length; b++) { 
      matrix[a][b] = Math.min(Math.min(matrix[a - 1][b] + 1, matrix[a][b - 1] + 1), matrix[a - 1][b - 1] + (key.charAt(a - 1) == match.charAt(b - 1) || key.charAt(a - 1) == '*' ? 0 : 1)); 
     } 
    } 

    return matrix[matrix.length - 1][matrix[0].length - 1]; 
} 

TL; DR：是否有一種很好的方式可以爲搜索字詞提供完成建議？

在此先感謝！

Answer 1

嘗試看看，K帶狀皰疹方法：http://infolab.stanford.edu/~ullman/mmds/book.pdf：77頁

它可能給一些想法impelenting這種模糊搜索系統

Answer 2

總有簡單的，窮舉法。即使有相當多的短語，它也可以很好地工作。

想象一下，您有一百萬個詞組的列表。用戶輸入字母'c'。您搜索所有包含字母'c'的短語列表並顯示它們。你也保持這個結果。

然後，用戶鍵入'a'。現在，您搜索從上一次搜索返回的字符串列表中的字符串「ca」。所以，你已經從所有短語中刪除了你所知道的那些包含字母'c'的短語。考慮到大約37％的英文單詞包含字母'c'（參見http://phrontistery.info/ihlstats.html），你已經將你的名單減少了近三分之二。

無論如何，你現在有一個包含字母「ca」的短語列表。與所有短語的列表相比，這個列表將會比較小。隨着用戶輸入字符，您可以繼續完善您的列表。

如果整個列表的初始搜索時間過長，則可以通過創建一個字典，按字母索引，並且包含包含該字母的單詞列表來輕鬆優化該字典。因此，例如，'c'的條目將包含「賽車」，「汽車」，「貓」，「主雕刻師」等等。因此，不需要搜索來獲得初始列表。

使用字典方法的另一個好處是，您可以預處理每個字母的列表，以便以該字母開頭的單詞位於列表的前面。這很好，因爲大多數時候當有人在搜索時，他正在尋找一個以他所鍵入的第一個字母開頭的單詞或短語。但你可以通過流行或任何其他標準輕鬆安排。

我已經使用過這種方法很多次了，並且它工作得很好。它實現起來很簡單，並且通常不需要任何優化就足夠快。上面提到的字典優化對於所有人來說都是足夠的，除了一些簡單的蠻力方法不起作用的情況外，有一次我需要兩個字典：一個用於第一個字符，另一個用於字母對。

即使事實證明這不是最終的解決方案，但它很有用，因爲它很容易證明是正確的，並且可以測試其他更復雜的算法。