正規表現の逆方向検索

時間がぽっかり空いたのでネットを巡回していました。

そしたら拙作SkRegExpへダメ出ししているブログが!

読んでみると、SkRegExpは「逆方向検索に対応していないからダメだ」と書かれていました。

確かに、SkRegExpは逆方向検索に対応していません。対応しようと考えたこともありません。

なぜなら、正規表現の逆方向検索ってどうすればいいのかわからないからです。

正規表現パターンを後ろから評価して検索すればいいんでしょうか?

ただし、これでは順方向で検索したときと結果が変わります。

たとえば、a*b と言う正規表現で aaabc と言う文字列を検索した場合。

順方向ではaaab がマッチします。

では逆方向から検索すると?

a*b を後ろから評価すると b*a です。

この場合、マッチするのは ab です。

順方向と逆方向でマッチ結果が異なります。

これでいいのでしょうか?

たぶん、違うでしょう。順方向でも逆方向でも同じ結果が欲しいはずです。

となると、考えられる方法は一つ。

文字列の末尾から一文字ずつ正規表現を適用していき、もっとも長くマッチした文字列でマッチ成功とすることです。

正規表現パターン a*b を文字列 aaabc に逆方向からマッチさせてみます。

  1. 5文字目 c の位置ではマッチしない
  2. 4文字目 b の位置では b にマッチする。
    ただし、最長マッチではないかもしれない。マッチした情報を保存し、3文字目からマッチを再試行。
  3. 3文字目 a の位置では ab にマッチする。
    ただし、最長マッチではないかもしれない。マッチした情報を保存し、2文字目からマッチを再試行。
  4. 2文字目 a の位置では aab にマッチする。
    ただし、最長マッチではないかもしれない。マッチした情報を保存し、1文字目からマッチを再試行。
  5.  1文字目 a の位置では aaab にマッチする
    これ以上文字列がない。したがってこのマッチが最長マッチ。aaab をマッチ結果として返す。

このような短い文字列でも、重い処理である正規表現マッチを5回繰り返す必要があります。

こんなことをするくらいなら、順方向に全マッチさせた方がはるかに速いです。最適化された正規表現ならなおさらです。

というわけで、SkRegExp が逆方向検索をサポートすることはありませんのでご了承下さい。

SkRegExpの最新バージョンはコチラからダウンロードできます。

 

コメントを残す

メールアドレスが公開されることはありません。