時間は平らな円だ。grep の最初のバージョンが 1973 年にリリースされたとき、それはファイルシステム上のテキストファイルに対して正規表現マッチングを行うための基本的なユーティリティだった。その後、開発ツールが高度になるにつれて、より特化したツールに徐々に置き換えられていった。最初は ctags のような、おおまかに構文ベースと言えるインデックスによって。その後、多くの開発者が特定のプログラミング言語向けの専用 IDE に移行し、構文解析と構文インデックスの構築、さらにしばしば型レベルの情報も組み合わせることで、コードベースを非常に効率的にナビゲートできるようになった。最終的には、これが Language Server Protocol (LSP) として標準化され、新旧すべてのテキストエディタにこうしたインデックスをもたらした。そして LSP が標準になりつつあったまさにそのとき、エージェントによるコーディングが登場し、どうなったかというと、エージェントは grep を本当に 好んで 使うのだ。

エージェントのためにコンテキストを収集するための、ほかの最先端の手法もある。私たちはこれまでも、多くのタスクでセマンティックインデックスを使うことでエージェントのパフォーマンスをどれだけ向上できるかを紹介してきたが、モデルが正規表現検索を使わないと解決できないクエリもある。つまり、この分野はそれなりに進歩してきたとはいえ、1973 年に立ち戻る必要がある、ということだ。

ほとんどのエージェント用ハーネス (私たちのものも含めて) は、検索ツールを提供する際にデフォルトで ripgrep を使用している。これは Andrew Gallant によって開発されたスタンドアロンの実行ファイルで、古典的な grep の代替となるものだが、 (ファイルの無視ルールなど) より理にかなったデフォルト設定と、はるかに優れたパフォーマンスを備えている。Andrew は正規表現マッチング時の速度について非常に多くの時間をかけて考え抜いてきたため、ripgrep はその高速さで広く知られている。

ripgrep がファイルの内容に対してどれだけ高速にマッチできたとしても、1 つ深刻な制約がある。それは、すべて のファイルの内容に対してマッチさせる必要がある、という点だ。小さなプロジェクトで作業しているときは問題ないが、とりわけ大規模な企業の Cursor ユーザーの多くは、非常に巨大なモノレポで作業している。途方もなく巨大だ。私たちは日常的に 15 秒以上かかる rg の実行を目にしており、これはコードを書いているエージェントをユーザーがインタラクティブにガイドしているときのワークフローを本当に停滞させてしまう。

正規表現のマッチングは、いまやエージェント駆動の開発における重要な要素となっており、私たちはこれを明示的に最適化することが非常に重要だと考えている。ちょうど伝統的な IDE が Go To Definition のような操作のためにローカルで構文インデックスを作成するように、私たちはモダンなエージェントがテキストを検索するときに行う中核的な処理のためのインデックスを構築している。

#古典的なアルゴリズム

正規表現マッチを高速化するためにテキストデータをインデックス化するというアイデアは、まったく新しいものではありません。これは 1993 年に Zobel、Moffat、Sacks-Davis による "Searching Large Lexicons for Partially Specified Terms using Compressed Inverted Files" という論文で初めて発表されました。彼らは、n-gram（文字列を n 文字幅で分割した部分列）を使って転置インデックス（inverted index）を構築する手法と、正規表現をインデックスで検索可能な n-gram の木構造へと分解するためのヒューリスティクスを提示しました。

この概念を以前に聞いたことがあるとしたら、おそらくその論文からではなく、Google Code Search の終了直後の 2012 年に Russ Cox が公開した ブログ記事 からでしょう。ここでは、こうしたインデックスを構成する基本的なビルディングブロックを手短におさらいします。というのも、その後に開発されたほぼすべてのインデックス手法に共通して関わってくるからです。

#反転インデックス

反転インデックスは、検索エンジンを支える基本的なデータ構造です。インデックス対象のドキュメント集合を元に、各ドキュメントをトークンに分割することで反転インデックスを構築します。これはトークナイゼーションと呼ばれ、その方法にはさまざまなものがありますが、この例では最も単純なやり方として、各単語をトークンとして扱います。トークンは辞書のようなデータ構造のキーとなり、値としては、それぞれのトークンが出現するすべてのドキュメントのリストが入ります。このリストは一般的に posting list と呼ばれます。各ドキュメントは数値、つまり「posting」で一意に識別されるからです。1 つ以上のトークンで検索するときは、その posting list を読み込みます。posting list が複数ある場合には、それらの共通部分を取ることで、すべての posting list に 登場するドキュメントを見つけます。

