Tag Archives: filter

Elasticsearch 的 CJK Bigram 設定

Elasticsearch 應該是目前大家搜尋引擎的首選了。而且預設的搜尋法不像以前的搜尋引擎,以前的搜尋引擎會把所有的中文字串當作一個 term,基本上是搜不到東西的。

不過偶而還是會出現一些問題,像是這樣:(這是在求職天眼通搜尋「訊力科技股份有限公司」的結果)

會發現出現了「104人力銀行_一零四資訊科技股份有限公司」,這是因為預設的搜尋演算法把中文字一個一個拆開,後面的「科技股份有限公司」八個字也都有出現,前面的「訊」與「力」也都有出現,於是就被拉出來了...

這種方式被歸類為 unigram 類的方式,像是「波音737 MAX」這一段就會被切成「波」、「音」、「737」與「MAX」。這個切法還算不錯,但有不少機會會遇到問題。

如果限制在 Elasticsearch 內建的功能,其實有更好的設定可以用,也就是對 CJK 文字改用 bigram 方式切:「CJK Bigram Token Filter」。

遇到英文數字還是照原來的切法,但遇到中文字 (更正確的說應該是 CJK) 會用 bigram 的方式切,像是搜尋詞「訊力科技股份有限公司」就會被切成「訊力」、「力科」、「科技」、「技股」、「股份」、「份有」、「有限」、「限公」與「公司」,而本來的「104人力銀行_一零四資訊科技股份有限公司」裡面就不會出現「訊力」、「力科」,於是就不會抓錯...

當然還是有更好的演算法,不過大多就需要另外安裝了,而 Elasticsearch 的升級又很容易跟這些另外裝的套件卡住,所以在考慮維護成本下,CJK Bigram Token Filter 應該是首選...

HyperLogLog 與 Bloom Filter

看到 FacebookPresto 裡增加使用 HyperLogLog 計算數量的能力,突然想到常常忘記這兩個拿準確度換速度的資料結構:「HyperLogLog in Presto: A significantly faster way to handle cardinality estimation」。

HyperLogLog (HLL) 是解決 Count-distinct problem 的資料結構,用很少的記憶體就可以給出一個誤差不大的值 (用 1.5KB 的空間處理十億等級的資料,誤差大約在 2%),所以 Presto 利用這個資料結構引進了 APPROX_DISTINCT() 以及其他的函數,就很容易在 L2/L3 cache 裡運算,藉此大幅提昇速度。

Depending upon the problem at hand, we can achieve speed improvements of anywhere from 7x to 1,000x.

先前也提過 Reddit 也用 HLL 統計資料:「Reddit 在處理 Page View 的方式」。

Bloom Filter 也是在處理大量資料的問題,但這個資料結構的功能不太一樣,是給出「有沒有存在」,使用空間與誤差大約是 10 bits per key (1% false positive),另外先前也有提到一些變形,可以提供其他功能。像是「Quotient filter」與「Cuckoo Filter:比 Bloom Filter 多了 Delete」。

擋 mobile.twitter.com 上的廣告

在桌機上面用 mobile.twitter.com 速度比 twitter.com 快很多,所以平常用桌機時都是用 mobile 這個版本在逛,但因為 mobile 版本對 css name 有處理過,使得 uBlock Origin 這類軟體不好處理廣告的部份...

前陣子在日本的時候發現頁面上多了一堆廣告,本來以為是在日本用日本 IP address 才會有所以就沒有太在意,結果回台灣後發現也出現了... 看起來是 css name 又因為改版被改掉而使得原本的規則失效了...

網路上找其他方法看看有沒有方向,結果找到「Block "Promoted Tweets" on mobile.twitter.com · Issue #351 · uBlockOrigin/uAssets」這篇,雖然最後的 commit 還是用 css name 的方式,但在留言處 Jud 提到可以用 Procedural cosmetic filters 中的 XPath 解決:

mobile.twitter.com##:xpath(/html/body//div[@role="article"][.//text()[starts-with(., "Promoted")]])

這條規則不算難懂,先找出 <div role="article"> 的元素,然後判斷下面的節點有沒有文字化開頭後是 Promoted 的字串。

在還沒有更新規則之前,這個拿來擋一擋應該還行... 不過條件寫的有點簡單,可能會有誤判,也許改抓 div 的「Promoted by 」應該會比較好?也就是這樣:

mobile.twitter.com##:xpath(/html/body//div[@role="article"][.//div[text()[starts-with(., "Promoted by ")]]])

就先這樣搞吧...

為什麼我還繼續用 RSS (Feed)

最近在一些地方冒出兩篇文章 (應該是 NuzzelHacker News,放在 tab 上好幾天,不是那麼確定來源...),一篇是最近發的「The Case for RSS」,另外一篇是五月的文章「RSS: there's nothing better」。這邊講的 RSS 比較廣義,不侷限於 RSS {0.91,1.0,2.0},而是包括了各式的 feed,像是後來標準化的 Atom

