Tengo alguna secuencia de palabras como entrada (por ejemplo, una oración o parte de una oración). Estoy buscando una manera de encontrar la posición y el contenido de la subcadena más similar dentro de un texto más grande, así como algún tipo de puntaje de similitud.
La subcadena coincidente puede contener errores tipográficos, palabras que suenan de manera similar o menos palabras o más, en comparación con la cadena de entrada.
¿Hay una forma establecida de hacer esto? Solo pude encontrar respuestas sobre cómo comparar directamente dos cadenas por similitud, pero nada sobre cómo encontrar la posición y el puntaje de similitud de la coincidencia más cercana dentro de un texto.
Estoy más interesado en las coincidencias en términos de personajes y/o cómo suenan las cosas, en lugar de significado.
Lo ideal sería buscar una manera de lograr esto en JavaScript, pero también son bienvenidas las sugerencias independientes del idioma.
Lo que desea utilizar es la deformación dinámica del tiempo .
Es un algoritmo para calcular un puntaje de similitud entre dos secuencias, pero también se puede usar para encontrar los lugares donde se encuentran las similitudes. Considere el pseudocódigo en el artículo vinculado (3 de mayo de 2022, si ha cambiado mientras tanto). Probablemente desee utilizar la segunda versión que incluye la restricción de localidad.
Extienda el algoritmo de la siguiente manera: después de calcular la matriz DTW, puede iterar hacia atrás desde DTW[n,m] hacia DTW[0,0] yendo siempre hacia el valor mínimo anterior. Es decir. si su posición actual es [i,j] entonces su próxima posición es [k,l] para la cual DTW[k,l] es mínimo de las tres posiciones posibles
k=i-1, l=jk=i-1, l=i-1k=i, l=j-1Suponiendo que su texto está en la primera dimensión y su "subcadena" en la segunda, tiene las siguientes correspondencias:
i que no aparece en la mejor coincidencia.i que aparece en la posición j en la mejor coincidencia.j en la mejor cadena coincidente. La mayor k para la que aparece [k,0] en la iteración hacia atrás y la menor l para la que aparece [l,m] serán el comienzo y el final de la mejor secuencia coincidente en su texto.