74921


Onigmo Boost.Regexなど\Kに対応するテキストエディタの正規表現です。

何万もの置換が連続する場合は処理時間もかなりになります。

たとえば以下の事例です。  
意味は鈴木を佐藤に変えるが、花と楓が前の文章に入っている行の場合は変更しない

\Kを使った場合

検索  
(^[^花楓]*)\K鈴木

置換  
佐藤

\Kを使わない場合

^([^花楓]*)鈴木

置換  
\1佐藤  
もしくは  
$1佐藤

前者は結果的にマッチする部分と置換される変換結果は同じですが、\Kを使うと、もともと対象文字部分しかヒットしないで\1をつける必要がないというシンプルさです。

後者は行のマッチ部分から鈴木までマッチして一度キャプチャーしてから置換で付け加えるという仕組みです。

置換する結果は同じと思います。もし違ったら指摘ください。

正規表現エンジンによってどちらか一方しか動かない場合があるので、どちらも動くと仮定した場合です。  
処理速度が軽い方はどちらでしょうか？


CC BY-SA 4.0
2021-03-26T09:14:10.897
74903
2021-03-26T14:28:31.200
2021-03-26T13:49:19.960
43999
43999
question
正規表現 emeditor
EmEditorで同じ目的を達成する正規表現の置換でも書き方によって処理速度の負荷は異なりますか？


はい、同じ目的を達成する正規表現でも、書き方によって処理速度は異なります。

このことについて詳細に解説するには、コンピューターがどのように正規表現の処理をしているのかについて知っていただく必要があります。ですが正規表現の処理の仕方はオートマトン型や
VM 型などいくつかあり、その実装もいくぶんか複雑ですので、短い回答で説明するのが難しいです。

そこでこの回答では、ふんわりとしたイメージのもとで解説することを目指し、詳細は書籍などにゆだねることとします。

## たとえばバックトラックで処理速度が変わる

例として、数字の列に対してマッチする正規表現について考えてみます。

`[0-9]*` という正規表現は数字の列にマッチします。たとえば `12345`
という文字列にマッチします。このとき、あくまでイメージですが、おおよそ次のような流れでマッチしていきます：先頭の 1 文字を見ると `1` であり、
`[0-9]` にマッチします。次の 1 文字も `[0-9]` です。このまま繰り返すと最後の文字まで `[0-9]` です。したがって `12345`
は `[0-9]*` にマッチします。

さて、別の正規表現として `(0*|1*|2*|3*|4*|5*|6*|7*|8*|9*)*`
というのも数字の列にマッチします（本当にそうなるか考えてみてください）。たとえば先ほどと同じように `12345`
という文字列にどんな風にマッチするかというと、次のような感じです：先頭の 1 文字を見ると `1` です。これは `0` ではなく、したがって `0*`
にマッチしません。`1` ではあるので `1*` にマッチするかもしれません。次の 1 文字を見ると `2` なので `1` ではありません。よって先頭の
1 文字に戻ります。先頭から 1 文字目までが `1*` にマッチすると分かりました。次の 1 文字を見ると `2` なので `2*`
にマッチしそうです。次の 1 文字を見ると `3` なので元の文字に戻ります。1 文字目から 2 文字目までが `2*`
にマッチすると分かりました。次の文字に進みます。`3` なので `3*` にマッチしそうです……（省略）……さて、5 文字目から末尾までが `5*`
にマッチすると分かりました。これで最後の文字です。したがって全体である `12345` が
`(0*|1*|2*|3*|4*|5*|6*|7*|8*|9*)*` にマッチすると分かりました。

随分と長くなってしまいました。別の正規表現の方では、何回か「マッチしないので戻る」という処理が発生しています。これをバックトラックといいます。同じ文字列たちにマッチする正規表現でも、バックトラックの回数が異なるものが存在します。そして場合によってはこのバックトラックの回数が処理速度に影響を与えます。（ただし、あくまで処理系が内部でどのように正規表現を処理しているのかに依存する、という注意書きはしておきます。）

このように、同じ文字列に対してマッチする正規表現でも書き方によって処理速度が異なる可能性があります。場合によっては大きく処理速度が変わります。処理が遅くなる要因はいくつかありますが、とりあえずはバックトラックに気を遣うと大抵は足りるはず……です。

## `\K` も使い方によっては処理速度に影響する

質問文に例として挙げられたものは、より高度な話が必要です。`\K` というのは Perl の正規表現で導入された記法で、[Perl
のドキュメント](http://perldoc.jp/docs/perl/5.26.1/perlre.pod)には以下のように書かれています：

> いくつかの理由から、`\K` は等価な `(?<=...)` 構成子より非常に効率的で、文字列の中で何かに続いている何かを効率的に
> 取り除きたいようなシチュエーションで効果的に役立ちます。

しかし今回おこないたい処理はドキュメントで触れられているようなシチュエーションではありませんし、そもそも正規表現処理系が Perl
ではないため処理の方法が異なり効率が変わっている可能性があります。

自分は EmEditor
における正規表現実装について知識が足りず、今回の例がどのくらい速度に差が出るのか明確な答えを出せません。手元に処理系があるのでしたらダミーのテキストを用意して処理速度のテストをすることはできると思いますので、そういった実験をしてみることである程度把握することは可能です。

## リンク

より詳しく知りたい場合のリンクをいくつか置いておきます。

  * 書き方による正規表現処理の重さは、時にセキュリティ的な問題を生むことがあり、そのひとつが ReDoS です。ReDoS の原理は今回の回答と類似している部分があるので、参考になることと思います。 
    * [その正規表現の書き方で大丈夫？ ReDoS 攻撃の怖さと対策方法](https://yamory.io/blog/about-redos-attack/) \-- yamory.io
    * [正規表現の落とし穴（ReDoS - Regular Expressions DoS）](https://qiita.com/prograti/items/9b54cf82a08302a5d2c7) \-- Qiita
  * 正規表現の処理の実装方法について詳しく知りたい場合は『正規表現技術入門』（新屋、鈴木、高田）が詳しいです <https://www.amazon.co.jp/dp/B07JHRL2NS>


CC BY-SA 4.0
2021-03-26T14:28:31.200
74921
2021-03-26T14:28:31.200
19110
74903
answer