11

パターンが各文字列に一致する量を評価しながら、パターンを一連の文字列と 1 つずつ比較する最良の方法は何でしょうか? 正規表現に関する私の限られた経験では、正規表現を使用して文字列とパターンを一致させることは、かなりバイナリ操作のようです...パターンがどれほど複雑であっても、最終的には一致するかしないかのどちらかです。単なるマッチング以上の機能を求めています。これに関連する優れた手法またはアルゴリズムはありますか?

次に例を示します。

パターンfoo barがあり、次の文字列から最も一致する文字列を見つけたいとしましょう。

foo for
foo bax
foo buo
fxx bar

さて、これらのどれも実際にはパターンに一致しませんが、どの不一致が最も一致に近いでしょうか? この場合、foo bax7 文字中 6 文字に一致するため、 が最適です。

これが重複した質問である場合はお詫びします。この質問が既に存在するかどうかを確認したときに、正確に何を検索すればよいかわかりませんでした。

4

2 に答える 2

3

これは機能します。ウィキペディアの例で確認しました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];
        }

}
于 2010-11-05T16:54:19.247 に答える
0

それは興味深い質問です！最初に頭に浮かんだのは、正規表現を照合する方法はDFAを作成することです。特定の正規表現用に構築されたDFAに直接アクセスできる場合（または自分で構築した場合）、最短パスをメジャーとして使用して、最後に遷移した状態からの距離と受け入れ状態から入力メジャーを実行できます。受け入れられるまでの距離はわかりますが、それを簡単に実行できるライブラリはありません。また、この方法でさえ、多くの場合、直感に正確に対応できない可能性があります。

于 2010-11-05T15:15:15.230 に答える