エムスリーテックブログ

エムスリー(m3)のエンジニア・開発メンバーによる技術ブログです

AIだけで新アルゴリズムによる正規表現ライブラリを作ってみた

生成AI Ruby

こんにちは。今回は、GeminiとClaude 4という2つのAIアシスタントだけを使って、正規表現ライブラリを一から作成した体験をお話しします。

きっかけ：古い理論への興味

事の始まりは、1964年のBrzozowski微分理論への興味でした。60年前に提唱されたこの理論はオートマトンを使わずに直接正規表現を解釈するアプローチでしたが、現実としてはオートマトンを利用した実装が行われています。

「現代のAIなら、この理論を実用的なライブラリとして実装できるのではないか？」

そんな思いから、実験的にAIアシスタントに以下のプロンプトを投げかけました：

新たな正規表現ライブラリを作りたい。協力して。

とりあえず、POCなので、Rubyあたりでお願い。

これを実現するアルゴリズムについて説明する。

あなたの役割と前提知識

私は、既存の正規表現マッチングアルゴリズムとは根本的に異なる、新しいアプローチ「FlowRegex法」を考案しました。あなたには、このアルゴリズムの概念を深く理解し、今後の議論やコード生成、説明に役立つように知識を共有してほしいです。

あなたは以下の概念について十分な知識を持っていることを前提とします。

正則言語と正規表現: その定義と表現力。 有限オートマトン (FA): DFA（決定性有限オートマトン）とNFA（非決定性有限オートマトン）の動作原理、状態遷移、受理。 ThompsonのNFAシミュレーション: 状態の集合を追跡し、バックトラックをしない線形時間でのマッチング。 バックトラック方式のNFA: Perl/PCRE/Python re などで使われる、再帰的なバックトラックによるマッチングと、そのReDoS (Regular Expression Denial of Service) 脆弱性。 コンパイラ理論の基礎: 字句解析、構文解析、最適化の一般的な概念。 ビット演算: 論理AND/OR/NOT、シフト演算など。 GPUコンピューティングの基礎: 並列処理の概念、SIMD/SIMTアーキテクチャ、ホストとデバイスの役割分担。

FlowRegex法の核心概念

私の「FlowRegex法」は、以下の点を核心とする正規表現マッチングアルゴリズムです。

「文字列全体におけるマッチ可能な終端位置の集合」を管理する 従来のオートマトンが「現在の文字列位置において、どの状態にいるか」という状態の集合を管理するのに対し、「FlowRegex法」は「入力文字列のどのインデックス（位置）で、現在の正規表現の部分パターンがマッチを終えられたか」というインデックスの集合を管理します。 このインデックスの集合は、ビットマスクで表現します。例えば、長さ1000の文字列の場合、1000ビットの整数（またはバイト配列）で表現され、あるインデックス i でマッチが終了する可能性があるなら、ビットマスクの i 番目のビットが 1 になります。

正規表現の各要素を「文字列終端位置の集合を食って、新しい文字列終端位置の集合を吐き出す関数」として定義する

   正規表現の各構成要素（リテラル、連接、選択、クリーネ閉包など）は、抽象的に「あるビットマスクを受け取り、新しいビットマスクを生成して返す関数」として定義されます。

   概念的な例:
       Literal('a') の関数: 入力ビットマスクでビットが立っている各位置 i について、文字列 S の i+1 番目の文字が 'a' なら、出力ビットマスクの i+1 番目のビットを立てる。
       Concat(R1, R2) の関数: まず R1 の関数にビットマスクを入力し、その出力をそのまま R2 の関数への入力とする。
       Alternation(R1, R2) の関数: R1 の関数の出力と R2 の関数の出力を取得し、それらのビットマスクをビット単位ORで結合する。
       KleeneStar(R) の関数: 入力ビットマスクに、R の関数を繰り返し適用します。この際、出力ビットマスクが**収束するまで（つまり、新しいビットが立たなくなるまで）**繰り返し、最終的な収束結果を返します。

バックトラックをしない 複数のマッチングパスが同時に進行し、結果のビットマスクに集約されるため、従来のバックトラック方式のような再帰的な探索や、選択肢を試しては戻る、という動作は発生しません。 これにより、ReDoS脆弱性を根本的に回避し、処理時間を文字列長に対して多項式時間（多くの場合線形時間）に保証できます。

驚異的な開発速度：正味数時間で完成

結果から言うと、正味数時間でフル機能の正規表現ライブラリが完成しました。これは従来の開発手法では考えられない速度です。

FlowRegexとして公開したライブラリは、想像以上に高機能なものとなりました。

AIアシスタントによる開発プロセス

役割分担の自然な発生

開発過程では、2つのAIアシスタントが自然に役割分担を行いました：

Gemini

  • 初期のアルゴリズム設計と理論的背景の整理
  • アーキテクチャの検討と設計方針の決定
  • 学術的な文献調査と理論的位置づけ

Claude 4

  • 実際のコード実装（15個のクラス、2000行超）
  • 包括的なテストケースの作成（10個のテストファイル）
  • 詳細なドキュメント整備
  • バグ修正とリファクタリング

AIによるコード生成の質

生成されたコードの品質も一定以上です：

  • 設計パターンの適用: Strategy パターン、Template Method パターンなどが自然に適用
  • エラーハンドリング: 適切な例外処理とエラーメッセージ
  • テスト駆動開発: 機能実装前にテストケースを先行作成
  • リファクタリング: 重複コードの除去と構造の最適化
