29

我用 Java 实现了 Levenshtein 算法，现在我得到了算法所做的更正，也就是成本。这确实有一点帮助，但没有多大帮助，因为我希望将结果作为百分比。

所以我想知道如何计算那些相似点。

我也想知道你们是怎么做的以及为什么。

4

6 回答 6

41

两个字符串之间的Levenshtein距离定义为将一个字符串转换为另一个字符串所需的最小编辑次数，允许的编辑操作是插入、删除或替换单个字符。（维基百科）

  • 所以 Levenshtein 距离为 0 意味着：两个字符串相等
  • 最大 Levenshtein 距离（所有字符都不同）是 max(string1.length, string2.length)

所以如果你需要一个百分比，你必须用它来缩放。例如：

"Hallo", "Hello" -> Levenstein distance 1 这两个字符串的最大 Levenstein 距离是：5。所以 20% 的字符不匹配。

String s1 = "Hallo";
String s2 = "Hello";
int lfd = calculateLevensteinDistance(s1, s2);
double ratio = ((double) lfd) / (Math.max(s1.length, s2.length));
于 2011-05-22T12:47:11.913 回答
19

您可以下载Apache Commons StringUtils并研究（并可能使用）他们对 Levenshtein 距离算法的实现。

于 2011-05-22T11:35:58.933 回答
4 
 // Refer This: 100% working

public class demo 
{
public static void main(String[] args) 
{
    String str1, str2;

    str1="12345";
    str2="122345";


    int re=pecentageOfTextMatch(str1, str2);
    System.out.println("Matching Percent"+re);
}

public static int pecentageOfTextMatch(String s0, String s1) 
{                       // Trim and remove duplicate spaces
    int percentage = 0;
    s0 = s0.trim().replaceAll("\\s+", " ");
    s1 = s1.trim().replaceAll("\\s+", " ");
    percentage=(int) (100 - (float) LevenshteinDistance(s0, s1) * 100 / (float) (s0.length() + s1.length()));
    return percentage;
}

public static int LevenshteinDistance(String s0, String s1) {

    int len0 = s0.length() + 1;
    int len1 = s1.length() + 1;  
    // the array of distances
    int[] cost = new int[len0];
    int[] newcost = new int[len0];

    // initial cost of skipping prefix in String s0
    for (int i = 0; i < len0; i++)
        cost[i] = i;

    // dynamically computing the array of distances

    // transformation cost for each letter in s1
    for (int j = 1; j < len1; j++) {

        // initial cost of skipping prefix in String s1
        newcost[0] = j - 1;

        // transformation cost for each letter in s0
        for (int i = 1; i < len0; i++) {

            // matching current letters in both strings
            int match = (s0.charAt(i - 1) == s1.charAt(j - 1)) ? 0 : 1;

            // computing cost for each transformation
            int cost_replace = cost[i - 1] + match;
            int cost_insert = cost[i] + 1;
            int cost_delete = newcost[i - 1] + 1;

            // keep minimum cost
            newcost[i] = Math.min(Math.min(cost_insert, cost_delete),
                    cost_replace);
        }

        // swap cost/newcost arrays
        int[] swap = cost;
        cost = newcost;
        newcost = swap;
    }

    // the distance is the cost for transforming all letters in both strings
    return cost[len0 - 1];
}

}
于 2014-10-08T06:50:06.117 回答
2

LevenshteinDistance

可以通过maven依赖使用

我确实认为使用此实现比编写自己的实现更好。

<dependency>
    <groupId>org.apache.commons</groupId>
    <artifactId>commons-text</artifactId>
    <version>1.3</version>
</dependency>

例如，看看下面的代码

import org.apache.commons.text.similarity.LevenshteinDistance;

public class MetricUtils {
    private static LevenshteinDistance lv = new LevenshteinDistance();

    public static void main(String[] args) {
        String s = "running";
        String s1 = "runninh";
        System.out.println(levensteinRatio(s, s1));
    }

    public static double levensteinRatio(String s, String s1) {
        return 1 - ((double) lv.apply(s, s1)) / Math.max(s.length(), s1.length());
    }
}
于 2018-04-04T09:47:38.830 回答
0

两个字符串之间的 Levenshtein 差异的最大值将是两个字符串长度的最大值。（这对应于每个字符的符号变化，直到较短字符串的长度，加上插入或删除，具体取决于您是从较短到较长还是反之亦然。）鉴于此，两者的相似性字符串必须是该最大值与该最大值与实际 Levenshtein 差值之间的差值之间的比率。

Levenshtein 算法的实现往往不会记录这些编辑应该是什么，但考虑到Wikipedia 页面上的抽象算法，计算起来应该不那么难。

于 2011-05-22T12:05:27.110 回答
-1

要计算分数，您需要最大可能成本（插入+删除+替代）。然后使用下面的公式 -

score = 1 - actual_cost/max_possible_cost

请参阅此内容以供参考 - Levenshtein Score Calculation Func

于 2018-12-22T06:19:24.943 回答