Medir distancias entre palabras

Para medir la distancia entre dos palabras considerando solo sus caracteres e ignorando su significado. Vamos contar el número mínimo de operaciones que deberíamos realizar sobre una palabra para convertirla en la otra.

¿Que operaciones existen?:

  • Sustitución de un carácter por otro.
  • Inserción de un carácter
  • Eliminación de un carácter
  • Transposición entre dos caracteres adyacentes.

Existen varios algoritmos, según que operaciones se quieran tener en cuenta:

Distancia Sus. Ins. Eli. Tra.
Hamming X
Jaro–Winkler X
LCS X X
Levenshtein X X X
Damerau-Levenshtein X X X X

El uso de estas distancias es muy variado, por ejemplo sugerir correcciones ortográficas o agrupar palabra similares.

Hay que tener en cuanta que esto solo es una medición de la distancia comparando caracteres de dos palabras, no se tiene en cuenta su significado. Por ello aunque “remando” por significado esta más próxima a “remar” que “retar” con estas distancias “remar” y “retar” son casi iguales.