13

ユーザーが検索文字列を入力しました。通常、検索文字列は空白を使用して分割され、OR検索が実行されます（項目が検索文字列要素のいずれかに一致する場合は一致します）。引用符を使用して空白を含むリテラルフレーズを囲む機能など、いくつかの「高度な」クエリ機能を提供したいと思います。

私は私のために文字列を分割するためにまともな正規表現を打ち出しましたが、実行するのに驚くほど長い時間がかかります（私のマシンでは> 2秒）。私はしゃっくりがどこにあるかを理解するためにそれを分解しました、そしてさらに興味深いことに、それは最後Matchが一致した後（おそらく入力の終わりに）発生するようです。文字列の最後までのすべての一致は、キャプチャできる時間よりも短い時間で一致しますが、最後の一致（それが何であるか-何も返されません）は、2秒のほぼすべてを要します。

この正規表現を少しスピードアップする方法について誰かが洞察を持ってくれることを期待していました。無制限の数量詞でルックビハインドを使用していることは知っていますが、前述のように、最後の一致が一致するまで、これによってパフォーマンスの問題が発生することはないようです。

コード 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;

namespace RegexSandboxCSharp {
    class Program {
        static void Main( string[] args ) {

            string l_input1 = "# one  \"two three\" four five:\"six seven\"  eight \"nine ten\"";

            string l_pattern =
                @"(?<=^([^""]*([""][^""]*[""])?)*)\s+";

            Regex l_regex = new Regex( l_pattern );

            MatchCollection l_matches = l_regex.Matches( l_input1 );
            System.Collections.IEnumerator l_matchEnumerator = l_matches.GetEnumerator();

            DateTime l_listStart = DateTime.Now;
            List<string> l_elements = new List<string>();
            int l_previousIndex = 0;
            int l_previousLength = 0;
            //      The final MoveNext(), which returns false, takes 2 seconds.
            while ( l_matchEnumerator.MoveNext() ) {
                Match l_match = (Match) l_matchEnumerator.Current;
                int l_start = l_previousIndex + l_previousLength;
                int l_length = l_match.Index - l_start;
                l_elements.Add( l_input1.Substring( l_start, l_length ) );

                l_previousIndex = l_match.Index;
                l_previousLength = l_match.Length;
            }
            Console.WriteLine( "List Composition Time: " + ( DateTime.Now - l_listStart ).TotalMilliseconds.ToString() );

            string[] l_terms = l_elements.ToArray();

            Console.WriteLine( String.Join( "\n", l_terms ) );

            Console.ReadKey( true );

        }
    }
}

出力
（これはまさに私が得ているものです。）

1つ
の「23」
4つの
5：「6つの7」
8つの
「9つの10」

4

1 に答える 1

18

正規表現を次のように変更してみてください。

(?<=^((?>[^"]*)(["][^"]*["])?)*)\s+

ここでの唯一の変更は、[^"]*をアトミックグループに入れることです。これにより、発生する壊滅的なバックトラッキングが防止されます。

注：上記の正規表現は、私がよく知らないC＃正規表現文字列構文を使用していないことは明らかですが、次のようになると思います。

@"(?<=^((?>[^""]*)([""][^""]*[""])?)*)\s+";

壊滅的なバックトラッキングが発生する理由：
有効な一致がすべて見つかると、次に試行される一致は、最後に引用されたセクション内のスペースです。スペースの前に奇数の引用符があるため、後読みは失敗します。

この時点で、後読みの内部の正規表現はバックトラックを開始します。アンカーは、常に文字列の先頭から開始することを意味しますが、一致したものの末尾から要素を削除することでバックトラックできます。後読みの内部の正規表現を見てみましょう。

^([^"]*(["][^"]*["])?)*

引用されたセクションはオプションであるため、正規表現のバックトラックとして削除できます。引用符で囲まれたセクション内にない引用符で囲まれていない文字のチャンクごとに、バックトラックする前に、各文字は[^"]*正規表現の先頭の一部として一致していました。そのセクションでバックトラックが開始されると、最後の文字が[^"]*一致したものから削除され、外側の繰り返しによってピックアップされます。この時点で、上記の壊滅的なバックトラッキングリンクの例と非常によく似たものになります。

于 2012-09-19T17:38:09.727 に答える