Stringähnlichkeitsalgorithmen?

Es scheint, Sie brauchen eine Art von fuzzy-matching. Hier ist die java-Implementierung von einiger ähnlichkeit Metriken http://www.dcs.shef.ac.uk/~sam/stringmetrics.html. Hier finden Sie ausführlichere Erläuterung der string-Metriken http://www.cs.cmu.edu/~wcohen/postscript/ijcai-ws-2003.pdf es hängt davon ab, wie verschwommen und wie schnell die Umsetzung erfolgen muss.

InformationsquelleAutor der Antwort

Wenn der Fokus auf Leistung, würde ich implementieren einen Algorithmus basierend auf einer trie Struktur

(funktioniert gut, um Wörter in einem text, oder um richtige Wort, aber in Ihrem Fall finden Sie schnell alle Wörter mit einem bestimmten Wort oder alle, aber ein Brief, zum Beispiel).

Folgen Sie bitte zuerst den wikipedia-link oben.Tries ist die Schnellste Worte Sortier-Methode (n Worte, Suche sO(n) zu erstellen, die versuchten, O(1) Suche s (oder wenn Sie es bevorzugen, wenn eine ist die Durchschnittliche Länge, O(eine) für die trie und O(s) für die Suche)).

Eine schnelle und einfache Umsetzung (optimiert) von Ihrem problem (ähnliche Wörter) besteht aus

• Machen die trie mit der Liste von Wörtern, die alle Buchstaben indiziert Vorder-und Rückseite (siehe Beispiel unten)
• Zu suchen sDurchlaufen von s[0] zu finden, das Wort in der Marina, dann s[1] etc...
• In der Marina, wenn die Anzahl der Buchstaben, die gefunden wurde, ist len(s)-k das Wort angezeigt wird, wo k ist die Toleranz (1 Brief fehlt, 2...).
• Der Algorithmus kann erweitert werden, um die Wörter in der Liste (siehe unten)

Beispiel, mit den Worten carvars.

Bau der Marina (großer Buchstabe bedeutet ein Wort hier zu Ende, während andere möglicherweise fortfahren). Die > - post-index (vorwärts gehen) und < ist pre-index (rückwärts gehen). In einem anderen Beispiel, das wir haben können, zeigen auch die Start-Brief, es wird nicht dargestellt, hier für Klarheit.

Die < und > in C++ zum Beispiel wäre Mystruct *previous,*next, Bedeutung von a > c < r Sie können direkt von a zu c, und Umgekehrt, auch von a zu 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

Suchen ausschließlich für Auto die Marina bietet Ihnen Zugriff vom 1., und Sie finden Auto (Sie hätte auch alles ab Autoaber auch alles, was mit Auto-innen - ist es nicht in der Beispiel - aber Vikar zum Beispiel hätte aus c > i > v < a < R).

Zu suchen, während es die 1-Buchstaben-falsche/fehlende Toleranz, die Sie Durchlaufen, die aus jedem Brief von sund zählen die Anzahl der aufeinander folgenden oder durch überspringen von 1 Brief - Briefe erhalten Sie von s in der trie.

suchen car,

• c: die Suche im trie für c < a und c < r (fehlende Buchstaben in s). Zu akzeptieren einen falschen Buchstaben in einem Wort wversuchen zu springen, die bei jedem Durchlauf die falschen Buchstaben zu sehen, wenn ar hinter, dieser ist O(w). Mit zwei Buchstaben, O(w2) usw... aber eine andere Ebene des index Hinzugefügt werden könnten, um den trie zu berücksichtigen, die springen über Briefe - die in der Marina Komplex und gierig in Bezug auf Speicher.
• adann r: dasselbe wie oben, aber auf der Suche nach hinten so gut

Dies ist nur um eine Idee über das Prinzip - das Beispiel oben kann haben einige Probleme (check ich morgen wieder).

InformationsquelleAutor der Antwort

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

InformationsquelleAutor der Antwort