注目★★★★★Lobsters
Luhn検証を正規表現化、巨大regexは最大4823万文字
30秒で把握
- 1Luhnアルゴリズムを100状態・1000遷移のDFAで検証
- 2DFAから生成したregexは最大4823万文字・変換に約20分
- 3grepとripgrepはメモリ不足、Pythonのreは実行可能
要約
この記事は、Luhnアルゴリズムで検査桁を検証する有限オートマトンと正規表現を構成できると論じた。偶数・奇数長の部分和を10で管理するDFAは100状態・1000遷移で実装できる。DFAから正規表現へ変換すると組合せ爆発が起き、生成された正規表現は偶数長用が32,461,605文字、奇数長用が48,236,673文字になった。変換には各約20分かかり、grepとripgrepはメモリ不足で終了した一方、Pythonのreは実行できた。形式上は同等でも、この問題ではDFAが正規表現より大幅にコンパクトになる。
あなたへの影響
データ検証やPIIスキャンを担当する日本のエンジニアは、巨大なregexの導入を避け、まずDFAや通常のコードによる検証を評価すべきです。
推奨：Luhn検証はカードの実在性や決済可否を確認する処理ではありません。