Skip to content

Instantly share code, notes, and snippets.

@josejuan
Created June 5, 2012 13:45
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
  • Save josejuan/2875084 to your computer and use it in GitHub Desktop.
Save josejuan/2875084 to your computer and use it in GitHub Desktop.
Levenshtein substring minimal distance, javascript implementation
/*
LevenshteinSubminimal(String A, String B) -> {k: Integer, t: String}
A, es la cadena que introduce el usuario
B, es la cadena candidata a ser alternativa del usuario
k, es la mínima Levenshtein de A sobre todas las subcadenas de B
t, es la cadena con menor distancia Levenshtein
*/
function LevenshteinSubminimal(A, B) {
var a = A.length;
var b = B.length;
// siempre comparamos A con las subcadenas de B
var f = function(s){return Levenshtein(A, s)};
// si A es mayor que B no comparamos subcadenas
if(a >= b)
return {k: f(B), t: B}
// peor caso y cotas
var m = {k: b+2, t: null}, c1 = a-1, c2 = a+1;
for(var p = 0; p < b - c1; p++)
for(var l = c1, c3 = Math.min(c2, b - p); l <= c3; l++) {
var t = B.substr(p, l), k = f(t);
// mejor caso
if(m.k >= k)
m = {k: k, t: t};
}
return m;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment