Algorytmy podobieństwa łańcuchów?

Levenshtein odległość to algorytm, który polecam. Oblicza minimalną liczbę operacji, które musisz wykonać, aby zmienić 1 ciąg znaków na inny. Im mniej zmian oznacza, że ciągi są bardziej podobne...

Jeśli skupimy się na wydajności, zaimplementowałbym algorytm oparty na trie struktura
(działa dobrze, aby znaleźć słowa w tekście, lub pomóc poprawić słowo, ale w Twoim przypadku można szybko znaleźć wszystkie słowa zawierające dane słowo lub wszystkie oprócz jednej litery, na przykład).

Proszę najpierw skorzystać z powyższego linku do Wikipedii.Tries jest najszybszą metodą sortowania słów (N words, search s, O(n) do utworzenia trie, O(1) do wyszukiwania s (lub jeśli wolisz, jeśli a jest średnią długością, O(an) dla trie i O(s) dla wyszukiwania)).

• Utwórz trie z listą słów, mając wszystkie litery indeksowane z przodu iz tyłu (patrz przykład poniżej)
• aby wyszukać s , wykonaj iterację z s [0] aby znaleźć słowo w trie, następnie s [1] itd...
• W trie, jeśli liczba znalezionych liter to len (s)-k wyświetlane jest słowo, gdzie k jest tolerancją (brak 1 litery, 2...).
• algorytm może być rozszerzony na słowa z listy (patrz poniżej)

Przykład, ze słowami car, vars.

Budowanie trie (duża litera oznacza koniec słowa tutaj, podczas gdy inne mogą kontynuować). > jest indeksem post (idź do przodu) i < jest indeksem pre (idź wstecz). W innym przykładzie możemy wskazać również literę początkową, nie jest ona tutaj przedstawiona dla jasności.
Na przykład < i > W C++ byłyby Mystruct *previous,*next, co oznacza, że z a > c < r można przejść bezpośrednio z a do c, a odwrotnie, również z a do 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

Szukam Samochodu Trie daje dostęp od 1., i znajdziesz samochód (znalazłbyś także wszystko zaczynając od samochód , ale także wszystko z samochodem w środku - nie jest to w przykładzie-ale np. zostałoby Znalezione z c > i > v < a < R).

Aby przeszukać, dopuszczając 1-literową niewłaściwą / brakującą tolerancję, iterację z każdej litery s , i policzyć liczbę kolejnych-lub pomijając 1-literową-liter, które otrzymujesz z s w trie.

Szukam car,

• c: wyszukiwanie trie dla c < a i c < r (brak litery w s ). Aby zaakceptować błędna litera w słowie w , spróbuj przeskoczyć przy każdej iteracji niewłaściwą literę, aby sprawdzić, czy arjest za, to jest O ( w ). Z dwoma literami, O ( w 2) itd... jednak do trie można dodać inny poziom indeksu, aby uwzględnić skok nad literami - czyniąc trie złożonym i chciwym w odniesieniu do pamięci.
• a, następnie r: to samo co wyżej, ale szukanie wstecz również

To jest po to, aby dać wyobrażenie o zasada-powyższy przykład może mieć pewne usterki (sprawdzę jutro ponownie).

Możesz to zrobić:

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;

Za pomocą matchedCharacters możesz określić "stopień" dopasowania. Jeśli jest równa długości igły , Wszystkie znaki w igły są również w ciągu . Jeśli zapisujesz również offset pierwszego dopasowanego znaku, Możesz również sortować wynik według "gęstości" dopasowanych znaków, odejmując offset pierwszego dopasowanego znaku od offsetu ostatniego dopasowanego znaku offset ; mniejsza różnica, tym bardziej gęsty mecz.

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