Perl 的 Regular Expression 的強度:NP-complete

這篇稍微偏 CS 理論一些...

以前在學校學 Formal language 的時候會帶出 Grammer、Language、Automaton 三個項目,就像是維基百科上的條列:

裡面可以看到經典的 Regular expression 會被分到 RG/RL/FSM 這三塊。

前幾天看到 gugod 寫的「[Perl] 以正規表示式來定義文法規則」這篇,裡面試著用 Perlregular 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

各種反直覺的項目

前陣子看到「The most counterintuitive facts in all of mathematics, computer science, and physics」這篇,講各種反直覺的項目,有空的時候拉一兩個來讀還蠻有趣的...

第一個提到的是 Homomorphic encryption。在密碼學的保護概念中,密文是不能被操作的,但我們可以透過重新設計密碼學系統,讓密文可以被運算:

1. It is possible to compute over encrypted data without access to the secret key: https://en.wikipedia.org/wiki/Homomorphic_encryption

2009 年的時候第一個 FHE (fully homomorphic encryption) 演算法被提出來後就被大量討論,這代表你可以把資料加密後丟上雲端,利用雲端的大量運算資源運算完後,再把資料拉回地端解密,得到運算後的結果。這算是 Lattice-based cryptography 的一個很重大的應用。

其他的主題也蠻有趣的,先丟著找機會翻...

第四堂:「Data Wrangling」

有陣子沒寫了,來還個債...

這個系列是從『MIT 的「The Missing Semester of Your CS Education」』這邊延伸出來的,這邊講的是「Data Wrangling」這篇。

這篇是在講 pipe 的用法,在講這些工具之前,其實有個很重要的概念應該要說明 (但沒有在這篇文章裡被提到),也就是 Unix philosophy,這個哲學是指 unix 環境下的工具,都會設計成只做好一件事情。

而要怎麼把這些工具串起來,最常見的就是 pipe,你可以在文章裡看到 grepsedsort 這些工具的用法,以及怎麼用 pipe 串起來。

這邊剛好也可以提一下,利用 pipe 可以把不同功能打散到不同的 process 上,剛好也可以稍微利用到現在常見的多 CPU 的環境。

另外上面因為提到了 grep,文章內花了不少篇幅在講 Regular expression 這個在 CS 課程裡面也是重要的基礎。

會放這種篇幅長度,一方面是 Regular expression 的實用性很高,另外一方面,學術上與自動機理論中的 DFANFA 都有關,算是學習計算理論的起點:

然後後面就有提到 AWK 這個工具,這邊要注意的是,雖然可以用 Perl 之類的工具作到類似的事情 (而且更強大),但 AWK 有被放到 POSIX 標準裡,所以在各種作業系統內幾乎都一定會出現,加上語法算是簡單,學起來還是很有幫助...

然後再最後面的段落冒出一個 gnuplot 畫個圖,以及示範 xargs 這種神器要怎麼用 (這邊會更建議看一下 manpage,可以配合 find 之類的工具用,並且平行化同時處理)。

然後最後示範了 binary data 怎麼處理。

第三堂:「Editors (Vim)」

這個系列是從『MIT 的「The Missing Semester of Your CS Education」』這邊延伸出來的,這篇文章講第三堂課「Editors (Vim)」,這篇也是我決定要連載的原因 (身為 Vim 愛好者的偏好)。

這邊講的是 Vim 而不是標準的 vi (這個對於初學者應該不太容易遇到了),相較起來親民一些...

從基本的操作開始說,模式的切換,插入刪除移動類的與區塊選取類的都有提到。

比較特別的是他用黑板畫 Finite-state machine 來解釋不同的按鍵操作會切換到不同的模式,應該說這不愧是給 CS 學生上的課?

另外補充一下,用搜尋引擎搜一下 vim cheatsheet,沒事可以看一下 (回憶一下),算是蠻好用的。

第二堂:「Shell Tools and Scripting」

這個系列是從『MIT 的「The Missing Semester of Your CS Education」』這邊延伸出來的,這篇文章講第二堂課「Shell Tools and Scripting」。

這堂有點像是第一堂的延伸,在講更多 shell 的操作與工具,然後說明 shell script 怎麼寫。

開頭就先說明有 function,然後講了不少 magic variable,像是 $0$1$9,而 $@$# 也提到了 (但居然沒提到 $*),然後再來是 $$!!$_

然後提到 true 與 false,接著就講條件 || 與 && 了。後面就開始講 shell 裡面的 for 與 if,基本上到這邊已經能寫不少東西了?

後面就介紹更多工具...

第一堂:Course overview + the shell

這個系列是從『MIT 的「The Missing Semester of Your CS Education」』這邊延伸出來的,這篇文章講第一堂課「Course overview + the shell」。

前面大概講一下這 11 堂各一個小時的課大概是什麼,後面就開始講 shell 下的操作了。

先講了一些基本指令 (date & echo),然後提到了環境變數 $PATH,接著就講目錄結構與 ls,然後就順便提到 man 可以拿來查說明,接著是講 redirect 與 pipe 以及 root 權限的特殊性 (以及 sudo)。

在課程最後面的這個範例,你第一眼看不會想到是第一堂課就可以教完的東西,但的確是結合了上面提到的所有東西,可以細細品味一下:

$ echo 1 | sudo tee /sys/class/leds/input6::scrolllock/brightness