この設計（その上に多くの複雑な仕組みを積み上げたもの）が、現在利用されているほとんどの検索エンジンの基盤になっています。ただし、これらは 自然言語 向けの検索エンジンであり、ここでやりたいのは正規表現による検索であり、しかもソースコード上でマッチさせることです。そのままではうまくいきません。

ここから何とか実用的なものを作ろうとするなら、トークナイゼーションについて徹底的に突き詰めて考える、という方法もあります。つまり、各プログラミング言語の構文を理解し、ソースコード中の識別子を分割する、といったことです。しかし、これを正しくやるのは非常に難しいです。GitHub の初期には、Code Search 機能がまさにその方式で動いていました。プログラミング言語向けの非常に複雑なトークナイザと、とても大きな ElasticSearch クラスタによるものです。しかし、結果は良くなく、この機能への評価も芳しくありませんでした。識別子を（それなりには）検索することはできましたが、正規表現でマッチさせることはできませんでした。そのためには、もっと良いトークナイゼーションの方法が必要です。

#トライグラム分解

ソースコードを単純にトークナイズしても、正規表現のマッチングにはあまり役立ちません。ドキュメントを、もっと基本的なチャンクに分割する必要があります。古典的なアルゴリズムではトライグラムを選びます。すなわち、トークンは入力文字列中の、互いに重なり合う3文字から成るすべての部分列です。

なぜ3文字なのでしょうか？これらのトライグラムを転置インデックスのキーとして保存するからです。もしバイグラム（2文字チャンク）を選ぶと、インデックス中のキーは最大でも 64k 個と少なくなりますが、各キーに対応するポスティングリストが巨大になってしまい、効率的に扱うには大きすぎます。逆にクアドグラム（4文字チャンク）にすると、ポスティングリストはとても小さくなり、それ自体は非常に良いことですが、転置インデックスのキーが数十億個になってしまい、やはり扱いが難しくなります。

そのため、トライグラムはちょうどよいバランスの中間点と言えます。これにより、ドキュメントをインデックスするときのトークナイズはとても単純になります。インデックス対象のドキュメントから、互いに重なり合う3文字のすべてのシーケンスを取り出し、それを転置インデックス内のトークンとして使えばよいのです。

実際の複雑さは、正規表現をトークナイズしてインデックスに対してマッチできるようにするときに生じます。正規表現には 構文 があるため、それをパースし、式のうち実際にテキストを表している部分から、どのトライグラムを抽出できるかをヒューリスティクスで判断する必要があります。

リテラル文字列をトライグラムに分解するのは単純で、ドキュメントをインデックスするときと同じアルゴリズムです。文字列中に含まれる、互いに重なり合うすべてのトライグラムを抽出します。これら すべて のトライグラムを含むドキュメントは、おそらくそのリテラルを含んでいるでしょう（ただし必ずしもそうとは限りません！）。オルタネーション（選択）は個別に分解され、どちらか一方がドキュメントに含まれていればマッチする、2つの分岐になります。転置インデックスへのクエリでは、ポスティングリストを積集合ではなく 結合 することでこれを表現します。文字クラスは多くのトライグラムに分解できます。[rbc]at のような小さなクラスでは、クラスの各要素ごとに1つのトライグラムになります。より広い文字クラスを使う場合は、その境界をまたぐトライグラムの抽出は単純にスキップします。

#ここまでのまとめ

