#データ構造

Andrew Quinnのフィンランド語辞書tskで、3GBのSQLite FTSが10MBのRust FSTになった話を読む。前方一致、語形変化、静的データ、接尾辞の共有が揃うと何が起きるか。

辞書引き、全文検索、オートコンプリートなど検索系処理で使われるデータ構造を網羅的に解説する。Trie、ダブル配列、転置インデックス、接尾辞配列、B+木、LSM木など10種類のデータ構造の仕組みと使い分けを整理した。