定期的な学習 (2) --- 単純なマッチング原理、--- Matching_PHP チュートリアル

定期学習(2) ---単純マッチング原理、---マッチング

主にPHPを用いて、単純マッチング原理の理解を書き留めます。

まず、通常のエンジンは主に DFA と NFA の 2 つのカテゴリに分類できます。とにかく、単純に理解すると、配列内のデータを検索する場合と同じように、いくつかのエンジンが開始されます。先頭から順に検索する場合もあれば、途中から検索を開始する場合もあり、異なる方法を使用します。比較的に、NFA の歴史は長く、NFA を使用するツールや言語も多くありますが、2 つのエンジンが混在して使用されることもあります。ある本で挙げられた例は非常に適切です。NFA はガソリン エンジンのようなもので、DFA は電気モーターのようなものです。どちらも車を動かすことができますが、使用するメカニズムが異なります。 NFA と DFA はどちらも長年にわたって開発されてきたため、POSIX と呼ばれる標準が導入されました。この標準では、通常のエンジンがサポートする必要があるメタキャラクターと機能、およびエンド ユーザーが得たい正確な結果が規定されています。

NFA は (正規) 表現に基づいて一致しますが、DFA は一致する文字列に基づいて一致します。 PHP は従来の NFA エンジンを使用しており、もちろん Perl も使用します。どのエンジンであっても、次の 2 つの一般原則があります: 1. 左端の結果が最初に照合されます。 2. 標準の量指定子 (+、?、*、{m,n}) が最初に照合されます。

文字列「tonight」に一致させるための既存の式は次のとおりです

NFA: 式主導、式の最初の部分から開始し、現在のテキストが一致するかどうかを確認し、一致する場合は、すべての式が一致し、全体が一致するまで式の次の部分に進みます。成功。式の最初の文字は t です。t 文字が見つからない場合は、文字列内を左から右に繰り返し検索します。見つかった場合、式の次の文字は o になります。一致する文字列の検索を続けます。最初の 2 つは一致する可能性があります。括弧でグループ化された選択ブランチを入力し、nite、nite、または night に一致し、これら 3 つの可能性を順番に試します。最初のブランチは nig を試行すると失敗し、2 番目のブランチは式の最初の n を試行すると失敗し、3 番目のブランチはたまたま完全に一致します。正規表現が主流のエンジンの場合、最終的な結論を導き出す前に正規表現をチェックする必要があります。

DFA: NFA とは異なり、文字列をスキャンする場合、DFA は現在有効な一致の可能性をすべて最初から記録し、存在する場合はその文字までをスキャンします。文字列内の n の場合、nite と night の 2 つの可能性が記録され (一致する文字列の観点から式が調べられます)、i または nite と night までスキャンを続けてから、g に進みます。残っている唯一の可能性は次のとおりです。 h と t が一致すると、エンジンはスキャン文字列がスキャンされたことを検出し、成功を報告します (少し深さと幅があるようです)。

つまり、一般に、テキスト主導の DFA エンジンの方が高速で、式主導の NFA は、パターンの最後に到達する前に、前のマッチングであっても、すべてのパターンを検出する必要があります。式が一致する 成功した場合は、後で再度テストすることが必要になる場合があり、これにより多くの時間が無駄になる可能性があります。 DFA は文字列によって支配されており、最大でも複数の可能性を 1 か所に記録でき、ターゲット テキスト内の文字は最大でも 1 回しか検出されません。

ただし、複数選択の分岐の順序は、異なるターゲット文字列にも大きな影響を与えます。たまたま一致する分岐が先頭にあれば、当然、より速く見つけることができます。

NFA は表現が主であるため、さまざまな表現を書くことは大きな影響を及ぼします。また、より柔軟に制御することができ、より可変性が高くなります。その中で、NFA (元々は主に PHP に基づいていた) には重要な機能があります: バックトラッキング---成功する可能性のある 2 つの一致から選択する必要がある場合、最初に 1 つを選択し、もう 1 つは後で必要になる可能性があることを覚えておいてください。この状況は主に、標準の数量指定子と複数選択分岐 (|) で発生します。

盗まれた写真:

式 ('/".*"!/') から始めて、最初に二重引用符 A を見つけます。次に、ピリオドは任意の文字と一致するため (デフォルトでは改行が含まれていないため、ここで考慮する必要はありません) 、メタ文字 * を加えたものは、複数の一致が可能であることを示します。標準量指定子の一致優先メカニズムにより、* は 0、1、またはそれ以上になる可能性があるため、突然文字列 B の最後に来ます。したがって、エンジンはこれら 2 つの状態を記憶します。つまり、* メタ文字が通過する場所である限り、一致する可能性もあれば、一致しない可能性もあります。 Mから最後まで収録されます。

