nächste Übereinstimmung zu finden, ist die Eingabezeichenfolge in einem Schreiben von Strings

Question

Ich habe Probleme eine Implementierung Verzeichnis von Strings beste Übereinstimmung für .net finden

Ich mag würde passen und Listen von Zeichenketten, zB:

Eingabestring: "öffentliche Grundschule Boleslaw in Wasosz"

Liste der Strings:

öffentliche Grundschule. B. Chrobrego Wasosz

Sondergrundschule

im.Henryka Sienkiewicz Grundschule in Wasosz

Grundschule. Romuald Traugutta in Ober Wasosz

Dies müßte klar mit abgestimmt werden "Public Primary School. B. Chrobrego Wasosz."

Welche Algorithmen sind für .net verfügbar?

Answer 1

Edit distance

bearbeiten Abstand ist ein Weg zum Quantifizieren, wie zwei unähnlichen strings (E. G., Wörter) sind sie miteinander durch die minimale Anzahl von Operationen erforderlich Zählen sie es in die andere Zeichenfolge zu transformieren.

Levenshtein distance

Informal ist der Levenshtein Abstand zwischen zwei Worten, die minimale Anzahl von Einzelzeichen Bearbeitungen (d.h.e Insertionen, Deletionen oder Substitutionen ) erforderlich, um ein Wort in die andere zu wechseln.

Fast, memory efficient Levenshtein algorithm

C# Levenshtein

using System; 

/// <summary> 
/// Contains approximate string matching 
/// </summary> 
static class LevenshteinDistance 
{ 
    /// <summary> 
    /// Compute the distance between two strings. 
    /// </summary> 
    public static int Compute(string s, string t) 
    { 
    int n = s.Length; 
    int m = t.Length; 
    int[,] d = new int[n + 1, m + 1]; 

    // Step 1 
    if (n == 0) 
    { 
     return m; 
    } 

    if (m == 0) 
    { 
     return n; 
    } 

    // Step 2 
    for (int i = 0; i <= n; d[i, 0] = i++) 
    { 
    } 

    for (int j = 0; j <= m; d[0, j] = j++) 
    { 
    } 

    // Step 3 
    for (int i = 1; i <= n; i++) 
    { 
     //Step 4 
     for (int j = 1; j <= m; j++) 
     { 
     // Step 5 
     int cost = (t[j - 1] == s[i - 1]) ? 0 : 1; 

     // Step 6 
     d[i, j] = Math.Min(
      Math.Min(d[i - 1, j] + 1, d[i, j - 1] + 1), 
      d[i - 1, j - 1] + cost); 
     } 
    } 
    // Step 7 
    return d[n, m]; 
    } 
} 

class Program 
{ 
    static void Main() 
    { 
    Console.WriteLine(LevenshteinDistance.Compute("aunt", "ant")); 
    Console.WriteLine(LevenshteinDistance.Compute("Sam", "Samantha")); 
    Console.WriteLine(LevenshteinDistance.Compute("flomax", "volmax")); 
    } 
} 

Answer 2

.NET nichts aus der Box nicht liefern - Sie benötigen einen Edit Distance einen Algorithmus selbst zu implementieren. Zum Beispiel können Sie Levenshtein Distance wie folgt verwenden:

// This code is an implementation of the pseudocode from the Wikipedia, 
// showing a naive implementation. 
// You should research an algorithm with better space complexity. 
public static int LevenshteinDistance(string s, string t) { 
    int n = s.Length; 
    int m = t.Length; 
    int[,] d = new int[n + 1, m + 1]; 
    if (n == 0) { 
     return m; 
    } 
    if (m == 0) { 
     return n; 
    } 
    for (int i = 0; i <= n; d[i, 0] = i++) 
     ; 
    for (int j = 0; j <= m; d[0, j] = j++) 
     ; 
    for (int i = 1; i <= n; i++) { 
     for (int j = 1; j <= m; j++) { 
      int cost = (t[j - 1] == s[i - 1]) ? 0 : 1; 
      d[i, j] = Math.Min(
       Math.Min(d[i - 1, j] + 1, d[i, j - 1] + 1), 
       d[i - 1, j - 1] + cost); 
     } 
    } 
    return d[n, m]; 
} 

Anruf LevenshteinDistance(targetString, possible[i]) für jede i, dann die Zeichenfolge possible[i] für LevenshteinDistance wählen, die den kleinsten Wert zurückgibt.