消息的來源大致分成兩種:

  • 已知的來源:這些人只要有新的文章你就會想看。
  • 未知的來源:你可能也會有興趣的文章。

前者你不會想要漏掉 (你就是想看才會訂啊)。而後者在早期有 Zite 這類用演算法推薦的產品,後來在 Zite 併入 Flipboard 整個爛掉後我就跳去用 Nuzzel (透過好友機制推薦,演算法相對單純)。

Facebook 將這兩者混在一起,讓「已知的來源」未必會出現,而是用演算法包起來並且用 PR 手段混淆:美其名稱為「個人化推薦」,實際上是想辦法讓內容提供者掏錢出來。這點在 Instagram 上也可以看到一樣的作法:把 timeline 打散,用演算法包裝起來,再美其名為「個人化推薦」。

而 RSS reader 可以避免「已知的來源」這塊漏掉。

另外也因為 RSS reader 因為設計的目標就是「有效率的閱讀」而不是「賺錢」,所以大多數都會有「已讀」與「未讀」的功能,這讓你同樣的資訊你不需要讀很多次。

而 RSS reader 容易分群閱讀 (有些 RSS reader 會提供 folder 或是 tag 的功能) 也讓你可以帶著不同的 mindset 看不同群的文章,像是科技類的文章與心靈雞湯文就可以分開。

AWS 裡 Security Group 的條件可以寫註解了...

AWS 裡 Security Group 的條件可以寫註解了:「New – Descriptions for Security Group Rules」。

這讓其他人比較好理解 (尤其不是常見的 port,或是有些特別的 IP address),另外也讓容易失憶的自己知道當初在幹什麼 XDDD

在 Git/Mercurial/Subversion 上 "-" 發生的問題

在「[ANNOUNCE] Git v2.14.1, v2.13.5, and others」這邊看到 - 開頭產生的問題:

These contain a security fix for CVE-2017-1000117, and are released in coordination with Subversion and Mercurial that share a similar issue. CVE-2017-9800 and CVE-2017-1000116 are assigned to these systems, respectively, for issues similar to it that are now addressed in their part of this coordinated release.

這算是老問題了,Git 對應的修正主要是朝 filter input 的方向修正,包括了禁用 - 開頭的 hostname,以及禁止 GIT_PROXY_COMMAND- 開頭,另外是禁止開頭是 - 的 repository name:

  • A "ssh://..." URL can result in a "ssh" command line with a hostname that begins with a dash "-", which would cause the "ssh" command to instead (mis)treat it as an option. This is now prevented by forbidding such a hostname (which should not impact any real-world usage).
  • Similarly, when GIT_PROXY_COMMAND is configured, the command is run with host and port that are parsed out from "ssh://..." URL; a poorly written GIT_PROXY_COMMAND could be tricked into treating a string that begins with a dash "-" as an option. This is now prevented by forbidding such a hostname and port number (again, which should not impact any real-world usage).
  • In the same spirit, a repository name that begins with a dash "-" is also forbidden now.

然後中華電信的 DNS server (168.95.1.1 & 168.95.192.1) 都查不到 marc.info,改用 Google 的 8.8.8.8 才查得到... =_=

Quotient filter

之前有提過「Cuckoo Filter:比 Bloom Filter 多了 Delete」,最近在「A general purpose counting filter: making every bit count」這邊看到 Quotient filter,也是類似 Bloom filter 的資料結構,但想要解決更多問題。

一般的 Bloom filter (BF) 會有這些問題:

  • The inability to delete items
  • Poor scaling out of RAM
  • The inability to resize dynamically
  • The inability to count the number of occurrences of each item, especially with skewed input distributions.

而文章裡提到的 Quotient filter (QF) 就是要解這些問題。另外還提到了 Rank-and-Select-based Quotient filter (RSQF) 以及 Counting Quotient filter (CQF)。雖然多了一些空間需求,但看起來解掉不少問題... (尤其是刪除的能力)

效能上也還不錯,尤其是讀取速度的部份... 不過不知道相對於 Cuckoo filter 差多少。

Cuckoo Filter:比 Bloom Filter 多了 Delete

在「Cuckoo Filter implementation in Go, better than Bloom Filters」這邊看到這個資料結構,有興趣的人也可以看「Cuckoo Filter:设计与实现」這篇介紹,下面是我抓重點整理。

Bloom Filter 支援的操作:

  • Add(element)
  • Query(element)

1970 年提出來的資料結構。優點是空間複雜度是 O(1),Query(element) 會有可接受的 false positive,缺點是不支援 Delete(element)、以及數量變多時誤判率的增加。

Cuckoo Filter 多了一組操作:

  • Delete(element)

2014 年提出來的資料結構。空間複雜度一樣是 O(1),但相同的空間用量下 false positive 變低,然後支援 Delete(element) 了。也因此論文直接寫「Cuckoo Filter: Practically Better Than Bloom」,表示可以直接替代。