Perl 的 Regular Expression 的強度：NP-complete
source link: https://blog.gslin.org/archives/2022/07/04/10777/perl-%e7%9a%84-regular-expression-%e7%9a%84%e5%bc%b7%e5%ba%a6%ef%bc%9anp-complete/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Perl 的 Regular Expression 的強度：NP-complete
這篇稍微偏 CS 理論一些...
以前在學校學 Formal language 的時候會帶出 Grammer、Language、Automaton 三個項目，就像是維基百科上的條列：
裡面可以看到經典的 Regular expression 會被分到 RG/RL/FSM 這三塊。
前幾天看到 gugod 寫的「[Perl] 以正規表示式來定義文法規則」這篇，裡面試著用 Perl 的 regular expression (perlre) 建構「遞歸下降解析器」 (Recursive descent parser)。
Recursive descent parser 可以當作是 CFG 的子集合，而 CFG 對應到的語言是 CFL，另外他對應到的自動機是 PDA。
我們已經知道 perlre 因為支援一堆奇怪的東西 (像是 backreference 或是 recursive pattern)，所以他能接受的 language 已經超過 RL，但我很好奇他能夠做到什麼程度。
用搜尋引擎翻了翻，查到對 PCRE 的分析 (這是一套與 Perl regular expression 語法相容的 library)：「Which languages do Perl-compatible regular expressions recognize?」。
在裡面有人提到「The true power of regular expressions」這篇文章，裡面給了一個在 PTIME 演算法，將 3SAT 轉換到 PCRE 裡解，這證明了 PCRE 是 NP-hard；另外也很容易確認 PCRE 是 NP，所以就達成了 NP-complete 的條件了...
本來一直以為 PCRE 只是 CFG/CFL/PDA 而已，沒想到這麼強，NPC 表示大多數現有的演算法都可以轉成 PCRE 形式放進去跑... XD
Related
圖片無損壓縮下的演算法比較
Hacker News 上看到「What’s the best lossless image format? Comparing PNG, WebP, AVIF, and JPEG XL」這篇，在講圖片的無損壓縮演算法。在 Hacker News 上的討論也可以看看：「What’s the best lossless image format? (siipo.la)」。 文章有點舊 (2021 年七月)，但應該還行... 另外作者看起來是以 service bandwidth 考量為主，在這種情境下，自然圖片一般都會以非無損的方式提供 (像是 JPEG)，而人造圖片則是以無損的方式提供 (像是 PNG)，所以在這邊討論無損的時候會以人造圖片的 dataset 來挑選，於是作者是跑去 Dribbble 上翻圖片當 dataset： What I ended up with was downloading a set of…
June 11, 2022In "Computer"
GTA 的啟動讀取效能問題
這件事情也已經過了一個禮拜，來整理一下發生什麼事情... 起因是 GTA Online 的遊戲開啟速度很慢，而有人一路 reverse engineering 找出問題並且解決：「How I cut GTA Online loading times by 70%」，對應的 Hacker News 討論有提到其他有趣的事情也可以看看：「How I cut GTA Online loading times by 70% (nee.lv)」。 作者的電腦不算太差，但光開啟 GTA Online 就需要六分鐘，網路上甚至有辦投票蒐集大家的等待時間，發現也有很多人反應類似的問題： 接下來就開始 reverse engineering 了，先觀察各種狀態後發現是卡在 CPU，而不是網路或 Disk I/O，然後就拿出 Luke Stackwalker 這個工具 profiling，不過因為沒有 debug symbol 幫忙 group，所以只能人工判斷後，可以看到兩個問題： 第一個問題發現效能是卡在 strlen()，而 call…
March 6, 2021In "Computer"
Perl 與 Python 在 Unicode 的處理
我試著在 Python 上找到 Perl Regular Expression 有提供的 General Category Property，不過沒有找到。而且發現 Python 沒有使用 PCRE。 先參考 Unicode.org 上的文件，Unicode Regular Expressions 這篇，在 Regular Expression 裡使用 General Category Property 指的是 \p{Lu} 這種用法，前面的範例表示大寫字母 (Uppercase Letter)，我在用 Perl 切詞的時候用了兩次這種 Regular Expression。 替代的方案是依照 Unicode Regular Expressions 裡的說法去找對應的範圍，然後自己寫 Regular Expression。 Update：Wikipedia 的 Mapping of Unicode characters 比較清楚，直接把 Hex Start…
July 20, 2007In "Computer"
Leave a Reply
Your email address will not be published. Required fields are marked *
Comment *
Name *
Email *
Website
Notify me of follow-up comments by email.
Notify me of new posts by email.
To respond on your own website, enter the URL of your response which should contain a link to this post's permalink URL. Your response will then appear (possibly after moderation) on this page. Want to update or remove your response? Update or delete your post and re-enter your post's URL again. (Learn More)
Post navigation
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK