英語版で読む
技術 約6分で読めます

3GBのSQLite FTSを10MBのRust FSTに置き換えたフィンランド語辞書で圧縮率300倍が出た条件

データ構造 検索 全文検索 Rust
いけさん目次

3GBのSQLiteデータベースが10MBのFSTバイナリになった、という数字が派手だった。
ただ、これはSQLiteをFSTに置き換えれば何でも300分の1になる話ではない。

Andrew Quinn氏の元記事を読むと、フィンランド語辞書のデータ形状がFSTにかなり向いていた。
検索対象は実行時にほぼ静的で、キーは大量の語形変化文字列。
しかもフィンランド語は接尾辞がよく繰り返される。

この条件だと、普通の全文検索基盤より、文字列集合そのものを圧縮して検索できるデータ構造のほうが向いている。

tskの問題は前方一致だけでは終わらなかった

対象はTaskusanakirja、略してtskというフィンランド語・英語辞書だ。
入力しながら候補を出すインクリメンタルサーチを持つので、最初は前方一致検索の問題になる。

前方一致ならTrieが素直だ。
文字ごとに枝を辿る木なので、katuやkadunのような語をキーとして持たせれば、入力文字数に比例して候補へ辿れる。
このブログでも以前、検索を速くするデータ構造の記事でTrieや転置インデックスをざっと整理した。

Quinn氏の最初の実装はGo製で、1文字、2文字、3文字の組み合わせをメモ化し、候補数にも上限を置く形だった。
約40万項目なら50MBから60MB程度で収まっていた。

そこでフィンランド語の語形変化が問題になる。
フィンランド語は膠着語で、語根に格語尾、複数、所有接尾辞、接語が重なる。
元記事では、変化形を含めると40Mから60M項目に膨らむと書かれている。

Trieは共通接頭辞を共有できる。
でも、同じ語尾で終わる大量の単語をうまく共有できない。
-ssa-mme-kinのような同じ末尾が何度も出ても、Trieの構造では末尾側の重複が残る。

SQLite FTSは悪手ではなく動く迂回路だった

そこで一度、SQLiteのFTSに寄せている。
SQLite FTS5はSQLiteの仮想テーブルモジュールで、文書集合に対してMATCH検索、前方一致クエリ、フレーズ検索、NEAR、ブーリアンクエリなどを提供する。
公式ドキュメントでも、FTS5は大量の文書から検索語を含むサブセットを効率よく探す機能として説明されている。

tskではこのSQLite FTS版も体感遅延なしで動いた。
問題は配布サイズだった。
一度だけとはいえ、3GBのダウンロードが必要になる。
「古いノートPCでも動くポケット辞書」という製品の制約から見ると、3GBは配布時にそのまま重さになる。

この段階でSQLiteが失敗だったとは言いにくい。
動く検索経路があったから、後でFST版を作るときに比較対象にもなる。
Hacker Newsの反応でも、単純な実装を先に作り、それと照合しながら最適化版を作る話として受け止められていた。

FSTは接尾辞も共有する

Rustのfst crateは、順序付きのバイト文字列の集合やマップを有限状態機械として表す。
docs.rsの説明では、共通の接頭辞と接尾辞を圧縮し、正規表現やレーベンシュタイン距離のオートマトン、辞書順の範囲で検索できるとされている。

Trieとの差は接尾辞の共有だ。
同じ接頭辞を持つ語だけでなく、同じ接尾辞へ落ちる経路も同じ状態としてまとめられる。

flowchart TD
    A["語形変化を展開"] --> B["大量の文字列キー"]
    B --> C["辞書順に並べる"]
    C --> D["FSTを構築"]
    D --> E["共通接頭辞を共有"]
    D --> F["共通接尾辞を共有"]
    E --> G["小さい検索用バイナリ"]
    F --> G

この図だけだと圧縮アルゴリズムに見えるが、FSTは検索用の構造でもある。
gzipのように展開してから検索するのではなく、圧縮された状態機械の上を辿って検索する。

Quinn氏のケースでは、3GBのSQLite FTSデータから10MBのFSTバイナリができた。
数値は元記事で丸められているが、桁としては300倍の削減だ。

条件が揃うと強いが、普通のDBではない

fst crateの制約を見ると、今回の圧縮がどれだけ条件依存か分かる。
キーはバイト文字列で、マップの値は符号なし64ビット整数。
構築時はキーを辞書順に挿入する必要がある。
実行時に頻繁に追加・削除する用途には向かない。

検索時の読み方にも癖がある。
FSTファイルはメモリマップで扱えるので、全体をプロセスのヒープへ載せずに検索できる。
ただし探索はランダムアクセスに近くなるため、遅いディスクやページキャッシュに乗らない状況では不利になる。
SSD前提ならかなり現実的だが、SQLiteの代替DBとして雑に置けるものではない。

今回のtskは、辞書データが実行時に静的で、検索対象キーが大量にあり、同じ語尾が繰り返され、値は定義IDのような小さい参照で足りる。
この組み合わせならFSTの制約がほとんど影響しない。

条件SQLite FTSRust FST
更新INSERTやUPDATEが自然再構築寄り
検索対象文書とトークン順序付き文字列キー
検索機能MATCH、ランキング、スニペットなど接頭辞、範囲、オートマトン検索
データ形状汎用共通の接頭辞と接尾辞が多いほど有利
配布サイズインデックス込みで膨らみやすい条件が合えばかなり小さい

SQLite FTSは文書検索のための部品だ。
ランキング、スニペット、フレーズ検索、NEARのような機能を持つ。
FSTはもっと狭く、文字列集合や文字列マップを小さく持って高速に辿る部品だ。

だから今回の話を「SQLiteは重い」と読むのは違う。
正しくは、文書検索エンジンとしてのFTSを、語形変化キーの静的マップとして使っていたところに、より狭い表現を当てたら一気に縮んだ、という話だ。

形態素解析辞書やオフライン検索の匂いがする

フィンランド語の例は極端に見えるが、「静的な巨大辞書を端末に持たせたい」用途は珍しくない。
形態素解析辞書、IME辞書、スペルチェッカー、オフライン辞書、ブラウザ内検索、CLIツールの補完候補あたりは近い匂いがある。

ただし日本語の辞書でそのまま同じ圧縮率になるとは限らない。
日本語は単語境界、読み、表記揺れ、活用、品詞情報、コスト計算が絡む。
MeCabやSudachiのような形態素解析器ではダブル配列Trieと最小コスト法の組み合わせが定番で、FSTだけで置き換えるというより、どの表をFST化できるかを見る話になる。

逆に、候補キーがすでに列挙済みで、結果がID参照で済み、データ更新がリリース時だけなら試す余地がある。
fst crateの例にも、構築時はストリームでファイルへ書き出し、検索時はメモリマップで読む流れが出てくる。
配布物を1ファイルにしたい辞書系ツールとは相性がいい。

参考