圧縮配列ライブラリyunomiをリライトしました

数年前に圧縮配列を作ってgithubで公開していました。この度そのライブラリを一から書き直してリニューアルしました。

元々圧縮配列ライブラリであることをメインに作っていたのですが、今回のリニューアルで簡潔データ構造のライブラリとしても使えるようになっています。

圧縮配列とは

大量のデータを配列に格納しないといけないとき、あまりにデータが大きすぎてメモリに乗り切らないことはありませんか？圧縮配列は情報を圧縮状態でメモリに格納するためのものです。圧縮されているためそのまま格納するより省メモリですみます。当然通常の配列に比べて速度は落ちますが、ランダム~~アクセス~~リードが可能です。yunomiでは、Kimmo Fredriksson and Fedor Nikitinの論文に記載してあるFibonacciコーディングによる圧縮配列を実装しています。詳細を知りたい方は参考文献に当たってみてください。

簡潔データ構造とは

簡潔データ構造とは、0, 1からなるビットベクトルの様子を調べるためのデータ構造(とアルゴリズム)です。主に2つの関数からなり、rank関数、select関数と呼ばれます。rank関数は、nビット目より前に何個1があるか求めます。select関数はn個目の1がどこに現れているかを求めます。rank/select関数を応用することで、圧縮配列のようなアプリケーションを実装することができます。

なぜ作ったのか

自分で気軽に使える簡潔データ構造のライブラリが欲しかったのです。簡潔データ構造自体はいろいろなOSSで(内部で使うために)実装されていますが、なかなかそれ自体をライブラリ化して切り出したものはあまり見かけません。知っている限りGPLなライブラリはありますが、それを非GPLなプロジェクトで利用するにはハードルが高いです。

なぜリライトしたのか

前述の通り、自分で気軽に使える簡潔データ構造ライブラリが欲しかったのですが、過去に書いたyunomiは簡潔データ構造ライブラリ部分と圧縮配列部分が入り交じっており、簡潔データ構造のライブラリとして使うことはできませんでした。そこで、再設計し、書き直そうと思いました。

以前のコードは数年前に急に思い立って数日間で一気に作り上げたものでした。一応動いてはいましたが、設計が甘く、ユーザー視点では使いにくいライブラリとなっていました。また、テストがほとんど存在しておらず、信頼性の面でも問題がありました。

今回のリニューアルは使いやすさに重点を置き、時間をかけて設計・実装を行いました。 (足かけ半年以上もかかっています。)

加えて今回のリニューアルでは、コードの信頼性に重点を置き、できるだけたくさんのテストを書きました。たぶんほぼすべての関数にテストが存在するはずです。リニューアル前のコードにはテストがほぼ存在しなかったことを考えると大きな進歩です。正直テストのないライブラリを使いたくありませんから。

開発環境

Mac OS X + clangで開発しました。また、同梱したDockerfileによる環境でもテストが通ることを確認しています。

今後やりたいこと

ちゃんとCIする
せっかくテストケースをたくさん書いたのでCIしたいです
旧バージョンとの速度比較
旧バージョンとはいくつかアルゴリズムも変更したところがあります。念のため調べておきたいです。

さいごに

どんな小さなものでもpull requestいただければ飛び上がって喜びます。