Оценка качества совпадений строк

Question

Что было бы лучшим способом сравнить шаблон с набором строк один за другим, а оценить количество совпадений с каждой строкой? В моем ограниченном опыте с регулярным выражением совпадающие строки с шаблонами с использованием регулярных выражений кажутся довольно двоичной операцией ... независимо от того, насколько сложна модель, в конце концов, она либо соответствует, либо нет. Я ищу большие возможности, помимо соответствия. Есть ли хорошая методика или алгоритм, которые относятся к этому?

Вот пример:

Допустим, у меня есть шаблон foo bar и я хочу, чтобы найти строку, которая наиболее близко соответствует его из следующих строк:

foo for 
foo bax 
foo buo 
fxx bar 

Теперь ни один из них на самом деле матч шаблон, но который не соответствует ближайшим к матчу? В этом случае foo bax будет лучшим выбором, так как он соответствует 6 из 7 символов.

Извините, если это дублированный вопрос, я действительно не знал, что именно искать, когда посмотрел, существует ли этот вопрос.

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. Если у вас был прямой доступ к DFA, который был built for a given regex (или просто построил его самостоятельно!), Вы могли бы запустить ввод, чтобы измерить расстояние от последнего состояния, в которое вы перешли, и состояние принятия, используя кратчайший путь как меру того, как закрыть его было принято, но я не знаю ни о каких библиотеках, которые позволили бы вам сделать это легко, и даже эта мера, вероятно, не будет точно отображать вашу интуицию в ряде случаев.