Panda Noir

JavaScript の限界を究めるブログです。

完備辞書をJavaScriptで実装してみました

d.hatena.ne.jp

ここを見て完備辞書を知り、wikiを見て理解を深めたので実装してみました。

完備辞書とは

完備辞書、またの名を「簡潔索引つき辞書」、「簡潔ビットベクトル」、「rank/select 辞書」、「簡潔辞書」。呼び方が全く統一されていません。そこまで頻出する概念でもないので仕方がないといえばそれまでです。本記事では以下完備辞書で統一します。

完備辞書とは簡潔データ構造*1の一種です。高速で配列にrank()とselect()を実行できます。なんと定数時間で完結します!

rank()とselect()とは

完備辞書が持っているrank(n)とselect(k)はそれぞれ「配列中の[0,n)の範囲の1の数を返す」「配列中のk番目の1の位置を返す」メソッドです。これらを(たとえ長さが10000000の配列でも!)定数時間で行うことができます。

実装

github.com こちらがその実装です。コードを見ると確かに定数時間で行えていることがわかります。

Demo

var FID = require('./fid.js'); // 適当なところに上のサイトのfid.jsを配置してください
var myfid = new FID([0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1]);
var n = 5;
myfid.rank(n); // 3
myfid.select(3); // 4

注意したいのはselect()が返す位置は「配列の添字 + 1」した数字ということです。 変更しました。0.0.2からは配列の添字と同じ数字を返します。

npm

npmにも公開したので npm install fid でインストールできます。

*1:簡潔データ構造とは、あるデータ構造に「サイズの小さい(=簡潔な)」補助データを加えて、高速でそのデータ構造を操作するデータ構造です。