原文地址:http://www.jmatrix.org/algorithm/166.html
字符串相似度计算是查找两个字符串的公共子串,利用公共子串的长度根据相应的公式来衡量两个字符串的相似程度。字符串相似度计算算法很多,如LCS算法、Levenshtein Distance算法、Heckel算法、GST算法等。对于历经N次笔试面试的人来说,这个再熟悉不过了。应要求,要帮忙写个计算两字符串相似度的算法,所以我特意去看了篇论文,并据此实现LCS与GST算法。
1. 概念
LCS(最长公共子序列)算法是将两个给定字符串分别删去0个或多个字符,但不改变剩余字符串的顺序后得到的长度最长的相同字符序列。给定字符串P、T、X,X称为P和T的最长公共子序列是指X是P和T的公共子序列,且对于P和T的任意公共子序列W,都有W<=X。
GST(Greedy String Tiling)算法是一种贪婪串匹配算法,这一算法对两个字符串进行贪婪式搜索以找出最大公有子串,它需要对要计算的两个字符串进行多次搜索,每次找出当前字符串中未“标注”部分的最长公共子串,并把找出的最长公共子串“标注”为已使用,避免最大匹配重复使用。
以“abcdefghijklmuvwxyz”与“ijkabclmdefghpq”为例解释GST的搜索过程:
(1)假如我们设最小匹配长度为2。第一次搜寻过程,先找到abc,此时最大匹配长度是3,之后找到defgh,因此它的长度大于3,所以此时最大匹配长度5,之后找到ijk,由于其长度小于5,放弃,最后是lm,其长度同样小于当前最大匹配长度5,放弃。
(2)将(1)中找到的最大匹配子串”标注为已使用“,重复(1)的过程,不过不再对”已标注子串“搜索,直到(1)中找到的最大匹配子串的长度为设置的最小匹配长度。
2. 应用场景
从上面的介绍中,可以看出LCS与GST的一个重要区别就是LCS得到的最大公共子串是严格有序的,对于一些顺序调换的情况,它计算出的相似度是比较低的,相反,GST并不要求其子串严格有序,只有存在相等子串,及时位置不对也可找到,因此相对来说,它计算出的相似度更高。
在分析生物学领域,DNA分子常被表示成一个字符串,两个DNA分子之间的相似性常用它们共同包含的碱基对的序列长度来度量,这是最长公共子序列应用最广泛的领域,LCS还可以应用于数据压缩、文件比较、语言识别等方面。GST算法在信息检索、文本编辑、信息提取等领域有重要的应用。
3. 算法实现。
这里先给出别人的算法伪码,之后使用Java简单的实现一下相应的算法。
3.1 LCS算法实现
对于LCS的实现,总所周知是采用动态规划,用C(i, j )表示长度为i的字符创P与长度为j的T的最优值,也即最长公共子串长度,递推式为:
- 当i=0或j=0时,C(i, j)=0;
- 当i,j>0且pi=qj时, C(i, j) = C(i+1, j+1) + 1;
- 当i,j>0且pi不等于qj时, C(i, j) = max( C(i+1, j) , C(i, j+1) );
因此,计算C(i, j)的过程为:
int lcs_length( char* T, char* P){
for(i = m; i>=0;i–)
{
if(P[i] == ‘\0′ || T[j] ==’\0′)
C(i, j) = 0;
else if(P[i] == T[j])
C(i, j) = C(i+1, j+1) + 1;
else
C(i, j) = max( C(i+1, j) , C(i, j+1) );
}
}
之后,根据C得到最长公共子串的过程为:
S = {};
i = 0;
j = 0 ;
while( i<m && j<n){
if(P[i]==T[j]){
add T[j] to end of S;
i++; j++;
}
else if(C[i+1,j]>=C[i,j+1])
i++;
else
j++;
}
Java实现代码为:
public class Lcs { private int matchs[][] = null; public void calculateLength(String pwd1, String pwd2) { int len = pwd1.length() > pwd2.length() ? pwd1.length() : pwd2.length(); matchs = new int[len + 1][len + 1]; // init the match array. for (int i = 0; i <= pwd1.length(); i++) { for (int j = 0; j <= pwd2.length(); j++) { matchs[i][j] = 0; } } // calculate for (int i = pwd1.length(); i >= 0; i--) { for (int j = pwd2.length(); j >= 0; j--) { if (i == pwd1.length() || j == pwd2.length()) { matchs[i][j] = 0; } else if (pwd1.charAt(i) == pwd2.charAt(j)) matchs[i][j] = 1 + matchs[i + 1][j + 1]; else { matchs[i][j] = max(matchs[i + 1][j], matchs[i][j + 1]); } } } } public String getLCS(String pwd1, String pwd2){ StringBuffer buf = new StringBuffer(); int i = 0,j=0,len1=pwd1.length(),len2 = pwd2.length(); while(ithis.matchs[i][j+1]) i++; else j++; } return buf.toString(); } //计算相似度 public double calSimilarity(String pwd1, String pwd2){ int length = getLCS(pwd1, pwd2).length(); return (2.0*length)/(pwd1.length()+pwd2.length()); } private int max(int src, int des) { return src > des ? src : des; } }
3.2 GST算法实现
GST的搜索过程在”概念“部分已详细介绍,所以这里直接给Java实现代码:
public class Gst { private final int MIN_LENGTH = 2; List titles = new ArrayList(); List matchs = new ArrayList(); //GST算法实现 public void calculateGST(String pwd1, String pwd2) { int maxlength, count; int len1 = pwd1.length(); int len2 = pwd2.length(); // 辅助标记变量 int[] mark1 = new int[len1]; int[] mark2 = new int[len2]; for (int i = 0; i < len1; i++) mark1[i] = 0; for (int j = 0; j < len2; j++) mark2[j] = 0; // algorithm do { matchs.clear(); maxlength = MIN_LENGTH; for (int i = 0; i < len1; i++) { if (mark1[i] == 1) continue; for (int j = 0; j < len2; j++) { if (mark2[j] == 1) continue; count = 0; while (pwd1.charAt(i + count) == pwd2.charAt(j + count) && mark1[i + count] != 1 && mark2[j + count] != 1) { count++; } if(count==maxlength) this.matchs.add(new Stats(i, j, count)); else if(count>maxlength){ this.matchs.clear(); this.matchs.add(new Stats(i, j, count)); maxlength = count; } } } //标记阶段,标记前面找到的最大匹配,防止重复使用 for(Stats stats : this.matchs){ int pos1 = stats.getPosFirst(); int pos2 = stats.getPosSecond(); int length = stats.getLength(); for(int i=0;i<length;i++){ mark1[pos1+i]=1; mark2[pos2+i]=1; } this.titles.add(stats); } } while (maxlength != MIN_LENGTH); } class Stats { private int posFirst; private int posSecond; private int length; public Stats(int posM, int posN, int length) { this.posFirst = posM; this.posSecond = posN; this.length = length; } public int getPosFirst() { return posFirst; } public int getPosSecond() { return posSecond; } public int getLength() { return length; } } //输出找到的匹配串供测试 public String getTitles(String pwd1){ StringBuffer buf = new StringBuffer(); for(Stats stats : this.titles){ int pos1 = stats.getPosFirst(); int length = stats.getLength(); for(int i=0;i<length;i++){ buf.append(pwd1.charAt(pos1+i)); } buf.append("\t"); } return buf.toString(); } //计算相似度 public double calSimilarity(String pwd1,String pwd2){ int length = 0; String []vals = getTitles(pwd1).split("\t"); for(String val: vals){ length+=val.length(); } return (2.0*length)/(pwd1.length()+pwd2.length()); } }
相关推荐
字符串相似度算法 字符串相似度算法 字符串相似度算法 字符串相似度算法 相似度 字符串
字符串相似度比较算法,可比较不同长度的任意两个字符串的相似度,以百分比显示。
Java 实现推荐系统 两个字符串 余弦相似度 算法。
两个字符串,计算出两个字符串的相似度,用于模糊匹配,很简单的小例子
比较两个字符串的相似度,利用Levenshein算法计算出两个字符串的最小编辑距离,根据最小编辑距离得出相似度,例如: 字符串1:1234 字符串2:51234,则他们的相似度为:4/5。
Levenshtein算法python也是用的这个对比字符串相似度的,还不错
主要介绍了java字符串相似度算法,是Java实现比较典型的算法,具有一定参考借鉴价值,需要的朋友可以参考下
java 计算字符串相似度
比较两个字符串的相似度,利用LCS算法计算出两个字符串的最长公序列,根据最长公序列得出相似度,例如: 字符串1:1234 字符串2:51234,则他们的相似度为:4*2/(4+5)。
Delphi计算或比较两组字符串的相似程度 对字符串进行挨个读取并进行比对,取得相似度
用途:可用于论文抄袭检测、DNA等。...算法实现思路:通过对一个字符串插入、删除、替换转变成另一个字符串所需要的步骤称为距离,计算两个字符串之间的距离,从而可以得到两个字符串之间的相似度。
NULL 博文链接:https://biansutao.iteye.com/blog/326008
一个实现不同字符串相似度和距离度量的库。目前实现了十几种算法(包括 Levenshtein 编辑距离和兄弟、Jaro-Winkler、最长公共子序列、余弦相似度等)。查看下面的汇总表以获取完整列表... python字符串相似度 下载 ...
针对传统字符串相似度算法复杂的局限,在向量空间模型(VSM)的基础上,提出一种同时考虑字符相邻位置关系和词序的字符串相似度计算模型。通过计算VSM中向量的汉明距离来描述字符串相邻程度,并以向量的曼哈顿距离...
Levenshtein:快速计算编辑距离以及字符串的相似度
编辑距离算法,比较字符串相似度 pb11.5版本
Java字符串相似度 一个实现不同字符串相似度和距离度量的库。 当前实现了十二种算法(包括Levenshtein编辑距离和同级,Jaro-Winkler,最长公共子序列,余弦相似性等)。 查看下面的摘要表以获取完整列表... 下载 ...
这个demo运行起来要注意,字符串数量不能太大,不然会发生内存泄漏
两个字符串的相似度算法实现——编辑距离之Levenshtein距离
Strutil strutil提供了用于计算字符串相似度的字符串度量标准以及其他字符串实用程序功能。 完整文档可在以下找到: : 。安装 go get github.com/adrg/strutil字符串指标杰罗·温克勒史密斯·沃特曼·高图索伦森-...