निकटतम मेल पता लगाएं तार के एक पत्र में इनपुट स्ट्रिंग है

Question

मैं मैच के लिए तार के एक कार्यान्वयन निर्देशिका खोजने में परेशानी .net लिए सबसे निकटतम मेल

मैं चाहते हैं और तार की सूची है, उदाहरण के लिए है:

इनपुट स्ट्रिंग: "। सार्वजनिक प्राइमरी स्कूल Wąsosz में Boleslaw"

तार की सूची:

सार्वजनिक प्राथमिक स्कूल। बी Chrobrego Wąsosz

विशेष प्राइमरी स्कूल

im.Henryka सींकीविक्ज़ प्राथमिक Wąsosz

प्राइमरी स्कूल में स्कूल। में ऊपरी Wąsosz

यह स्पष्ट रूप से के साथ मिलान किया जाना आवश्यक होगा Romuald Traugutta "सार्वजनिक प्राथमिक स्कूल। बी Chrobrego Wąsosz।"

क्या एल्गोरिदम वहाँ .net के लिए उपलब्ध हैं?

Answer 1

Edit distance

संपादित दूरी कैसे दो भिन्न तार बढ़ाता का एक तरीका है (ई.जी., शब्द) वे एक और आपरेशन की न्यूनतम संख्या की गणना के द्वारा वे अन्य स्ट्रिंग में बदलने के लिए आवश्यक हैं।

Levenshtein distance

अनौपचारिक रूप से, दो शब्दों के बीच Levenshtein दूरी एकल चरित्र संपादन (अर्थात सम्मिलन, हटाना या प्रतिस्थापन ) दूसरे में एक शब्द बदलने के लिए आवश्यक की न्यूनतम संख्या है।

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

नेट बॉक्स से बाहर कुछ भी आपूर्ति नहीं करता है - आप एक Edit Distance एक एल्गोरिथ्म अपने आप को लागू करने के लिए की जरूरत है। प्रत्येक i के लिए

// 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]; 
} 

कॉल LevenshteinDistance(targetString, possible[i]), तो LevenshteinDistance कौन सा सबसे छोटा मान देता है के लिए स्ट्रिंग possible[i] लेने: उदाहरण के लिए, अगर आप इस तरह Levenshtein Distance उपयोग कर सकते हैं,।