सहिष्णुता के साथ तारों की तुलना

Question

मैं स्ट्रिंग की सरणी के साथ एक स्ट्रिंग की तुलना करने का एक तरीका ढूंढ रहा हूं। सटीक खोज करना बिल्कुल आसान है, लेकिन मैं चाहता हूं कि मेरा प्रोग्राम वर्तनी की गलतियों को सहन करे, स्ट्रिंग के हिस्सों को खोए और इसी तरह।

क्या कोई ऐसी ढांचा है जो ऐसी खोज कर सकती है? मुझे कुछ याद आ रहा है कि खोज एल्गोरिदम मैच के प्रतिशत या इस तरह के कुछ प्रतिशत द्वारा कुछ परिणाम आदेश लौटाएगा।

Answer 1

आप Levenshtein Distance algorithm का उपयोग कर सकते हैं।

"दो तारों के बीच लेवेनशेटिन दूरी को एक स्ट्रिंग को दूसरे में बदलने के लिए आवश्यक संपादनों की न्यूनतम संख्या के रूप में परिभाषित किया जाता है, स्वीकार्य संपादन संचालन एक वर्ण के सम्मिलन, हटाना या प्रतिस्थापन के साथ होता है।" - Wikipedia.com

यह एक dotnetperls.com से है:

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

आप वास्तव में Damerau-Levenshtein distance algorithm है, जो भी अनुमति देता है पात्रों स्थानांतरित किया जाना है, जो डेटा प्रविष्टि में एक आम मानवीय भूल है उपयोग करने के लिए पसंद कर सकते हैं। आपको here का सी # कार्यान्वयन मिलेगा।

Answer 2

यहां दो विधियां हैं जो तारों के बीच Levenshtein Distance की गणना करती हैं।

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

एक बार आपके पास परिणाम होने के बाद, आपको यह निर्धारित करना होगा कि आप किसी मिलान के लिए थ्रेसहोल्ड के रूप में किस मूल्य का उपयोग करना चाहते हैं या नहीं। अपने विशेष दहलीज पर निर्णय लेने में मदद करने के लिए यह कैसे काम करता है इसका एक अच्छा विचार प्राप्त करने के लिए नमूना डेटा के समूह पर फ़ंक्शन चलाएं।

/// <summary> 
    /// Calculates the Levenshtein distance between two strings--the number of changes that need to be made for the first string to become the second. 
    /// </summary> 
    /// <param name="first">The first string, used as a source.</param> 
    /// <param name="second">The second string, used as a target.</param> 
    /// <returns>The number of changes that need to be made to convert the first string to the second.</returns> 
    /// <remarks> 
    /// From http://www.merriampark.com/ldcsharp.htm 
    /// </remarks> 
    public static int LevenshteinDistance(string first, string second) 
    { 
     if (first == null) 
     { 
      throw new ArgumentNullException("first"); 
     } 
     if (second == null) 
     { 
      throw new ArgumentNullException("second"); 
     } 

     int n = first.Length; 
     int m = second.Length; 
     var d = new int[n + 1, m + 1]; // matrix 

     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 = (second.Substring(j - 1, 1) == first.Substring(i - 1, 1) ? 0 : 1); // cost 
       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]; 
    } 

Answer 3

.NET ढांचे में कुछ भी नहीं है जो आपको इस आउट ऑफ़ द बॉक्स के साथ मदद करेगा।

सबसे आम वर्तनी गलतियाँ वे हैं जहां पत्र शब्द का एक सभ्य ध्वन्यात्मक प्रतिनिधित्व है, लेकिन शब्द की सही वर्तनी नहीं है।

उदाहरण के लिए, यह तर्क दिया जा सकता है कि sword और sord (हाँ, यह एक शब्द है) में वही ध्वन्यात्मक जड़ें हैं (जब आप उन्हें उच्चारण करते हैं तो वे वही ध्वनि करते हैं)।

कहा जा रहा है कि, ऐसे कई एल्गोरिदम हैं जिनका उपयोग आप शब्द (यहां तक ​​कि गलत वर्तनी वाले) को फोनेटिक रूपों में अनुवाद करने के लिए भी कर सकते हैं।

पहला Soundex है। यह लागू करने के लिए काफी सरल है और .NET implementations of this algorithm की उचित संख्या है। यह अपेक्षाकृत सरल है, लेकिन यह आपको वास्तविक मूल्य देता है जो आप एक-दूसरे से तुलना कर सकते हैं।

दूसरा Metaphone है। हालांकि मुझे मेटाफोन का मूल .NET कार्यान्वयन नहीं मिल रहा है, लेकिन प्रदान किए गए लिंक में कई अन्य कार्यान्वयन के लिंक हैं जिन्हें परिवर्तित किया जा सकता है। कनवर्ट करने का सबसे आसान शायद Java implementation of the Metaphone algorithm होगा।

