执行模糊搜索建议/单词完成

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'的条目将包含“赛车”，“汽车”，“猫”，“主雕刻师”等等。因此，不需要搜索来获得初始列表。

使用字典方法的另一个好处是，您可以预处理每个字母的列表，以便以该字母开头的单词位于列表的前面。这很好，因为大多数时候当有人在搜索时，他正在寻找一个以他所键入的第一个字母开头的单词或短语。但你可以通过流行或任何其他标准轻松安排。

我已经使用过这种方法很多次了，并且它工作得很好。它实现起来很简单，并且通常不需要任何优化就足够快。上面提到的字典优化对于所有人来说都是足够的，除了一些简单的蛮力方法不起作用的情况外，有一次我需要两个字典：一个用于第一个字符，另一个用于字母对。

即使事实证明这不是最终的解决方案，但它很有用，因为它很容易证明是正确的，并且可以测试其他更复杂的算法。