すでに、これらのドキュメントをトークナイズするにはトライグラムが適していること、インデックスを構築するときのドキュメントのトークナイズ方法、検索時のクエリのトークナイズ方法を理解しています。これらをすべて組み合わせることで、正規表現に対して 非常に効率的に マッチできる実際の検索インデックスを構築できます。任意の正規表現をトライグラムの集合に分解し、転置インデックスから関連するすべてのポスティングリストを読み込むことで、その正規表現に マッチする可能性のある ドキュメントの一覧を得ることができます。これは重要です！最終的な結果セットは、実際にすべての候補ドキュメントを読み込み、正規表現を「昔ながらのやり方」でマッチさせることでのみ得られます。しかし、この限定されたドキュメント集合だけを対象にするほうが、コードベース全体をファイルごとにスキャンしてマッチさせるよりも常に高速です。

この設計は、あらゆる面で完全に実用的です。google/codesearch や sourcegraph/zoekt のようなプロジェクトは、トライグラムの転置インデックスを使って大規模なインデックスに対して良好なパフォーマンスを提供しています（そして、一般的な検索エンジンと同様、その上にさらに多くの複雑な仕組みを積み重ねています）。しかし、ここには明らかな欠点もあります。インデックスサイズは決して小さく なく、クエリ時の分解にはトレードオフが存在します。単純なヒューリスティクスを使うと、クエリは少数のトライグラムに分解され、それはマッチ対象となる候補ドキュメントが非常に多くなることを意味します。複雑なヒューリスティクスを使うと、最終的に数十個、場合によっては数百個のトライグラムになる可能性があり、それらすべてを転置インデックスから読み込む処理は、いっそ最初からすべてを総当たりで検索してしまうのと同じくらい遅くなるかもしれません。

これより良い方法があります。

#サフィックス配列：寄り道

正規表現検索のためのテキストデータのインデックス化の歴史を扱っているので、ここで少し寄り道して、Nelson Elhage が 2015 年に自身の livegrep Web サービス向けに開発したこの実装について取り上げたいと思います。ほかの大規模な業界の取り組みと比べると、livegrep はごく小規模です — Linux Kernel の最新バージョンだけをインデックス化しています — が、その対象範囲が限定されているため、その実装は世の中にあるほかのどれとも大きく異なっており、とても興味深く、語る価値があります。

Nelson はこの問題に第一原理から取り組みました。この検索エンジンには、転置インデックスは使われていません。その代わり、すべてのソースコードがサフィックス配列の中にインデックス化されています。

ここでの欠点は何でしょうか。サフィックス配列は入力文字列から構築しなければなりません。これは大きな制約です。大規模なコードベース（あるいは複数の異なるコードベース）をインデックス化しようとする場合、まずすべての内容を 1 つの文字列に連結し、その上でサフィックス配列を構築する必要があります。サフィックス配列内でマッチを見つけた際には、そのマッチ位置を、それを含む元のファイルに対応付けるための補助的なデータ構造も必要になります。克服不可能な複雑さというわけではありませんが、インデックスを動的に更新するコストを非常に高くしてしまいます。スケールさせるのが非常に難しいアプローチです。

#確率的マスクを用いたトライグラムクエリ

少し伝統的な設計に話を戻しましょう。ここでは、GitHub が Project Blackbird のために元々開発したアプローチを紹介します。これは、旧来の Code Search 機能を置き換えることを目指したリサーチプロジェクトでした。前に述べたように、旧来の検索はソースコードをトークン化して実装されており、正規表現をマッチさせることができませんでした。この新しい実装の目標は、それが可能な仕組みを開発することでした。

最初のいくつかの試行では、トライグラムをキーにした古典的な転置インデックスを使おうとしましたが、すぐに容量の問題にぶつかりました。GitHub には非常に多くのコードがあり、トライグラムでインデックスすると、検索するには大きすぎる posting list（ポスティングリスト）ができてしまったのです。

トライグラムがうまく機能しなかったため、次のステップはインデックスする n-gram のより良いサイズを見つけることでした。ビグラムは posting list が手に負えないほど巨大になるため広すぎ、クアドグラムはインデックス内のキーが多くなりすぎるため細かすぎることを見てきました。トライグラムはその中間の 一種の スイートスポットですが、実際には理想のサイズは…3.5-gram 程度なのです。しかし、文字を半分に分割することはできませんよね？

