Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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
You can’t perform that action at this time.
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.