Évaluation de la qualité des correspondances de chaînes

Question

Quel serait le meilleur moyen de comparer un modèle avec un jeu de chaînes, un par un, alors que évalue la quantité avec laquelle le modèle correspond à chaque chaîne? Dans mon expérience limitée avec regex, assortir des chaînes avec des modèles utilisant regex semble être une opération binaire assez ... peu importe comment le modèle est compliqué, à la fin, il correspond ou non. Je suis à la recherche de plus grandes capacités, au-delà de l'appariement. Y a-t-il une bonne technique ou un bon algorithme en rapport avec cela?

Voici un exemple:

Disons que j'ai un modèle foo bar et je veux trouver la chaîne qui correspond le mieux à sortir des chaînes suivantes:

foo for 
foo bax 
foo buo 
fxx bar 

Maintenant, aucun d'entre eux fait correspondre le motif, mais quelle non-correspondance est le le plus proche d'être une correspondance? Dans ce cas, foo bax serait le meilleur choix, car il correspond à 6 des 7 caractères. Excuses s'il s'agit d'une question en double, je ne savais pas vraiment exactement ce que je devais rechercher lorsque je cherchais à voir si cette question existait déjà.

Answer 1

Celui-ci fonctionne, j'ai vérifié avec Wikipedia exemple 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

C'est une question intéressante! La première chose qui vient à l'esprit est que la façon dont les expressions régulières sont appariées est en construisant un DFA. Si vous aviez un accès direct au DFA qui était built for a given regex (ou que vous l'avez construit vous-même!), Vous pouvez mesurer la distance entre le dernier état de transition et un état d'acceptation, en utilisant le chemin le plus court C'était d'être accepté, mais je ne connais pas de bibliothèques qui vous permettraient de le faire facilement et même cette mesure ne correspondrait probablement pas exactement à votre intuition dans un certain nombre de cas.