はてなブックマークFirefox拡張, JavaScript で IS 法 による Suffix Array 構築

はてなブックマークFirefox拡張


昨日、はてなブックマークFirefox拡張をリリースしました。おかげさまでベータ版からダウンロード数は累積で1万ダウンロードを突破し、アクティブユーザー数も伸びています。

開発者の id:secondlife が g:subtech:id:secondlife:20090415:1239804170 で技術的な側面からのちょっとした TIPS なども紹介していますので、興味のある方はご一読ください。

検索では思いのほか SQLite の like 検索が高速なのに驚いた。はてブ検索では、検索ワードから URL, Title, コメント にマッチしたものを表示していて、それ専用の search_data だかかんらかの検索用カラムがある。ここにデータ入れるときに全部小文字にして、SQLite のプラグマで case-senstive になるようにしている(SQLite 標準での like は case-insenstive なマッチ)。これで Like 速度が約二倍に。この場合、10 件のデータを引くのに、50000 件のブックマークデータで、前後方一致の like 検索で平均 200ms ぐらい。

に関して裏話的なことを一つ補足します。

ブラウザ上でのブックマークのインクリメンタルサーチは、手持ちのデータによっては比較的大きめの検索をかける必要があったので、計算量の方が少々心配でした。結果としては上記のように現実的な所では SQLite から引くことでカバーできたのですが、別途 Suffix Array を使っての検索を行うことも検討していました。

JavaScript 組み込みのソート関数で Suffix Array を作ろうとすると例によって厳しいので、IS 法で Suffix Array を構築してみることにし、IS 法を使った SA-IS を JavaScript に移植したライブラリを id:tarao が作りました。この実装は github にあるはてなブックマークFirefox拡張のソースコードに含まれています。

現時点までの実装では、Suffix Array の構築に 1.4Mbytes くらいのデータ (naoya のブックマーク, 約 ブックマーク7,000件) で組み込みのソートだと 430MB のメモリを消費するところ、SA-IS 移植版で 50MB に抑えられています。計算時間的には数百k のデータで組み込みソートより速度が逆転します。10Mbytes くらいのデータ (約6万件程度) では組み込みソートでは開発機(ThinkPad X40) で計算不可能、SA-IS 移植版でメモリ消費 500MB、構築までに 139 sec くらいでした。

当初の予定では、ブックマークに更新がかかったらバックグラウンドで定期的に Suffix Array を構築しなおして、インクリメンタル検索は Suffix Array を使うオプションを用意することを考えていましたが、今のところは組み込んでいません。プロトタイプ開発で止まっています。Suffix Array 構築には CPU で結構な計算をするので、その間 PC に負荷がかかり続けるというのが一つ課題です。この辺り、エンジニアリング的には結構面白い課題だと思います。

Firefox拡張開発までの経緯などほかの裏話は、また折を見て書いてみようかなと思います。