使用Javascript检测两个字符串之间的差异
detect differences between two strings with Javascript
使用Javascript,我想检查两个字符串之间有多少差异。
类似于:
var oldName = "Alec";
var newName = "Alexander";
var differences = getDifference(oldName, newName) // differences = 6
- 添加到名称中的任何字母都应算作每个字母的一次更改
- 更改一个字母应算作每个字母的更改。交换两个
- 字母应该算作两个变化,因为你真正的每个变化
leter - 但是,移动一个字母并插入另一个字母只应算作一次更改
例如:
将"Alex"更改为"Alexander"将是5个更改,因为添加了5个字母
将"Alex"改为"Allex"只会是一个变化,因为你添加了一个"l"并将其余部分转移,但没有将其更改为
将"Alexander"更改为"Allesander"将是2个更改(添加"l"并将"x"更改为一个"s")。
我可以将每个名称拆分成一个字母数组,并像这个jsFiddle中的函数一样简单地进行比较:
function compareNames(){
var oldName = $('#old').val().split("");
var newName = $('#new').val().split("");
var changeCount = 0;
var testLength = 0;
if(oldName.length > newName.length){
testLength=oldName.length;
}
else testLength=newName.length;
for(var i=0;i<testLength;i++){
if(oldName[i]!=newName[i]) {
changeCount++;
}
}
alert(changeCount);
}
但我如何解释字母的变化不算作变化
更新:以下是我如何使其工作
Levenstein距离正是我所需要的。感谢Peter!
工作jsFiddle
$(function () {
$('#compare').click(function () {
var oldName = $('.compare:eq(0)').val();
var newName = $('.compare:eq(1)').val();
var count = levDist(oldName, newName);
$('#display').html('There are ' + count + ' differences present');
});
});
function levDist(s, t) {
var d = []; //2d matrix
// Step 1
var n = s.length;
var m = t.length;
if (n == 0) return m;
if (m == 0) return n;
//Create an array of arrays in javascript (a descending loop is quicker)
for (var i = n; i >= 0; i--) d[i] = [];
// Step 2
for (var i = n; i >= 0; i--) d[i][0] = i;
for (var j = m; j >= 0; j--) d[0][j] = j;
// Step 3
for (var i = 1; i <= n; i++) {
var s_i = s.charAt(i - 1);
// Step 4
for (var j = 1; j <= m; j++) {
//Check the jagged ld total so far
if (i == j && d[i][j] > 4) return n;
var t_j = t.charAt(j - 1);
var cost = (s_i == t_j) ? 0 : 1; // Step 5
//Calculate the minimum
var mi = d[i - 1][j] + 1;
var b = d[i][j - 1] + 1;
var c = d[i - 1][j - 1] + cost;
if (b < mi) mi = b;
if (c < mi) mi = c;
d[i][j] = mi; // Step 6
//Damerau transposition
if (i > 1 && j > 1 && s_i == t.charAt(j - 2) && s.charAt(i - 2) == t_j) {
d[i][j] = Math.min(d[i][j], d[i - 2][j - 2] + cost);
}
}
}
// Step 7
return d[n][m];
}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.0/jquery.min.js"></script>
<input type="button" id="compare" value="Compare" /><br><br>
<input type="text" id="old" class="compare" value="Alec" />
<input type="text" id="new" class="compare" value="Alexander" />
<br>
<br>
<span id="display"></span>
詹姆斯·韦斯特盖特的职能:
Jame展示此功能的帖子
我手头没有Javascript实现本身,但您正在做一些已有完善算法的事情。具体来说,我相信您正在寻找两个字符串之间的"Levenstein距离",即插入、替换和删除的数量(假设您将删除视为更改)。
Levenstein-distance的维基百科页面有各种伪代码实现,您可以从中开始,还有可能对您有所帮助的参考。
替代实现:
/**
* Computes the Levenshtein edit distance between two strings.
* @param {string} a
* @param {string} b
* @return {number} The edit distance between the two strings.
*/
goog.string.editDistance = function(a, b) {
var v0 = [];
var v1 = [];
if (a == b) {
return 0;
}
if (!a.length || !b.length) {
return Math.max(a.length, b.length);
}
for (var i = 0; i < b.length + 1; i++) {
v0[i] = i;
}
for (var i = 0; i < a.length; i++) {
v1[0] = i + 1;
for (var j = 0; j < b.length; j++) {
var cost = Number(a[i] != b[j]);
// Cost for the substring is the minimum of adding one character, removing
// one character, or a swap.
v1[j + 1] = Math.min(v1[j] + 1, v0[j + 1] + 1, v0[j] + cost);
}
for (var j = 0; j < v0.length; j++) {
v0[j] = v1[j];
}
}
return v1[b.length];
};
相关文章:
- 是否有任何JavaScript UI组件可以显示字符串之间的差异
- jQuery在两个字符串标识符之间选择HTML
- 使用Javascript获取两个字符串之间的字符串数组
- Json和$scope的角度之间的差异$eval应用于JSON字符串时
- 如何使用JavaScript Regex替换字符串中双引号之间的文本
- 如何在jQuery中搜索两个字符之间的字符串
- 我可以在两个javascript文件之间传递一个字符串吗?
- 使用 JavaScript 中的正则表达式替换大文本中两个字符之间的每个出现的字符串
- 如何通过jQuery Ajax在HTML和PHP之间来回传输json字符串
- 如何在 javascript 中使用正则表达式在其他两个字符串之间找到一个字符串
- 删除两个字符串正则表达式之间的所有内容
- javascript:获取特定字符串之间的字符串
- 在第二次出现时提取方括号之间的字符串
- 如何在JavaScript中返回两个日期(当前日期和输入日期)之间的字符串差异
- Javascript Regex匹配两个字符串之间的子字符串,但子字符串可以包含DOT(.)
- 在jQuery或JavaScript中获取两个字符串之间的文本
- JavaScript函数,用于在全宽度和半宽度形式之间转换UTF8字符串
- Regex表达式,用于替换两个字符(包括字符)之间的字符串
- 如何删除两个单词之间的字符串
- 获取数字之间字符串的内容