Skip to content

Instantly share code, notes, and snippets.

@Marak
Forked from graphnode/levenshtein.js
Created May 18, 2011 23:21
Show Gist options
  • Save Marak/979807 to your computer and use it in GitHub Desktop.
Save Marak/979807 to your computer and use it in GitHub Desktop.
levenshtein function in javascript
function levenshtein(s1, s2) {
// http://kevin.vanzonneveld.net
// + original by: Carlos R. L. Rodrigues (http://www.jsfromhell.com)
// + bugfixed by: Onno Marsman
// + revised by: Andrea Giammarchi (http://webreflection.blogspot.com)
// + reimplemented by: Brett Zamir (http://brett-zamir.me)
// + reimplemented by: Alexander M Beedie
// * example 1: levenshtein('Kevin van Zonneveld', 'Kevin van Sommeveld');
// * returns 1: 3
if (s1 == s2) {
return 0;
}
var s1_len = s1.length;
var s2_len = s2.length;
if (s1_len === 0) {
return s2_len;
}
if (s2_len === 0) {
return s1_len;
}
// BEGIN STATIC
var split = false;
try{
split=!('0')[0];
} catch (e){
split=true; // Earlier IE may not support access by string index
}
// END STATIC
if (split){
s1 = s1.split('');
s2 = s2.split('');
}
var v0 = new Array(s1_len+1);
var v1 = new Array(s1_len+1);
var s1_idx=0, s2_idx=0, cost=0;
for (s1_idx=0; s1_idx<s1_len+1; s1_idx++) {
v0[s1_idx] = s1_idx;
}
var char_s1='', char_s2='';
for (s2_idx=1; s2_idx<=s2_len; s2_idx++) {
v1[0] = s2_idx;
char_s2 = s2[s2_idx - 1];
for (s1_idx=0; s1_idx<s1_len;s1_idx++) {
char_s1 = s1[s1_idx];
cost = (char_s1 == char_s2) ? 0 : 1;
var m_min = v0[s1_idx+1] + 1;
var b = v1[s1_idx] + 1;
var c = v0[s1_idx] + cost;
if (b < m_min) {
m_min = b; }
if (c < m_min) {
m_min = c; }
v1[s1_idx+1] = m_min;
}
var v_tmp = v0;
v0 = v1;
v1 = v_tmp;
}
return v0[s1_len];
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment