本文同時介紹了我正在開發的工具 jsongrep，以及其所使用的內部搜尋引擎的技術原理。我也討論了用於比較 jsongrep 與其他類似 JSON 路徑查詢工具和實作效能的基準測試策略。在這篇文章中，我將先展示這個工具，接著從概念上解釋為何它快速，再說明其背後的自動機理論，最後以基準測試證明其效能。

首先我要說明，這篇文章深受 Andrew Gallant 的出色工具 ripgrep 及其相關部落格文章「ripgrep is faster than {grep, ag, git grep, ucg, pt, sift}」的啟發。

jsongrep（執行檔為 jg）接受一個查詢和 JSON 輸入，並列印出所有路徑符合查詢的值。以下用一個範例文件 sample.json 逐步建立查詢語言：

{

"name": "Micah",

"favorite_drinks": ["coffee", "Dr. Pepper", "Monster Energy"],

"roommates": [

{"name": "Alice", "favorite_food": "pizza"}

]

}

點路徑（dot paths）透過名稱選擇巢狀欄位。欄位名稱間的點（.）表示串接——「先匹配這個欄位，再匹配那個欄位」：

$ cat sample.json | jg 'roommates[0].name'

roommates.[0].name: "Alice"

萬用字元可匹配任意單一鍵（*）或任意陣列索引（[*]）：

$ cat sample.json | jg 'favorite_drinks[*]'

favorite_drinks.[0]: "coffee"

favorite_drinks.[1]: "Dr. Pepper"

favorite_drinks.[2]: "Monster Energy"

交替符號（|）匹配任一分支，如同正則表達式的 alternation：

$ cat sample.json | jg 'name | roommates'

name: "Micah"

roommates: [ { "name": "Alice", "favorite_food": "pizza" } ]

遞迴下降使用 * 和 [*] 包含在 Kleene 星號中，可任意深度遍歷樹狀結構。例如，尋找任意深度的所有 name 欄位：

$ cat sample.json | jg '(* | [*])*.name'

name: "Micah"

roommates.[0].name: "Alice"

模式 (* | [*])* 表示「跟隨任意鍵或任意索引，零次或多次」，即遍歷所有可能路徑。最後的 .name 則過濾只留下以 name 欄位結尾的路徑。等價地，jg 提供 -F（"fixed string"）選項作為這類遞迴下降查詢的簡寫：

$ cat sample.json | jg -F name

name: "Micah"

roommates.[0].name: "Alice"

可選符號（?）匹配零次或一次：

$ cat sample.json | jg 'roommates[0].favorite_food?'

roommates.[0]: { "name": "Alice", "favorite_food": "pizza" }

roommates.[0].favorite_food: "pizza"

注意內部字串 "pizza" 同時符合 ? 的零次與一次匹配。

jsongrep 智能偵測是否將輸出管線接到 less 或 sort 等命令，若是則不顯示 JSON 路徑，但可用 --with-path 選項強制顯示。

jsongrep 的核心理念是：JSON 文件是樹狀結構，物件和陣列是分支，純量是葉節點，鍵與索引標記邊。查詢 JSON 文件即是描述這棵樹的路徑。jsongrep 的查詢語言是鍵與索引字母表上的正則語言。想像正則表達式，但匹配的是樹的邊而非字串的字元。

為何正則語言重要？因為正則語言可編譯成確定性有限自動機（DFA），DFA 以單次掃描、每個輸入符號 $O(1)$ 的工作量處理輸入，無需回溯、無遞迴堆疊，也不會因病態查詢導致指數爆炸。查詢編譯一次後，搜尋幾乎免費。這是 jsongrep 與 jq、jmespath、jsonpath-rust 等工具的關鍵差異。後者在 JSON 樹的每個節點解釋查詢，評估條件，並遞迴深入匹配分支。若查詢包含遞迴下降（.. 或 $..），可能重複訪問子樹或維護工作清單。

jsongrep 則根本不同——它先將查詢編譯成 DFA，再對文件樹單次遍歷，每條邊執行一次 $O(1)$ 狀態轉移。無解釋、無回溯、單次通過。結果是 jsongrep 非常快速：

在約 190 MB 的大型資料集上，端到端搜尋效能明顯優於其他工具。

不過，jsongrep 目前尚未像 jq 那般普及。jq 是 JSON 查詢、過濾與轉換的首選工具。

jsongrep 的查詢語言刻意不如 jq 豐富。它是搜尋工具，不是轉換工具——只尋找值，不計算新值。沒有過濾器、算術或字串插值。

jsongrep 還很新，尚未經過大量實戰考驗。

接下來深入介紹 jsongrep 的 DFA 查詢引擎內部實作。

搜尋引擎核心為五階段管線：

1. 使用 serde_json_borrow（零拷貝）將 JSON 解析成樹。

2. 將使用者查詢解析成查詢抽象語法樹（AST）。

3. 透過 Glushkov 演算法從查詢建構非確定性有限自動機（NFA）。

4. 使用子集建構法將 NFA 決定化為 DFA。

5. 深度優先遍歷 JSON 樹，根據 DFA 狀態轉移搜尋並收集匹配結果。

以查詢 roommates[*].name 為例，解析後的 AST 表示為序列結構，包含欄位 roommates、陣列萬用字元 [*] 及欄位 name。

Glushkov 演算法將查詢線性化，為每個符號編號，計算 First、Last 及 Follows 集合，組裝出無 epsilon 過渡的 NFA。此 NFA 狀態數為符號數加一，起始狀態連接 First 集合中符號，Follows 集合定義狀態間轉移，Last 集合標記接受狀態。

以 roommates[*].name 為例，NFA 為一條簡單鏈：

$q_0 \xrightarrow{roommates} q_1 \xrightarrow{[*]} q_2 \xrightarrow{name} q_3$

接著使用子集建構法將 NFA 決定化為 DFA。DFA 狀態為 NFA 狀態集合，接受狀態為包含任一 NFA 接受狀態的集合。對此查詢，NFA 已是確定性，DFA 結構相同。

jsongrep 在字母表中加入 Other 符號，處理查詢中未出現的鍵，轉移至死狀態以有效跳過不匹配分支。

搜尋時，從 JSON 根節點與 DFA 起始狀態開始，對每個子節點邊標籤查找 DFA 轉移。若無轉移，整個子樹被跳過。若新狀態為接受狀態，記錄匹配結果。遞迴進入子節點並帶入新狀態。

此方法使得整個搜尋為 $O(n)$，n 為 JSON 節點數，無回溯且每個節點最多訪問一次。jsongrep 使用 serde_json_borrow 實現零拷貝解析，減少大型文件的記憶體負擔。

基準測試方面，使用 Criterion.rs 框架，測試四個不同大小的資料集，並與五款 JSON 查詢工具比較：jsongrep、jsonpath-rust、jmespath、jaq、jql。

基準分為文檔解析時間、查詢編譯時間、查詢搜尋時間及端到端時間四組，確保公平比較。

結果顯示，jsongrep 在大型資料集的端到端搜尋速度遠超其他工具，尤其在搜尋階段表現優異。其零拷貝解析與 DFA 單次遍歷策略是關鍵優勢。

jsongrep 是開源且 MIT 授權，提供 GitHub、crates.io 及線上基準測試報告，並可作為 Rust 函式庫嵌入專案中，實現快速 JSON 搜尋功能。