编程算法
比较字符串(String)相似程度的算法。
LD(s1, s2)=把s1变成s2需要的{增加,删除,替换}操作之和。
汉字的特殊处理:http://www.cnitblog.com/ictfly/archive/2005/12/27/5828.aspx
<html>
<head>
<title>求两个字符串的相似度,Levenshtein Distance算法实现</title>
</head>
<body>
<h3>求两个字符串的相似度,Levenshtein Distance算法实现</h3>
字符串1:<input id="s" type="text" value="小谢天空"><br>
字符串2:<input id="t" type="text" value="小谢的天空"><br>
<input type="button" value="计算" onclick="test()"><br>
<div id="r"></div>
</body>
</html>
<script>
//求两个字符串的相似度,返回差别字符数,Levenshtein Distance算法实现
function Levenshtein_Distance(s,t){
var n=s.length;// length of s
var m=t.length;// length of t
var d=[];// matrix
var i;// iterates through s
var j;// iterates through t
var s_i;// ith character of s
var t_j;// jth character of t
var cost;// cost
// Step 1
if (n == 0) return m;
if (m == 0) return n;
// Step 2
for (i = 0; i <= n; i++) {
d[i]=[];
d[i][0] = i;
}
for (j = 0; j <= m; j++) {
d[0][j] = j;
}
// Step 3
for (i = 1; i <= n; i++) {
s_i = s.charAt (i - 1);
// Step 4
for (j = 1; j <= m; j++) {
t_j = t.charAt (j - 1);
// Step 5
if (s_i == t_j) {
cost = 0;
}else{
cost = 1;
}
// Step 6
d[i][j] = Minimum (d[i-1][j]+1, d[i][j-1]+1, d[i-1][j-1] + cost);
}
}
// Step 7
return d[n][m];
}
//求两个字符串的相似度,返回相似度百分比
function Levenshtein_Distance_Percent(s,t){
var l=s.length>t.length?s.length:t.length;
var d=Levenshtein_Distance(s,t);
return (1-d/l).toFixed(4);
}
//求三个数字中的最小值
function Minimum(a,b,c){
return a<b?(a<c?a:c):(b<c?b:c);
}
function test(){
var s=document.getElementById("s");
var t=document.getElementById("t");
var r=document.getElementById("r");
var l=Levenshtein_Distance_Percent(s.value,t.value);
r.innerHTML='字符串1:'+s.value+'<br>字符串2:'+t.value+'<br>'+'相似度:'+l+'<br>算法参考:<a href="http://www.merriampark.com/ld.htm" target="_blank">http://www.merriampark.com/ld.htm</a>';
}
</script>
分享到:
相关推荐
字符串相似度算法 字符串相似度算法是一种衡量两个字符串之间相似度的方法,广泛应用于自然语言处理、数据挖掘、机器学习等领域。在本文中,我们将讨论一种常用的字符串相似度算法:Levenshtein Distance。 什么是...
**字符串相似度算法——...总的来说,编辑距离算法提供了一种量化比较字符串相似度的有效手段,是理解和处理文本数据的重要工具。在阅读提供的“ld.htm”文件后,可以更深入地了解这个算法的实现细节和实际应用案例。
总的来说,LD文本比较算法是通过计算字符串间的最小编辑距离来评估它们的相似度,这个概念在各种文本处理任务中都有重要应用。通过理解和实现这样的算法,可以提升我们在文本分析、信息检索等方面的能力。
在这个"LD的两字符串相似度计算.zip"压缩包中,可能包含了一个名为"readme.txt"的文件,它可能解释了如何使用这个算法或者给出了一个示例。另外,"com"可能是程序代码的组成部分,可能是一个Python、Java或其他编程...
一个完整可直接用的LD算法计算两个字符串之间的相似度。
LD算法(Levenshtein Distance)又称编辑距离算法(Edit ...以字符串A通过插入字符、删除字符、替换字符变成另一个字符串B,那么操作的过程的次数表示两个字符串的差异。本资源为此算法的python实现。(python 2.7)
3. **字符遍历**:遍历输入字符串中的每一个字符,通过比较字符的ASCII码来判断其是否为数字。 - 如果字符的ASCII码在48到57之间,则表示该字符为数字。 - 根据数字的实际值更新对应数组元素的值,即增加该数字...
各种数据结构、算法及实用的C#源代码 C#,字符串相似度的莱文斯坦距离(Levenshtein Distance)算法与源代码 ...莱文斯坦距离被定义为:将字符串a变换为字符串b所需的删除、插入、替换操作的次数Ld。
这个算法是通过动态规划实现的,可以解决两个字符串的最优匹配问题。在编程中,我们可以用二维数组来存储每个位置上的最小编辑距离,最后返回右下角的值。这个算法在文本处理、拼写检查等领域有着广泛应用。 2. ...
本文实例讲述了C#计算字符串相似性的方法...A=”abcd”, B=”abc”, 那么 LD(A,B)=1,只需在B字符串中插入一个字符那么就完全等于A A=”abcd”, B=”abcd”, 那么 LD(A,B)= ,因为这两个货完全相同 A=”abcd”, B=
在实现字符串比较时,不仅要考虑算法的正确性,还要注重其实现的效率。在上述实现中,使用数组循环和线性查找是非常耗时的操作,特别是当字符串很长时。使用`HashSet`和`Dictionary`这类数据结构,以及采用LCS、LD...
开发者通过分析和理解这些资源,能够掌握如何通过编程计算两个字符串之间的编辑距离,并能够将这一算法应用到具体的软件开发和实际问题解决中。 莱文斯坦距离的应用场景非常丰富。在搜索引擎技术中,它可以用来评估...
在处理大型字符串时,更高效的算法如KMP(Knuth-Morris-Pratt)算法、Boyer-Moore算法和Rabin-Karp算法等会被优先考虑。这些算法通过预处理子串的模式匹配表或利用滑动窗口减少不必要的比较,从而提高查找速度。 在...
计算机考研C语言基础算法是计算机考研的基础知识之一,本文将从运算符和表达式、输入输出语句、字符串操作三个方面对C语言基础算法进行详细介绍。 一、运算符和表达式 在C语言中,运算符是用于执行某种操作的符号...
编辑距离算法,即Levenshtein Distance (LD)算法。 这个算法其实是一个动态规划(DP)。levenshtein() 返回两个字符串之间的 Levenshtein 距离。 Levenshtein 距离,又称编辑距离,指的是两个字符串之间,由一个...
通过以上分析,我们可以看出,编辑距离算法是衡量字符串相似度的一种有效方法。在实际应用中,根据具体需求选择合适的实现方式和优化方案尤为重要。例如,在大规模数据处理中,可以考虑使用更高效的算法变体或其他...
LD算法是一种用于计算两个序列之间差异的算法,通常用于字符串比较领域,如拼写检查和文本相似度分析。在SQL注入攻击的过滤中,LD算法被用来比较用户输入与正常请求之间的差异程度。通过设定一个阈值,当用户输入与...
他是以字符串A通过插入字符、删除字符、替换字符变成另一个字符串B,那么操作的过程的次数表示两个字符串的差异。 文件1里面是需要比较的内容,文件2是被比较的文本,现在需要找到在文件1中每一行的文本在文件2中...