尋找 O(log(n)) 的 regex associative array || William’s Blog

尋找 O(log(n)) 的 regex associative array

2008 年五月 10 日 (星期六) 2:04 pm
分類：電腦
標籤： programming, regex, 資料結構

Perl 素來以 regular expression（以下簡稱 regex）見長，簡潔，有力。儘管其他語言或程式庫競相學習（像 PCRE、PHP、Java、Python 的 regex 都有很濃的 Perl 風味），但是它們的 regex 並非內建的一等公民，用起來綁手綁腳，總不像 Perl 那麼方便。

Perl 有一個很好用的 grep 函數，可在陣列裡尋找符合 regex 條件的多筆資料：

#!/usr/bin/perl -w

my @data = (
  "Alice",
  "Bill",
  "Bill Clinton",
  "Bill Gates",
  "Hillary Diane Rodham Clinton"
);

@target = grep(/^bil/i, @data);  # 不分大小寫尋找 "bil" 開頭的字串

map {print; print "\n";} @target;

PHP 透過 PCRE 程式庫，也有 preg_grep() 可用。其他語言如果想達到類似效果，又沒有 foreach + functor 之類的 higher-order 組合技，恐怕也只能乖乖的用最原始也最繁瑣的迴圈去湊。

Perl 的 grep 是「用 regex 來找字串」；不過有時候，我們可能需要反過來「用字串來找 regex」。也就是說，給定一筆字串資料，希望能在一整組 n 個 regex 裡，尋找一個能與該字串吻合的 regex，並觸發對應的動作。

至於這 n 個 regex 要存在何處？

最直覺的方法就是擺在 key-value pair 的 associative array 裡（以 Perl 的術語來說：hash，以 C++/Java 術語來說：map，以 Smalltalk/Python 術語來說：dictionary），甚至是 Bloom filter 裡。如果這個 associative array 是以 tree 實作（像 C++ 的 map），效率為 O(log(n))；若是以 hash table 實作，效率甚至可達 O(1)：

#!/usr/bin/perl -w

sub action1 { print "Action #1 triggered.\n"; }
sub action2 { print "Action #2 triggered.\n"; }
sub action3 { print "Action #3 triggered.\n"; }

my %rulebase = (
  /^ali/i => \& action1,
  /^bil/i => \& action2,
  /^car/i => \& action3,
);

my $x = $rulebase{ "Bill" };  # 以 "Bill" 尋找吻合的規則
& $x();                       # 觸發對應的規則

只可惜在 Perl 裡，regex 不能直接當成 key，必須改成字串型式：

my %rulebase = (
  "/^ali/i" => \& action1,
  "/^bil/i" => \& action2,
  "/^car/i" => \& action3,
);

可是如此一來，以下這段程式就失效，永遠也無法配對到合適的 key：

my $x = $rulebase{ "Bill" };  # 以 "Bill" 尋找吻合的規則（但無效！）

必須改用最沒效率的迴圈方式，逐一掃過 n 個 regex。

這真是嚴重的退化呀！效率從 O(log(n)) 退化成 O(n)。

我應該不是第一個有「用字串來找 regex」需求的人。上網查了一下，Tie::RegexpHash、Tie::Hash::Regex 和 Regexp::Match::List 都在處理這類事情，可惜的是，從原始碼來看，內部仍舊是以陣列、迴圈的型式逐一比對 regex，因此效率也都是 O(n)。

有沒有效率接近 O(log(n)) 的 regex associative array 呢？

若以編譯器技術的角度來說，這等於是做一個類似 lex 的 scanner 核心，再針對以下幾點修改：

由 lex 規格 → DFA/NFA 的過程，要 in-memory、run-time 產生。
要做成程式庫的型式。

程式語言 meta-programming 動態特性愈強，愈容易借用現成的 lex 資源拼湊出這種效果（像 Java 強者或許 JFlex + BCEL 三兩下就搞定），但這畢竟還是繞了一個彎，既不雅觀，維護成本也高於原生支援的程式庫。若單以機制而論，C++ 的 Boost.Spirit 另闢蹊徑，最接近我想要的效果，但限制頗多，語法更是難以恭維。

有沒有效率接近 O(log(n)) 的 regex associative array 呢？

如果應用對象只鎖定在 URL 字串身上，而不是任意字串，那麼，Adblock Plus 的兩階段取巧法門頗有可觀之處：

不過，這種取巧法門的整體表現，高度取決於 “shortcut” 的優劣：

需要處理 “shortcut” 的碰撞問題。
不適用於較複雜的 regex。
不適用於充滿 character class 以及 operator 的 regex。

所以，即使應用對象只鎖定在 URL 字串，變因仍然很大；遑論一般化的可能性。

有沒有效率接近 O(log(n)) 的 regex associative array 呢？

看樣子，還需要繼續尋找這樣的資料結構呀……

◤建議您一併閱讀以下文章：

著作授權方式：Creative Commons 條款。

