finite

Daily Hacker News 上看到的紋章，「Erasure Coding for Distributed Systems」這篇討論了 Erasure code。

以前在學校裡面學 coding theory 的時候有學到一些經典的演算法，尤其是一定會教到 Reed-Solomon error correction 這個演算法，不過實務上 Reed-Solomon 因為用到 finite field 運算 (又稱 Galois field，所以簡寫常用 $GF$ )，所以效率並不算好，在 RAID 系統上面除非 controller 的 CPU 或是晶片對 GF 運算加速，不然大多都會用替代算法。

For the special cases of 1-3 parity chunks ( $m \in {1,2,3}$ ), there are algorithms not derived from Reed-Solomon and which use only XORs:

允許掛一顆的演算法就是 RAID 5，這邊用 XOR 就很容易導出來，並且分析證明。

開始有難度的是允許掛兩顆的演算法，也就是一般熟知的 RAID 6，在這篇文章裡面提到了好幾個演算法，不過有些有專利問題：

$m=2$ is also known as RAID-6, for which I would recommend Liberation codes[8][9] as nearly optimal with an implementation available as part of Jerasure, and HDP codes[10] and EVENODD[11] as notable but patented. If $k+m+2$ is prime, then X-Codes[12] are also optimal.

允許掛三顆的則是提到 STAR coding：

$m=3$ can be done via STAR coding

算是留個記錄好了，這些演算法又讓我想到先前剛進 Migo 的時候還學到 Raptor code，但使用場景不對反而遇到問題，又是另外一個故事了...

回到開頭的 Reed-Solomon，會印象很深還是因為當初在數學系的集合論學了 finite field 好幾年後，在資工系第一次看到居然可以用 finite field 解決這個問題...

這篇稍微偏 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

Tag: finite

RAID6 的 Erasure code 實作

Perl 的 Regular Expression 的強度：NP-complete