-
-
Save mgan59/980048 to your computer and use it in GitHub Desktop.
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]; | |
} |
haha thanks. it was weird to see this gist come across my stream because I just used the python-levenshtein package today. And up until today I had never heard of Levenshtein and had just used hamming-distance algorithms
h̬̭̦̯̹͍̩̱͓͚̩̣̻̩̩̙̳̝̖̗̣͉̼̭̣̥͇̯͓̙̙͖̦̻̣̘̖̤͙̪͎̭̘̦̫̜̗̙̜͚͎̱̙̘̗̭͖̗̺͕̺̖͇̯͉ͯͫ͋͒͋ͥͯ̂͗̑ͣ̄ͩ̌̚̕ͅę̰͈͇͓̼͎̜̤̩̯̙̞̖͇̬͔͎̫̝̋͆ͪ̐́̐ͤ̌̌ͣͧ̔͂ͨ̊ ̧̥̹̺̘͕̤͇͈̝̬̲̳̦͕̯͖̯͕̹̺̰̰͖̟̜̻̩̮̘̯̲̱̝̲̜̪̤͖̃̓̾̃̌̋͂͛̑̈̓̇̿ͮ̊̾d͈̦̖̬̟̯̼͇̦͉̯͓̰̣͖̣͎͖͖͍̹̻̭̟̺̥̘͉͎̝̙̟͈̭͍̖̺̫͚̯̱͍̺͕̼̳̙̭̩͂̏̈̉̓̏͌ͪ̓̓̌͞ͅe̞̻͖̙̗̪͔̟̥͔͍̹̦̪̹̝̳̩̮̲͔̞̦͉̙̳̱̯̮̘̲̠̲̦̫̲̮̭̭̝̪̜̰̰̣̜̤͎̘͕̠̺̺̗̼̻̰̙̩̱͂̓̈̈̓͋̉ͫͪ͒͡ͅm̢̲̭̰͙̬͓̜̬̪̻̗͖̙̟͖̺̼͓̭̹̳̰̲̯̤̝̺̠͖̙̦̭̻̠͚̪̭̹̬̙͙̰̦̬̦̝̎́̓̓̓ͥ͂ͦ́͛̎̈̓ͭ̀ͥ͑ͫ̀ͅa̼̗͉͈̖͎̙̩̺̦͇͚͙̘ͪ̿ͩ̌ͨͨ̋ͧ͐ͭͧ̀n͓͓̳̺̺̙̬̹̮̭͉̟̭̮̪̞͓̗͇̳̯̫̯͎̪̱͌̌͌̽̆̍̿͂ͩ̊̐̎̍͆̌̑ͩ̓̇͡ḑ̘̳̜̞̫̫̲͙̣̣͍͇̻̮͎̺̣̯̙͚̰̺͇͖͚̞̜̹͉̰̞̞̞͇͎̬͇͈̟̠̩̟̳͚̲̼͖̻͎̯̮͉͍͉ͭ̏̊̓͋̿ͦͨs͖͎͎̞̠͈̯̰̦͎̟̦̱̗̮̩̭̞͈̺̳̱͚̭͙̪̝͉̬̹̣͙̘̰͇̮̤͍͖͚͕͍͍͍̯̣̫̩̥̣̝̺̻̠̹̖̜͇͓̮͚̺̙̖̰̊ͥͧͪ́ͥ̏͑̄ͪͪͣ̕ ̱͖͎̹̳̭̜̮̦̖̖̫̫̥̦̣̖̱̱̫̰̜͈̥̫̜̮̟̩̣̳̥̭̼̦̮͕̼͎̙̟̘͕̉̉ͩ͂̂̈ͯ̆̉̑ͦ̑̅ͮ̃̎̿̑̚͝ͅl̢͎̘̖͔̖̮̙͔̖̩͓̻͎̪̭͖̳͉͇̜̥̜̪̠̪̞̺̠̦̲͇͉̮͕͚͕͌̓̊̐̿͗̒̉̐͌ͪͥ̚ͅͅe̷͎̼̫̻̣̹̪̙̰̣̤͚̥̞̝̟̪̲̣͚͔͙̲̬͍̯͕͍͖͍̫͓͖̤̤͖̲͓̹͎̫̗̐̄ͤ̂͆ͬͤ̂ͥ̒̀̅́̆͂͆̇͑v̛̝̩͎͎̤̻͎̩͚̥̰̫̱̥̰̪͇͙͉̳̟̥͇̠ͬ͂͑ͫ̍͛̈̋ͬ̆̍͆͛̍̄̚ͅé̻̗̮̩̞̲̮̣̟̰̝ͯͩ́ͫ̉ͩͤ̈ͮͤͣ͒̿̿ͩ͌̑ͦ́n̸̩̰̰̹͖̝̞̪͈̱̝ͪ̏ͯ͛ͅͅͅş̺̖̞͈̗̣̜͕̗̮͙̟͚͓̖̫͍͉̮̝̼̱̥̹̺̻͇͔̥̩͔̱̣̱̫̎͑͆̄ͤ̀ͨ͗ͤ̓͋̇̓́́ͥͨͣ̚h͎̲̝͎̲̯͇̪̳̰̦̠̹̝̖̬̬̤͕̦͇͚̥͍̟̺̫͍̤͎̱͔͕͍̭̰̙̖̼̜̔̈̓̽͆͋̍̑́͌̚͝ͅͅt̖̥̗̺̮͚͔ͥ̾̄͊̌̐ͪ̿̃ͥ͘e̸̻̱͙̩͎͓͈̦͖̞̱͔̫̜̻̬͔̘̠͎͇̬̤̪͉̳̗̫͔̭̼̝͕̥̯͙̞̮̱̼̲͔̖͛ͧ͆ͦ́͗̒͂̉ͤ̀̆͊ͅi̸̦͓̳̪̖͖̳̜͙̹̩̩͈̝̤̦̫͓͙̗̮̬̪̦̲̺̝̺̬̩̣̼̤̖̱̫̘̭̥͖̮̳̼͍̠̱̙͖̗͇͎̬̣̩̻͉̤̘̝̮̮̖͚̎ͯͭ͐ͩ̏̅ͅͅͅn͓̤̬̙̖̦͉̪͖̘͓̲̜̦̝̜̝͓̝͚̱̹̹͙̮͕͕̬̜̗̭̟̬͚̜̣̹̤̪̻̣̩͔̬͙̘̖͔̟̰̬͎̲̘̞͓̩̻̝̆̅ͫͥ͆͗͆̽̈ͯ͢ͅͅ ̧̞̹̳̖̞̻̻̹̠̫̝͙̝̪͖̱͎̱͉͉̜̮̯͎̻̳̌ͧ̌ͨ̇ͫ͌͆̚a̴̖͓̱͍̝̞̘̙̲̯̠̰̮͖̣̼͂̈̂͑ͣ̈ͮ̒̾͆̓ͭ̑̐͋ͅl̹̱̤͖̩̙̙̩̹̤̻̥͙͇̞͍͈͎̘̣̻̫͖̲̮̹̗̩͇̖͉̱̼͈̮̹͕̩͔̼̼̰̩͉͕̈̿̌ͭ͆̑͐̽͒ͭ̐̄̿͌̅͋͝ͅͅġ͙͕̪̥̭̝̫̃̅͊͡o̠̠͈̪̥͎̣̹̯͍͎͕̖͇̱͔̻̥͇̘͖͈̞̽́̉̃̿ͩ̅͛̿̈̐ͫ̕r̛͎̘̺̰̠̼̗̳̜̺̗̹͉̬̳͕̰̟̱̫̩̫̮̜̬̝͈͖͉͓̞̪͈̰̼͈̲̹̭̺̳̙͐͐ͥ̐ͮͭͨ̅ͩ̍̐ͯ̍ͨͦͨ̚ͅỉ̢̪͙̗̫̬͚͉̘͉̟̖͍̜̘̙̰̠͇̙̥͖͇̗̻̞̪̖̣̹͎͖̼̤̭̱̜ͨ̉ͫ͒ͫ̒ͧ͑͋̒ͩ͗͑̈̒̚t͔̳̻̥̹͙͈̺͖͇͔͍̮̼̲̹̣͈̞̻̞̰͎̱̥̘̼̻̠̙̼̠͇̙͈̤̗͇̭͇̖̗̭̣̥̣̞͎͙̘̮͍̘̹̙͓̣̺ͦͯͧͣ͛̃ͨ̈̍ͥ͆̈͑̇ͧ͝ͅͅh̘̳͙̙̟͎̲͍̱̪̹̤̮̣͇̪̪͔̥̯̲̳̝̣͇͇̩͇̰̼̤̗͉͚̲̹̦̹̼͉͔̗̩̺̹̝̱̣ͭ͂̿͗̓̊̅ͬ̃̽ͫ͑͆̽̇ͦ̚͘m̬̩͇͎̪̤̪̗̥̻̜̠̖̬̼͍̺̘̫̯͍̮̜̪͎̰̲̟̲͍̤̺̥̯̜̥̰̹̲̞̹̯͕͚̯̲͕̖̟͕̠͓̝̥͙̘̦̭͔̫͍̠̦̥̙̣̾̉̌̓͞ͅs̘̝͚̬̯̤͍͔͉͕̼̤͔̩̦̮̘͙̥̜̞̱̞̦͖̬̯͇͈̫̬̭͖̮̫͚͖̣̝̻͎̹͎̲̹͉̗̩̼͙̪͇̤̖̗̫̄̉͂̊͗̒̐͝ͅͅͅ
@gf3 also has a library that does this as a module.