正規表現とReDoS
一致結果だけでなく、不一致時の計算量と受け付ける入力長を設計に含めます。
説明
正規表現は同じ文字列を複数の分け方で照合する場合があります。繰返しを入れ子にすると、不一致を確定するまでに多くの候補を試し、短い入力でも処理が増えることがあります。
Python reの(a+)+とa+を比較します。末尾に一文字だけ不一致を置き、実測した5回の中央値を資料として読みます。式の単純化と入力長の上限を適用し、受理する文字列が変わらないかも調べます。
一致結果だけでなく、不一致時の計算量と受け付ける入力長を設計に含めます。
1一致する入力と末尾不一致を比較する
(a+)+は一つ以上のaの組を、さらに一つ以上繰り返します。
from sd10 import *
for text in ("aaaa","aaaa!"):
print(text,re.fullmatch文字列全体が式へ一致するか調べる(r"(a+)+",text) is not None)aaaaはTrue、末尾に!があるとFalseです。遅くなりやすいのは、長い一致部分の後で失敗するケースです。
2入れ子の繰返しをコンパイル結果で見る
re.DEBUGでPythonが解析した構造を表示します。
pattern = re.compile(r"(a+)+",re.DEBUGパターンの解析構造と命令を表示する)MAX_REPEATの内部に、さらにMAX_REPEATがあり、同じa列を複数に分割して試せる構造です。表示の命令や最適化はエンジン・版によって異なります。
3文字列の分割候補数を計算する
n個のaの間にはn-1か所の切れ目があります。各切れ目を使うかどうかで、空でない組への分割は2のn-1乗通りです。
for n in (4,12,16,20):
print(n,2**(n-1)空でない組への分割数を計算する)4文字は8通り、20文字は524288通りです。これは組合せ数の説明であり、Python内部で実行した命令数そのものを数えた値ではありません。
4固定入力の実測時間を比較する
同じ環境で各入力を5回測った中央値です。単位はナノ秒で、今回はaの後に!を付けています。
measured = timings()保存した実測資料を読む
print(measured["python"],measured["samples"])
for row in measured["rows"]入れ子と単純な式の中央値を比較する:
print(row)aを12、16、20個と増やすと、nestedの時間が急増しています。linearは単純なa+です。この値は採取時の実測資料で、別端末の所要時間を保証する値ではありません。
5単純な式へ変えて受理範囲を照合する
対象の仕様が一文字以上のaだけなら、繰返しの入れ子は不要です。
samples = ["","a","aaaa","aaaa!","!","aa\na"]
for value in samples:
print(repr(value),bool(re.fullmatch(r"(a+)+",value)),bool(re.fullmatch(r"a+",value)入れ子を除いた式の結果を比較する))この代表ケースでは両方の一致結果が揃います。一般の式の変更では同値性を確認し、計測値が短くなっただけで仕様維持を判断しません。
6入力長を照合の前に制限する
上限16文字の契約として、照合に入る前に長さを判定します。
def accept(value):
return len(value)<=16正規表現へ渡す前に上限を適用する and re.fullmatch(r"a+",value) is not None
for value in ("a"*16,"a"*17,"a"*15+"!"):
print(len(value),accept(value))16個のaはTrue、17文字は長さで拒否、末尾!は式で拒否します。式の改善と長さ制限を組み合わせています。
7必要が単純なら文字検査とも比較する
仕様がASCIIのaだけなら、正規表現を使わない検査も選べます。
def plain(value):
return 1<=len(value)<=16 and all(c=="a" for c in value)文字ごとの条件で同じ仕様を表す
print([(repr(v),accept(v)==plain(v)) for v in samples])代表ケースで結果が一致します。文字種が複雑な場合も、必要な仕様を先に定めてから実装方法を選びます。
まとめ
末尾不一致など、失敗時の入力も測ります。
式の修正後は受理する範囲を照合します。
処理の前段で入力長を制限します。
操作履歴と解説を振り返れます。
Python 3.15 / 固定の公開試料
from sd10 import *
for text in ("aaaa","aaaa!"):
print(text,re.fullmatch(r"(a+)+",text) is not None)aaaa True aaaa! False
pattern = re.compile(r"(a+)+",re.DEBUG)MAX_REPEAT 1 MAXREPEAT
SUBPATTERN 1 0 0
MAX_REPEAT 1 MAXREPEAT
LITERAL 97
0. INFO 4 0b0 1 MAXREPEAT (to 5)
5: REPEAT 14 1 MAXREPEAT (to 20)
9. MARK 0
11. REPEAT_ONE 6 1 MAXREPEAT (to 18)
15. LITERAL 0x61 ('a')
17. SUCCESS
18: MARK 1
20: MAX_UNTIL
21. SUCCESSfor n in (4,12,16,20):
print(n,2**(n-1))4 8 12 2048 16 32768 20 524288
measured = timings()
print(measured["python"],measured["samples"])
for row in measured["rows"]:
print(row)3.15.0 5
{'length': 13, 'a_count': 12, 'nested_median_ns': 81959, 'linear_median_ns': 250}
{'length': 17, 'a_count': 16, 'nested_median_ns': 1379375, 'linear_median_ns': 291}
{'length': 21, 'a_count': 20, 'nested_median_ns': 23451542, 'linear_median_ns': 375}samples = ["","a","aaaa","aaaa!","!","aa\na"]
for value in samples:
print(repr(value),bool(re.fullmatch(r"(a+)+",value)),bool(re.fullmatch(r"a+",value)))'' False False 'a' True True 'aaaa' True True 'aaaa!' False False '!' False False 'aa\na' False False
def accept(value):
return len(value)<=16 and re.fullmatch(r"a+",value) is not None
for value in ("a"*16,"a"*17,"a"*15+"!"):
print(len(value),accept(value))16 True 17 False 16 False
def plain(value):
return 1<=len(value)<=16 and all(c=="a" for c in value)
print([(repr(v),accept(v)==plain(v)) for v in samples])[("''", True), ("'a'", True), ("'aaaa'", True), ("'aaaa!'", True), ("'!'", True), ("'aa\\na'", True)]演習完了