La distancia Levenshtein nos da una manera de calcular la distancia entre dos cadenas similares en términos de caracteres individuales desordenadas:Algoritmo para medir la distancia entre las secuencias desordenadas
quick brown fox quikc brown fax
La distancia Levenshtein = 3.
Lo es un algoritmo similar para la distancia entre dos cadenas con subsecuencias similares? Por ejemplo, en
quickbrownfox brownquickfox
la distancia Levenshtein es de 10, pero esto no tiene en cuenta el hecho de que las cadenas tienen dos subsecuencias similares, lo que los hace más "similar" que las palabras completamente desordenados como
quickbrownfox qburiocwknfox
y, sin embargo, esta versión completamente desordenada tiene una distancia de Levenshtein de ocho.
¿Qué medidas de distancia existen que tienen en cuenta la longitud de subsecuencias, sin asumir que las subsecuencias se pueden dividir fácilmente en palabras distintas?
¿Cómo es este tema fuera de tema? Tal vez uno podría simplemente mejorar el título. – Dario
Se le preguntó muchas veces bajo un mejor nombre: o) http://stackoverflow.com/questions/451884/similar-string-algorithm o http://stackoverflow.com/questions/653157/a-better-similarity-ranking-algorithm -for-variable-length-strings o http://stackoverflow.com/questions/246961/algorithm-to-find-similar-text Por cierto: me gusta especialmente la idea con la distancia basada en la compresión. – MaR
@Dario: ¿Qué título sugerirías? –