帶O（N）和反向引用支持的正則表達式

Question

正如您所知，有兩種不同的正則表達式實現：一種使用回溯（pcre），另一種使用有限自動機（re2）。

這兩種算法都有其侷限性：在特定情況下，pcre可能需要指數時間才能找到匹配，而有限自動機不支持反向引用。

PCRE實現支持反向引用，像/a?a?a?a?aaaa/對aaaa表達式匹配效率非常低，越a的表達和輸入有 - 的時間也就越長，並與他們的30+如果時間會花費很多。

與有限自動機版很好地處理所有的這些實施方式和具有O（N） 從輸入的複雜性，但不支持反向引用：

PCRE時間針對複雜的表達式 - http://i.stack.imgur.com/D4gkC.png NFA處理那些，但不支撐反向引用 - http://i.stack.imgur.com/t2EwI.png

上支持反向引用一些資料：

RE2 - http://code.google.com/p/re2/

一個重要的例外是，RE2不支持反向引用和廣義零寬度斷言，因爲它們無法有效實施。

湯普森NFA - http://swtch.com/~rsc/regexp/regexp1.html

正如前面提到的，沒有人知道如何實現與反向引用有效正則表達式，儘管沒有人能夠證明這是不可能的要麼。 （具體地講，這個問題是NP完全的，這意味着如果有人沒有找到一個有效的實施，這將是計算機科學家重大新聞，將贏得100萬美元的獎金。）

所以我創建了自己的版本，這兩個支持反向引用並具有O（N）複雜性。它用haskell編寫，大約有600個（〜200個是空白的，200個類型的聲明，可以跳過）。它嚼通過/a?a?aa/對aa（與a 100）約10秒，據我所知，它是唯一版本，可以匹配

/a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?(a?a?a?a?a?a?a?a?a?a?aaaaaaaaaa)aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\1/ 

對

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa 

在理智（約10秒）的時間。它當然支持我在互聯網上找到的基本正則表達式規範中列出的所有其他功能。

問題是：它真的是一個「計算機科學家的重大新聞」，如果是這樣，我該怎麼辦？ PS：我將在一週內顯示源代碼 - 我仍然想用分析器運行一些測試並替換一些內部數據結構。

Answer 1

我相信你是困惑。所有正則表達式都可以用離散有限自動機（DFA）來表示，並且（因此）可以在O（n）時間內解出。 Perl正則表達式（PREG）（以及由許多語言提供的正則表達式庫）匹配大於正則表達式的語言，即：正則表達式存在於PREG中。

如果你想更多地瞭解這種常規語言的搜索。每一種常規語言都可以用一個正則表達式來表示（因此也就是相似的名稱），每一個正則表達式都代表一種常規語言。 PREG可以代表非常規語言的事物。此外，沒有人喜歡有人說「我可以做到這一點，這很棒，但我不會解釋怎麼做」。這足以讓人不相信你（忽略你誤解正則表達式的含義）。

Answer 2

功能語言似乎有效地實現了正則表達式。我已經看到一個用Common-Lisp編寫的非常酷的書：CL_PPCRE

如果你能證明O（n）這可能是一個有趣的結果，但你必須確保你真的有線性時間複雜度，不是很有效。

Answer 3

您建議的測試用例不匹配。您沒有足夠的a s來匹配反向引用（僅足以匹配反向引用之前）。如果我添加10名a是如此，它相匹配，在glibc的正則表達式匹配報告成功瞬間

$ echo aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa | sed -re \ 
    '/a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?(a?a?a?a?a?a?a?a?a?a?aaaaaaaaaa)aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\1/!d' 
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa 

Answer 4

你可以看看這個鏈接的文章，似乎這已經由其他人來完成：

Regular Expression Matching Can Be Simple And Fast (but is slow in Java, Perl, PHP, Python, Ruby, ...)