在Java中使用Levenshtein distance改进搜索结果

algorithm java search levenshtein-distance search-engine

2022-09-01 10:00:36

我有以下工作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

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

我花了几个小时来研究它，失去了创造力的视野。

我的问题：是否可以微调现有方法以返回相关/相关单词或者我应该采取另一种方法 Or???在所有情况下，是的或否，我很感激是否可以获得有关改善搜索结果的意见和灵感？

更新

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

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

所以我做了距离排序，结果是这样的：

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，它几乎解决了这个问题。
@uSeemSurprised，它解决了问题，但需要不断操纵。
@Gene概念非常好，但它在外部URL上中继。

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

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

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

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

答案 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];
    }

}

答案 2

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

每当有连续的字符匹配时，就可以降低分数，从而使搜索更具相关性。

例如：假设我们想要减少分数的因素是10，那么如果在一个单词中我们找到了子字符串“job”，当我们找到“j”时，我们可以将分数降低10，当我们找到字符串“jo”时，我们可以将其降低（10 + 20），最后当我们找到“job”时，分数降低（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 Distance的复杂性也有所增加，现在而不是现在，我们还在跟踪计数器，该计数器计算我们遇到的连续字符数。O(n^3)O(n^2)

在找到一些连续的子字符串然后不匹配之后，您可以通过逐渐增加分数来进一步玩乐谱，而不是像当前那样，我们将固定分数1添加到总分中。

同样在上面的解决方案中，您可以删除得分为> = 0的字符串，因为它们根本不是相关的，您还可以选择其他一些阈值以进行更准确的搜索。