めでたく今年度から社会人な訳ですが、ここ1年はずっと検索について関わってました。昨年の秋から、Luceneのソースコードリーディング勉強会も社内で開催し、かなり活発に議論される良い勉強会が開けていたと思います。
(業務の上でもかなりクリティカルな問題も解決していたり)

さて、検索関連で避けては通れぬ辞書のデータ構造として、Trie木の実装を今回は紹介したいと思います。その中でも、ダブル配列という方法でgoで実装しました。この実装自体は正直何番煎じだという感じですが、自分で手を動かすことが大事。

Trie木は辞書に登録されている単語の接頭辞を共通して保存しておくことで、効率よく単語を検索するためのデータ構造です。大まかな概要は他のページに譲るとして、これを単純に木構造として実装すると、ノードから次のノードへの探索が、エッジの個数に対して線形になってしまいます。

これをDouble配列という方法をとることで、ノードから次のノードへの探索が高速化されます。

詳しくは有名な解説ブログ情報系修士にもわかるダブル配列に譲ります。

ただ、上で紹介したブログは単語に対する検索のアルゴリズムしか紹介されていません。ダブル配列の構築については、こちらのスライドも見つけましたが、こちらでは貪欲的に配列を詰めていく方法が紹介されていました。

貪欲的でなく最適な構成の作り方はまたの機会としたいと思います。

とにかく、本稿ではダブル配列は情報系修士にもわかるダブル配列の例と同じものが与えられていたものとして、検索するプログラムを書きたいと思います。

package main

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

    offset    uint8
    stopIndex uint8
}

func NewDoubleArray(vocabulary string) *doubleArray {
    return &doubleArray{
        offset:    vocabulary[0],
        stopIndex: vocabulary[len(vocabulary)-1] - vocabulary[0] + 1,
    }
}

func (da *doubleArray) Search(word string) bool {
    current := uint8(0)

    for i := range word {
        code := word[i] - da.offset
        next := da.base[current] + code

        if int(next) >= len(da.check) || current != da.check[next] {
            return false
        }

        current = next
    }

    return true
}

func main() {
    word := "abcde"
    da := NewDoubleArray(word)

    da.base = []uint8{1, 3, 9, 2, 8, 7, 8, 0, 6, 0, 0, 0, 0}
    da.check = []uint8{0, 0, 3, 0, 0, 1, 1, 8, 4, 8, 2, 5, 6}

    println(da.Search("ade")) // true
    println(da.Search("ace")) // true
    println(da.Search("add")) // false
    println(da.Search("ee"))  // false
}

今回は終端文字を特に導入していないので、部分文字列でもヒットしてしまいますが、次回のダブル配列の構成の際に終端文字を導入したいと思います。