java - 在 Java 中使用 Levenshtein 距离改进搜索结果

Question

我有以下工作 Java 代码，用于在单词列表中搜索单词，它可以完美地按预期工作:

public class Levenshtein {
    private int[][] wordMartix;

    public Set similarExists(String searchWord) {

        int maxDistance = searchWord.length();
        int curDistance;
        int sumCurMax;
        String checkWord;

        // preventing double words on returning list
        Set<String> fuzzyWordList = new HashSet<>();

        for (Object wordList : Searcher.wordList) {
            checkWord = String.valueOf(wordList);
            curDistance = calculateDistance(searchWord, checkWord);
            sumCurMax = maxDistance + curDistance;
            if (sumCurMax == checkWord.length()) {
                fuzzyWordList.add(checkWord);
            }
        }
        return fuzzyWordList;
    }

    public int calculateDistance(String inputWord, String checkWord) {
        wordMartix = new int[inputWord.length() + 1][checkWord.length() + 1];

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

        for (int j = 0; j <= checkWord.length(); j++) {
            wordMartix[0][j] = j;
        }

        for (int i = 1; i < wordMartix.length; i++) {
            for (int j = 1; j < wordMartix[i].length; j++) {
                if (inputWord.charAt(i - 1) == checkWord.charAt(j - 1)) {
                    wordMartix[i][j] = wordMartix[i - 1][j - 1];
                } else {
                    int minimum = Integer.MAX_VALUE;
                    if ((wordMartix[i - 1][j]) + 1 < minimum) {
                        minimum = (wordMartix[i - 1][j]) + 1;
                    }

                    if ((wordMartix[i][j - 1]) + 1 < minimum) {
                        minimum = (wordMartix[i][j - 1]) + 1;
                    }

                    if ((wordMartix[i - 1][j - 1]) + 1 < minimum) {
                        minimum = (wordMartix[i - 1][j - 1]) + 1;
                    }

                    wordMartix[i][j] = minimum;
                }
            }
        }

        return wordMartix[inputWord.length()][checkWord.length()];
    }

}

现在当我搜索像 job 这样的词时，它会返回一个列表:

输出

joborienterede
jobannoncer
jobfunktioner
perjacobsen
jakobsen
jobprofiler
jacob
jobtitler
jobbet
jobdatabaserne
jobfunktion
jakob
jobs
studenterjobber
johannesburg
jobmuligheder
jobannoncerne
jobbaser
job
joberfaringer

如您所见，输出有很多相关的词，但也有不相关的词，如 jakob、jacob 等，这对于 Levenshtein 公式是正确的，但我想进一步构建并编写一个可以微调我的搜索的方法，以便我可以获得更多相关和相关的词。

我已经为此工作了几个小时，却失去了创造力。

我的问题:是否可以微调现有方法以返回相关/相关单词或者我应该采取其他方法还是？在所有情况下是或否，如果能获得关于改进搜索结果的意见和灵感，我将不胜感激？

---

更新

很久以前问过这个问题后，我还没有真正找到解决方案，我又回到了它，因为现在是我需要有用答案的时候了，可以用 JAVA 代码示例提供答案，但是什么最重要的是一个详细的答案，其中描述了用于索引最佳和最相关的搜索结果并忽略不相关的单词的可用方法和方法。我知道这是一个开放且无止境的领域，但我需要一些灵感才能从哪里开始。

Note: The oldest answer right now is based on one of the comment inputs and is not helpful (useless), it just sorting the distance, that does not mean getting better search results/quality.

于是我做了距离排序，结果是这样的:

job
jobs
jacob
jakob
jobbet
jakobsen
jobbaser
jobtitler
jobannoncer
jobfunktion
jobprofiler
perjacobsen
johannesburg
jobannoncerne
joberfaringer
jobfunktioner
jobmuligheder
jobdatabaserne
joborienterede
studenterjobber

所以单词 jobbaser 是相关的，而 jacob/jakob 是不相关的，但是 jobbaser 的距离大于 jacob/jakob。所以这并没有真正帮助。

---

关于答案的一般反馈

• @SergioMontoro，它几乎解决了这个问题。
• @uSemSurprise，它解决了问题，但需要不断操纵。
• @Gene 概念很棒，但它是在外部 url 上中继的。

---

谢谢 我要亲自感谢所有为这个问题做出贡献的人，我得到了很好的答案和有用的评论。

特别感谢@SergioMontoro、@uSemSurprise 和@Gene 的回答，这些回答不同但有效且有用。

@D.Kovács 指出了一些有趣的解决方案。

我希望我能给所有这些答案提供赏金。 选择一个答案并给予奖励，这并不意味着其他答案无效，而这只意味着我选择的特定答案对我有用。

Answer 1

如果不理解像@DrYap 这样的单词的含义，下一个比较两个单词的逻辑单元(如果你不是在寻找拼写错误的话)是音节。修改 Levenshtein 以比较音节而不是字符非常容易。困难的部分是将单词分解成音节。有一个Java实现TeXHyphenator-J可用于拆分单词。基于这个连字符库，这里是 Michael Gilleland & Chas Emerick 编写的 Levenshtein 函数的修改版本.更多关于音节检测 here和 here .当然，您需要避免两个单音节词的音节比较，这可能使用标准的 Levenshtein 来处理这种情况。

import net.davidashen.text.Hyphenator;

public class WordDistance {

    public static void main(String args[]) throws Exception {
        Hyphenator h = new Hyphenator();
        h.loadTable(WordDistance.class.getResourceAsStream("hyphen.tex"));
        getSyllableLevenshteinDistance(h, args[0], args[1]);
    }

    /**
     * <p>
     * Calculate Syllable Levenshtein distance between two words </p>
     * The Syllable Levenshtein distance is defined as the minimal number of
     * case-insensitive syllables you have to replace, insert or delete to transform word1 into word2.
     * @return int
     * @throws IllegalArgumentException if either str1 or str2 is <b>null</b>
     */
    public static int getSyllableLevenshteinDistance(Hyphenator h, String s, String t) {
        if (s == null || t == null)
            throw new NullPointerException("Strings must not be null");

        final String hyphen = Character.toString((char) 173);
        final String[] ss = h.hyphenate(s).split(hyphen);
        final String[] st = h.hyphenate(t).split(hyphen);

        final int n = ss.length;
        final int m = st.length;

        if (n == 0)
            return m;
        else if (m == 0)
            return n;

        int p[] = new int[n + 1]; // 'previous' cost array, horizontally
        int d[] = new int[n + 1]; // cost array, horizontally

        for (int i = 0; i <= n; i++)
            p[i] = i;

        for (int j = 1; j <= m; j++) {
            d[0] = j;
            for (int i = 1; i <= n; i++) {
                int cost = ss[i - 1].equalsIgnoreCase(st[j - 1]) ? 0 : 1;
                // minimum of cell to the left+1, to the top+1, diagonally left and up +cost
                d[i] = Math.min(Math.min(d[i - 1] + 1, p[i] + 1), p[i - 1] + cost);
            }
            // copy current distance counts to 'previous row' distance counts
            int[] _d = p;
            p = d;
            d = _d;
        }

        // our last action in the above loop was to switch d and p, so p now actually has the most recent cost counts
        return p[n];
    }

}