時間是個扁平的圓圈。第一個版本的 grep 在 1973 年發行時，只是檔案系統中文件上進行正規表示式比對的基本工具。多年下來，隨著開發工具愈趨進步，它逐漸被更專門的工具取代。先是像 ctags 這類大致語法層級的索引。之後，許多開發者改用針對特定程式語言設計的專用 IDE，透過剖析與建立語法索引，往往再加上型別層級資訊，讓他們能非常有效率地瀏覽程式碼庫。最終，這些能力在 Language Server Protocol (LSP) 中被標準化，讓所有文字編輯器——新的舊的——都能使用這些索引。就在 LSP 正逐步成為標準時，Agent 式程式開發出現了，而結果就是：這些代理實在太「愛」用 grep 了。

還有其他最先進的技術可以為 Agent 收集上下文。我們先前談過，在許多任務中使用語意索引可以大幅提升 Agent 的效能，但也有一些查詢，模型只能透過正規表示式搜尋來解決。這代表我們得回到 1973 年的做法，即使這個領域此後已經進步了不少。

大多數 Agent 執行框架，包括我們自己的，都在提供搜尋工具時預設使用 ripgrep。這是 Andrew Gallant 開發的獨立可執行檔，是經典 grep 的替代品，但有更合理的預設值 (例如在忽略檔案方面) ，而且效能好得多。ripgrep 之所以快得出名，是因為 Andrew 在比對正規表示式時，花了非常多時間思考速度這件事。

不論 ripgrep 在單一檔案內容上比對得多快，它都有一個嚴重限制：它必須在「所有」檔案的內容上比對。這在小型專案裡還算沒問題，但許多 Cursor 使用者——特別是大型企業客戶——都是在非常龐大的 monorepo 中工作。大到令人頭疼。我們經常看到 rg 呼叫要跑超過 15 秒，而這真的會讓任何正在主動與 Agent 互動、引導它寫程式的人整個工作流程卡住。

正規表示式比對現在已是 Agent 式開發中不可或缺的一環，我們認為明確針對這一點進行優化至關重要：就像傳統 IDE 會在本機建立語法索引用來支援「跳至定義」這類操作一樣，我們正在為現代 Agent 在查找文字時執行的核心操作建立索引。

#經典演算法

為了加速正則表達式比對而對文本資料進行索引處理，這個概念早已不是新鮮事。最早是在 1993 年，由 Zobel、Moffat 和 Sacks-Davis 在一篇名為 "Searching Large Lexicons for Partially Specified Terms using Compressed Inverted Files" 的論文中提出。他們提出了一種方法，使用 n-grams（以 n 個字元為寬度的字串片段）來建立反向索引，並用啟發式方法將正則表達式分解成一棵由 n-grams 組成的樹，再到索引中查找。

如果你先前聽過這個概念，很可能不是來自那篇論文，而是來自 Russ Cox 在 2012 年、Google Code Search 關閉後不久發表的一篇部落格文章。我們來快速複習一下這些索引的基礎構成，因為後來發展出的幾乎所有索引方法基本上都沿用了它們。

#倒排索引

倒排索引是搜尋引擎背後的核心資料結構。給定一組要建立索引的文件，你會先把每份文件切分成一連串 token。這個過程稱為「tokenization（斷詞／切詞）」，而其實有很多不同做法——在這個例子裡，我們會使用最簡單的方式：把每個單字視為一個 token。這些 token 接著會成為類似字典的資料結構中的鍵（key），而對應的值（value）則是：對於每一個 token，它出現過的所有文件列表。這個列表通常被稱為 posting list，因為每份文件都由一個數值或「posting」唯一識別。當你搜尋一個或多個 token 時，我們會載入它們各自的 posting list；如果 posting list 多於一個，我們就把它們取交集，找出那些 同時出現在所有 posting list 裡 的文件。

這樣的設計（再在其上堆疊大量額外的複雜度）是現今多數搜尋引擎的基礎。不過，那些是給 自然語言 用的搜尋引擎，而我們想搜尋的是正規表示式（regular expressions），而且要在原始碼上進行比對。這樣就不太適用了。

你可以試著靠「非常仔細地思考 tokenization」來做出某種程度有用的東西——瞭解每種程式語言的語法、拆解原始碼中的識別字，等等。但這非常難做好。回到 GitHub 的早期，他們的 Code Search 功能就是這樣實作的：使用一個對程式語言非常複雜的 tokenizer，加上一個非常龐大的 Elasticsearch 叢集。結果並不理想，大家對這個功能的評價也很差。你大概可以搜尋到識別字（某種程度上），但無法比對正規表示式。要做到這點，你需要一種更好的 tokenization 方式。

