JavaScript 上的 fuzzy search library

Hacker News Daily 上看到 Show HN (作者自己或是主要的 contributor 上來發表的作品) 給了一個號稱速度很快,吃資源很少的 fuzzy search library:「Show HN: uFuzzy.js – A tiny, efficient fuzzy search that doesn't suck (github.com/leeoniya)」。

這種已經發展許久,但突然有一天有人說他的東西超好超棒棒的,除非是有新的基礎演算法突破,不然馬上就會想到很經典的「Three circles model」,中間的那些區塊就懶的畫上去了:

依照他的「測試」,可以看到他宣稱完全領先的狀態:

但回過頭來看評論:

Thank you for this!

I am also quite frustrated with the current state of full text search in the javascript world. All libs I've tried miss the most basic examples and their community seems to ignore it. Will give yours a try but it already looks much better from the comparison page.

Edit: Nope, your lib doesn't seem to handle substitution well (THE most common type of typo), so yep, we are back to square one ...

From fuzzy search I expected that entering "super meet boy" or "super maet boy" will return "Super Meat Boy" but unfortunately currently it doesn't work this way and it's quite disappointing.

https://leeoniya.github.io/uFuzzy/demos/compare.html?libs=uF...

看起來這個 library 沒有辦法解決 fuzzy search 最常見的 case (小 typo),依照範例描述的更像是 substring 搜尋加上一些額外的的功能,反而比較像是 auto completion library,或是講的比較廣一點,可以算是 auto suggestion library。

不過我覺得真正的重點 (對我來說的重點) 是下面的比較表格,因為列出了目前市場上的方案,這份清單之後可以拿來參考...

PHP 8.2 預計要將一些字串內指定變數的方法標為 Deprecated,在 9.0 移除

Twitter 上看到這個蠻大的改變:

裡面的連結是「PHP RFC: Deprecate ${} string interpolation」,在文件中提到了 PHP 語言支援的四種字串內指定變數的方式:

  1. Directly embedding variables (“$foo”)
  2. Braces outside the variable (“{$foo}”)
  3. Braces after the dollar sign (“${foo}”)
  4. Variable variables (“${expr}”, equivalent to (string) ${expr})

提案在 PHP 8.2 裡將 3 與 4 兩種方式標為 deprecated,並且在 PHP 9.0 移除,目前看起來是 31:1 通過了...

SQLite 目前在規劃的 Strict Table,以及我從來不知道原來可以這樣惡搞...

Hacker News Daily 上看到「STRICT Tables」這篇,在講 SQLite 目前在規劃 strict table,對應的討論可以參考「Strict Tables – Column type constraints in SQLite - Draft (sqlite.org)」這邊。

我在 draft 文件開頭看到這個驚人的事實:轉型失敗的時候會直接寫進去,不是錯誤或是 0 或是 NULL 之類的值 XDDD

For example, if a table column has a type of "INTEGER", then SQLite tries to convert anything inserted into that column into an integer. So an attempt to insert the string '123' results in an integer 123 being inserted. But if the content cannot be losslessly converted into an integer, for example if the input is 'xyz', then the original string is inserted instead. See the Datatypes In SQLite document for additional information.

實際上測試建了一個表格測試:

SQLite version 3.31.1 2020-01-27 19:55:54
Enter ".help" for usage hints.
sqlite> CREATE TABLE a (id INTEGER PRIMARY KEY NOT NULL, col1 INTEGER);
sqlite> INSERT INTO a (id, col1) VALUES (1, 'a');
sqlite> SELECT * FROM a;
id          col1      
----------  ----------
1           a         

我果然跟 SQLite 不熟...

YAML 的問題 (挪威問題)

Hacker News 首頁上看到的,YAML 寫多的人都遇過類似的問題:「The Norway Problem - why StrictYAML refuses to do implicit typing and so should you」,對應的討論「The Norway Problem (hitchdev.com)」也可以看一下。

第一個「經典」是字串不需要包起來就很容易出事,這邊提到的例子是因為保留字而中槍,挪威的簡碼 NO 變成 False 了:

