java - 实现模糊搜索建议/单词完成

Question

我有一堆短语的列表。因为这是一个相当长的列表，所以我还有一个文本框，用户可以在其中输入内容作为搜索栏。截至目前，不完全包含搜索栏中字母的术语将被过滤掉。不过，我想让它列出一些关于这个词可能是什么的建议。

注意:我不是在寻找“您的意思是...”或类似 here 的拼写检查算法或 here或 here (尽管第一个链接的 this image 看起来不错)；我想要一种能够为不完整单词或短语建议最佳匹配的算法；例如“bat” 应该比 “car” 更适合 “battery”。

使用 Google 的方法返回以(大致)相同的字母开头的最常见的几个字符串也是不切实际的，因为据我所知，列表中的每个元素与任何其他。

此外，我想在 Java (8) 中执行此操作；但是，其他语言的答案也是可以接受的，只要它们不使用 Java 没有等效项的内置函数即可。如果它有用，我写了一个修改版本的 Levenshtein 距离(如下)，它用表示“任何字符”的星号填充搜索字符串。这适用于单个单词，例如"mud" 是 "muddy" 的完美匹配，但考虑到人们可能会使用 "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 页

它可能会为插入这种模糊搜索系统提供一些想法