LOUDSとは、木構造をビット列でメモリ効率よく表現したデータ構造で、Trie木の表現に利用されています。

Trie木のルートにさらに親ノードを追加(スーパールートと呼ばれる)し、スーパールートから幅優先探索を行います。
各ノードで、子ノードの数だけ1を並べて、末尾に0を追加します。

そうして得られるビット列を LBS (LOUDS bit-string) と言います。

詳細は有名なブログに譲ります。

ビットベクトル構築

ここでは、まずTrie木からビットベクトルを構築するところまでの実装をします。

package main

import (
    "fmt"
    "math/bits"
)

type codeInt byte
type vocabulary struct {
    stopIndex codeInt
}

func newVocabulary(voc string) vocabulary {
    return vocabulary{
        stopIndex: codeInt(voc[len(voc)-1] + 1),
    }
}

func (v *vocabulary) codes(word string) []codeInt {
    codes := make([]codeInt, len(word)+1)
    for i := range word {
        codes[i] = codeInt(word[i])
    }
    codes[len(word)] = v.stopIndex
    return codes
}

type TrieTree struct {
    vocabulary
    root *trieNode
}

type trieNode struct {
    code     codeInt
    children *[]trieNode
}

func NewTrieTree(voc string) *TrieTree {
    return &TrieTree{
        vocabulary: newVocabulary(voc),
        root:       &trieNode{children: &[]trieNode{}},
    }
}

func (t *TrieTree) Add(word string) {
    codes := t.codes(word)
    t.root.traverse(0, codes)
}

func (n *trieNode) traverse(i int, codes []codeInt) {
    if i == len(codes) {
        return
    }

    for _, child := range *n.children {
        if child.code == codes[i] {
            child.traverse(i+1, codes)
            return
        }
    }

    next := trieNode{code: codes[i], children: &[]trieNode{}}
    *n.children = append(*n.children, next)
    next.traverse(i+1, codes)
}

// ----- LOUDS -----

type lbsBlock uint8

const lbsOffsetMax = 8

type lbs struct {
    blocks []lbsBlock
    offset uint
}

func (l *lbs) add(b byte) {
    if l.offset == lbsOffsetMax {
        l.blocks = append(l.blocks, lbsBlock(b))
        l.offset = 1
    } else {
        if b == 1 {
            l.blocks[len(l.blocks)-1] += lbsBlock(1 << l.offset)
        }
        l.offset += 1
    }
}

type Louds struct {
    lbs  *lbs
    char []codeInt
}

func (l *lbs) String() (res string) {
    for i := 0; i < len(l.blocks); i++ {
        tmp := fmt.Sprintf("%08b", bits.Reverse8(uint8(l.blocks[i])))
        if i == len(l.blocks)-1 {
            tmp = tmp[:l.offset]
        }
        if len(tmp) == 8 {
            tmp += "|"
        }
        res += tmp
    }
    return
}

func (l *lbs) extend() {
    next := make([]lbsBlock, cap(l.blocks)*2)
    copy(next, l.blocks)
    l.blocks = next
}

func (l *Louds) extendChar() {
    next := make([]codeInt, cap(l.char)*2)
    copy(next, l.char)
    l.char = next
}

func NewLouds(t *TrieTree) *Louds {
    l := &Louds{
        lbs: &lbs{ //[1,0]
            offset: 2,
            blocks: []lbsBlock{1},
        },
        char: []codeInt{0},
    }

    q := []trieNode{*t.root}
    for len(q) > 0 {
        n := q[0]
        fmt.Printf("%d, %s\n", n.code, string(n.code))
        q = q[1:]
        l.char = append(l.char, n.code)

        for _, c := range *n.children {
            l.lbs.add(1)
            q = append(q, c)
            fmt.Printf("%v, %b\n", l.lbs, l.lbs.blocks)

        }
        l.lbs.add(0)
        fmt.Printf("%v, %b\n", l.lbs, l.lbs.blocks)

    }

    return l
}

func main() {
    voca := "abcdefghijklmnopqrstuvwxyz"
    t := NewTrieTree(voca)
    t.Add("bo")
    t.Add("bit")
    t.Add("big")
    t.Add("bite")
    t.Add("an")
    t.Add("and")
    t.Add("ant")

    fmt.Printf("\n--------------\nBuildng DoubleArray\n--------------\n")
    louds := NewLouds(t)
    fmt.Printf("%b\n", louds.lbs.blocks)
}

今回の実装ではLBSは8ビット整数の配列とオフセット(配列の最終要素は現在何ビットまで保持しているかの情報)で表現しています。(実用上は64ビットを使ったほうが効率良いと思われるが、デバッグのしやすさのために8ビット整数を使っています)

構築までは、幅優先探索を行うだけなのでそこまで難しくありませんでした。LBSを用いてノードの探索を行う必要がありますが、そのためには、このLBS上である演算が必要になります。

その演算を効率よく行うためには、簡潔ビットベクトルというデータ構造を用いる必要があります。次回は、簡潔ビットベクトルを実装していきたいと思います。