正規表現でのバックトラック定義と使用分析 [JS および Java 実装]

この記事の例では、正規表現におけるバックトラッキングの定義と使用法を分析します。ご参考までに、詳細は以下の通りです:

これが私にとって「バックトラッキング」との初めての接触であり、それについてあまり知りません。ここで、今後の参考のために、精神的な美徳として私が理解していることを記録しておきます。

使用する正規表現のマッチング基準は大きく分けて、左端（一番先頭）のマッチング結果を優先するものと、標準のマッチング量指定子（*、+、?、{m, n}）が先にマッチングするものがあります。

「左端の一致を優先」は、その名前が示すように、文字列の先頭から一致の最後まで一致することです。これが「標準の一致量指定子」を「非決定的な有限オートマトン (これは「式主導」と呼ばれ、もう 1 つは「決定論的有限オートマトン (DFA)」で、「テキスト主導」とも呼ばれます。現在 JavaScript で使用されている正規表現は「式主導」です。式の優位性とテキストの優位性を説明するのは少し面倒ですが、最初に例を見てみるとわかりやすいかもしれません。

// 使用正则表达式匹配文本
var reg = /to(nite|knight|night)/;
var str = 'doing tonight';
reg.test(str);

上記の例では、最初の要素 [t] は、ターゲット文字列で 't' が見つかるまで繰り返し試行されます。その後、次の文字が [o] と一致するかどうかを確認し、一致する場合は次の要素 (nite|knight|night) を確認します。その本当の意味は「夜」、「騎士」、または「夜」です。エンジンはこれら 3 つの可能性を順番に試します。 [nite] を試すプロセスでは、最初に [n]、次に [i]、次に [t]、最後に [e] を試します。この試みが失敗した場合、エンジンは、一致が成功するか失敗が報告されるまで、別の可能性を試みます。式内の制御は異なる要素間で転送されるため、「式の優位性」という名前が付けられます。

上記の例と同様に、「text-led」は文字列をスキャンするときに現在有効な一致をすべて記録します。エンジンが t に移行すると、現在処理されている一致の可能性に潜在的な一致が追加されます:

次にスキャンされるすべての文字で、現在の一致の可能性のシーケンスが更新されます。 2 つの文字をスキャンし続けると、状況は次のようになります:

有効な一致候補は 2 つになります (ナイトは除外されます)。 g をスキャンすると、一致する可能性のあるものは 1 つだけ残ります。 h と t が一致すると、エンジンは一致が完了したことを検出し、成功を報告します。 「テキスト主導型」とは、スキャンする文字列内のすべての文字がエンジンを制御するためです。

「表現型リーダーシップ」がどのように機能するかを理解したい場合は、今日のトピック「バックトラッキング」をご覧ください。バックトラックは、道路の分岐点に遭遇したら、まず各交差点に印を付けます。行き止まりにぶつかった場合は、以前に作った、まだ試したことのない道を示す標識に遭遇するまで、来た道を戻ることができます。その道を歩けない場合は、戻って次のマークを見つけ、出口が見つかるまで、または未踏の道をすべて完了するまで、これを繰り返すことができます。

多くの場合、正規表現エンジンは 2 つ (またはそれ以上) のオプションから選択する必要があります。 /…x?…/ が発生した場合、エンジンは X と一致するかどうかを試行する必要があります。 /...の場合最初の X が一致すると、この要件が満たされ、次の X を試行するかどうかを決定する必要があります。続行する場合は、3 番目の X、4 番目の X などを一致させるかどうかも決定する必要があります。選択するたびに、ここに別の選択肢があることを思い出させるためのマークが実際に作成され、将来の使用のために予約されています。バックトラッキング プロセス中に考慮すべき重要な点が 2 つあります。最初にどのブランチを選択する必要がありますか?バックトラックするときに、以前に保存したどのブランチが使用されますか?

最初の質問は、次の重要な原則に従って選択されます:

「試行する」と「試行をパススルーする」のどちらかを選択する必要がある場合、一致する優先度数量詞について、エンジンは「試行する」を優先します。 "、優先数量子を無視する場合は、「パスバイ試行」が選択されます。

2 番目の質問は、次の原則に基づいています:

最も最近保存されたオプションは、ローカル障害によりバックトラックが強制された場合に返されるものです。使用される原則は LIFO (後入れ先出し) です。

まず、道路をマーキングする例をいくつか見てみましょう:

1. バックトラックなしで照合する

「abc」と照合するには [ab?c] を使用します。 【a】マッチング後の現在のマッチング状況は以下の通りです

现在轮到[b?]了，正则引擎需要决定：是需要尝试[b]呢，还是跳过？因为[？]是匹配优先的，它会尝试匹配。但是，为了确保在这个尝试最终失败之后能够恢复，引擎会把：

添加到备用状态序列中。也就是说，稍后引擎可能从下面的位置继续匹配：从正则表达式中的[b?]之后，字符串的c之前（也就是说当前的位置）匹配。这实际上就是跳过[b]的匹配，而问题容许这样做。引擎做好标记后，就会继续向前检查[b]。在示例中，它能够匹配，所以新的当前状态变为：

最终的[c]也能成功匹配，所以整个匹配完成。备用状态不再需要了，所以不再保存它们。

2、进行了回溯的匹配

下面要匹配的文本是“ac”，在尝试[b]之前，一切都与之前的过程相同。显然，这次[b]无法匹配。也就是说，对[……？]进行尝试的路走不通了。因为有一个备用状态，这个“局部匹配失败”产工会导致整体匹配失败。引擎会进行回溯，也就是说，把“当前状态”切换为最近保存的状态。

在[b]尝试之前保存的尚未尝试的选项。这时候，[c]可以匹配c，所以整个匹配宣告完成。

3、不成功的匹配

现在要匹配的文本是“abx”。在尝试[b]以前，因为存在问号，保存了这个备用状态：

[b]能够匹配，但这条路往下却走不通了，因为[c]无法匹配x。于是引擎会回溯到之前的状态，“交还”b给[c]来匹配。显然，这次测试也失败了。如果还有其他保存的状态，回溯会继续进行，但是此时不存在其他状态，在字符串中当前位置开始的整个匹配也就宣告失败。

例子1： 提取字符串 提取 da12bka3434bdca4343bdca234bm 提取包含在字符a和b之间的数字，但是这个a之前的字符不能是c,b后面的字符必须是d才能提取。

例如这里就只有3434这个数字满足要求。那么我们怎么提取呢？

首先我们写出提取这个字符串的表达式： (?

Java代码片段如下：

Pattern p = Pattern.compile( "(?<!c)a(//d+)bd " );
Matcher m = p.matcher( "da12bka3434bdca4343bdca234bm" );
 while (m.find()){
 System.out.println(m.group( 1 )); //我们只要捕获组1的数字即可。结果 3434
 System.out.println(m.group(0)); // 0组是整个表达式，看这里，并没有提炼出(?<!c)的字符 。结果 a3434bd
}

例子2： 将一些多位的小数截短到三位小数：\d+\.\d\d[1-9]?\d+

在这种条件下 6.625 能进行匹配，这样做没有必要，因为它本身就是三位小数。最后一个“5”本来是给 [1-9] 匹配的，但是后面还有一个 \d+ 所以，[1-9] 由于是“?”可以不匹配所以只能放弃当前的匹配，将这个“5”送给 \d+ 去匹配，如果改为：

\d+\.\d\d[1-9]?+\d+

的侵占形式，在“5”匹配到 [1-9] 时，由于是侵占式的，所以不会进行回溯，后面的 \d+ 就匹配不到任东西了，所以导致 6.625 匹配失败。

这种情况，在替换时就有效了，比如把数字截短到小数点后三位，如果正好是三位小数的，就可以不用替换了，可以提高效率，侵占量词基本上就是用来提高匹配效率的。

把 \d+\.\d\d[1-9]?+\d+ 改为 \d+\.\d\d(?>[1-9]?)\d+ 这样是一样的。

希望本文所述对大家JavaScript程序设计有所帮助。

更多正規表現でのバックトラック定義と使用分析 [JS および Java 実装]相关文章请关注PHP中文网！