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

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

Вот пример:

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

foo for
foo bax
foo buo
fxx bar

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

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


string-matching language-agnostic levenshtein-distance
person Community    schedule 05.11.2010    source источник
comment
Я не уверен, что понимаю ваш вопрос, поскольку вы сказали, что он либо соответствует шаблону, либо нет, что вы подразумеваете под количеством, например, сколько символов совпадает?   -  person user472875    schedule 05.11.2010
comment
Хороший вопрос; Мне это тоже интересно.   -  person Paul Sonier    schedule 05.11.2010
comment
да, я думаю, я ищу другой метод, чем сопоставление регулярных выражений. извиняюсь за недопонимание, меняю вопрос...   -  person    schedule 05.11.2010
comment
@W_P, вы имеете в виду алгоритмы нечетких строк, такие как soundex и/или Расстояние Левенштейна, но тогда вместо двух строк у вас есть шаблон и строка? Или я не в себе? :)   -  person Bart Kiers    schedule 05.11.2010
comment
хм, все еще смотрю на это, но мое первое впечатление таково, что расстояние Левенштейна - это то, что я ищу ... Я отредактировал вопрос, приведя пример того, о чем я говорю.   -  person    schedule 05.11.2010
comment
при условии, что шаблоны представляют собой простые строки и не имеют списка символов или квантификаторов и т. д., тогда расстояние Левенштейна является точным (но немного дороже для вычисления больших шаблонов). Если это правда, то общее выражение для того, что вы ищете, — это метрики сходства строк.   -  person Flexo    schedule 05.11.2010
comment
@Bart Kiers, если вы предоставите расстояние Левенштейна в качестве ответа, я отмечу его как принятый   -  person    schedule 05.11.2010
comment
@W_P, я вижу, что кто-то уже опубликовал что-то о расстоянии Левенштейна: вместо этого не стесняйтесь принять этот ответ.   -  person Bart Kiers    schedule 05.11.2010

Ответы (2)


arrow_upward
3
arrow_downward

Этот работает, я проверил пример из Википедии 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];
        }

}
person ant    schedule 05.11.2010
comment
На самом деле существует множество различных алгоритмов расстояния редактирования, в зависимости от того, что именно вы хотите сравнивать. - person Antal Spector-Zabusky; 05.11.2010

arrow_upward
0
arrow_downward

Это интересный вопрос! Первое, что пришло на ум, это то, что способ сопоставления регулярных выражений заключается в построении DFA. Если у вас был прямой доступ к DFA, который был построен для заданного регулярного выражения (или только что создан это сами!) вы можете запустить входную меру расстояния от последнего состояния, в которое вы перешли, и состояния принятия, используя кратчайший путь как меру того, насколько он был близок к принятию, но я не знаю никаких библиотек, которые позволит вам сделать это легко, и даже эта мера, вероятно, не будет точно соответствовать вашей интуиции в ряде случаев.

person Flexo    schedule 05.11.2010