11

正規表現のリストがあるとしましょう（外部ソースから読み取る-ファイル、データベースなど）。文字列がこれらの正規表現のどれに一致するかを確認したい。

これらすべての正規表現を反復して照合することはできますが、リストが膨大になる可能性があり、これは重要な操作です。

これらすべての正規表現を 1 つに (それらの間に | を使用して) 結合することはできますが、問題は、すべてではなく、最初に一致した正規表現しか識別できないことです。

もう 1 つのアイデアは、これらすべての正規表現のオートマトンを作成し、対応する正規表現のインデックスなどで最終状態をマークすることです。http://cs.au.dk/~amoeller/automaton/を見ていましたが、これは正規表現とオートマトンを扱うことができるようですが、私の問題を解決するために拡張できるかどうかはわかりません。

他にアイデアはありますか？

いくつかのコメントを明確にするために、コード サンプルを追加しました。

import java.util.regex.Matcher;
import java.util.regex.Pattern;


public class PatternTest {
    public static void main(String[] args) {
        Pattern p = Pattern.compile("(a(?:b|c)a)|((?:a|b)ba)|(ab(?:a|c))");     
        Matcher m = p.matcher("aba");
        System.out.println(m.matches());
        System.out.println(m.groupCount());
        for (int i = 0, n = m.groupCount(); i < n; i++) {
            System.out.println(m.group(i));
        }
    }
}

印刷します

true
3
aba
aba
null

ご覧のとおり、最初のグループのみが一致しており、他の 2 つのグループを一致させる方法がわかりません。

その他の調査結果 - 上記のオートマトン ライブラリを使用すると、問題は次のようになります。

4

3 に答える 3

6

私は dk.brics.automaton に基づいてそのようなソリューションを実装しました。ここで見つけることができます。 https://github.com/fulmicoton/multiregexp

于 2013-10-20T17:14:57.097 に答える
3

dk.brics.automatonはこれを直接サポートしていませんが、オートマトン (および関連するオートマトン操作) の表現を一般化して、さまざまな種類の受け入れ状態を区別することができます。たとえば、Stateクラスに int フィールドを追加することから始めて、「accept」が設定されている場合は常にこのフィールドを使用します。

于 2013-03-09T15:24:18.167 に答える
3

決定的な答え (ある場合) を得るには、次のような情報がさらに必要です。

  1. あなたは、正規表現のリストが膨大であると言います。もっと具体的に言えますか？数千？何百万？何十億と何十億？

  2. これらの正規表現を書いたのは誰ですか? 彼らは何をしているのか知っていますか? 正規表現は、リストに追加される前に(正確性とパフォーマンスについて)徹底的にテストされていますか?

  3. サンプル コードでは、matches()メソッドを使用します。これには、文字列全体を記述する正規表現が必要です。これは、正規表現が実際
    \A(?:(a(?:b|c)a)|((?:a|b)ba)|(ab(?:a|c)))\z
    に which に一致"aba"するが or には一致しない"aaba"かのように動作し"abaa"ます。Java を使用する前に他のツールや言語で正規表現を使用したことがある場合、この動作に驚くかもしれません。従来、文字列は、正規表現が文字列内の部分文字列 (長さがゼロの部分文字列であっても) を記述している場合、正規表現に「一致する」と常に言われてきました。Java でその動作を実現するには、Matcher のfind()メソッドを使用する必要があります。

  4. 最小または最大の長さ、共通の部分文字列、または共有文字サブセットなど、リスト内のすべての正規表現から引き出すことができる共通の要素はありますか? たとえば、サンプル パターンの 1 つに一致する文字列は、 にも一致する必要があります[abc]{3}。ある場合は、それらに基づいてフィルターを作成し (正規表現かもしれないし、そうでないかもしれません)、深刻なマッチングが始まる前に実行することをお勧めします。(すでにそのような最適化が行われている Perl を使用している場合、これはお勧めしませんが、Java は少しの助けを受け入れることを誇りに思っていません。☺)

しかし、正規表現をすべて 1 つに連結するのではなく、個別の正規表現を使用することをお勧めします。Frankenregex のパフォーマンスが必ずしも向上するとは限らず、トラブルシューティングは悪夢です! 次のように、すべての Pattern オブジェクトを事前にコンパイルし、事前に Matcher オブジェクトを作成して、すべての一致に再利用できます。

m.reset(s).usePattern(p);

ここにデモがあります。私は何の保証もできません (正規表現を書いた人に翻弄されます) が、解決策が可能であれば、これが最も有望なアプローチだと思います。

于 2013-03-09T15:12:05.150 に答える