相似度得分 – Levenshtein

我在Java中实现了Levenshtein算法，现在我正在通过算法进行校正，即成本。 这确实有点帮助但不多，因为我希望结果为百分比。

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

我也想知道你们这样做的原因以及原因。

Answer 1

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

• 所以Levenshtein距离为0表示：两个弦都相等
• 最大Levenshtein距离（所有字符都不同）是max（string1.length，string2.length）

因此，如果您需要一个百分比，您必须使用它来指向比例。 例如：

“你好”，“你好” – > Levenstein距离1这两个字符串的Max Levenstein距离是：5。所以20％的字符不匹配。

String s1 = "Hallo"; String s2 = "Hello"; int lfd = calculateLevensteinDistance(s1, s2); double ratio = ((double) lfd) / (Math.max(s1.length, s2.length)); 

Answer 2

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

Answer 3

  // 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]; } } 

Answer 4

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

Levenshtein算法的实现倾向于不记录那些编辑应该是什么，但是在维基百科页面上给出抽象算法并不难以计算。

Answer 5

我认为这将是有用的链接LevenshteinDistance

它可以通过maven依赖使用

maven依赖

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

  org.apache.commons commons-text 1.3  

例如，请看下面的代码

 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()); } }