countries:
- GB
- IE
- FR
- DE
- NO
>>> from pyyaml import load
>>> load(the_configuration)
{'countries': ['GB', 'IE', 'FR', 'DE', False]}

同樣的是字串問題,「看起來」是數字的就會變成數字:

python: 3.5.3
postgres: 9.3

然後還是字串,人名遇到保留字:

first name: Christopher
surname: Null

這種問題都是碰過一次學一次...

作者另外提到的 StrictYAML 改變了 YAML 規格,我會看看就好,能用 JSON 也許還是會偏好先用 JSON,不是完全解決,但踩雷的機率會少很多。

PostgreSQL 的 Fuzzy Matching

在「Fuzzy Name Matching in Postgres」這邊看到 PostgreSQL 下怎麼設計 Fuzzy Matching 的方式,文章裡用的方法主要是出自 PostgreSQL 的文件:「F.15. fuzzystrmatch」。

文章最後的解法是 Soundex + Levenshtein

翻了一下資料,這個領域另外有 NYSIIS (New York State Identification and Intelligence System):

The New York State Identification and Intelligence System Phonetic Code, commonly known as NYSIIS, is a phonetic algorithm devised in 1970 as part of the New York State Identification and Intelligence System (now a part of the New York State Division of Criminal Justice Services). It features an accuracy increase of 2.7% over the traditional Soundex algorithm.

以及 Metaphone

Metaphone is a phonetic algorithm, published by Lawrence Philips in 1990, for indexing words by their English pronunciation. It fundamentally improves on the Soundex algorithm by using information about variations and inconsistencies in English spelling and pronunciation to produce a more accurate encoding, which does a better job of matching words and names which sound similar. As with Soundex, similar-sounding words should share the same keys. Metaphone is available as a built-in operator in a number of systems.

不過這些都是以英文為主,中文的沒特別翻到...

User-Agent 的淘汰提案

看到廢除更新 User-Agent 字串的提案:「Intent to Deprecate and Freeze: The User-Agent string」。

一方面是 User-Agent 裡面太多沒用的假資料 (像是每一家都是 Mozilla),另外 User-Agent 會帶出一些隱私問題 (辨識資訊)。

目前的提案是希望改用 User-Agent Client Hints (UA-CH) 取代 User-Agent 的功能,把預定義好的東西透過對應的 HTTP header 傳遞。

Chromium 的計畫是在 M81 (stable 版預定在 2020 年三月中釋出) 先 deprecate navigator.userAgent,所以有存取時 web console 上會出現警告。而 M83 (2020 年六月初) 則是不再更動 user agent 字串 (鎖住)。到了 M85 (2020 年九月中) 則是統一 desktop 的 user agent 字串,並且盡可能統一 mobile 上的字串。

另外裡面也有整理了其他瀏覽器的意願:

Edge: Public support

Firefox: Public support for freezing the UA string - “freezing the User Agent string without any client hints—seems worth-prototyping”

Safari: Shipped to some extent. Safari has attempted to completely freeze the UA string in the past, without providing an alternative mechanism. That got a lot of pushback, which resulted in somewhat reverting that decision. Nowadays, their UA string seems frozen, other than updates to the OS version and the browser major version.

雖然不是完全都同意,但看起來應該有機會在今年陸陸續續搞定...

超快速的 Base64 encoding/decoding 實做

看到「Base64 encoding and decoding at almost the speed of a memory copy」這個,可以超級快速編解碼 Base64 的資料。

實做上是透過 IntelAVX-512 加速,在資料夠大的情況下 (超過 L1 cache 的大小),可以達到接近字串複製的速度 (這邊提到的 memcpy()):

We show how we can encode and decode base64 data at nearly the speed of a memory copy (memcpy) on recent Intel processors, as long as the data does not fit in the first-level (L1) cache. We use the SIMD (Single Instruction Multiple Data) instruction set AVX-512 available on commodity processors. Our implementation generates several times fewer instructions than previous SIMD-accelerated base64 codecs.

不過這樣 AMD 暫時要哭哭...

JSON Canonicalization

這篇是講 JSON object 上的簽名,但實際上就是在討論 JSON Canonicalization 的前因後果:「How (not) to sign a JSON object」。