# AIが生成したクラス階層の例
class RegexElement
  def apply(input_mask, text, debug: false)
    raise NotImplementedError
  end
end

class Literal < RegexElement
  # 具体的な実装...
end

class Concat < RegexElement
  # 関数合成の実装...
end

学術論文レベルの理論整備

単なるコード生成にとどまらず、AIは学術論文レベルの理論的背景も整備しました：

Abstract（概要）の自動生成

本研究では、Brzozowski (1964)の正規表現微分理論を現代的なビットマスク演算で実装した正規表現マッチングライブラリ「FlowRegex」を提案する。60年前に提唱された微分理論は、オートマトン構築を経由せずに直接的な正規表現マッチングを可能とし、積集合・補集合演算を自然にサポートする優れた理論的基盤を持つ。

先行研究との詳細比較

AIは自動的に以下の比較表を生成：

手法 得意分野 制約・弱点 適用場面
DFA 高速マッチング 状態爆発、メモリ消費大 単純パターン、高頻度処理
Thompson NFA 安定性、ReDoS耐性 やや低速 汎用的な正規表現処理
バックトラック 高機能（後方参照等） ReDoS脆弱性 複雑な正規表現、小規模データ
フロー正規表現法 並列処理、複数文字列 単純ケースで劣る 大規模並列処理、GPU活用

理論的基盤の文献調査

AIは関連する学術論文を自動的に調査し、適切な引用を生成：

  • Brzozowski (1964) の原論文*1
  • 山本 (2003) の正規表現関数による実装*2
  • Varatalu et al. (2025) の最新の微分ベース実装*3

完成したライブラリの機能

AIが実装した機能は予想以上に高度でした：

基本機能

  • 基本的な正規表現構文（リテラル、連接、選択、グループ化）
  • 量指定子（*, +, ?, {n,m}）
  • 文字クラス（\d, \s, \w, [a-z]など）

高度な機能

  • 先読み演算子（(?=...), (?!...)）による積集合・補集合演算
  • ファジーマッチング（編集距離対応）
  • 2段階マッチングによる部分文字列抽出
  • ReDoS攻撃への完全耐性

特に、ReDoS攻撃パターンに対して29,000倍以上の性能向上を達成したのは驚きでした。

AIアシストの革新的側面

1. 理論の現代的解釈

60年前の理論を現代的に再解釈する能力：

  • 古典的なBrzozowski微分理論
  • 現代的なビットマスク演算での実装
  • GPU並列処理への拡張可能性

2. 包括的なテスト設計

AIは自動的に以下のテストを生成：

  • 基本機能テスト（49テストケース）
  • ReDoS攻撃耐性テスト
  • ファジーマッチングテスト
  • 先読み演算子テスト
  • Unicode対応テスト

3. ドキュメント作成の自動化

  • README.md（学術論文形式）
  • API仕様書
  • 使用例とサンプルコード
  • 理論的背景の詳細解説

4. 段階的な機能拡張

AIは段階的にライブラリを拡張：

  1. 基本的な正規表現機能
  2. 量指定子の追加
  3. 文字クラスの実装
  4. 先読み演算子の追加
  5. ファジーマッチングの実装
  6. 2段階マッチングの追加

各段階で適切なテストとドキュメントも同時に生成されました。

開発体験から見えたAIの可能性

驚いたこと

  1. 理論理解の深さ: 複雑な数学的概念を正確に理解し実装
  2. コード品質: 人間が書くレベルの構造化されたコード
  3. テスト網羅性: エッジケースまで考慮した包括的テスト
  4. 文書作成能力: 学術論文レベルの技術文書

課題として見えたこと

  1. 最適化の限界: アルゴリズムレベルの最適化は人間の指示が必要
  2. 創造性の境界: 既存理論の組み合わせは得意だが、完全に新しい発想は困難
  3. 文脈の継続: 長期間の開発では文脈の維持に工夫が必要

将来への示唆

この実験から見えた、AIアシスタントを活用した開発の可能性：

研究開発の加速

  • 理論から実装まで数時間で完結
  • 複数の実装案の並行検討が可能
  • 文献調査と理論整理の自動化

教育への応用

  • 複雑なアルゴリズムの実装例として活用
  • 理論と実装の橋渡し
  • 段階的学習のためのサンプル提供

産業応用の可能性

  • プロトタイプ開発の超高速化
  • 理論研究の実用化促進
  • 新技術の検証コスト削減

まとめ

AIアシスタントとの協働により、以下を数時間で実現できました：

  • 理論的に新しい正規表現ライブラリの完全実装
  • 学術論文レベルの理論的背景の整備
  • 包括的なテストスイートの作成
  • 詳細なドキュメントの作成

これは従来の開発手法では数週間から数ヶ月を要する作業量です。

AIアシスタントは単なるコード生成ツールではなく、理論的思考のパートナーとして機能することが実証されました。特に、古い理論を現代的に再解釈し、実用的なライブラリとして実装する過程は、人間とAIの協働の新しい可能性を示していると思います。

今後、このような協働スタイルが研究開発の標準となり、理論から実装までの時間を劇的に短縮できる時代が来るのかもしれません。

We are hiring!

エムスリーやそのグループ会社では常に素敵なエンジニアを募集しております！ 興味あればぜひお越しください！

jobs.m3.com

*1:https://dl.acm.org/doi/10.1145/321239.321249

*2:https://cir.nii.ac.jp/crid/1050564287837265792

*3:https://www.microsoft.com/en-us/research/wp-content/uploads/2025/01/popl25-p2-final.pdf