活動報告。
Rustで簡潔データ構造のライブラリを3つリリースしました。

これらの簡潔データ構造に興味のある方、APIを綺麗に整備してREADMEも分かりやすく書いたつもりですので、是非スターをお願いします✌

SIGMOD 2018の論文を眺めていて、Best PaperのSuRF: Practical Range Query Filtering with Fast Succinct Triesを読んで興味を持ちました。
一致検索も範囲検索も高速にできる省メモリなデータ構造SuRFに関する論文。どうやら簡潔データ構造を使っているらしい。

簡潔データ構造というのは、データサイズが情報理論的下限と同程度に小さく、かつ非圧縮なデータ構造と比肩する高速さを兼ね備えたデータ構造です。
チート級ですが、多くの場合「データの追加や更新には対応してない」などの制約があるため、使う場面は限定されたりします。

SuRFの基礎となるFST (Fast Succinct Trie)というデータ構造も簡潔データ構造なのですが、FSTの基礎にはさらにLOUDSという簡潔データ構造があり、さらにさらにLOUDSの基礎にはFIDという簡潔データ構造があり…
久しぶりに趣味プログラミングする題材としては面白そうだったので、FID -> LOUDS -> FST -> SuRF という順序でSIGMOD 2018 Best Paperのデータ構造を実装することにしました。

プログラミング言語はRustを使いました。Rustは出た当初から興味があったのですが、この機会に手を出すことができました。
簡潔データ構造は省メモリがウリなので、データのメモリ配置が簡素（JavaやLLのように、勝手に実体とそれを指すオブジェクトを構築しない。GCもない）である必要があります。
それができる言語で実用的なのはC, C++, Rustくらいしか思い浮かびませんでしたが、新しいチャレンジとしてRustを使いました。

Rustは良い言語ですね。自分はC, C++の経験はまあまあありますが、Rustは所有権・移動・借用という概念をコンパイル時の制約として取り入れており、C, C++で心の中で気にしていたことがコンパイルで強制されます。
最初はネット上のドキュメントで学び、騙し騙し書いていて、コンパイルを通すのにも難儀しましたが、『プログラミングRust』を1.5周くらい読むとスムーズに書けるようになってきました。

で、FID, LOUDSのライブラリを作ってCrates.io (Rustライブラリのregistry。JavaのMaven, RubyのRubyGemsみたいなやつ)にも登録しました。

その後FST -> SuRFと実装しようと思ってましたが、LOUDSのAPIにちょっと自身が持てず、FSTよりも簡単な応用例としてLOUDSベースのTrieを作ってみました。

そしてGWが明けて力尽き今に至ります。

1~2年ぶりくらいの趣味プログラミングでしたが、案外勘は鈍らないものですね。また時間を見つけてSuRFまで実装したいと思います。