　　等到结尾发现没有"，于是回溯，需要说明，引擎总是回溯到最近记录的状态（类似栈），一个个往前回溯，直到遇到一个双引号的地方（C），然后匹配匹配到双引号后面（D），发现不是感叹号!，失败，再次回溯（状态记录不为空），到E处又找到了一个双引号，与刚才情况相同，继续匹配（F）发现没有感叹号，失败，继续回溯到G，同样由于后边（H）不是感叹号，仍需要回溯，到I，这时记录的状态已经没有了，也无法继续回溯了，第一轮匹配失败告终，但还没完，引擎的传动装置继续从A处双引号的下一个位置开始继续寻找第一个符合条件的双引号，到J，然后类似上一轮的过程继续上演。最终也没找到 "..."! 这样的字符串，过程却很曲折。

　　从上面的例子可以看出：一是 .*  这种形式的效率非常低，尤其在失败的时候（当然平常我们那几行代码几乎忽略不计），而且很容易出错，比如用 /".*/" 匹配一对双引号包围的字符串来匹配 ab"cde"fgh""ijk"lmn，最终的结果是"cde"fgh""ijk"，最开始的双引号和最末尾的双引号中间的全部内容；二是如果有类似 ((...)*)*、((...)+)*之类的，外面里面同时记录不定状态的，回溯次数呈指数级上升，甚至形成死循环，更加耗时。当然对于改进状态的引擎提前检测这种状况，并报告错误，如同浏览器在自己跳转自己的页面那样报错。

 　　因此在用到量词时，比如+，它可以匹配一个到多个，大于一个时，不是必须的，有两种选择状态，可以有也可以没有，这两种状态就是日后可能会在回溯中用到的状态，称为备用状态，?也是如此。

　　对于匹配双引号及之间的字符，中间不包括转义后的双引号的情况，我们可以使用忽略优先，'/".*?"/' ，忽略优先按量词的最小限度匹配， *最小是没有，相当于先检测空串，没有先匹配一个字符马上检测双引号，这在一定只要检测到右边有一个双引号匹配即成功结束，它匹配上图中的 "McDonald's"也省去了很多回溯。

　　当然，对于这种需要检测两个字符间的其他字符，还有一种办法，如 '/"[^"]"/'，排除型字符组，它也达到了相同的需求，但情况不总是这样。

　　比如，匹配与之间的字符，使用 '/[^<\/b>]*<\/b>/' ？注意字符组一次只能匹配一个字符，这里是匹配在和之间的，非<、/、b、>的任意一个字符，字符组不能把里边的字符当一个整体，对于整体、多个字符的检测，可以选择环视。环视与位置相关，生来就是限定周围的字符，一个或多个均可。这里需要否定型环视，因为我们需要的不能是的字符，为了好看中间隔开。

    '/<b>(   (?!<\/b>) . )*<\/b>/'   <span>//</span><span> 否定型环视</span>

　　但是上面仍能匹配"abcdef"，所以还要在其之间排除，中间环视检测，/可以有或没有都行

    '/<b> ( (?! <\/? b >) . )* <\/b>/'

    <span>$pattern_1</span> = '/(\w+)(\d?)/'<span>;
    </span><span>$pattern_2</span> = '/(\w+)(\d+)/'<span>;
    </span><span>$pattern_3</span> = '/(\w+)(\d*)/'<span>;
    </span><span>$subject</span> = 'abc12345'<span>;
    </span><span>preg_match</span>(<span>$pattern_1</span>, <span>$subject</span>, <span>$match_1</span><span>);
    </span><span>preg_match</span>(<span>$pattern_2</span>, <span>$subject</span>, <span>$match_2</span><span>);
    </span><span>preg_match</span>(<span>$pattern_3</span>, <span>$subject</span>, <span>$match_3</span><span>);
    </span><span>echo</span> 'match=><pre class="brush:php;toolbar:false">'<span>;
    </span><span>var_dump</span>(<span>$match_1</span>, <span>$match_2</span>, <span>$match_3</span>);

    <span>$pattern</span> = '/\w+:/'<span>;
    </span><span>$subject</span> = 'abcdefghijk';

<span>    (</span>?>   (\d+)+  )    <span>//</span><span> 里面的\d+的状态也会被抛弃</span>
    (?: abc (\d\d) )   <span>//</span><span> 外层的括号不会被捕获，但里面的括号不受影响，\1仍记录着数字字符</span>

    <span>$pattern</span> = '/cat/'<span>;
    </span><span>$subject</span> = 'indicate big cat';

    <span>$pattern</span> = 'fat|cat|belly|your'<span>;
    </span><span>$subject</span> = 'The dragging belly indicates that your cat is too fat';