¿Algoritmos de similitud de cadenas?

La distancia Levenshtein es el algoritmo que recomendaría. Calcula el número mínimo de operaciones que debe hacer para cambiar 1 cadena en otra. Cuantos menos cambios haya, las cadenas serán más similares...

Si el enfoque está en el rendimiento, implementaría un algoritmo basado en un trie estructura
(funciona bien para encontrar palabras en un texto, o para ayudar a corregir una palabra, pero en su caso puede encontrar rápidamente todas las palabras que contienen una palabra dada o todas menos una letra, por ejemplo).

Por favor, siga primero el enlace de wikipedia de arriba.Tries es el método de clasificación de palabras más rápido (n palabras, buscar s, O (n) para crear el trie, O(1) para buscar s (o si se prefiere, si un es el promedio de longitud, O(un) para el trie y O(s) para la búsqueda)).

Una implementación rápida y fácil (para optimizar) de su problema (palabras similares) consiste en

• Haga el trie con la lista de palabras, teniendo todas las letras indexadas al frente y al revés (ver ejemplo a continuación)
• Para buscar s, repetir de s[0] para encontrar la palabra en el trie, entonces s [1] etc...
• En el trie, si el número de letras encontradas es len (s)-k se muestra la palabra, donde k es la tolerancia (falta 1 letra, 2...).
• El algoritmo puede extenderse a las palabras de la lista (ver más abajo)

Ejemplo, con las palabras car, vars.

Construyendo el trie (letra grande significa que una palabra termina aquí, mientras que otra puede continuar). El {[5] } es post-index (go forward) y < es pre-index (go atrasado). En otro ejemplo podemos tener que indicar también la letra inicial, no se presenta aquí para mayor claridad.
Los < y > en C++, por ejemplo, serían Mystruct *previous,*next, es decir, de a > c < r, puedes ir directamente de a a c, y viceversa, también de a a R.

  1.  c < a < R
  2.  a > c < R
  3.    > v < r < S
  4.  R > a > c
  5.        > v < S
  6.  v < a < r < S
  7.  S > r > a > v

Buscando estrictamente coche el trie te da acceso desde 1., y encuentras car (habrías encontrado también todo comenzando con car , pero también cualquier cosa con car dentro-no está en el ejemplo-pero vicar por ejemplo se habría encontrado de c > i > v < a < R).

Para buscar mientras se permite la tolerancia incorrecta/faltante de 1 letra, se itera desde cada letra de s, y se cuenta el número de letras consecutivas-o saltando 1 letra - que se obtiene de s en el trie.

Buscando car,

• c: buscando en el trie c < a y c < r (falta la letra en s). Aceptar un letra incorrecta en una palabra w , intente saltar en cada iteración la letra incorrecta para ver si ar está detrás, esto es O( w). Con dos letras, O (w 2) etc... pero otro nivel de índice podría añadirse al trie para tener en cuenta el salto sobre las letras - haciendo el trie complejo, y codicioso con respecto a la memoria.
• a, luego r: igual que arriba, pero buscando hacia atrás también

Esto es solo para proporcionar una idea sobre el principio-el ejemplo anterior puede tener algunos problemas técnicos (lo comprobaré de nuevo mañana).

Usted podría hacer esto:

Foreach string in haystack Do
    offset := -1;
    matchedCharacters := 0;
    Foreach char in needle Do
        offset := PositionInString(string, char, offset+1);
        If offset = -1 Then
            Break;
        End;
        matchedCharacters := matchedCharacters + 1;
    End;
    If matchedCharacters > 0 Then
       // (partial) match found
    End;
End;

Con Caracteres emparejados puede determinar el "grado" de la coincidencia. Si es igual a la longitud de aguja, todos los caracteres aguja también están en string. Si también almacena el desplazamiento del primer carácter coincidente, también puede ordenar el resultado por la "densidad" de los caracteres coincidentes restando el desplazamiento del primer carácter coincidente del desplazamiento del último carácter coincidente offset; baja la diferencia, cuanto más denso sea el partido.

class Program { 
    static int ComputeLevenshteinDistance(string source, string target) {
        if ((source == null) || (target == null)) return 0;
        if ((source.Length == 0) || (target.Length == 0)) return 0;
        if (source == target) return source.Length;

        int sourceWordCount = source.Length;
        int targetWordCount = target.Length;

        int[,] distance = new int[sourceWordCount + 1, targetWordCount + 1];

        // Step 2
        for (int i = 0; i <= sourceWordCount; distance[i, 0] = i++);
        for (int j = 0; j <= targetWordCount; distance[0, j] = j++);

        for (int i = 1; i <= sourceWordCount; i++) {
            for (int j = 1; j <= targetWordCount; j++) {
                // Step 3
                int cost = (target[j - 1] == source[i - 1]) ? 0 : 1;

                // Step 4
                distance[i, j] = Math.Min(Math.Min(distance[i - 1, j] + 1, distance[i, j - 1] + 1), distance[i - 1, j - 1] + cost);
            }
        }

        return distance[sourceWordCount, targetWordCount]; 
    }

    static void Main(string[] args){ 
       Console.WriteLine(ComputeLevenshteinDistance ("Stackoverflow","StuckOverflow"));
       Console.ReadKey();
    }
}