#三元組分解

直接對原始碼做天真的（naive）斷詞，對於比對正規表示式並沒有什麼用。我們需要把文件拆成更基本的片段。經典的演算法會選擇三元組（trigram）：在輸入字串中，每一段彼此重疊、長度為三個字元的序列就是一個 token。

為什麼是三個？我們會把這些三元組當作倒排索引中的鍵。如果我們選擇二元組（bigrams，長度為 2 的片段），索引中的鍵會很少，最多大約 64k 個，但每個鍵對應的 posting list 會非常巨大——大到無法有效處理。如果我們改用四元組（quadgrams，長度為 4 的片段），posting list 會非常小，這點本身很好，但倒排索引中的鍵會多到有數十億個，同樣也很難處理。

因此，三元組是一個不錯的折衷方案。這讓在對文件做索引處理時的斷詞變得非常簡單：從要做索引的文件中，擷取所有彼此重疊、長度為 3 的字元序列，並將它們作為倒排索引中的 tokens。

真正的複雜度出現在要對正規表示式進行斷詞，以便能在索引上進行比對時。正規表示式具有「語法」，所以你需要先解析它們，並使用啟發式方法來判斷，哪些三元組可以從那些實際代表文字的表示式片段中擷取出來。

將一個 字面量字串 分解成三元組相對直接，因為這和在為文件建立索引時使用的演算法相同。擷取字串中所有彼此重疊的三元組；包含了這些所有三元組的文件很可能就包含這個字面量（但不一定！）。交替（alternations） 會被分別分解，形成兩個分支，只要文件中包含其中任一分支就可以符合。我們在倒排索引上查詢時，會透過「聯集」 posting list，而不是對它們做交集。字元類別可以被分解成很多三元組。像 [rbc]at 這種小型的類別，會對類別中的每個元素各產生一個三元組。當使用 較廣泛的字元類別 時，我們則會直接略過跨越這些邊界的三元組擷取。

#把一切串在一起

我們已經知道 trigram 是為這些文件做 tokenization 的正確方式，也知道在建立索引時如何對文件做 tokenization，以及在搜尋時如何對查詢做 tokenization。現在我們可以把這一切組合起來，做成一個實際可用的搜尋索引，用來 極為高效地 比對 regular expression。藉由把任意 regular expression 分解成一組 trigram，並從倒排索引中載入所有相關的 posting list，我們最後會得到一份文件清單，這些文件 有可能 符合我們的 regular expression。這點很重要！最終的結果集合仍然必須透過實際載入所有潛在文件，並用「傳統方式」去比對 regular expression 才能取得。但先把文件縮小成這個子集合，永遠比逐個檔案掃描並比對整個程式碼庫要快得多。

就各方面來說，這個設計是完全可行、可用的。像 google/codesearch 和 sourcegraph/zoekt 這類專案，就是利用 trigram 的倒排索引，在大型索引上提供良好效能（而且就像所有搜尋引擎一樣，它們在上面再疊加了更多複雜度）。但這裡也有明顯的缺點：索引大小 並不 小，而且在查詢階段做分解時必須做取捨。如果你只用簡單的啟發式方法，就會把查詢分解成少量 trigram，結果會得到非常多必須比對的潛在文件。如果你使用複雜的啟發式方法，最後可能會得到數十甚至數百個 trigram，而從倒排索引載入這些 trigram 的成本，可能會和從頭搜尋全部內容一樣慢。

我們可以做得更好。

#後綴陣列：一次小小的繞道

既然我們正在介紹為了正則表達式搜尋而對文字資料進行索引處理的歷史，我想稍微繞個路，談談 Nelson Elhage 在 2015 年為他的 livegrep 網頁服務所開發的這個實作。和其他大型業界方案相比，livegrep 規模很小——它只為最新版本的 Linux 核心建立索引——但也正因為範圍較小，它的實作方式與市面上其他任何東西都大不相同，這也讓它變得非常有趣，值得拿出來討論。

Nelson 從基本原理出發來處理這個問題：這個搜尋引擎並沒有使用倒排索引。相反地，所有原始碼都被索引在一個後綴陣列之中。

