Created
June 5, 2012 13:45
-
-
Save josejuan/2875084 to your computer and use it in GitHub Desktop.
Levenshtein substring minimal distance, javascript implementation
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
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