4

「!」、「?」を検索して、英文の終わりを判断しようとしています (おおよそのことです)。または「.」、ただし「.」の場合 Mr. や Dr. などの一般的な略語が前に付いていない場合のみ。

次の正規表現を少しでも効率的にする方法はありますか? おそらく、負の後読みをサイズの降順、またはアルファベット順でソートすることでしょうか?

これが私が今持っている正規表現です：

((?<!St|Sgt|Rev|Ltd|Inc|Lt|Jr|Sr|Esq|Inst|Hon|Gen|Cpl|Comdr|Col|Corp|Mr|Dr|Gov|Mrs|Ms|[A-Z]|Assn|Capt)(\.)|(!)|(\?))(\s*$|\s+([_$#]|[A-Z][^.]))

問題：

http://regex.powertoy.org/のサイトでは、「7 は 21044 個のプローブに一致 (終了)」と報告しています。単純な段落でさえ... 21044 という数字のとんでもないサイズは、否定的な後読みの数と密接に関係しているようです。

RegEx エンジンを通過するデータが数 GB あるため、RegEx エンジンの計算の複雑さを軽減しようとしています。

これを引き締める方法はありますか？否定的な後読みは本当にこれを達成するための最良/唯一の方法ですか? 代わりに先読みとしてそれを行う方法はありますか? 正規表現はこのタスクに不適切なツールですか?

編集: ActionScript または PHP の正規表現エンジンを使用できます。

編集:文間のスペースの数を数えることはできません。 本当！？はぁ。

最適化に関して、正規表現エンジンの内部の仕組みを理解していない場合は、回答しないでください。

前もって感謝します。

4

3 に答える 3

4

最初に期間を一致させます。これの代わりに：

(?<!St|Sgt|Rev|Ltd|Inc|...|Capt)\.

...これを行う：

\.(?<!(?:St|Sgt|Rev|Ltd|Inc|...|Capt)\.)

このように、正規表現エンジンは、次の文字がピリオドであると判断する前に後読みを実行する必要があります。その変更を行うと、プローブ数は28,423から1,945になります。(Powertoy サイトが提供するデフォルトのテキストを使用しています。何も提供していないためです。)

また、次の 2 つの選択肢を組み合わせて、(!)|(\?)1 つにし([!?])ます。これにより、プローブ数が1,344に減少します。また、一致の個々の部分をキャプチャする必要がない場合は、.(?:...)の代わりに非キャプチャ括弧を使用することをお勧めします(...)。プローブ数には反映されませんが、正規表現がより効率的になります。

編集:正規表現をよく見ると、一致するものが見つからなかった理由が[A-Z]代替手段であることがわかります。一致全体が大文字と小文字を区別しないモードで行われるため、その代替手段は他のすべてを切り捨てます。/i修飾子を削除するか、(?-i:...)コンストラクトでローカルにオーバーライドする必要があります。@Swissが提案したように、（単語境界）を追加すること\bも良い考えです。それはあなたを残します：

(?-i:\.(?<!\b(?:St|Sgt|Rev|Ltd|Inc|...|[A-Z]|Assn|Capt)\.)

...[!?]変更に伴い、Regex Powertoy サイトの 1404 プローブで 6 つの一致が得られます。

于 2010-10-19T05:17:20.170 に答える
4

おそらく、 とのマッチングに成功した後にのみ、否定後読みテストを実行してみてください。すべての文字ではなく:

(?x:  # Allow spacing and comments
    (   
        (\.)    # First match "."
        (?<!    # Then negative-look-behind for titles followed by "."
            (?: St|Sgt|Rev|Ltd|Inc|Lt|Jr|Sr|Esq|Inst|Hon|Gen|Cpl|Comdr|Col|Corp|Mr|Dr|Gov|Mrs|Ms|[A-Z]|Assn|Capt)
            \.
        )
      |  (!)  
      |  (\?)
    )
    ( \s* $  |  \s+ ( [_$#] | [A-Z] [^.] ))
)

これにより、サイトの最初のヘルプ テキストを使用して、powertoy.org でのプローブの数が 70000 から 2500 程度に減少しました。(しかし、powertoy は複数行の正規表現や "x" フラグなどを気に入らなかったため、正規表現を 1 行にまとめてテストする必要がありました)。

タイトルのリストで一般的なプレフィックスを使用することで、さらに先に進むことができます。

(?x:  # Allow spacing and comments
    (
        (\.)    # First match "."
        (?<!    # Then negative-look-behind for titles followed by "."
            (?:Assn|C(?:apt|ol|omdr|orp|pl)|Dr|Esq|G(?:en|ov)|Hon|I(?:nc|nst)|Jr|L(?:t|td)|M(?:[rs]|rs)|Rev|S(?:gt|[rt])|[A-Z])
            \.
        )
      |  (!)  
      |  (\?)
    )
    ( \s* $  |  \s+ ( [_$#] | [A-Z] [^.] ))
)

これにより、プローブ数は約 2000 まで減少しました。

編集:
プローブ数を減らすもう 1 つのトリックは、後読みセクションの先頭に大文字の先読みを含めることです (ただし、正規表現がより効率的になるとは言えませんでした) (また、単語境界に対する@Swissの提案):

        (?<!   # Then negative-look-behind for titles followed by "."
               \b (?= [A-Z] )  # But first ensure we have a capital letter before going on
               (?:Assn|C(?:apt|ol|omdr|orp|pl)|Dr|Esq|G(?:en|ov)|Hon|I(?:nc|nst)|Jr|L(?:t|td)|M(?:[rs]|rs)|Rev|S(?:gt|[rt])|[A-Z])
            \.
        )
于 2010-10-19T05:17:28.723 に答える
2

プレスを止めろ！

編集した質問によると、このプロジェクトでは PHP または ActionScript のいずれかを使用しています。これは、これまでに提供されたソリューションのどれも役に立たないことを意味します。元の正規表現は遅すぎるだけでなく、ターゲット プラットフォームではまったく機能しません。Regex Powertoy サイトで機能する理由は、そのサイトが Java regex フレーバーを使用しており、後読みに対する制限が緩いためです。

後読みは、正規表現機能の中でも厄介者のようなものです。ほとんどすべてのフレーバーは、1 つのフレーバーで使用できる式の種類に制限を課します。たとえば、Perl や Python では、式は固定長である必要があります。(?<!St)は動作しますが(?<!Sgt|Rev)、動作し(?<!St|Sgt)ません。Java ははるかに寛大です。可能な最大長が事前に決定できる限り、可変長の後読み式を受け入れるため、(?<!St|Sgt)と同様に機能しますが(?<!\w{3,12})、機能し(?<!\w+)ません。

PHP と ActionScript の正規表現はどちらも PCRE ライブラリによって強化されています。これは、後読みに関して Perl や Python よりもわずかに緩いだけです。後読み式が代替の場合、各代替の長さは固定する必要がありますが、すべてが同じ長さである必要はありません。ただし、これは正規表現の最上位の「レベル」でのみ許可されます。つまり、後読みは別のグループ化構造を含むことも、1 つに含めることもできません。

これが、これまでに提供されたすべてのソリューションを機能させない部分です。グループ化の制限を回避するために、 と のチェックを に結合し、.と!を選択肢に分配する必要がありました。?[.!?]\b\.

/([.!?])(?<!\bSt\.|\bSgt\.|\bRev\.|\bLtd\.|\bInc\.|\bLt\.|\bJr\.|\bSr\.|\bEsq\.|\bInst\.|\bHon\.|\bGen\.|\bCpl\.|\bComdr\.|\bCol\.|\bCorp\.|\bMr\.|\bDr\.|\bGov\.|\bMrs\.|\bMs\.|\b[A-Z]\.|\bAssn\.|\bCapt\.)(?:\s*$|\s+(?:[_$#]|[A-Z][^.]))/

これにより、プローブ数が2208まで増加しますが、これは最初の数よりも 1 桁優れています。それが数GBのテキストに対して十分に速いかどうかはわかりません。

編集:あなたのコメントでは、タイトルを長さでグループ化することを提案しましたが、うまくいきませんでした。しかし、さらに一歩進んで、これらのグループのそれぞれを独自の後読みに配置すると、(驚いたことに)うまくいくように見えます。フリースペース モードでの表示は次のとおりです。

/(?:
   \.
     (?<!\bComdr\.)
     (?<!(?=\b[A-Z])(?:Assn|C(?:apt|orp)|Inst)\.)
     (?<!(?=\b[A-Z])(?:C(?:ol|pl)|Esq|G(?:en|ov)|Hon|Inc|Ltd|Mrs|Rev|Sgt)\.)
     (?<!(?=\b[A-Z])(?:Dr|Jr|Lt|M[rs]|S[rt])\.)
     (?<!\b[A-Z]\.)
   |
   [!?]
 )
 (?:\s*$|\s+(?:[_$#]|[A-Z][^.]))
/x

実際の動作を確認するには、ideone.com の PHP デモをチェックしてください。

于 2010-10-19T08:56:35.343 に答える