Elsevier 限制加州大學的存取權限

三月的時候加州大學系統 (UC) 因為 Elsevier 不接受 open access 的條件而公開宣佈不續約 (參考「加州大學宣佈不與 Elsevier 續約」),後來 Elsevier 應該是試著看看有沒有機會繼續合作,所以在這段期間還是一直提供服務給加州大學系統。

前幾天在 Hacker News 上看到「Elsevier cuts off UC’s access to its academic journals (latimes.com)」,總算是確定要動手了:「In act of brinkmanship, a big publisher cuts off UC’s access to its academic journals」。

不過也不是直接拔掉,而是限制存取權,看不到新東西 (以 2019/01/01 為界):

As of Wednesday, Elsevier cut off access by UC faculty, staff and students to articles published since Jan. 1 in 2,500 Elsevier journals, including respected medical publications such as Cell and the Lancet and a host of engineering and scientific journals. Access to most material published in 2018 and earlier remains in force.

UC 提出的商業模式是讓投稿者負擔費用,而存取者不需要負擔,與現有的商業模式剛好相反。UC 提出的模式鼓勵「知識的散佈」,而現有的商業模式則是反過來,希望透過知識的散佈而賺~大~錢~發~大~財~:

UC demanded that the new contract reflect the principle of open access — that work produced on its campuses be available to all outside readers, for free.

That was a direct challenge to the business model of Elsevier and other big academic publishers. Traditionally, the publishers accept papers for publication for free but charge steep subscription fees. UC is determined to operate under an alternative model, in which researchers pay to have their papers published but not for subscriptions.

另外在 Hacker News 上的 comment 裡看到一些專案也正在進行,像是歐洲的「Plan S」也是在推動 open access:

The plan requires scientists and researchers who benefit from state-funded research organisations and institutions to publish their work in open repositories or in journals that are available to all by 2021.

另外「PubPub · Community Publishing」也是 open source 領域裡蠻有趣的計畫,後面看起來也有不少學術單位在支持。

GrabFood 用定位資料修正餐廳的資訊

Grab 的「How we harnessed the wisdom of crowds to improve restaurant location accuracy」這篇是他們的 data team 整理出來,如何使用既有的資料快速的修正餐廳資訊。裡面提到的方法不需要用到 machine learning,光是一些簡單的統計算法就可以快速修正現有的架構。

這些資訊其實是透過司機用的 driver app 蒐集來的,在 driver app 上有大量的資訊傳回伺服器 (像是定時回報的 GPS 位置,以及取餐狀態),而這些司機因為地緣關係,腦袋裡的資訊比地圖會準不少:

One of the biggest advantages we have is the huge driver-partner fleet we have on the ground in cities across Southeast Asia. They know the roads and cities like the back of their hand, and they are resourceful. As a result, they are often able to find the restaurants and complete orders even if the location was registered incorrectly.

所以透過這些資訊他們就可以反過來改善地圖資料,像是透過司機按下「取餐」的按鈕的地點與待的時間,就可以估算餐聽可能的位置,然後拿這個資訊比對地圖上的資料,就很容易發現搬家但是地圖上沒更新的情況:

Fraction of the orders where the pick-up location was not “at” the restaurant: This fraction indicates the number of orders with a pick-up location not near the registered restaurant location (with near being defined both spatially and temporally as above). A higher value indicates a higher likelihood of the restaurant not being in the registered location subject to order volume

Median distance between registered and estimated locations: This factor is used to rank restaurants by a notion of “importance”. A restaurant which is just outside the fixed radius from above can be addressed after another restaurant which is a kilometer away.

另外也有不少其他的改善 (像是必須在離餐聽某個距離內才能點「取餐」,這個「距離」會因為餐聽可能在室內商場而需要的調整),整個成果就會反應在訂單的取消率大幅下降:

整體看起來是系統產生清單後讓人工後續處理 (像是打電話去店家問?),但這個方式所提供的清單準確度應該很高 (因為司機不會沒事跟自己時間過不去,跑到奇怪地方按下取餐),用這些資料跑簡單的演算法就能夠快速修正不少問題...

歐洲研究機構的資助者推動研究論文的開放存取

在「Radical open-access plan could spell end to journal subscriptions」這邊看到歐洲 11 個研究機構資助者成立了「cOAlition S」,推動研究論文的開放存取。

目標是在 2020 年開始,由這些機構所資助的研究都必須投在符合完全開放條件的平台上:

cOAlition S signals the commitment to implement, by 1 January 2020, the necessary measures to fulfil its main principle: “By 2020 scientific publications that result from research funded by public grants provided by participating national and European research councils and funding bodies, must be published in compliant Open Access Journals or on compliant Open Access Platforms.

而現在大約只有 15%:

According to a December 2017 analysis, only around 15% of journals publish work immediately as open access (see ‘Publishing models’) — financed by charging per-article fees to authors or their funders, negotiating general open-publishing contracts with funders, or through other means.

用這種方式降低那些收錢才能下載的平台的影響力...

Facebook 自己找人研究,Social Media 是否對人類有害 XDDD

之前看到「Hard Questions: Is Spending Time on Social Media Bad for Us?」這篇,一直不知道要怎麼吐槽... 然後看到 Twitter 上的這則 tweet XDDD

既視感太重了,找了一下其他行業對應的資料:

真的不知道怎麼吐槽 XDDD