追蹤留言回應：以 RSS 2.0 方式。
文章永久網址：
» http://william.cswiz.org/blog/archives/2008-05-10/regex-associative-array/
引用通告 (trackback)：
» http://william.cswiz.org/blog/archives/2008-05-10/regex-associative-array/trackback/

本站歡迎您以合乎創用CC 的方式，將文章選錄至網路書籤或社群網站，也別忘了將您寶貴的意見（尤其是延伸的評論、補充、彙整、反駁等）留言在本站。謝謝！

8 項留言回應給 “尋找 O(log(n)) 的 regex associative array”

1 Thinker 留言：
2008 年五月 10日於 7:02 pm
FYI,
http://heaven.branda.to/~thinker/GinGin_CGI.py/show_id_doc/320
2 單中杰留言：
2008 年五月 11日於 7:16 am
Perl 的 grep 與 Unix 的 grep 不同，與 regex 沒有直接關係，只是在一個 list 中選取符合任意條件的元素罷了，相當於許多其他語言稱之為 filter 的功能。

print join(",", grep { 123 % $_ == 0 } 1..123), "\n";
1,3,41,123

所以應該沒有什麼 O(log(n)) 的效率可言。更何況 Perl 根本沒有做到 regex 的基本算法，所以就算是拿單一字串配對單一 regex 都可能花費 exponential time。

要是 Perl 有做到 regex 的基本算法的話，就可以於 runtime 把許多要配對的 regex 組合成一個 regex 再進行配對，以達成優於 O(n) 的效率。
3 william 留言：
2008 年五月 11日於 9:44 am
@Thinker：謝謝！的確是我想探討的事。

@單中杰：Perl 的 grep 的確與 Unix 的 grep 不同，但你所提供的文獻卻令我驚訝。

兩個問題需要再檢討：
1. Perl6 是否有改進？
2. Java 的 Pattern.compile() 是否真的有在內部轉換成 FA？
4 小影留言：
2008 年五月 11日於 1:01 pm
這篇論文有講過…

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

http://swtch.com/~rsc/regexp/regexp1.html
5 jeffhung 留言：
2008 年五月 11日於 7:15 pm
我之前的碰到這個問題的作法很簡單，就是先從 regex 裡抽出 keyword：透過簡單地對 regex 分析，可以抽出「一定要有的 sub string」出來。實際在用時，就先用這個 keyword 過濾，然後才丟給 regex，這樣就可以大量減少 regex 比對的次數。
6 william 留言：
2008 年五月 11日於 8:33 pm
@小影：你列的論文，就是單中杰提出的那篇。

@jeffhung：你提的方法，就是 Adblock Plus 用的方法，差別只在於 “shortcut” 的取法。
7 路人留言：
2008 年五月 12日於 2:16 pm
因為 perl regex 有 back reference，所以它並不等同於 formal language 的 regular expression，也就不等同於 regular language 或 FA。

若限定只接受 FA 可處理的 perl regex，是可以造出一個 FA 來判斷 input string 是否被 n regex or 起來的 FA accept，complexity = O(strlen(input string))。
若不只是判斷 match，還要在 n 個 regex 裡，找到一個能與該字串吻合的 regex，也許也可以做到，不過還要想想就是。

至於 O(log(n)) 感覺是不大可能，要能達到 log，似乎需要一次能讓 search space 減為 1/k 的方法，目前能想到滿足這條件的通常要有 ordered 或 monotonic function 這樣的特性 (想想 binary search or search tree)。FA 似乎沒有這種特性?

順道一提，我猜如果問題是：在 n 個 regex 裡，找所有能與該字串吻合的 regex，complexity 應該會是 O(n)。
想法和上面差不多，當答案可能有 n 個時，似乎不存在一個比 O(n) 還好的描述法來描述答案。若是有 ordered 特性的話，不管答案有幾個，都可以用二個值：上下界來描述答案 (C++ STL 的 equal_range 就是如此)，但 in general regex 似乎沒有更好的改進描述法的特性?
8 william 留言：
2008 年五月 13日於 11:11 am
看起來這問題比我當初設想得更複雜，而且還需要分成兩個子問題：
1. 個別 regex 層次：妥善處理 submatch extraction、backreference。
2. n 個 regex 層次。
以第一個層次而言，我贊成 Russ Cox 的說法：

[...] it would be reasonable to use Thompson’s NFA simulation for most regular expressions, and only bring out backtracking when it is needed. A particularly clever implementation could combine the two, resorting to backtracking only to accommodate the backreferences.

不過這問題相當複雜，Cox 文章之後引發的討論也相當多。

至於第二個層次，如果這個 regex associative array 資料結構只需 batch insert 及 query，不需 update 及 delete，我想短期之內最快的實現方法，還是用 lex 之類的工具產生一個 compile-time 的 skeleton。

不知道 sendmail、spam filter 之類的系統是如何做的？

William’s Blog readings, ideas, feelings, photos, etc. by William Yeh