動的ウェーブレット行列(dynamic wavelet matrix)

ウェーブレット行列が動的になって帰ってきました

ウェーブレット行列との違い

通常のウェーブレット行列は一度索引を構築すると後から変更することはできませんでした.
動的ウェーブレット行列では,内部のデータ構造として簡潔ビットベクトルの代わりに動的ビットベクトルを使うことで,値のinsert,delete,updateができるようになります.
その変わり,すべての操作にO(log N)がついてしまいます.これは簡潔ビットベクトルではrankやselectが定数時間でできたのに対し,動的ビットベクトルではO(log N)がかかってしまうためです.
insert,delete,updateができること以外は通常のウェーブレット行列と同じなので,可能な操作についてはウェーブレット行列を参照してください.
insert,delete,updateも動的ビットベクトルさえ実装できてしまえばとても単純な操作で実現できます.

insert

ウェーブレット行列のaccessとほとんど同じ操作です.追加したい値のbitを辿りながら索引にいれていきます.
挿入したbitの移り先を求めたいため,動的ビットベクトルにbitを挿入してから次の位置を求めます.
bit_arraysは各行の動的ビットベクトルが入った索引で,begin_oneは各行の0の個数です.詳しくはソースを参照してください.

// cをposに挿入
for (uint64_t i = 0; i < bit_arrays.size(); ++i) {
    const uint64_t bit = (c >> (num_of_bit - i - 1)) & 1;  // cの上からi番目のbit
    bit_arrays.at(i).insert(pos, bit);                     // 移り先を求める前に,挿入する
    pos = bit_arrays.at(i).rank(bit, pos);                 // bitの移り先を求める
    if (bit) {
        pos += this->begin_one.at(i);
    }
    else {
        this->begin_one.at(i)++;                           // 削除したbitが0の場合,1の開始位置が1増える
    }
}

delete

こちらもウェーブレット行列のaccessとほとんど同じ操作です.削除したい値のbitを辿りながら索引から消していきます.
削除するbitの移り先を求めたいため,次の位置を求めてから動的ビットベクトルからbitを削除します.

// posを削除
for (uint64_t i = 0; i < bit_arrays.size(); ++i) {
    uint64_t bit = bit_arrays.at(i).access(pos);       // もとの数値のi番目のbit

    auto next_pos = bit_arrays.at(i).rank(bit, pos);   // bitの移り先を先に求めておく
    bit_arrays.at(i).erase(pos);                       // pos番目の要素をビットベクトルから削除する

    if (bit) {
        next_pos += this->begin_one.at(i);
    }
    else {
        this->begin_one.at(i)--;                       // 追加したbitが0の場合,1の開始位置が1増える
    }
    pos = next_pos;
}

update

deleteの後にinsertをよべばいいです.

その他

ウェーブレット行列では各値の開始インデックスを覚えておくことでrankなどの操作を高速にできていました1が,動的ウェーブレット行列ではできなくなります(たぶん).

ソース

github.com