• ダブル配列の静的構築を実装しました

ダブル配列①:単純クエリ編の続き。前回はダブル配列が与えられた上で、指定の単語が辞書に存在するかを判定することをしました。
今回は、ダブル配列の静的(事前にデータが全て与えられている状態)構築を実装してみます。

また、

  • 最適な静的構築が構成できるか調べてみたが、よくわからなかった
  • 動的構築は衝突時の子孫のデータの更新が結構大変

だったので、今回は静的構築に限定します。

Trie木のナイーブ実装

静的構築の場合は、まずTrie木をナイーブなデータ構造で実装してしまいます。

package main

import "fmt"

type codeInt uint8
type vocabulary struct {
    offset    codeInt
    stopIndex codeInt
}

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

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

type TrieTree struct {
    vocabulary
    root *trieNode
}

type trieNode struct {
    code     codeInt
    children *[]trieNode // https://medium.com/veltra-engineering/is-the-golang-slice-a-pointer-or-not-a-pointer-99433f2cea17
}

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

func (t *TrieTree) Add(word string) {
    codes := t.codes(word)
    fmt.Printf("Add: %d\n", codes)
    t.root.traverse(0, codes)
}

func (n *trieNode) traverse(i int, codes []codeInt) {
    fmt.Printf("i: %d, n: %p, n.children: %p\n", i, n, n.children)
    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)
    //fmt.Printf("add node: %p, children: %d\n", &next, len(n.children))
    next.traverse(i+1, codes)
    //fmt.Printf("add node: %p, children: %d\n", &next, len(n.children))
}

細かいポイントですが、goのスライスの扱いにハマりました。

n.children = append(n.children, next)

では動作せず、以下のようにポインタで保持する必要がありました。

*n.children = append(*n.children, next)

これは、スライス自体は構造体で、スライスが保持する配列はポインタであるということに起因しています。
こちらのブログを参考にしました。

ダブル配列の構築

事前に作成したTrie木をベースにダブル配列を構築します。

// -- Double Array --
type indexInt uint8

type doubleArray struct {
    base  []indexInt
    check []indexInt

    vocabulary
}

func NewDoubleArray(t *TrieTree) *doubleArray {
    da := &doubleArray{
        vocabulary: t.vocabulary,
        base:       make([]indexInt, 4),
        check:      make([]indexInt, 4),
    }

    da.build(indexInt(0), t.root)

    return da
}

func (da *doubleArray) build(current indexInt, n *trieNode) {
    fmt.Printf("current: %d\n", current)
    fmt.Printf("base:  %v\n", da.base)
    fmt.Printf("check: %v\n", da.check)

    offset := indexInt(1)
    for !da.acceptable(*n.children, offset) {
        offset++
    }

    da.base[current] = offset
    for _, child := range *n.children {
        next := offset + indexInt(child.code)
        da.check[next] = current + 1
    }

    for _, child := range *n.children {
        next := offset + indexInt(child.code)
        da.build(next, &child)
    }
}

func (da *doubleArray) acceptable(nodes []trieNode, offset indexInt) bool {
    for _, child := range nodes {
        next := offset + indexInt(child.code)
        if len(da.check) <= int(next) {
            da.extend()
        }

        if da.check[next] != 0 {
            return false
        }
    }
    return true
}

func (da *doubleArray) extend() {
    newBase := make([]indexInt, cap(da.base)*2)
    copy(newBase, da.base)

    newCheck := make([]indexInt, cap(da.check)*2)
    copy(newCheck, da.check)

    da.base = newBase
    da.check = newCheck
}

func (da *doubleArray) search(word string) (int, indexInt) {
    current := indexInt(0)

    for i, code := range da.codes(word) {
        next := da.base[current] + indexInt(code)

        fmt.Printf("- search %d to %d\n", current, next)

        if int(next) >= len(da.check) || current != da.check[next]-1 {
            fmt.Printf("- search fail, %v\n", int(next) >= len(da.check))
            return i, current
        }

        current = next
    }

    return len(word), current
}

func (da *doubleArray) Search(word string) bool {
    res, _ := da.search(word)
    return res == len(word)
}

func main() {
    fmt.Printf("\n--------------\nBuildng Tree\n--------------\n")
    voca := "abcde"
    t := NewTrieTree(voca)
    t.Add("ac")
    t.Add("ac")
    t.Add("ace")
    t.Add("ade")
    t.Add("adea")
    t.Add("bae")
    t.Add("bca")
    t.Add("dae")
    t.Add("eee")

    fmt.Printf("\n--------------\nBuildng DoubleArray\n--------------\n")
    da := NewDoubleArray(t)
    fmt.Printf("\n--------------\nSearching DoubleArray\n--------------\n")
    fmt.Printf("base:  %v\n", da.base)
    fmt.Printf("check: %v\n", da.check)
    fmt.Printf("%v\n", da.Search("ace")) // true
    fmt.Printf("%v\n", da.Search("ade")) // true
    fmt.Printf("%v\n", da.Search("dae")) // true
    fmt.Printf("%v\n", da.Search("acb")) // false
}

静的構築のポイントは、現在注目しているノードの子ノードが全て配置できるところを探せばその時点で配置が確定するという点です。

    offset := indexInt(1)
    for !da.acceptable(*n.children, offset) {
        offset++
    }

動的構築の場合は、このようにはうまくいかず、新しい子ノードが配置される際に、すでに配列の値が埋まってしまい配置できないということが起きます。その場合は、衝突処理を行って子孫に波及して再配置を行わなければなりません。(この処理がかなり厄介で挫折しました。)

ちなみに今回の実装では、base配列とcheck配列がサイズの上限に達したら、サイズを2倍にするといったリスト配列の実装を行なっています。

次回

接頭辞検索を実装すれば完成。ここまでできていればもうすぐのはず。