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

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

主に PHP を使って単純マッチング原理の理解を書きます。

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

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

文字列 'tonight' に一致する既存の式は次のとおりです

    '/to(nite|knite|night)/'

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

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

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

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

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

盗まれた画像:

式 ('/".*"!/') から開始して、最初に二重引用符 A を見つけ、次にドットが任意の文字に一致するため、 (デフォルトには改行が含まれていないため、ここで考慮する必要はありません)、さらにメタ文字 * は、標準数量子の一致優先メカニズムにより、突然末尾に来ることを意味します。文字列 B は、* の間には 0、1、またはそれ以上の値を指定できるため、これらの形式はすべて正常に一致する可能性が高く、エンジンはこれら 2 つの状態を記憶します。つまり、1 つで一致する場合と一致しない場合があります。 * メタキャラクターが通過する限り、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 style="color: #008000;">//</span><span style="color: #008000;"> 否定型环视</span>

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

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

 　　上一篇写到了“交还”，在回溯过程中就伴随着交还，如上面的'/".*"!/'，因发现双引号后面不是感叹号，而不得不回溯，此时选择另一种备用状态---不匹配刚才匹配到的字符，进行回退，是一个明显的交还。例子：

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

　　使用捕获型括号，分组，引擎记住两个括号中匹配的文本。结果如下：

　　　　

　　从上到下依次为$match_1、$match_2、$match_3，由于\w与\d有公共部分，而且两个量词都是匹配优先，从结果来看，前一个+量词匹配得最多（键值为1的项），pattern_1中，\d?没有匹配，pattern_2中，\d+只匹配了一个，pattern_3中，\d*没有匹配，而它们讷的过程都类似于，先让\w+匹配到末尾，然后引擎看剩余的模式，\d?可有可无，那就无，因为无正则匹配也是成功，不交还。\d+必须匹配一个，否则将导致匹配失败，这里它会交还一个，因为它必须服从使得全局匹配的成功。对于\d*也是如此，可以不匹配，不交还。

　　假如这里的pattern是'/(\w+)(\d\d)/'，那么它就必须交还两个数字，如果没有交还或是带匹配字符串中没有，就只能报告失败。所以有两个规律：

　　1. 先来先服务原则，匹配优先的量词在前，先尽量满足自己；

　　2. 必须服从全局匹配结果，有造成失败的可能，引擎会强迫匹配优先量词交还，否则整个匹配失败。

　　如果不交还呢？就会提前报告失败。必须谈到占有优先量词和固化分组，以+为例形式是 \w++、 (?>\w+)

    <span style="color: #800080;">$pattern</span> = '/\w+:/'<span style="color: #000000;">;    </span><span style="color: #800080;">$subject</span> = 'abcdefghijk';

　　如例，我们人当然能一眼看出来，字符串结尾没有冒号肯定失败，但是程序不会这样，它会一轮又一轮的匹配-回溯，因为它记住了一些可选择性的状态，但现在我们已经明确知道了这些状态是没用的，回溯也是白费力气，回溯前就已经失败了。所以可以 \w++: 或者 (?>\w+): ，有了占有优先或者固化分组，这些可选择性的状态都会被抛弃，\w+一直匹配到字符串结尾，单词没了，然后检测冒号存不存在，冒号不存在，但是现在有没有可供回溯的状态，立即报告失败，如果是几十万行的文本会节省很多时间。

　　需要注意的是，固话分组或是占有优先对嵌套在里面的量词也是有作用的，这点跟?:只分组不捕获不同

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

 　　最后记录下选择分支的一个坑，例

    <span style="color: #800080;">$pattern</span> = '/cat/'<span style="color: #000000;">;    </span><span style="color: #800080;">$subject</span> = 'indicate big cat';

　　cat当然会匹配indicate中间的cat，因为它在前面。再看这个

    <span style="color: #800080;">$pattern</span> = 'fat|cat|belly|your'<span style="color: #000000;">;    </span><span style="color: #800080;">$subject</span> = 'The dragging belly indicates that your cat is too fat';

　　NFA以表达式为主导，从表达式的角度看字符串，因此先检测到的是fat，结果是fat吗？结果仍是cat！所以NFA的引擎始终优先匹配选择分支选择最左端的匹配结果，哪怕它位于选择分支的后边。

　　这也说明，NFA引擎的正则，只要表达式中还存在可能的多选分支，正则引擎会回溯到存在尚未尝试的多选分支的地方，这个过程不断重复，直到完成全局匹配，如果不是这样，上例中fat先匹配成功就已经作为结果返回了。多选状态不是匹配优先，也不是忽略优先，但是尝试是从左到右。而对于DFA和某些POSIX NFA，匹配的不是最靠字符串左端的文本，而是选择分支中最长的分支。

　　正则的细节太多，扯不清楚，还是得看书理解，尤其是对于正则的调校，以及某些常用的判断技巧，比如匹配" "包围的字符串，中间可以有\"和其他转义序列，还是很麻烦的，推荐《精通正则表达式》，中文翻译挺棒，读起来也不生硬，而且还有很多技巧性的东西，比如“消除循环”是一大利器。end

 

1楼stma

学习了~