/**
Levenshtein distance最先是由俄国科学家Vladimir Levenshtein在1965年发明,用他的名字命名。不会拼读,可以叫它edit distance(编辑距离)。
Levenshtein distance可以用来:
Spell checking(拼写检查)
Speech recognition(语句识别)
DNA analysis(DNA分析)
Plagiarism detection(抄袭检测)
LD用m*n的矩阵存储距离值。算法大概过程:
str1或str2的长度为0返回另一个字符串的长度。
初始化(n+1)*(m+1)的矩阵d,并让第一行和列的值从0开始增长。
扫描两字符串(n*m级的),如果:str1[i] == str2[j],用temp记录它,为0。否则temp记为1。然后在矩阵d[i][j]赋于d[i-1][j]+1 、d[i][j-1]+1、d[i-1][j-1]+temp三者的最小值。
扫描完后,返回矩阵的最后一个值即d[n][m]
*/
public class LD
{
/**
* 计算矢量距离
* Levenshtein Distance(LD)
* @param str1 str1
* @param str2 str2
* @return ld
*/
public int ld(String str1, String str2)
{
//Distance
int [][] d;
int n = str1.length();
int m = str2.length();
int i; //iterate str1
int j; //iterate str2
char ch1; //str1
char ch2; //str2
int temp;
if (n == 0)
{
return m;
}
if (m == 0)
{
return n;
}
d = new int[n + 1][m + 1];
for (i = 0; i <= n; i++)
{ d[i][0] = i;
}
for (j = 0; j <= m; j++)
{
d[0][j] = j;
}
for (i = 1; i <= n; i++)
{
ch1 = str1.charAt(i - 1);
//match str2
for (j = 1; j <= m; j++)
{
ch2 = str2.charAt(j - 1);
if (ch1 == ch2)
{
temp = 0;
}
else
{
temp = 1;
}
d[i][j] = min(d[i - 1][j] + 1, d[i][j - 1] + 1, d[i - 1][j - 1] + temp);
}
}
return d[n][m];
}
private int min(int one, int two, int three)
{
int min = one;
if (two < min)
{
min = two;
}
if (three < min)
{
min = three;
}
return min;
}
/**
* 计算相似度
* @param str1 str1
* @param str2 str2
* @return sim
*/
public double sim(String str1, String str2)
{
int ld = ld(str1, str2);
return 1 - (double) ld / Math.max(str1.length(), str2.length());
}
/**
* 测试
* @param args
*/
public static void main(String[] args)
{
LD ld = new LD();
double num = ld.sim("xie", "xies");
System.out.println(num);
}
}
分享到:
相关推荐
Levenshtein算法python也是用的这个对比字符串相似度的,还不错
计算两个字符串相似度,返回0-1的相似值 0为完全不同,1位完全相同 例如:上海如家酒店中环店,以下是与其比较的相似度 上海如家酒店中环店 1.000000 上海中环店如家酒店 0.888889 上海中环如家酒店 0.823529 如家...
比较两个字符串的相似度,利用LCS算法计算出两个字符串的最长公序列,根据最长公序列得出相似度,例如: 字符串1:1234 字符串2:51234,则他们的相似度为:4*2/(4+5)。
输入2个中文字符串,计算2个字符串的相似度,用于相似度排序。
用途:可用于论文抄袭检测、DNA等。...算法实现思路:通过对一个字符串插入、删除、替换转变成另一个字符串所需要的步骤称为距离,计算两个字符串之间的距离,从而可以得到两个字符串之间的相似度。
Levenshtein Distance-两字符串相似度计算...
C#中文文本匹配,字符串匹配,中文词语匹配,计算2个句子相似度 中文匹配C#中文文本匹配,字符串匹配,中文词语匹配,计算2个句子相似度 C#中文文本匹配,字符串匹配,中文词语匹配,计算多个句子相似度 C#中文文本...
在网站开发中,我们经常使用php similar text 计算两个字符串相似度。本文涉及到similar text函数语法、用法详解,感兴趣的朋友一起学习吧
比较两个字符串的相似度,利用Levenshein算法计算出两个字符串的最小编辑距离,根据最小编辑距离得出相似度,例如: 字符串1:1234 字符串2:51234,则他们的相似度为:4/5。
两个字符串,计算出两个字符串的相似度,用于模糊匹配,很简单的小例子
Levenshtein:快速计算编辑距离以及字符串的相似度
自己开发的Excel函数,可以判定两个字符串的相似度。
Java 实现推荐系统 两个字符串 余弦相似度 算法。
Strutil strutil提供了用于计算字符串相似度的字符串度量标准以及其他字符串实用程序功能。 完整文档可在以下找到: : 。安装 go get github.com/adrg/strutil字符串指标杰罗·温克勒史密斯·沃特曼·高图索伦森-...
主要介绍了java字符串相似度算法,是Java实现比较典型的算法,具有一定参考借鉴价值,需要的朋友可以参考下
一个完整可直接用的LD算法计算两个字符串之间的相似度。
最后对两个指标加权求和得到字符串相似度的定量描述。与传统的算法比较,该算法更简便,时间复杂度为O(n log(n))。实验结果表明,该方法提高了字符串相似度的准确率,得到的数据结果更合理。
#region 计算字符串相似度 /// /// 计算字符串相似度 /// /// ”str1″>字符串1 /// ”str2″>字符串2 /// 相似度 public static float Levenshtein(string str1, string str2) {
//计算两个字符串的长度。 int len1 = str1.Length; int len2 = str2.Length; //建立上面说的数组,比字符长度大一个空间 int[,] dif = new int[len1 + 1, len2 + 1]; //赋初值,步骤B。 for (int a = 0; a &...