カーソルのAIエージェント向け高速正規表現検索アプローチ

エージェントワークフローにおける正規表現パフォーマンスへの対応

Cursorは、大規模なコードベースで従来のripgrepのような正規表現ツールがワークフローを停滞させるボトルネックに対処するため、AIコーディングエージェント向けにインデックス付き正規表現検索を開発しています。この問題は、rgの呼び出しが頻繁に15秒を超え、AIエージェントのインタラクティブなガイダンスを妨げるエンタープライズのモノレポで特に深刻です。

現在のツールの根本的な問題

Cursorを含むほとんどのAIエージェントハーネスは、正規表現検索にripgrepを使用するのがデフォルトです。ripgrepは、ファイル無視の適切なデフォルト設定により従来のgrepよりも優れたパフォーマンスを提供しますが、1つの根本的な制限があります：すべてのファイルの内容をスキャンしなければならないことです。これは、開発者がAIエージェントとリアルタイムで対話する必要がある大規模なコードベースでは問題となります。

古典的な研究に基づくインデックス手法

このインデックス手法は、1993年にZobel、Moffat、Sacks-Davisが発表した「Searching Large Lexicons for Partially Specified Terms using Compressed Inverted Files」の研究に基づいています。この方法では、n-gram（n文字の文字列セグメント）を使用して転置インデックスを作成し、正規表現をインデックスで検索可能なn-gramのツリーに分解するヒューリスティックを適用します。

転置インデックスの仕組み

転置インデックスは、検索エンジンの背後にある基本的なデータ構造です。文書はトークン化（この場合、個々の単語をトークンとして）を通じてトークンに分割されます。これらのトークンは辞書のような構造のキーとなり、値は各トークンを含むすべての文書を識別するポスティングリストです。複数のトークンを検索する場合、システムはそれらのポスティングリストを読み込み、指定されたすべての用語を含む文書を見つけるために交差させます。

このアプローチは、従来のIDEが「定義へ移動」などの操作のために構文インデックスを作成する方法に類似していますが、現代のAIエージェントがテキストを検索する際に実行する正規表現検索操作に特化しています。