Open zwhu opened 7 years ago
莱文斯坦距离,又称Levenshtein距离,是编辑距离的一种。指两个字串之间,由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符,插入一个字符,删除一个字符。
莱文斯坦距离与 react 有千丝万缕的关系,所以花了几天的时间研究了 levenshtein 的算法,以及使用 js 实现了一遍,从 这里 (此链接给出了大多数语言版本的实现)copy 了测试用例。后面如果有时间我再另写一篇莱文斯坦距离与 React 的 key 的关系的文章。
key
'use strict' const min = Math.min // 构造二维数组 const initialArray = (lgt1, lgt2) => { let array = [] for (let i = 0; i < lgt1; i++) { array[i] = Array(lgt2) } return array } /** * Levenshtein Distance * 从一个字符串转成另一个字符串所需要的最小操作步数 */ const levenshtein = (sa, sb) => { let d = [] , algt = sa.length , blgt = sb.length , i = 0 , j = 0 if(algt === 0) return blgt if(blgt === 0) return algt // 初始化二维数组 d = initialArray(algt + 1, blgt + 1) for (i = 0; i < algt + 1; i++) { d[i][0] = i } for (j = 0; j < blgt + 1; j++) { d[0][j] = j } for(i = 1; i < algt + 1; i++) { for(j = 1; j < blgt + 1; j++) { if(sa[i - 1] === sb[j - 1]) { d[i][j] = d[i - 1][j - 1] } else { d[i][j] = min( d[i - 1][j] + 1, d[i][j - 1] + 1, d[i - 1][j - 1] + 1 ) } } } return d[i - 1][j - 1] } // test case // copy from https://rosettacode.org/wiki/Levenshtein_distance#JavaScript ;[ ['', '', 0], ['yo', '', 2], ['', 'yo', 2], ['yo', 'yo', 0], ['tier', 'tor', 2], ['saturday', 'sunday', 3], ['mist', 'dist', 1], ['tier', 'tor', 2], ['kitten', 'sitting', 3], ['stop', 'tops', 2], ['rosettacode', 'raisethysword', 8], ['mississippi', 'swiss miss', 8] ].forEach(function(v) { var a = v[0], b = v[1], t = v[2], d = levenshtein(a, b); if (d !== t) { console.log('levenstein("' + a + '","' + b + '") was ' + d + ' should be ' + t) } })
上面初始化数组还有效率优化的空间,不过我为了让代码有良好的可读性,就没有再继续压缩循环的次数了。
莱文斯坦距离与 react 有千丝万缕的关系,所以花了几天的时间研究了 levenshtein 的算法,以及使用 js 实现了一遍,从 这里 (此链接给出了大多数语言版本的实现)copy 了测试用例。后面如果有时间我再另写一篇莱文斯坦距离与 React 的
key
的关系的文章。