crit-bit 木 (その1)

D. J. Bernstein (以下 djb) が 2006 年に発表した crit-bit 木 はビット列用のwikipedia:基数木で、 二分木になっています。 djbqhasm に C 言語で記述したソースコードが入っています。 葉にビット列を保持し、 節はビット位置を持ちます。 節のビット位置は、 その位置にゼロを持つビット列と、 その位置に1を持つビット列の両方が木に含まれていることを表しています。 ビット値が異なるビットのことを、 critical bit、 略して crit-bit と名付けます。 crit-bit のビット位置を節にした二分木が crit-bit 木です。

例えば、 次の3つの文字列をゼロ終端 ASCII エンコーディングでビット列にすると、 crit-bit は 25 ビット位置と 29 ビット位置の 2 つになっています。

           0                        25  29  ビット位置
                                    v   v   crit-bit
'xyz`'  => '01111000011110010111101000000000'
'xyza' => '0111100001111001011110100110000100000000'
'xyze' => '0111100001111001011110100110010100000000'
           --------........--------........

これを木にします。 この木にはいくつか特徴があり、 ビット列は葉になり、 行きがけ順で葉が辞書順に並びます。 同じ接頭辞をもつ葉が部分木にまとまります。 左端の葉は最小で、 右端の葉が最大になります。

('xyz' 25 ('xyza' 29 'xyze'))

ビット位置からいちいちバイト位置とビット・マスクを計算するのはわずらわしいので、 それらの組を節に持たせることにします。 child は 2 個の要素をもつ配列とし、 crit-bit がゼロのときと、 1 のときのそれぞれの子を参照します。

削除の記述を簡潔にするため、 根をダミー節のゼロ側の子につなぎます。 ダミー節の 1 側の子は nil です。

module Critbit
  class Node
    attr_accessor :child, :offset, :bitmask

    def initialize(child, offset, bitmask)
      @child, @offset, @bitmask = child, offset, bitmask
    end
  end

  class Tree
    def initialize
      @top = Node.new([nil, nil], 0, 0)
    end

    def root() @top.child[0] end

#@< 木にビット列が含まれているかどうかを調べます@>
#@< 接頭辞を持つビット列を列挙します@>
#@< 木にビット列を追加します@>
#@< 木からビット列を削除します@>
  private
#@< ビット列の crit-bit を辿って、 葉の直上の節を求めます@>
#@< ビット列から節で示した crit-bit のビット値を抜き出します@>
#@< 2つのビット列の最初の crit-bit のビット位置を求めます@>
  end
end

節には、 1 ヶ所が 1 になっているビット・マスクと、 それを当てはめるべきバイト位置が記録してあります。 ビット・マスクとバイト位置の組でビット位置を表しているわけです。 なお、 djb はビット反転したもの (例: 0b11111011) をビット・マスクに使っていますが、 ここでは反転せずに (例: 0b00000100) そのままにしています。

#@< ビット列から節で示した crit-bit のビット値を抜き出します@>=
    def direction(key, node)
      ((key.getbyte(node.offset) || 0) & node.bitmask) == 0 ? 0 : 1
    end

木には crit-bit のビット・パターンが記録してあるだけなので、 指定したビット列が木に含まれているかどうかを調べるときは、 ビット列の crit-bit パターンが途中まで一致する葉を求めて、 葉とビット列が一致するかどうかを判定します。 assoc_tree は key と crit-bit のビット・バターンが一致する葉を求めます。 葉を直接返すのではなく、 節 r の rside が葉になっている節を返します。 さらに、 節 r の親の節 q も返します。 このようになっているのは、 削除メソッドから assoc_tree を切り出した名残りです。

#@< 木にビット列が含まれているかどうかを調べます@>=
    def member?(key)
      assoc_tree(key) {|q, qside, r, rside| r.child[rside] == key }
    end

木が空のときは、 根を nil にしてあります。 また木にビット列が一つしかないときは、 根はビット列になっています。 複数のビット列を含んでいるときは、 根は節になります。 根の左右は、 根かまたはビット列であって、 nil になることはありません。

#@< ビット列の crit-bit を辿って、 葉の直上の節を求めます@>=
    # result: q.child[qside] -> r.child[rside] -> leaf  when the tree is not empty
    #         q.child[qside] -> nil && r.child[rside] -> nil  when the tree is empty
    def assoc_tree(key)
      q, qside = @top, 0
      r, rside = @top, 0
      if not r.child[rside].nil?
        while Node === r.child[rside]
          q, qside = r, rside
          r = r.child[rside]
          rside = direction(key, r)
        end
      end
      yield q, qside, r, rside
    end