那麼這裡的缺點是什麼？後綴陣列必須從一個輸入字串建構而來。這是個很大的限制。如果你試圖為一個巨大的程式碼庫（或甚至許多不同的程式碼庫）建立索引處理，你必須先把所有內容串接成單一字串，再從中建構出後綴陣列。而在後綴陣列中找到比對位置之後，你還需要額外的資料結構，將該比對位置對應回實際包含它的原始檔案。這樣的複雜度並非不可克服，但會讓動態更新索引變得非常昂貴。這種解法非常難以具備良好的擴展性。

#使用機率遮罩的 Trigram 查詢

先回到一些較傳統的設計：以下這個方法最初是在 GitHub 為 Project Blackbird 開發的。這是一個研究專案，目標是取代舊的 Code Search 功能。如我們先前討論過的，舊版搜尋是透過將原始碼斷詞實作的，因此無法比對正規表示式，而新實作的目標，就是要做出能夠支援這點的系統。

最初的幾個版本嘗試使用以 trigram 作為鍵的典型反向索引，但很快就遇到容量問題。GitHub 上有大量程式碼，而使用 trigram 來為其建立索引，會產生過於龐大的 posting list（倒排列表），使得搜尋變得幾乎不可行。

既然 trigram 效果不佳，下一步就是找出要建立索引的 n-gram 的更佳長度。我們已經看過，bigram 太粗略，因為它們的 posting list 會變得大到無法管理；而 quadgram 又太精細，因為我們的索引裡會出現太多鍵。Trigram 在兩者之間是一個折衷的_甜蜜點_，但在實務上，理想長度更像是……3.5-gram。然而我們不可能把一個字元拆成兩半，對吧？

事實上，我們可以做出非常接近的東西：這個設計主張仍然使用 trigram 作為反向索引的鍵，並在 posting list 上增加額外資訊，用來描述在該文件中緊接在該 trigram 之後出現的「第四個字元」。為了達成這點，我們可以簡單地把第四個字元以額外的一個位元組儲存起來，但那又會讓索引變成 quadgram 索引，而我們已經知道那樣會太大、難以儲存。我們改為儲存的是一個 bloom filter，其中包含所有緊接在該 trigram 之後的字元。

產生出來的索引極為高效，但也有一個主要缺點。Bloom filter 可能會飽和。這是 bloom filter 一個不幸的特性；它們可以被更新，但如果你往裡面加入過多資料，最終濾器中的所有位元都會被設為 1。而一旦 bloom filter 飽和，它就會與所有東西都相符，如此一來，我們又回到本文一開始提到的那種索引效能了。

這是一種極度壓縮儲存空間的索引，但當你需要就地更新它時，就會變得相當棘手。

#稀疏 N-gram：更聰明的 Trigram 選取方式

這裡有另一個非常聰明的點子。你可能在 ClickHouse 的正則表達式運算子中看過它，也可能在 GitHub 幾年前推出、支援正則表達式比對的新版 Code Search 功能中看過。這個東西叫作稀疏 N-gram（Sparse N-grams），而且是各種折衷方案中最甜蜜的那一個。

傳統的 trigram 索引會擷取輸入中「每一個」連續 3 字元的片段，但你可以想像這會產生「大量的重複」。每個 trigram 的字元都會在相鄰的 trigram 裡被重複一次！在這個演算法中，我們會擷取隨機數量的 n-gram，而且每個 n-gram 的長度也會是隨機的。

當然，這裡所說的「隨機」不可能是真正的隨機，否則索引就無法被查詢。我們會對文件中的每一組字元配對指派一個「權重」。這個權重可以是任何值，只要它是決定性的即可（ClickHouse 使用的是那兩個字元的 crc32 雜湊）。接著，我們的稀疏 n-gram 就是所有這樣的子字串：在子字串兩端的權重都嚴格大於子字串內部所有位置的權重。

關鍵在於，這表示稀疏 n-gram 可以有「任何長度」。它們的長度並不固定。這也代表我們最後可能會產生非常多稀疏 n-gram —— 甚至比只擷取 trigram 還要多。但是，因為這些 n-gram 是以決定性的方式產生的，我們就能在查詢階段做出一些非常重要的最佳化。我們來看看怎麼做。

我們能做得比這更好嗎？可以！而且事實上會好非常多。我們在這個演算法中一直使用 crc32 作為權重函式的範例。不過，只要是具決定性的雜湊函式，在這裡其實都能運作。讓我們選一個非常聰明的做法：一種雜湊函式，會對實際上_非常罕見_的每個字元對給予高權重，而對_非常常見_的字元對給予低權重。

