स्ट्रिंग मैचों की गुणवत्ता

Question

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

चलें कहते हैं कि मैं एक पैटर्न foo bar है और मैं स्ट्रिंग है कि सबसे निकट निम्नलिखित तार से बाहर यह मिलान प्राप्त करना चाहते हैं: वास्तव में

foo for 
foo bax 
foo buo 
fxx bar 

अब, इनमें से कोई भी

यहाँ एक उदाहरण है मैच पैटर्न, लेकिन एक मैच होने के लिए निकटतम है जो गैर-मिलान है? इस मामले में, foo bax सबसे अच्छा विकल्प होगा, क्योंकि यह 7 अक्षरों में से 6 में से मेल खाता है।

क्षमा करें यदि यह एक डुप्लिकेट प्रश्न है, तो मुझे वास्तव में पता नहीं था कि वास्तव में क्या खोजना है जब मैंने देखा कि यह प्रश्न पहले से मौजूद है या नहीं।

Answer 1

यह एक काम करता है, मैं विकिपीडिया उदाहरण के साथ की जाँच distance between "kitten" and "sitting" is 3

public class LevenshteinDistance { 

    public static final String TEST_STRING = "foo bar"; 

    public static void main(String ...args){ 
     LevenshteinDistance test = new LevenshteinDistance(); 
     List<String> testList = new ArrayList<String>(); 
     testList.add("foo for"); 
     testList.add("foo bax"); 
     testList.add("foo buo"); 
     testList.add("fxx bar"); 
     for (String string : testList) { 
      System.out.println("Levenshtein Distance for " + string + " is " + test.getLevenshteinDistance(TEST_STRING, string)); 
     } 
    } 

    public int getLevenshteinDistance (String s, String t) { 
      if (s == null || t == null) { 
      throw new IllegalArgumentException("Strings must not be null"); 
      } 

      int n = s.length(); // length of s 
      int m = t.length(); // length of t 

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

      int p[] = new int[n+1]; //'previous' cost array, horizontally 
      int d[] = new int[n+1]; // cost array, horizontally 
      int _d[]; //placeholder to assist in swapping p and d 

      // indexes into strings s and t 
      int i; // iterates through s 
      int j; // iterates through t 

      char t_j; // jth character of t 

      int cost; // cost 

      for (i = 0; i<=n; i++) { 
      p[i] = i; 
      } 

      for (j = 1; j<=m; j++) { 
      t_j = t.charAt(j-1); 
      d[0] = j; 

      for (i=1; i<=n; i++) { 
       cost = s.charAt(i-1)==t_j ? 0 : 1; 
       // minimum of cell to the left+1, to the top+1, diagonally left and up +cost     
       d[i] = Math.min(Math.min(d[i-1]+1, p[i]+1), p[i-1]+cost); 
      } 

      // copy current distance counts to 'previous row' distance counts 
      _d = p; 
      p = d; 
      d = _d; 
      } 

      // our last action in the above loop was to switch d and p, so p now 
      // actually has the most recent cost counts 
      return p[n]; 
     } 

} 

Answer 2

यह एक दिलचस्प सवाल है! पहली बात यह है कि दिमाग में आया है कि जिस तरह से नियमित अभिव्यक्तियों का मिलान किया जाता है वह DFA बनाकर होता है। यदि आपके पास built for a given regex (या बस इसे स्वयं बनाया गया है) के लिए सीधे पहुंच थी, तो आप इनपुट को उस अंतिम स्थिति से दूरी को माप सकते हैं जिसे आपने संक्रमण किया था और एक स्वीकार्य स्थिति का उपयोग करके, इसे कम करने के उपाय के रूप में एक छोटा रास्ता स्वीकार किया जाना था, लेकिन मुझे किसी भी पुस्तकालय से अवगत नहीं है जो आपको आसानी से ऐसा करने देगा और यहां तक ​​कि यह उपाय शायद कई मामलों में आपके अंतर्ज्ञान पर बिल्कुल सही नहीं होगा।