尋找所有正規表達式匹配一直都是 O(n²) 複雜度

背景

本文探討了一個長期被忽視的正規表示式（Regex）效能問題：即使是標榜線性時間複雜度的引擎，在執行「尋找所有匹配項」（FindAll）時，其複雜度往往會退化至平方時間 O(n²)。作者指出，這類引擎雖然解決了災難性回溯問題，卻在處理重疊或連續匹配時，因重複掃描輸入字串而陷入效能陷阱，並提出 Aho-Corasick 演算法與其開發的 RE# 引擎作為可能的解決方案。

社群觀點

針對這篇技術文章，Hacker News 社群的討論呈現出多樣化的焦點。首先，最引人注目的爭論圍繞在文章的寫作風格上。由於作者全篇使用小寫字母且句式結構特殊，不少讀者質疑這是否為大型語言模型（LLM）生成的結果，或是刻意模仿某種特定的網路寫作風格以規避 AI 檢測。雖然作者親自現身澄清文章為親手撰寫，僅在修辭上尋求 AI 協助，但這場關於「AI 寫作特徵」的辯論反映了技術社群對於內容真實性的高度敏感。

在技術層面上，社群成員對 O(n²) 複雜度的實際影響有深入探討。有觀點認為，雖然理論上的最壞情況確實存在，但在實際應用（如日誌分析）中，正規表示式通常伴隨著明確的邊界限制，這能有效遏止病態的回溯行為。例如，使用者通常不會尋找像 .*a|b 這種極端模糊的模式，而是會加上單字邊界限制，這使得理論上的效能問題在現實場景中顯得較為少見。然而，也有資深開發者分享了在 Python 等環境中遇到的實際案例，指出即使沒有災難性回溯，某些看似簡單的模式（如 \d+\s+）在特定輸入下仍會因重複嘗試匹配而導致效能大幅下降。

此外，關於如何解決此問題，社群內存在不同的哲學取向。部分留言者建議透過優化正規表示式本身來規避風險，例如使用負向後行斷言（negative lookbehind）來避免重複掃描已知的字元。另一派意見則主張，與其追求完美的演算法，不如從工程實踐著手。他們認為，處理不可信的正規表示式最安全的方法是將其視為不可信的程式碼進行沙盒化處理，透過 API 層級限制執行時間與記憶體消耗，一旦超時便回傳錯誤，這比限制正規表示式的功能更具實務可行性。

延伸閱讀

在討論過程中，社群成員提供了一些具價值的參考資源。針對 Python 引擎中的效能陷阱，有讀者推薦參考 Python 官方論壇中關於 re.prefixmatch 與 \d+\s+ 效能診斷的討論串。對於想要深入了解不同引擎功能差異的讀者，則有留言提到 Wikipedia 上的正規表示式引擎比較表，特別是關於各家引擎對變動長度後行斷言（variable length lookbehind）的支援程度。此外，文中提到的 RE# 引擎及其在 PLDI 會議發表的相關研究，也是理解兩階段掃描演算法的重要參考。