這個雜湊函式很容易計算。由於我們要對原始碼進行索引處理，我們可以從網路上擷取數個 TB 的開源程式碼，並為其中找到的所有字元對建立一個頻率表。那個頻率表就是我們的雜湊函式。看看當我們把它套用到演算法時會發生什麼事：權重最高的現在落在最少見的字元對上，而正因為如此，covering 模式 會讓需要查詢的 n-gram 變得_更少_，而且可能匹配的文件也更少。

這種將 posting 查詢次數降到最低的方法，會是建立可在使用者機器上高效率查詢索引的理想起點。

#所有這一切，都在你的機器上完成

用來加速正則表達式搜尋的索引必須存在於_某個地方_。前面我們看到的所有設計都是部署在伺服器端，而前述的語意索引也是在伺服器上管理與查詢。不過在這裡，我們選擇走不同的路：我們在使用者自己的機器上建立並查詢這些索引。

讓這些索引保留在本機有好幾個理由。首先，索引只是完成正則表達式比對所需的_其中一_個部分。它們只會提供一個範圍縮小後的文件子集合，表示正則表達式有可能在其中比對成功，但你仍然需要個別掃描每個檔案。若在伺服器上執行，就代表要嘛同步所有檔案，要嘛在伺服器與用戶端之間來回進行高成本的往返操作。在用戶端上執行這些事則非常簡單，並且也避開了許多與資料儲存相關的安全與隱私疑慮。

延遲對這項功能也非常重要。我們的 Composer 模型擁有業界最快的 TPS 之一，而我們正努力讓它同時變得更聰明_又_更快。對於模型_持續不斷_ (而且經常是並行地) 使用的這種關鍵操作，如果再加入網路往返，只會增加摩擦、造成停滯，並且讓我們朝著與與 Agents 互動時的目標相反的方向前進。

與語意索引不同的是，正則表達式搜尋的索引必須_非常即時_，特別是在模型要讀取自己剛寫入的內容時。我們不需要持續更新語意索引，因為檔案被修改後重新計算其 embedding，並不會讓新的 embedding 在多維空間中產生明顯位移；我們執行的最近鄰搜尋仍然會把 Agent 帶往正確的方向。然而，如果代理正在搜尋特定文字卻找不到，它往往會開始徒勞無功地亂找、浪費 token，最終反而抵消我們一開始做效能最佳化的用意。

把這些索引搬到用戶端，當然也帶來一系列的挑戰。同步磁碟資料可能既複雜又昂貴，但在實務上我們讓它非常有效率：我們透過底層 Git 儲存庫中的一個 commit 來決定索引的狀態。使用者與代理的變更則以一個加在其上的額外層級儲存。這讓更新變得非常快速，也讓在啟動時的載入與同步變得非常快。

為了確保編輯器中的記憶體使用量維持在最低，我們將索引儲存在兩個獨立的檔案中。第一個檔案包含索引的所有倒排列表，一個接著一個——在建構過程中，我們會直接將其 flush 到磁碟。另一個檔案則包含一個排序過的表格，其中有所有 n-gram 的雜湊值以及它們在倒排列表檔案中對應倒排列表的偏移量。只在這裡儲存雜湊值而不存完整的 n-gram 是安全的：在極少數情況下，雜湊碰撞可能會讓某個倒排列表變得較廣泛 (在實務上極少發生) ，但不會產生錯誤結果。這也讓我們的查詢表有非常緊湊的配置。接著，我們在編輯器行程中只對這張表使用 mmap，並用二元搜尋來處理查詢。搜尋會回傳一個偏移量，而我們則直接在倒排列表檔案中從該偏移量位置讀取資料。

#結論

我們發現，為快速模型（例如我們自己的 Composer 2）提供文字搜尋索引，會為 Agentic 工作流程帶來質性的差異。這種影響在較大型的企業儲存庫中更加明顯，因為 grep 是少數幾個其延遲會隨著所處理程式碼的規模與複雜度而增加的 Agent 操作之一。看看這些以 Composer 2 執行的範例工作流程：完全移除搜尋程式碼庫所花費的時間，能帶來可觀的時間節省——尤其是在 Agent 調查錯誤時——並且讓迭代有效得多。

至於接下來會如何，誰知道呢！目前在為 Agent 提供上下文方面，有許多令人振奮的發展，也有很多研究人員正投入這個領域——包括我們的團隊。我們將持續優化現有方法的效能，包括 semantic indexes，並希望推出全新的方式，進一步提升 Agent 的效能，同時始終確保它們能在真正關鍵的地方運作：也就是在全球最大型的儲存庫中，而 Agentic 開發的未來正是在那裡真正獲得動能。