在處理 JSON 資料時,「判斷兩個 JSON object 是否相同」是一個不怎麼簡單的問題,其中一個想法是找一個機制可以把意義相同的 JSON object 都轉成相同的 (byte)string representative,這也就是 JSON Canonicalization。當你可以確保意義相同的 JSON Canonicalization 後,你就可以對 string 本身簽名。

這件事情其實在 XML 就有過同樣的歷史故事 (yeah,總是有人愛在某種資料格式上面疊上簽名),也就是「XML Signature」這個方式。

在 XML 這邊不幸的是,還不少標準選用 XML Signature,像是當年為了實做 Google Apps (現在叫做 G Suite) 的 SSO,而需要接 SAML...

回到原來的 JSON Canonicalization,可以馬上想到的變化包括了空白與 object 裡 key 的順序,也就是這兩個:

{"a":1,"b":2}
{
  "b": 2,
  "a": 1
}

但不幸的是,還有 Unicode 來一起亂,也就是下面這個跟上面有相同的意思:

{
  "\u0062": 2,
  "\u0061": 1
}

另外還有其他的地雷是平常不會想到的,如果你因為複雜而決定用 library 來做,那也代表 library 必須面對這些複雜的情境,未必沒有 bug...

所以文章作者在最後面才會請大家不要再來亂了 XDDD

Maybe you don’t need request signing? A bearer token header is fine, or HMAC(k, timestamp) if you’re feeling fancy, or mTLS if you really care.

Canonicalization is fiendishly difficult.

Add a signature on the outside of the request body, make sure the request body is complete, and don’t worry about “signing what is said versus what is meant” – it’s OK to sign the exact byte sequence.

把 HTML 資料都塞到 URL 裡的服務

如標題說的,專案叫做「URL Pages」,是一個把 HTML 的原始碼都放到 url string 裡的服務。服務本身可以在 http://jstrieb.github.io/urlpages 這邊使用。

現在網路上有很多地方可以塞 demo page (像是 GitHub 自己提供的 GitHub Pages),這個方式需要依賴 JavaScript 提供各種轉換機制,應該會有不少 side-effect bug,看起來會有不少技術瓶頸,就當作是個實驗性質的專案來看,真的需要放 demo page 的還是可以隨便找空間放比較簡單,像是前面提到的 GitHub Pages 其實可以直接在 GitHub 的網頁上操作...

在 DOM 操作時的 insertAdjacentElement

看到「Why I'm still using jQuery in 2019」這篇,裡面提到了 jQuery 很多操作上相較於 vanilla javascript 簡單很多,其中一個例子提到了 DOM 操作的 insertAdjacentElement()

el.insertAdjacentElement('afterend', other) undoubtedly works, but $(el).after(other) is actually palatable.

其實我不知道 insertAdjacentElement() 這個功能,我知道的操作都是透過 parentElementfirstChild 在移動位置,然後用 appendChild()insertBefore() 放進去。

跑去 MDN 上查了「Element.insertAdjacentElement() - Web APIs | MDN」後才發現有這個好用的東西:

targetElement.insertAdjacentElement(position, element);

position 的四個變化減少了以前組積木組多了會頭暈的情況。

接下來是研究支援度的問題,才發現可能是因為 Firefox 一直到 48 才支援 (從「Firefox version history」可以看到 48 是 2016 年八月釋出),所以網路上大多數的文章都還是用組積木的方式在介紹 DOM 操作,以避免相容性的問題:

Firefox 48 was released on August 2, 2016 for both desktop and Android.

另外還看到 insert​Adjacent​HTML()insert​Adjacent​Text() 可以用,其中讓我注意到 MDN 上面提到 insert​Adjacent​HTML() 居然是 Firefox 8+?本來以為是 48+ 的誤植,但從 Mozilla 的記錄「Implement insertAdjacentHTML」這邊可以看到,應該是在 Firefox 8 的時候實作的,這樣的話可以當作 insertAdjacentElement() 的替代品 (如果考慮到古早的相容性),只是這邊需要輸入 html string,跟其他操作是是用 element 不太一致...

意外的學到不少歷史故事... @_@