En la entrada Distancia de Levenshtein entre dos cadenas explico como implementar en C# dicho algoritmo, utilizado para calcular el mínimo número de operaciones requeridas para transformar una cadena de caracteres en otra.
Usando ese algoritmo se pueden crear métodos muy útiles, como por ejemplo uno que nos indique el grado de similitud que existe entre dos cadenas. Este método se puede utilizar junto con otro para saber cual de todas las cadenas de un arreglo/listado/colección/… se parece más a otra cadena concreta.
¿Escenarios en los que pueda resultar útil? Seleccionar de forma automática un recurso ( sprite, objeto, clase, clip de audio, etc… ) al generar una nueva entidad, que junto con el uso de nomenclaturas, permite automatizar tareas o solucionar problemas en caso de errores tipográficos.
public static float CalculateSimilarity ( string p_strA, string p_strB )
{
if ( string.IsNullOrEmpty ( p_strA ) ||
string.IsNullOrEmpty ( p_strB ) )
return 0.0f;
else if ( string.Equals ( source, p_strB ) )
return 1.0f;
int steps = LevenshteinDistance ( p_strA, p_strB );
return ( 1.0f - ( steps / ( float )Mathf.Max ( p_strA.Length, p_strB.Length ) ) );
}
El valor devuelto se encontrará siempre comprendido dentro del rango [0,1], ambos valores extremos inclusive ( […] ).
Las comprobaciones iniciales se pueden quitar y el método seguirá devolviendo exactamente los mismos resultados. Se tendrían que medir tiempos y estimar las probabilidades de que se den esos casos concretos ( cadenas vacías o iguales ) para comprobar si su presencia está justificada o si por el contrario únicamente sirven para extender el tiempo de ejecución sin justificación.
Algunos ejemplos del uso del método anterior.
Strings.CalculateSimilarity ( "casa", "calle" ) ); // 0.4 Strings.CalculateSimilarity ( "casa", "casa" ) ); // 1 Strings.CalculateSimilarity ( "casa", "case" ) ); // 0.75 Strings.CalculateSimilarity ( "casa", "cas" ) ); // 0.75 Strings.CalculateSimilarity ( "casa", "casas" ) ); // 0.8 Strings.CalculateSimilarity ( "casa", "asac" ) ); // 0.5 Strings.CalculateSimilarity ( "casa", "xxxx" ) ); // 0 Strings.CalculateSimilarity ( "casa", "xxxxx" ) ); // 0 Strings.CalculateSimilarity ( "casa", "xxx" ) ); // 0 Strings.CalculateSimilarity ( "casa", "" ) ); // 0 Strings.CalculateSimilarity ( "", "casa" ) ); // 0
En el siguiente código se utiliza el método CalculateSimilarity para descubrir cual de todas las cadenas de un listado es la más parecida a otra pasada como parámetro. El método devuelve el indice de la cadena, que no la cadena en si.
public static int WhichIsMoreSimilar ( string p_base, string[] p_options )
{
float tmpSimilarity;
float maxSimilarity = -1f;
int selectIndex = -1;
for ( int i = p_options.Length - 1; i >= 0; i-- )
{
string str = p_options[ i ];
if ( ( selectIndex == -1 || ! string.Equals ( str, p_options[ selectIndex ] ) ) &&
( tmpSimilarity = CalculateSimilarity ( p_base, str ) ) > maxSimilarity )
{
maxSimilarity = tmpSimilarity;
selectIndex = i;
}
}
return selectIndex;
}