Wavelet Matrix (ウェーブレット行列) を実装してみた
コメント
ウェーブレット木のほうも実装してみたが、ウェーブレット木の世界のスライドに「(ウェーブレット木よりウェーブレット行列を)"常にこちらを利用すべき?"」とあるように、ウェーブレット行列のほうが簡単でいいと思う。ただし追記可能にする場合にウェーブレット木の形で持った方が楽な気がする。
ウェーブレット(木/行列)はまず静的なデータ構造である。つまり初めに与えられたあるデータに対して構築をし、その後そのデータに対してのクエリを処理できる。
これは左右の範囲と上下の値でクエリできるデータ構造だ。2次元の点の集合も表せる。
2次元を表せるのがやはり大きな特徴で、これによってquantileなど有用なクエリができる。
静的であることがたまにキズだ。全ての操作にさらにO(log n)を乗算していいなら、全部動的にすれば動的にもなるとは思う。
実装
今回以下のクエリを実装した。計算量の表記では(n = 要素数, m = アルファベットサイズ, m' = min(n, m) = 最大の相違なる要素の種類数)を用いる。
- access: data[i]にアクセスする。O(log m)
- rank_all: 範囲[l, r)とあるアルファベットaに対して、の中で(x < a, x = a, x > a)であるそれぞれの個数を求める。O(log m)
- select: あるアルファベットvalが(k+1)番目に出現する位置を求める。O(log m log n) (ただしランダムなデータではexpect O(log m)?)
- quantile: ある範囲の中で(k+1)番目に大きいアルファベットを求める。O(log m)
- 優先度付きBFS: ある範囲,上下の中でtopk「出てくる個数が大きいk個列挙する」などを求められる。O(log m m' log m')?。最悪ケースが悪いので使いづらそうだ。
- DFS: ある範囲,上下の中で「最大の/最小の」というもの、例えばrangemaxk「大きい方からk個列挙する」などを求められる。O(min(k log m, m'))?。上界はもう少し下げられると思う。個数kに対してO(k log m)でできるのは心強いので、使えそうだ。
他にintersectというクエリもあるようだが、O(範囲サイズ log m)以外の実装方法がわからなくて実装できなかった。
今回selectはあまり使っていないので、恐らくselectをうまく使うようなクエリもあるのかな?
今回メモリの節約を少しだけ心がけている。もし(n*4*log m)bytesのメモリを使っていいならFullyIndexableDictionaryのselectをO(1)にしてできる。
!まったくVerifyしていないのでかなりの可能性で間違っている!
typedef unsigned int u32; inline int popcount(u32 x) { x = x - ((x >> 1) & 0x55555555); x = (x & 0x33333333) + ((x >> 2) & 0x33333333); return ((x + (x >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; } //(k+1)番目の1の立っている位置(最下位から)を返す //http://graphics.stanford.edu/~seander/bithacks.html#SelectPosFromMSBRank を参考にした inline int select32(u32 x, int k) { u32 a, b, c; int t, s; a = (x & 0x55555555) + ((x >> 1) & 0x55555555); b = (a & 0x33333333) + ((a >> 2) & 0x33333333); c = (b & 0x0f0f0f0f) + ((b >> 4) & 0x0f0f0f0f); t = (c & 0xff) + ((c >> 8) & 0xff); s = 0; s += ((t - k - 1) & 128) >> 3; k -= t & ((t - k - 1) >> 8); //if(k >= t) s += 16, k -= t; t = (c >> s) & 0xf; s += ((t - k - 1) & 128) >> 4; k -= t & ((t - k - 1) >> 8); //if(k >= t) s += 8, k -= t; t = (b >> s) & 0x7; s += ((t - k - 1) & 128) >> 5; k -= t & ((t - k - 1) >> 8); //if(k >= t) s += 4, k -= t; t = (a >> s) & 0x3; s += ((t - k - 1) & 128) >> 6; k -= t & ((t - k - 1) >> 8); //if(k >= t) s += 2, k -= t; t = (x >> s) & 0x1; s += ((t - k - 1) & 128) >> 7; //if(k >= t) s += 1; return s; } //※静的なデータ構造 //constructした後setを何回か呼び、その後buildを呼んだ後にrank,selectが行える struct FullyIndexableDictionary { static const int NOTFOUND = -1; static const int SELECTT_INTERVAL = 32; //SELECTT_INTERVAL >= 32 * RANKT_INTERVAL int length, blockslength, count; vector<u32> blocks; vector<int> ranktable, selecttable0, selecttable1; FullyIndexableDictionary(int len): length(len) { blocks.resize((blockslength = (len + 31) / 32) + 1); } inline void set(int i) { blocks[i / 32] |= 1 << i % 32; } void build() { if(length == 0) { count = 0; return; } ranktable.assign(blockslength + 1, 0); selecttable0.clear(); selecttable1.clear(); int prev0 = 0, prev1 = 0, count0 = 0, count1 = 0; for(int i = 0; i < blockslength; i ++) { ranktable[i] = count1; count1 += popcount(blocks[i]); count0 = 32 * (i + 1) - count1; if(prev1 < (count1+SELECTT_INTERVAL-1) / SELECTT_INTERVAL) selecttable1.push_back(i), prev1 = (count1+SELECTT_INTERVAL-1) / SELECTT_INTERVAL; if(prev0 < (count0+SELECTT_INTERVAL-1) / SELECTT_INTERVAL) selecttable0.push_back(i), prev0 = (count0+SELECTT_INTERVAL-1) / SELECTT_INTERVAL; } ranktable[blockslength] = count1; selecttable1.push_back(blockslength-1); selecttable0.push_back(blockslength-1); count = count1; } inline bool access(int pos) const { return blocks[pos / 32] >> pos % 32 & 1; } inline int rank(int pos) const { //[0..pos)の1の個数 int block_idx = pos / 32; return ranktable[block_idx] + popcount(blocks[block_idx] & (1U << pos % 32)-1); } inline int rank(bool b, int pos) const { return b ? rank(pos) : pos - rank(pos); } inline int rank(bool b, int left, int right) const { return rank(b, right) - rank(b, left); } //O(log n)は重いよねえ。expect O(1) (たぶん) ならできるけど最悪ケースがなあ //あるいはメモリ4*length bytes でO(1)でもできるが template<bool b> int select(int k) const { //(k+1)番目のbの位置 if((b ? count : length - count) <= k) return NOTFOUND; int selecttable_index = k / SELECTT_INTERVAL; int l = (b ? selecttable1 : selecttable0)[selecttable_index], u = (b ? selecttable1 : selecttable0)[selecttable_index + 1] + 1; //ブロックを二分探索 while(l + 1 < u) { int m = (l + u) / 2; ((b ? ranktable[m] : m * 32 - ranktable[m]) <= k ? l : u) = m; } return l * 32 + select32(b ? blocks[l] : ~blocks[l], k - (b ? ranktable[l] : 32 * l - ranktable[l])); } inline int select(bool b, int k) const { return b ? select<true>(k) : select<false>(k); } inline int select(bool b, int k, int left) const { return select(b, rank(b, left) + k); } }; /* WaveletMatrix。たしかにこっちの方が「常に」使うべきな気がする */ inline unsigned int BITMASK(int i) { return (1 << i) - 1; } //※メモリ, 時間はだいたい支配的な部分のみ書く //メモリ: (length * bitsize / 8) bytes struct WaveletMatrix { typedef unsigned long long Val; static const int NOTFOUND = -1; static const Val UNDEFINED = Val(-1); static const int MAX_BITSIZE = 64; int length, bitsize; Val maxval; vector<FullyIndexableDictionary> dicts; vector<int> mids; //追加メモリ: (2 * length * sizeof Val) bytes //時間: bitsize * length * 大きめ void init(const vector<Val>& data) { length = data.size(); maxval = *max_element(data.begin(), data.end()); if(Val(1) << (8 * sizeof Val - 1) <= maxval) bitsize = 8 * sizeof Val; else for(bitsize = 0; Val(1) << bitsize <= maxval; bitsize ++) ; dicts.assign(bitsize, length); mids.assign(bitsize, 0); vector<Val> datacurrent(data), datanext(length); for(int bit = 0; bit < bitsize; bit ++) { int pos = 0; for(int i = 0; i < length; i ++) if((datacurrent[i] >> (bitsize - bit - 1) & 1) == 0) datanext[pos ++] = datacurrent[i]; mids[bit] = pos; for(int i = 0; i < length; i ++) if((datacurrent[i] >> (bitsize - bit - 1) & 1) != 0) dicts[bit].set(i), datanext[pos ++] = datacurrent[i]; dicts[bit].build(); datacurrent.swap(datanext); } } Val access(int pos) const { Val val = 0; for(int bit = 0; bit < bitsize; bit ++) { bool dir = dicts[bit].access(pos); val = val << 1 | (dir ? 1 : 0); pos = dicts[bit].rank(dir, pos); if(dir) pos += mids[bit]; } return val; } int rank(Val val, int left, int right) const { if(val > maxval) return 0; for(int bit = 0; bit < bitsize; bit ++) { bool dir = val >> (bitsize - bit - 1) & 1; left = dicts[bit].rank(dir, left), right = dicts[bit].rank(dir, right); if(dir) left += mids[bit], right += mids[bit]; } return right - left; } int rank(Val val, int right) const { return rank(val, 0, right); } int rank_all(Val val, int left, int right, int& out_lt, int& out_gt) const { if(val > maxval) { out_lt = right - left; out_gt = 0; return 0; } out_lt = out_gt = 0; for(int bit = 0; bit < bitsize; bit ++) { bool dir = val >> (bitsize - bit - 1) & 1; int leftcount = dicts[bit].rank(dir, left), rightcount = dicts[bit].rank(dir, right); (dir ? out_lt : out_gt) += (right - left) - (rightcount - leftcount); left = leftcount, right = rightcount; if(dir) left += mids[bit], right += mids[bit]; } return right - left; } inline int rank_lt(Val val, int left, int right) const { int tmp_lt, tmp_gt; rank_all(val, left, right, tmp_lt, tmp_gt); return tmp_lt; } inline int rangefreq(int left, int right, Val bottom, Val up) { return rank_lt(up, left, right) - rank_lt(bottom, left, right); } //O(bitsize log length) (FID::selectがlog nで最悪の場合) int select(Val val, int k) const { if(val > maxval) return NOTFOUND; static int lefts[MAX_BITSIZE], rights[MAX_BITSIZE]; int left = 0, right = length; for(int bit = 0; bit < bitsize; bit ++) { lefts[bit] = left, rights[bit] = right; bool dir = val >> (bitsize - bit - 1) & 1; left = dicts[bit].rank(dir, left), right = dicts[bit].rank(dir, right); if(dir) left += mids[bit], right += mids[bit]; } for(int bit = bitsize-1; bit >= 0; bit --) { k = dicts[bit].select(val >> (bitsize - bit - 1) & 1, k, lefts[bit]); if(k == FullyIndexableDictionary::NOTFOUND || k >= rights[bit]) return NOTFOUND; k -= lefts[bit]; } return k; } int select(Val val, int k, int left) const { return select(val, k + rank(val, left)); } void quantile(int left, int right, int k, Val& out_val, int& out_k) const { if(right - left <= k) { out_val = UNDEFINED; out_k = NOTFOUND; return; } Val val = 0; for(int bit = 0; bit < bitsize; bit ++) { int count = dicts[bit].rank(true, left, right); bool dir = k < count; val = val << 1 | (dir ? 1 : 0); if(!dir) k -= count; left = dicts[bit].rank(dir, left), right = dicts[bit].rank(dir, right); if(dir) left += mids[bit], right += mids[bit]; } out_val = val; out_k = k; } struct IdxVal { int idx; Val val; IdxVal() {} IdxVal(int i, Val v): idx(i), val(v) {} }; inline Val quantile(int left, int right, int k) const { Val tmp_val; int tmp_k; quantile(left, right, k, tmp_val, tmp_k); return tmp_val; } inline IdxVal quantile_idxval(int left, int right, int k) const { Val tmp_val; int tmp_k; quantile(left, right, k, tmp_val, tmp_k); return IdxVal(select(tmp_val, tmp_k, left), tmp_val); } inline Val maximum(int left, int right) const { return quantile(left, right, 0); } inline Val minimum(int left, int right) const { return quantile(left, right, right - left - 1); } struct Range { int left, right; int bit; Val val; Range(int l, int r, int b, Val v): left(l), right(r), bit(b), val(v) {} }; //O(bitsize min(length, maxval) log min(length, maxval))? //priority_queueではやはり最悪ケースが… //でもランダムで適当(バラけすぎとかが無い)なデータに対しては結構速い template<typename F, typename FOut> int rectbfsk(const F& f, int left, int right, Val bottom, Val up, int k, FOut& out) const { int k0 = k; up = min(up, maxval+1); priority_queue<Range, vector<Range>, F> q(f); q.push(Range(left, right, 0, 0)); while(k && !q.empty()) { Range t = q.top(); q.pop(); if(t.bit == bitsize) { f.pushvalues(out, t, k); }else { int leftcount = dicts[t.bit].rank(false, t.left); int rightcount = dicts[t.bit].rank(false, t.right); if( rightcount - leftcount != 0 && bottom <= ((t.val << (bitsize - t.bit)) | BITMASK(bitsize - t.bit - 1))) q.push(Range(leftcount, rightcount, t.bit + 1, t.val << 1)); if( (t.right - t.left) - (rightcount - leftcount) != 0 && (((t.val << 1 | 1) << (bitsize - t.bit - 1))) < up) { q.push(Range( (t.left - leftcount) + mids[t.bit], (t.right - rightcount) + mids[t.bit], t.bit + 1, t.val << 1 | 1)); } } } return k0 - k; } struct ValCount { Val val; int count; ValCount(Val v, int c): val(v), count(c) {} ValCount() {} }; struct FreqList { inline bool operator()(const Range& x, const Range& y) const { return x.right - x.left < y.right - y.left || (x.right - x.left == y.right - y.left && x.val > y.val); } inline void pushvalues(vector<ValCount>& out, const Range& t, int& k) const { out.push_back(ValCount(t.val, t.right - t.left)); k --; } }; inline int topk(int left, int right, Val bottom, Val up, int k, vector<ValCount>& out) const { return rectbfsk<FreqList,vector<ValCount> >(FreqList(), left, right, bottom, up, k, out); } template<typename F, typename FOut> struct DfsInfo { const F& f; FOut& out; Val bottom, up; DfsInfo(const F& f_, FOut& o, Val b, Val u): f(f_), out(o), bottom(b), up(u) {} }; //O(min(k bitsize, min(length, maxval)))? //minじゃなくてもう少しなめらかな関数で上界得られそうだけど…kつの中で幅に入らない分は共有されるイメージ //でもO(k bitsize)はやはり心強いな。k=1ならO(bitsize)となるわけだし template<typename F, typename FOut> void rectdfsk_dfs(const DfsInfo<F,FOut>& info, int bit, Val val, int left, int right, int& k) const { if(bit == bitsize) { info.f.pushvalues(info.out, val, right - left, k); return; } int leftcount = dicts[bit].rank(left); int rightcount = dicts[bit].rank(right); if(F::MAXF) { if(k > 0 && rightcount - leftcount != 0 && (((val << 1 | 1) << (bitsize - bit - 1)) < info.up)) rectdfsk_dfs<F,FOut>(info, bit+1, val << 1 | 1, leftcount + mids[bit], rightcount + mids[bit], k) if( k > 0 && (right - left) - (rightcount - leftcount) != 0 && (info.bottom <= ((val << (bitsize - bit)) | BITMASK(bitsize - bit - 1)))) rectdfsk_dfs<F,FOut>(info, bit+1, val << 1, left - leftcount, right - rightcount, k) }else { if( k > 0 && (right - left) - (rightcount - leftcount) != 0 && (info.bottom <= ((val << (bitsize - bit)) | BITMASK(bitsize - bit - 1)))) rectdfsk_dfs<F,FOut>(info, bit+1, val << 1, left - leftcount, right - rightcount, k) if(k > 0 && rightcount - leftcount != 0 && (((val << 1 | 1) << (bitsize - bit - 1)) < info.up)) rectdfsk_dfs<F,FOut>(info, bit+1, val << 1 | 1, leftcount + mids[bit], rightcount + mids[bit], k) } } template<bool maxf> struct MinMaxList { enum { MAXF = maxf }; inline void pushvalues(vector<ValCount>& out, Val val, int count, int& k) const { out.push_back(ValCount(val, min(k, count))); k -= min(k, count); } }; template<typename F, typename FOut> int rectdfsk(const F& f, int left, int right, Val bottom, Val up, int k, FOut& out) const { rectdfsk_dfs<F,FOut>(DfsInfo<F,FOut>(f, out, bottom, up), 0, 0, left, right, k); return k; } template<bool maxf> int rectminmaxk(int left, int right, Val bottom, Val up, int k, vector<ValCount>& out) const { return rectdfsk<MinMaxList<maxf>,vector<ValCount> >(MinMaxList<maxf>(), left, right, bottom, up, k, out); } }; ostream& operator<<(ostream& o, const WaveletMatrix::IdxVal& idxval) { return o << "(" << idxval.idx << ": " << idxval.val << ")"; }