Algorithmes de similarité de chaîne?

La distance Levenshtein est l'algorithme que je recommanderais. Il calcule le nombre minimum d'opérations que vous devez faire pour changer 1 chaîne en une autre. Le moins de changements signifie que les chaînes sont plus similaires...

Si l'accent est mis sur la performance, j'implémenterais un algorithme basé sur un trie structure
(fonctionne bien pour trouver des mots dans un texte, ou pour aider à corriger un mot, mais dans votre cas, vous pouvez trouver rapidement tous les mots contenant un mot donné ou tous, mais une lettre, par exemple).

Veuillez d'abord suivre le lien wikipedia ci-dessus.{[2] } est la méthode de tri des mots la plus rapide (N mots, Recherche s , O(n) pour créer le trie, O (1) pour rechercher s (ou si vous préférez, si un est la longueur moyenne, O(un) pour la trie et O(s) pour la recherche)).

Une implémentation rapide et facile (à optimiser) de votre problème (mots similaires) consiste en

• faire le trie avec la liste des mots, ayant toutes les lettres indexées avant et arrière (voir l'exemple ci-dessous)
• Pour rechercher s, effectuer une itération à partir de s[0] pour trouver le mot dans la trie, puis s[1] etc...
• Dans la trie, si le nombre de lettres trouvées len(s)-k, le mot est affiché, où k est la tolérance (1 lettre manquante, 2...).
• l'algorithme peut être étendu aux mots de la liste (Voir ci-dessous)

Exemple, avec les mots car, vars.

Construire le trie (grande lettre signifie un mot fin ici, tandis qu'un autre peut continuer). Le > est post-index (aller de l'avant) et de < est pré-index (aller arriéré). Dans un autre exemple, nous devrons peut-être indiquer également la lettre de départ, elle n'est pas présentée ici pour plus de clarté.
Les < et > en C++ par exemple seraient Mystruct *previous,*next, ce qui signifie de a > c < r, vous pouvez aller directement de a à c, et inversement, aussi de 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

Vous cherchez strictement voiture le trie vous donne accès à partir de 1. et vous trouvez voiture (vous pouvez également trouver de tout, en commençant par voiture, mais aussi tout ce qui avec la voiture à l'intérieur - ce n'est pas dans l'exemple - mais vicaire par exemple aurait été trouvé à partir de c > i > v < a < R).

Pour rechercher tout en autorisant une tolérance erronée / manquante de 1 lettre, vous itérez à partir de chaque lettre de s , et comptez le nombre de lettres consécutives - ou en sautant 1 lettre - que vous obtenez de s dans le trie.

Recherche car,

• c: la recherche de la trie pour c < a et c < r (lettre manquante dans s). Pour accepter un mauvaise lettre dans un mot w, essayez de sauter à chaque itération de la mauvaise lettre pour voir si ar est derrière, c'est O(w). Avec deux lettres, O(w2) etc... mais un autre niveau d'index pourrait être ajouté au trie pour prendre en compte le saut sur les lettres-rendant le complexe trie, et gourmand en mémoire.
• a, puis r: comme ci-dessus, mais en cherchant aussi en arrière

Ceci est juste pour fournir une idée sur le Principe - l'exemple ci-dessus peut avoir quelques pépins (je vais vérifier à nouveau demain).

Vous pouvez faire ceci:

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;

Avec matchedCharacters, vous pouvez déterminer le "degré" de la correspondance. Si elle est égale à la longueur de aiguille, tous les caractères aiguille, sont également dans string. Si vous stockez également le décalage du premier caractère apparié, vous pouvez également trier le résultat par la "densité" des caractères appariés en soustrayant le décalage du premier caractère apparié du décalage du dernier caractère apparié offset ; Le abaissez la différence, plus le match est dense.

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();
    }
}