使用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公式是正确的,但我想进一步构建并编写一个方法,可以微调我的搜索,所以我可以得到更多相关和相关的词.

我已经工作了几个小时,失去了创造力.

我的问题:是否有可能微调现有方法以返回相关/相关的字或者我应该采取另一种方法或??? 在所有情况下是或否,我很欣赏是否可以获得有关改善搜索结果的输入和灵感？

---

UPDATE

在长时间回答这个问题之后,我还没有真正找到解决方案,我回到它,因为是时候我需要一个有用的答案,可以用JAVA代码样本提供答案,但最重要的是详细的回答可用方法和方法的描述,用于索引最佳和最相关的搜索结果,并忽略任何相关的单词.我知道这是一个开放和无穷无尽的领域,但我需要一些灵感来开始一些地方.

注意:现在最老的答案是基于其中一个评论输入而没有帮助(没用),它只是对距离进行排序,这并不意味着获得更好的搜索结果/质量.

所以我进行了距离排序,结果是这样的:

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

所以word jobbaser是相关的,jacob/jakob是不相关的,但jobbaser的距离大于jacob/jakob.所以这并没有真正帮助.

---

有关答案的一般反馈

• @SergioMontoro,它几乎解决了这个问题.
• @uSeemSurprised,它解决了问题,但需要不断操纵.
• @Gene的概念非常好,但它在外部网址上传播.

---

谢谢 我个人感谢所有为这个问题做出贡献的人,我得到了很好的答案和有用的评论.

特别感谢@SergioMontoro,@ uSeemSurprised和@Gene的答案,这些答案是不同但有效且有用的答案.

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

我希望我能给予所有这些答案赏金.选择一个答案并给予赏金,这并不意味着其他答案无效,但这只意味着我选择的特定答案对我有用.

Answer 1

如果不理解@DrYap建议的单词的含义,那么比较两个单词的下一个逻辑单元(如果你不是在寻找拼写错误)就是音节.修改Levenshtein以比较音节而不是字符非常容易.困难的部分是将单词分解为音节.有一个Java实现TeXHyphenator-J,可用于分割单词.基于这个连字库,这里是Michael Gilleland和Chas Emerick编写的Levenshtein函数的修改版本.更多关于这里和这里的音节检测.当然,你要避免使用标准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];
    }

}

Answer 2

您可以通过在连续字符匹配时调整评分来修改Levenshtein距离.

只要存在匹配的连续字符,就可以减少分数,从而使搜索更加相关.

例如:让我们说我们想要降低得分的因子是10然后如果总之我们发现子串"作业"我们可以将得分减少10当我们遇到"j"时将其减少(10 + 20)当我们找到字符串"jo"并最终在我们找到"工作"时将得分减少(10 + 20 + 30).

我在下面写了一个c ++代码:

#include <bits/stdc++.h>

#define INF -10000000
#define FACTOR 10

using namespace std;

double memo[100][100][100];

double Levenshtein(string inputWord, string checkWord, int i, int j, int count){
    if(i == inputWord.length() && j == checkWord.length()) return 0;    
    if(i == inputWord.length()) return checkWord.length() - j;
    if(j == checkWord.length()) return inputWord.length() - i;
    if(memo[i][j][count] != INF) return memo[i][j][count];

    double ans1 = 0, ans2 = 0, ans3 = 0, ans = 0;
    if(inputWord[i] == checkWord[j]){
        ans1 = Levenshtein(inputWord, checkWord, i+1, j+1, count+1) - (FACTOR*(count+1));
        ans2 = Levenshtein(inputWord, checkWord, i+1, j, 0) + 1;
        ans3 = Levenshtein(inputWord, checkWord, i, j+1, 0) + 1;
        ans = min(ans1, min(ans2, ans3));
    }else{
        ans1 = Levenshtein(inputWord, checkWord, i+1, j, 0) + 1;
        ans2 = Levenshtein(inputWord, checkWord, i, j+1, 0) + 1;
        ans = min(ans1, ans2);
    }
    return memo[i][j][count] = ans;
}

int main(void) {
    // your code goes here
    string word = "job";
    string wordList[40];
    vector< pair <double, string> > ans;
    for(int i = 0;i < 40;i++){
        cin >> wordList[i];
        for(int j = 0;j < 100;j++) for(int k = 0;k < 100;k++){
            for(int m = 0;m < 100;m++) memo[j][k][m] = INF;
        }
        ans.push_back( make_pair(Levenshtein(word, wordList[i], 
            0, 0, 0), wordList[i]) );
    }
    sort(ans.begin(), ans.end());
    for(int i = 0;i < ans.size();i++){
        cout << ans[i].second << " " << ans[i].first << endl;
    }
    return 0;
}

链接到演示:http://ideone.com/4UtCX3

这里FACTOR为10,您可以尝试其他单词并选择合适的值.

另请注意,上述Levenshtein距离的复杂性也有所增加,现在我们也O(n^3)不再O(n^2)像现在那样跟踪计算我们遇到的连续字符数的计数器.

您可以在找到一些连续的子串然后不匹配后逐渐增加分数,而不是当前我们将固定分数1添加到总分中的方式.

同样在上面的解决方案中,你可以删除得分> = 0的字符串,因为它们根本不是释放的,你也可以选择一些其他阈值来获得更准确的搜索.