comparación de cuerdas con la cadena más similar

Question

alguien sabe si existe un algoritmo que da una cadena A y una matriz de cadenas B, compara la cadena A con todas las cadenas en B dando la salida más similar.

Por "el más parecido" Quiero decir que, por ejemplo,

si la secuencia de A es: "hola mundo ¿cómo estás"

continuación

"asdewr asdf hola mundo cómo asfrqr que"

es más similar que:

"h2ll4 w1111 h11 111 111"

Answer 1

La medida habitual para esto es Levenshtein distance. Calcule la distancia de Levenshtein desde el original hasta cada candidato, y tome la menor distancia como el candidato más probable.

Answer 2

Esto se hace generalmente con la comprobación de un montón de variaciones de la cadena que tiene ... eche un vistazo a los algoritmos de corrección ortográfica, p. Ej. here

Answer 3

Define similitud. Algoritmos que pueden hacer esto incluyen:

1. Levenshtein/LCS/n-gram distancia (comparar la cadena con cada una de las cadenas en su conjunto, tomar la una con la distancia más bajo) de indexación
2. TF-IDF
3. Levenshtein automata
4. Hopfield networks
5. BK-trees

Todo lo cual puede factiblemente por implementado en C o C++. Google "similitud de cadenas", "búsqueda duplicada" o "vinculación de registros" para las métricas y algoritmos disponibles.