ある節のビット位置は、 その節を頂点とする部分木の中で、 最小になっています。 この性質を利用することで、 木の中に含まれている共通の接頭辞をもつビット列を列挙することができます。 接頭辞の crit-bit のビット・パターンに一致する葉を求めて、 葉が接頭辞で始まっていることを調べておきます。 その後に、 接頭辞にビット・パターンが一致する節を頂点として、 部分木中の全部の葉を行きがけ順で列挙します。

#@< 接頭辞を持つビット列を列挙します@>=
    def each_prefix(prefix)
      not @top.child[0].nil? or return self
      node = @top.child[0]
      if not prefix.empty?
        q = node
        while Node === q
          side = direction(prefix, q)
          node = q.child[side] if q.offset < prefix.bytesize
          q = q.child[side]
        end
        (0 ... prefix.bytesize).all? {|i| q.getbyte(i) == prefix.getbyte(i) } or return self
      end
      stack = []
      while true
        while Node === node
          stack.push node.child[1]
          node = node.child[0]
        end
        yield node
        not stack.empty? or break
        node = stack.pop
      end
      self
    end

ビット列の削除は簡単です。 crit-bit のビット・パターンが一致する葉を求め、 その葉がビット列に一致するときに、 木から取り除きます。 根をダミーの節につないであり、 ダミーの節の 1 側の子を nil にしているため、 木が空になるとき、 自動的に根が nil になってくれます。

#@< 木からビット列を削除します@>=
    def delete(key)
      assoc_tree(key) {|q, qside, r, rside|
        if key == r.child[rside]
          q.child[qside] = r.child[1 - rside]
        end
      }
      self
    end

ビット列の挿入は、 まず crit-bit のビット・パターンに一致する葉を求めることから始めます。 葉とビット列の最初の crit-bit を探して、 そのビット位置を持つ節を作ります。 そして、 その節を木の適切な位置に挿入します。 このロジックを自分で考えるのは面倒で、 djb のやりかたをそのまま真似するのが一番です。 といっても、 元のコードは C 言語で、 節の子ポインタへの参照を使う書き方になっているので、 ruby に直訳できません。 同じ意味になるように、 アレンジして下のようにしておきました。 ところで、 ビット・マスクの大小比較が元の djb の C 言語版の逆になっています。 この理由は、 ビット位置を LSB 側が大きくなる順に付けるためです。 ビット・マスクをビット反転すると、 ビット・マスクが大きい方がビット位置も大きくなります。 ここの版はビット・マスクをビット反転していないので、 ビット・マスクが小さい方がビット位置が大きくなるのです。 djb がわざわざビット反転したのは、 ここの大小関係の比較の初見の違和感をなくすのが理由の一つなのかもしれません。

#@< 木にビット列を追加します@>=
    def insert(key)
      leaf = assoc_tree(key) {|_1, _2, r, rside| r.child[rside] }
      if leaf.nil?
        @top.child[0] = key
        return self
      end
      node = find_critical_bit(leaf, key) or return self
      q, qside = @top, 0
      while Node === q.child[qside]
        r = q.child[qside]
        # meanings: not (r.bitoffset > node.bitoffset) or break
        # note: bit offset in a byte: MSB => 0 .. LSB => 7
        not (r.offset > node.offset) or break
        not (r.offset == node.offset && r.bitmask < node.bitmask) or break  #! 2018-06-21 fix
        q, qside = r, direction(key, r)
      end
      side = direction(leaf, node)
      node.child[1 - side] = key.dup
      node.child[side] = q.child[qside]
      q.child[qside] = node
      self
    end

crit-bit のビット位置の求め方も djb を真似ています。 バイト単位で共通の接頭辞を読み飛ばします。 完全に一致するときは、 nil を返します。 そうでないときは、 最初の異なるバイト同士のビットごとの排他的論理和を求めます。 その際、 ビット列の長さが足りないときは、 ゼロのビットが無限に後ろに続いているとみなします。 これの MSB 側を 1 つだけ残し、 他の LSB 側をすべてゼロにすることで、 ビット・マスクにします。

#@< 2つのビット列の最初の crit-bit のビット位置を求めます@>=
    def find_critical_bit(s1, s2)
      offset = 0
      while offset < s2.bytesize && s1.getbyte(offset) == s2.getbyte(offset)
        offset += 1
      end
      if offset == s1.bytesize && offset == s2.bytesize
        nil    # same string
      else
        bitmask = (s1.getbyte(offset) || 0) ^ (s2.getbyte(offset) || 0)
        bitmask |= bitmask >> 1
        bitmask |= bitmask >> 2
        bitmask |= bitmask >> 4
        bitmask &= ~(bitmask >> 1)
        Node.new([nil, nil], offset, bitmask)
      end
    end