実は、それにかなり近いことができます。この設計では、転置インデックスのキーとしてトライグラムを使い、その posting list に「その特定のドキュメントでそのトライグラムに続く第 4 文字」に関する追加情報を持たせることを提案しています。そのために、その第 4 文字を単に 1 バイトとして保存することもできますが、そうするとインデックスはクアドグラムインデックスになってしまい、クアドグラムは大きすぎて保存できないことは既に見た通りです。そこで代わりに保存するのが、特定のトライグラムに続くすべての文字を含む bloom filter です。

こうして得られるインデックスは極めて効率的ですが、大きな欠点があります。Bloom filter は飽和してしまう可能性があるのです。これは Bloom filter の残念な性質で、更新はできるものの、あまりに多くのデータを追加すると、最終的にはフィルタ内のすべてのビットが 1 に設定されてしまいます。一度 Bloom filter が飽和すると、あらゆるものにマッチしてしまい、最初に説明したインデックスと同じ性能に逆戻りしてしまいます。

これはストレージを最小化するインデックスですが、その場で更新しなければならないときには扱いにくくなります。

#スパース N-gram: より賢いトライグラム選択

ここでもうひとつ、とても賢いアイデアを紹介します。これは ClickHouse の正規表現オペレーターや、数年前にリリースされ正規表現マッチにも対応している GitHub の新しい Code Search 機能で使われているのを見たことがあるかもしれません。これは「スパース N-gram」と呼ばれるもので、中間的なアプローチとしてはまさに理想的な手法です。

従来のトライグラムインデックスは、連続する3文字列を すべて 抜き出しますが、これによって 大量の冗長性 が生まれることが分かると思います。どのトライグラムにも、その隣のトライグラムと重複する文字が含まれているからです。このアルゴリズムでは、ランダムな数の N-gram を、各 N-gram についてランダムな長さで抽出します。

もちろん、ここでいう ランダム は完全なランダムではありません。そうでなければインデックスをクエリできなくなるからです。ドキュメント内のすべての文字ペアに「重み」を割り当てます。この重みは、決定的である限りどんな値でも構いません（ClickHouse では、2文字の crc32 ハッシュを使います）。そして、スパース N-gram はすべて、「両端の重みが、その内部に含まれるすべての重みよりも厳密に大きい」ような部分文字列として定義されます。

重要なのは、スパース N-gram の長さは 任意 でよいという点です。一律ではありません。また、単にトライグラムを抽出するだけの場合よりも、むしろ多くのスパース N-gram が生成されてしまう可能性もあります。しかし N-gram が決定的な方法で生成されているおかげで、クエリ時に非常に重要な最適化がいくつも行えます。どうなるか見てみましょう。

これよりうまくできるでしょうか？できます。しかも、実際のところ、はるかに良くできます。これまでアルゴリズム内の重み関数の例として crc32 を使ってきましたが、決定的でありさえすれば、どんなハッシュ関数でもここでは機能します。そこで、とても賢いやり方を選びましょう。実際には「非常にまれ」な文字ペアに高い重みを与え、「非常に頻繁」な文字ペアには低い重みを与えるハッシュ関数です。

このハッシュ関数は計算が容易です。これからソースコードにインデックスを付けていくにあたり、インターネット上から数テラバイト分のオープンソースコードを取得し、その中に現れるすべての文字ペアについて頻度テーブルを作成できます。その頻度テーブルこそが、ハッシュ関数になります。それをアルゴリズムに適用するとどうなるかを見てみましょう。最も高い重みが、出現頻度が最も低い文字ペアに対応するようになり、その結果として、covering モード では照会すべき n-gram がさらに少なくなり、一致する可能性のあるドキュメントも少なくなります。

このように、ポスティングリストの参照回数を最小化するアプローチは、ユーザーのマシン上で効率的にクエリできるインデックスを構築するための、理想的な出発点となります。

#これらすべてを、あなたのマシンの中で

正規表現検索を高速化するためのインデックスは、どこか に存在している必要があります。ここまで見てきた設計はすべてサーバー側にデプロイされており、これまで説明してきたセマンティックインデックスもサーバーで管理・クエリされています。そこで私たちは、ここでは別のアプローチを取っています。インデックスの構築とクエリを、ユーザーのマシン上で行うという選択です。

