Calificación de la calidad de las coincidencias de cadena

Question

¿Cuál sería la mejor manera de comparar un patrón con un conjunto de cadenas, una por una, mientras que clasificando la cantidad con la que el patrón coincide con cada cadena? En mi limitada experiencia con expresiones regulares, la coincidencia de cadenas con patrones usando expresiones regulares parece ser una operación bastante binaria ... no importa cuán complicado sea el patrón, al final, coincide o no. Estoy buscando mayores capacidades, más allá de la mera coincidencia. ¿Hay una buena técnica o algoritmo que se relacione con esto?

He aquí un ejemplo:

Digamos que tengo un patrón foo bar y quiero encontrar la cadena que más se acerque a cabo de las siguientes cadenas:

foo for 
foo bax 
foo buo 
fxx bar 

Ahora, ninguna de estas, en realidad coincide el patrón, pero que no coincide es el más cercano para que coincida? En este caso, foo bax sería la mejor opción, ya que coincide con 6 de los 7 caracteres.

Disculpa si esta es una pregunta duplicada, realmente no sabía exactamente qué buscar cuando miré para ver si esta pregunta ya existe.

Answer 1

obras Éste, he comprobado con el ejemplo Wikipedia 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

¡Esa es una pregunta interesante! Lo primero que me vino a la mente es que la forma en que se combinan las expresiones regulares es construyendo un DFA. Si tenía acceso directo al DFA que era built for a given regex (¡o lo construyó usted mismo!), Puede ejecutar la entrada para medir la distancia desde el último estado al que hizo la transición y un estado de aceptación, usando una ruta más corta como medida de qué tan cerca está fue para ser aceptado, pero no conozco ninguna biblioteca que te permita hacer eso fácilmente e incluso esta medida probablemente no se correspondería con tu intuición en una cantidad de casos.