使用Javascript,我想检查两个字符串之间有多少差异.
就像是:
var oldName = "Alec";
var newName = "Alexander";
var differences = getDifference(oldName, newName) // differences = 6
例如:
将"Alex"更改为"Alexander"将有5个更改,因为已添加5个字母
将"Alex"更改为"Allex"只会改变一个,因为您添加了"l"并将其余部分移位但未更改它们
将"亚历山大"改为"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);
}
但是,我如何解释不换算的字母转换？
更新:这是我如何运作
Levenshtein距离正是我所需要的.谢谢彼得!
$(function () {
$('#compare').click(function () {
var oldName = $('.compare:eq(0)').val(); …我正在尝试创建或找到Levenshtein距离公式的CoffeeScript实现,即编辑距离.这是我到目前为止,任何帮助都将非常感激.
levenshtein = (s1,s2) ->
n = s1.length
m = s2.length
if n < m
return levenshtein(s2, s1)
if not s1
return s2.length
previous_row = [s2.length + 1]
for c1, i in s1
current_row = [i + 1]
for c2, j in s2
insertions = previous_row[j + 1] + 1
deletions = current_row[j] + 1
substitutions = previous_row[j] # is this unnescessary?-> (c1 != c2)
current_row.push(Math.min(insertions,deletions,substitutions))
previous_row = current_row
return previous_row[previous_row.length-1]
#End Levenshetein Function
顺便说一句:我知道这个代码在很多层面都是错误的,我很高兴接受任何建设性的批评.只是想改进,并找出这个公式!
CodeEdit1:修补了Trevor指出的错误,上面的当前代码包括这些更改
更新:我问的问题是 - 我们如何在CoffeeScript中使用Levenshtein？
以下是Levenshtein距离算法的"步骤",以帮助您了解我想要完成的任务. …
对于客户端搜索工具,我需要找到一个单词的Levenshtein距离以及数百万个其他单词.用户应该能够将大约二十个单词的短文与一本书进行比较.用户可以通过查找书中文本的最具特征的单词的位置来做到这一点."寻找位置"并不意味着寻找完全匹配,但几乎与levenshtein匹配.我从已经可用的实现开始,但我需要更快的速度.我最终得到了这个:
var rowA = new Uint16Array(1e6);
var rowB = new Uint16Array(1e6);
function levenshtein(s1, s2) {
var s1_len = s1.length, s2_len = s2.length, i1, i2 = 0, a, b, c, c2, i = 0;
if (s1_len === 0)
return s2_len;
if (s2_len === 0)
return s1_len;
while (i < s1_len)
rowA[i] = ++i;
while (i2 < s2_len) {
c2 = s2[i2];
a = i2;
++i2;
b = i2;
for (i1 = 0; i1 < s1_len; ++i1) {
c = a + …我尝试根据给定的十六进制值获得最匹配的颜色名称.例如,如果我们有六角颜色,#f00我们就得到颜色名称red.
'#ff0000' => 'red'
'#000000' => 'black'
'#ffff00' => 'yellow'
我目前使用levenshtein距离算法来获得最接近的颜色名称,到目前为止效果很好,但有时并不像预期的那样.
例如:
'#0769ad' => 'chocolate'
'#00aaee' => 'mediumspringgreen'
那么任何想法如何让结果更接近？
这是我为获得最接近的颜色而做的:
Array.closest = (function () {
// http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#JavaScript
function levDist(s, t) {
if (!s.length) return t.length;
if (!t.length) return s.length;
return Math.min(
levDist(s.substring(1), t) + 1,
levDist(t.substring(1), s) + 1,
levDist(s.substring(1), t.substring(1)) + (s[0] !== t[0] ? 1 : 0)
);
}
return function (arr, str) {
// http://stackoverflow.com/q/11919065/1250044#comment16113902_11919065
return arr.sort(function (a, b) {
return levDist(a, str) …背景：我有一个包含 13,000 条人名记录的列表，其中一些是重复的，我想找出相似的来进行手动复制过程。
对于像这样的数组：
["jeff","Jeff","mandy","king","queen"]
什么是获得的有效方法：
[["jeff","Jeff"]]
解释， ["jeff","Jeff"]因为他们的 Levenshtein 距离是 1（可以像 3 一样可变）。
/*
Working but a slow solution
*/
function extractSimilarNames(uniqueNames) {
let similarNamesGroup = [];
for (let i = 0; i < uniqueNames.length; i++) {
//compare with the rest of the array
const currentName = uniqueNames[i];
let suspiciousNames = [];
for (let j = i + 1; j < uniqueNames.length; j++) {
const matchingName = uniqueNames[j];
if (isInLevenshteinRange(currentName, matchingName, 1)) {
suspiciousNames.push(matchingName);
removeElementFromArray(uniqueNames, matchingName);
removeElementFromArray(uniqueNames, currentName); …我正在寻找Javascript中的通用Levenshtein实现。它必须快速并且对短字符串和长字符串有用。它也应该多次使用（因此进行缓存）。最重要的是，它计算出一个简单的Levenshtein距离。我想出了这个：
var levenshtein = (function() {
var row2 = [];
return function(s1, s2) {
if (s1 === s2) {
return 0;
} else {
var s1_len = s1.length, s2_len = s2.length;
if (s1_len && s2_len) {
var i1 = 0, i2 = 0, a, b, c, c2, row = row2;
while (i1 < s1_len)
row[i1] = ++i1;
while (i2 < s2_len) {
c2 = s2.charCodeAt(i2);
a = i2;
++i2;
b = i2;
for (i1 = 0; i1 < s1_len; ++i1) …