0

正規表現の任意のリストがあるとしましょう(IList<Regex> lst;たとえば)。文字列の前の方に一致するものを見つける方法はありますか?

もちろん、文字列でそれぞれを試して、どの一致が最も低いインデックスを持つかを確認するという簡単な解決策がありますが、これは長い文字列では非効率的です。

もちろん、戻って各正規表現から文字列を取り出し ( Regex.ToString())、それらをすべて連結することもできます ( "(regex1)|(regex2)|(regex3)")。

編集:基本的に、文字列操作と再コンパイルなしで、既にコンパイルされた正規表現を組み合わせる方法はありますか?

4

3 に答える 3

2

通常、複数のグループで 1 つの式を実行すると、各式を順番に実行するよりも遅くなることはよく知られています。1 つの式を作成する方が速いように見えるかもしれませんが、実際には正規表現エンジンは最初の式を見つけるために最初に文字列全体を検索し、おそらく文字列の最後まで検索しますが、一致が見つかると戻ります。したがって、強制的に最初の Match を返す方法はありません。これは、.NET Regex エンジンの仕組みによるものです。

各正規表現は文字列の前に始まる可能性がありますが、一致が長くなる可能性があるため、次のように検索の最後を現在最も古い一致のインデックスに制限することはできません。

        // WARNING WILL NOT ALWAYS RESULT IN THE RIGHT VALUES
        List<Regex> rxs = new List<Regex>(4);
        rxs.Add(new Regex("def"));
        rxs.Add(new Regex("abc"));
        rxs.Add(new Regex("bcd"));
        rxs.Add(new Regex("cde"));

        string target = "abcdef";
        int firstIndex = target.Length;
        string firstMatch = string.Empty;

        foreach (var rx in rxs)
        {
            var match = rx.Match(target, 0, firstIndex);
            if (match.Success)
            {
                firstIndex = match.Index;
                firstMatch = match.Value;
                if (firstIndex == 0) break;
            }
        }
        return firstMatch;

これは、各正規表現が一致する最大長がわかっている場合に機能します。その場合は次を使用します。

        // WARNING WILL NOT ALWAYS RESULT IN THE RIGHT VALUES
        List<Regex> rxs = new List<Regex>(4);
        rxs.Add(new Regex("def"));
        rxs.Add(new Regex("abc"));
        rxs.Add(new Regex("bcd"));
        rxs.Add(new Regex("cde"));

        string target = "abcdef";
        int firstIndex = target.Length;
        string firstMatch = string.Empty;

        foreach (var rx in rxs)
        {
            var match = rx.Match(target, 0, firstIndex + GetMaxLength(rx));
            if (match.Success)
            {
                firstIndex = match.Index;
                firstMatch = match.Value;
                if (firstIndex == 0) break;
            }
        }
        return firstMatch;

ただし、最初の位置で一致を見つけるとすぐにショートサーキットできるため、その後の潜在的な実行を節約できます。

        foreach (var rx in rxs)
        {
            var match = rx.Match(target);
            if (match.Success)
            {
                if (match.Index < firstIndex)
                {
                    firstIndex = match.Index;
                    firstMatch = match.Value;    
                }
                if (firstIndex == 0) break;
            }
        }

ちょっとしたトリックで、現在の最初の一致候補のインデックスを使用して検索を制限できますが、実際には、考えられるすべての一致を検索するよりも遅くなると思います。

        List<string> rxs = new List<string>(4);
        rxs.Add( "def");
        rxs.Add( "abc");
        rxs.Add( "bcd");
        rxs.Add( "cde");

        string target = "abcdef";
        int firstIndex = target.Length;
        string firstMatch = string.Empty;

        foreach (var rx in rxs)
        {
            var match = Regex.Match(target, @"(?<!\A[\w\W]{" + firstIndex + "})" + rx);
            if (match.Success)
            {
                if (match.Index < firstIndex)
                {
                    firstIndex = match.Index;
                    firstMatch = match.Value;    
                }
                if (firstIndex == 0) break;
            }
        }

最後に、実験と測定を行って、自分に最適な方法を見つけてください。


いくつかの追加情報があります。正規表現の少なくとも 1 つが文字列の先頭近くにあります。

その場合、長さインデックスに適切な値を使用して最初にスキャンすることを選択できるrx.Match(targetstring, 0, 1024 /* First scan */)ため、一致が見つからない場合にのみ and を使用し、2 回目のパスで検索を広げます。ターゲット文字列が非常に大きくなる可能性がある場合、これにより計算能力が大幅に節約されます。

于 2012-11-29T14:06:36.407 に答える
0

RegularExpressions.Match正規表現マッチングによって返される型には、一致が見つかった元の文字列内の位置を示すプロパティが含まれていますIndex

いくつかの異なる正規表現の結果からこれを比較して、最初に一致したものを決定できます。

何かのようなもの

 (from m in regexList
 let match = m.Match(targetstring)
 orderby match.Index
 select m.Value).FirstOrDefault()

注:テスト環境を作成するためにLinqpadにすばやくカットアンドペーストするコードを提供しなかったため、構文やその他の問題についてこれをテストしていません。今すぐ作業に取り掛かる必要があります。しかし、これで一般的なアイデアが得られるはずです。

これは、正規表現が既にコンパイルされているかどうかとは関係ありません。最終的には、ターゲット文字列に対してそれぞれを試す必要があります。

ランタイム環境は通常の状況でコンパイルされた正規表現のコンパイルとキャッシュを管理するため、試行する前に正規表現を選択できるようにする追加情報またはコンテキストがまだ共有されていない限り、質問が何を得ているのかわかりませんターゲット文字列に対してそれを。

于 2012-11-29T11:30:42.643 に答える
0

独自の正規表現マッチャーを使用しない唯一の方法は、実際には連結ルートです。それぞれを名前付きサブグループに入れ、その後、どのグループが実際に一致したかを調べて、元の正規表現がどの一致したかを判断できます。

大規模な入力を同時に心配している場合、そのステップがボトルネックではない可能性が高いため、なぜ再コンパイルについてそれほど心配しているのでしょうか...

于 2012-11-29T11:41:29.497 に答える