Flip4Mac 2.1.1.70

• Added support for Windows Media 9 Advanced playback. • Improved ASX handling. • Improved support for MPEG 4 playback. • Resolved some issues related to 2-pass VBR encoding.

Ignore case with Teminal tab completion

echo "set completion-ignore-case On" >> ~/.inputrc

Opera 推出了中文(chinese)和台灣(taiwanese)的網站 http://tw.opera.com/。

Hash table 是 computer science 常用的一種 data structure。在已知 key 的情況下，可以很快的找到相對應的 value。通常這個 key value 可能是數值，pointer，或是字串；通常字串會經過 hash function 算出一個數字來當作的 key。那如果 key 是 regular expression，當程式在做 lookup 動作時，是拿一串文字去 hash table 找，是否有一個 regular expression 的 key 符合這串文字，並且找出相對應的 value。例如

hash[ "^abc.*$" ] = 1;
print hash[ "abcdef" ]; // output 1

問題可能在於 regular expression 怎麼做 hash function，並且由文字去 lookup 得到相對應的 regular expression 為 key 的 value？ 這個問題蠻難的，不過看到的這個應用，倒是並不會完全都是 regex 特殊字元（像是 ^[a-zA-Z]+$）。應用的例子，可能大家都有在用，就是 Firefox add-ons 的 AdBlock Plus。filter 內有上百個廣告 URL 的 patterns（雖然它只提供 wildcard 字元，但是內部是轉成 regex 來 matching），如果使用者 subscribe 多個 filter list，甚至可以多到上千個吧。當 Firefox 瀏覽一個網頁時，少說幾十個網址需要去跟這幾百個 patterns 做比對。當然最簡單的方式就是，每遇到一個網址，就拿去從頭到尾地把 patterns 拿來作 regular expression 的 matching。當然比到了就是可能 white-list or black-list 裡面的一項，看要阻擋還是放行；沒有比到當然就是放行。Regular expression 實際上在比對時，當然所花費的成本比一般 string compare 高很多。 AdBlock Plus 怎麼做呢？其實說穿了就蠻簡單的，事實上它並不是真的完全拿 regular expression 來做出特殊的 hash function。而是用 regular expression 中內含一般文字，像是 "http://ad*.udn.com/*" 這種（會先轉成 /http:\/\/ad.*\.udn\.com\/.*/ 的 regex 格式供 javascript 比對用），裡面穿插了一些普通的字串。而 AdBlock Plus 它會從中去找出這些特徵（它是從 pattern 後半段去找，因為通常大部分 patterns 前面開頭不是 http:// 就是 *.udn.com/* 這種，從頭找對 URL 似乎沒有好處），並且長度是 8 的特徵字串，像是 ".udn.com"，並且不包含 regular expression 特殊字元（當然可能找出來不只一種，像是 "udn.com/" 也是 8 個字）。然後就拿這段文字當作 key 去存 hash table。之後瀏覽 udn.com 內容，每次做 URL 比對時候，例如 "http://ad1.udn.com/RealMedia/ads/something.gif"，它就從字串的頭開始，取每一段長度 8 的字串出來給 hash table 去找，所以它依序是給 hash table 找了 "http://a", "ttp://ad", "tp://ad1", ... 到了 ".udn.com" 終於在 hash table 中有找到東西，然後當然就把相對應的 regex 拿來比對是不是符合這個 filter pattern。 其實說穿了，前面的問題並沒有解決，如果是這個例子，用上面的做法就非常不適用：

hash[ "[0-9]+" ] = 1;
hash[ "[a-z]+" ] = 2;
hash[ "[A-Z]+" ] = 3;
print hash[ "abc" ];

事實上後面的做法，並不是真的拿 regular expression 去算出 hash 來作 pairing，而只是剛好在 URL filter patterns 上有這種特徵，就是內含部份網址或路徑，也是因為有這些特徵才比較好辨別哪些是正常內容，哪些是廣告才會有的 URL。利用這種特性，剛好去找出裡面的一些 signature 來建立 hash table，用來作為之後比對時加速尋找真正要比對的 patterns，並不是盲目地完全都去一一比較。 Ref 1: Perl Tie::Hash::Regex Match hash keys using Regular Expressions Ref 2: How does Adblock Plus process its filters and which filters are faster?

五一勞動節，放假一天。工程師節(6/6)沒有放假。所以是勞工（字面解釋 XD)。 記得距離上次 patch 才沒多久，這是又準備要 Code Freeze 進 QA cycle，不過沒有準備來得及 resolve，也不太想那麼趕。雖然說上次是 patch，不過我怎麼感覺做的東西是 new item or enhancement，一點都不像 "patch"。