これらのインデックスをローカルに保つことには、いくつかの合理的な理由があります。まず、インデックスは正規表現をマッチさせるために必要なもののうちの 一部 にすぎません。インデックスは正規表現がマッチしうるドキュメントの範囲を絞り込みますが、最終的には各ファイルを個別に走査する必要があります。これをサーバー側で行うには、すべてのファイルを同期するか、高コストな往復通信をクライアントと繰り返す必要があります。クライアント側で行うのであれば単純であるうえに、データ保存にまつわる多くのセキュリティ・プライバシー上の懸念も回避できます。

この機能ではレイテンシも非常に重要です。Composer モデルは業界でも最速クラスの TPS を持っており、私たちはそれをより賢く、かつ より高速に するために日々改善を続けています。モデルが 常に (しばしば並列で) 利用するようなクリティカルな処理にネットワーク往復を挟むと、摩擦やスタール (stall) を生み、Agent との対話で目指している方向性とは逆行してしまいます。

セマンティックインデックスと異なり、正規表現検索用のインデックスは、特にモデルが自分自身の書き込みを読むという観点から、非常に鮮度が高い 必要があります。ファイルが変更されたあとにその埋め込みを再計算しても、新しい埋め込みが多次元空間の中で大きく位置を変えることはないため、セマンティックインデックスを継続的に更新する必要はありません。最近傍探索を行えば、Agent を正しい方向に導くことができます。しかし、Agent が特定のテキストを検索して見つけられない場合、不毛な探索に走ってしまい、トークンを浪費し、そもそものパフォーマンス最適化の目的を台無しにしてしまいます。

これらのインデックスをクライアントに持ち込むことには、もちろん固有の課題もあります。ディスク上のデータを同期するのは複雑で高コストになりがちですが、実際には非常に効率よく行えるようにしています。基盤となる Git リポジトリのコミットをベースにしてインデックスの状態を管理し、その上にユーザーと Agent の変更をレイヤーとして保存します。これにより更新は非常に高速で、起動時の読み込みや同期もとても速くなります。

エディタのメモリ使用量を最小限に抑えるため、インデックスは 2 つの別々のファイルに保存しています。1 つ目のファイルにはインデックスのすべてのポスティングリストを順番に格納しており、構築時にこれをそのままディスクにフラッシュします。もう 1 つのファイルには、すべての n-gram に対するハッシュと、それに対応するポスティングリストのポスティングファイル内でのオフセットを持つソート済みテーブルを格納します。ここで完全な n-gram を保存せずにハッシュのみを保存しても常に安全です。2 つのハッシュが衝突した場合 (実際には極めて起こりにくい) にポスティングリストがやや広くなる可能性はありますが、誤った結果を返すことはありません。また、ルックアップテーブルのレイアウトを非常にコンパクトにできます。そのうえで、このテーブル だけ をエディタプロセスで mmap し、バイナリサーチを使ってクエリを処理します。検索はオフセットを返し、そのオフセット位置をポスティングファイルから直接読み込みます。

#結論

私たちは、自社の Composer 2 のような高速なモデルにテキスト検索インデックスを提供することで、エージェント型ワークフローに質的な違いが生まれることを見出しました。この効果は、より大規模なエンタープライズリポジトリではさらに顕著です。というのも、grep はエージェントの操作の中でも、処理対象のコードの規模や複雑さに応じてレイテンシーが増大する数少ないものの 1 つだからです。Composer 2 で動作するこれらのワークフロー例を見てみてください。コードベースの検索に費やされる時間を完全になくすことで、意味のある時間短縮が得られます。特にエージェントがバグを調査する際にはその効果が大きく、はるかに効果的に反復できるようになります。

次に何が来るのかについては、誰にもわかりません！ エージェントにコンテキストを提供することをめぐっては、数多くの刺激的な進展があり、この分野には私たちを含め、多くの研究者が取り組んでいます。私たちは、semantic indexes を含む現在のアプローチのパフォーマンスを引き続き最適化していきます。また、エージェントのパフォーマンスをさらに向上させる、まったく新しい方法も生み出したいと考えています。その一方で、それらが本当に重要な場所、すなわちエージェント型開発の未来が真に勢いを増している世界最大級のリポジトリで運用可能であることを、常に確実にしていきます。