यह ध्यान दिया जाना चाहिए कि मेटाफोन एल्गोरिदम संशोधन के माध्यम से चला गया है।Double Metaphone है (जिसमें .NET implementation है) और Metaphone 3 है। मेटाफोन 3 एक वाणिज्यिक अनुप्रयोग है, लेकिन सामान्य अंग्रेजी शब्दों के डेटाबेस के विरुद्ध चलाने पर डबल मेटाफोन एल्गोरिदम के लिए 89% सटीकता दर की तुलना में 98% सटीकता दर है। आपकी ज़रूरत के आधार पर, हो सकता है कि आप (डबल मेटाफोन के मामले में) या खरीद (मेटाफोन 3 के मामले में) एल्गोरिदम के स्रोत को देखना चाहें और पी/इनवॉक लेयर के माध्यम से इसे परिवर्तित या एक्सेस कर सकें (सी ++ कार्यान्वयन हैं लाजिमी है)।

मेटाफोन और साउंडएक्स इस अर्थ में भिन्न है कि साउंडएक्स निश्चित लंबाई संख्यात्मक कुंजी उत्पन्न करता है, जबकि मेटाफोन विभिन्न लंबाई की चाबियां उत्पन्न करता है, इसलिए परिणाम अलग होंगे। अंत में, दोनों आपके लिए समान प्रकार की तुलना करेंगे, आपको केवल यह पता लगाना होगा कि आपकी आवश्यकताओं और संसाधनों (और वर्तनी की गलतियों के लिए असहिष्णुता स्तर) के अनुसार आपकी आवश्यकताओं को सर्वोत्तम तरीके से कौन सा अनुकूल बनाता है।

Answer 4

आप ओपन सोर्स CommonLibrary.NET project में साउंडएक्स और लेवेनशेटिन दूरी एल्गोरिदम के कार्यान्वयन पा सकते हैं।

Answer 5

आपका दूसरा विकल्प ध्वनि या मेटाफोन का उपयोग करके ध्वन्यात्मक रूप से तुलना करना है। मैंने अभी एक लेख पूरा किया है जो दोनों एल्गोरिदम के लिए सी # कोड प्रस्तुत करता है। आप इसे http://www.blackbeltcoder.com/Articles/algorithms/phonetic-string-comparison-with-soundex पर देख सकते हैं।

Answer 6

यहां लेवेनशेटिनडिस्टेंस विधि का कार्यान्वयन है जो एक ही परिणाम उत्पन्न करते समय बहुत कम स्मृति का उपयोग करता है। यह "0 मैट्रिक्स पंक्तियों के साथ इटरेटिव" शीर्षक के तहत इस wikipedia article में मिले छद्म कोड का सी # अनुकूलन है।

public static int LevenshteinDistance(string source, string target) 
{ 
    // degenerate cases 
    if (source == target) return 0; 
    if (source.Length == 0) return target.Length; 
    if (target.Length == 0) return source.Length; 

    // create two work vectors of integer distances 
    int[] v0 = new int[target.Length + 1]; 
    int[] v1 = new int[target.Length + 1]; 

    // initialize v0 (the previous row of distances) 
    // this row is A[0][i]: edit distance for an empty s 
    // the distance is just the number of characters to delete from t 
    for (int i = 0; i < v0.Length; i++) 
     v0[i] = i; 

    for (int i = 0; i < source.Length; i++) 
    { 
     // calculate v1 (current row distances) from the previous row v0 

     // first element of v1 is A[i+1][0] 
     // edit distance is delete (i+1) chars from s to match empty t 
     v1[0] = i + 1; 

     // use formula to fill in the rest of the row 
     for (int j = 0; j < target.Length; j++) 
     { 
      var cost = (source[i] == target[j]) ? 0 : 1; 
      v1[j + 1] = Math.Min(v1[j] + 1, Math.Min(v0[j + 1] + 1, v0[j] + cost)); 
     } 

     // copy v1 (current row) to v0 (previous row) for next iteration 
     for (int j = 0; j < v0.Length; j++) 
      v0[j] = v1[j]; 
    } 

    return v1[target.Length]; 
} 

यहां एक ऐसा फ़ंक्शन है जो आपको प्रतिशत समानता देगा।

/// <summary> 
/// Calculate percentage similarity of two strings 
/// <param name="source">Source String to Compare with</param> 
/// <param name="target">Targeted String to Compare</param> 
/// <returns>Return Similarity between two strings from 0 to 1.0</returns> 
/// </summary> 
public static double CalculateSimilarity(string source, string target) 
{ 
    if ((source == null) || (target == null)) return 0.0; 
    if ((source.Length == 0) || (target.Length == 0)) return 0.0; 
    if (source == target) return 1.0; 

    int stepsToSame = LevenshteinDistance(source, target); 
    return (1.0 - ((double)stepsToSame/(double)Math.Max(source.Length, target.Length))); 
}