作ったもの

トライ木をGraphvizで可視化するものを作りました。

$ brew install graphviz
$ go get github.com/kotaroooo0/mute

$ vi data.txt
$ mute -s data.txt | dot -T png -o sample.png

# data.txt
keynote
keycase
king
kingdom
macbook

keynoteとkeycaseでkeyまで一致しているのが分かります。

遊び方

Trie木を可視化を行う事で、Slackの共通接頭辞大会などしてみてください。あいつとあいつのidいつも間違えそうになるんだよなと再認識したりできます。 Slackのチャンネルで/whoと入力するとメンバーが取得でき、data.txtにコピーしてください。 mute -s data.txt | dot -T png -o sample.pngとすれば、画像が出力されます。

トライ木とは

トライ木は順序付き木の一種です。 trieの名称は"retrieval"が語源です。形態素解析に使われる辞書などに用いられています。

共通接頭辞検索に適したデータ構造であり、時間計算量、空間計算量共に優れています。空間計算量に関しては様々なデータ構造が提案されています。

実装

github.com

主にアルゴリズムの要素があるのは以下の2点です。

トライ木を作成する部分

挿入したい単語長分のループを回し、挿入を行います。すでに接頭辞が一致している場合はさらに一個深いノードへ進んでいくだけで、一致しなくなったら一個深い段階に新しいノードを作成します。

func (n *Node) insert(w string) error {
    runes := []rune(w)
    currentNode := n
    for i, r := range runes {
        if nextNode, ok := currentNode.Children[r]; ok {
            currentNode = nextNode
        } else {
            currentNode.Children[r] = newNode(string(r), make(map[rune]*Node), false)
            currentNode = currentNode.Children[r]
        }

        // 終端にチェック
        if i == len(runes)-1 {
            currentNode.End = true
        }
    }
    return nil
}

トライ木を探索しdotfileを生成する部分

DFSで探索を行いながら、dotfileを生成していきます。 visitAllで再帰的に処理する事でDFSを実現しています。

無名関数で実装することにより、generateDotfile関数で全て完結することができます。無名関数で再帰を行うには、var visitAll func(n *Node)のように宣言することが必須であり、これがないとvisitAllが未定義とコンパイルエラーになります。

例えばに、無名関数で実装せずにグローバルにvisitAll関数を宣言しようとすると、g := gographviz.NewGraph()をグローバル宣言する必要がでてきます。

func generateDotfile(trie *Node, output string) (string, error) {
    g := gographviz.NewGraph()
    g.SetName("G")
    g.SetDir(true)

    var fontSize = "35"
    var visitAll func(n *Node)
    visitAll = func(n *Node) {
        for _, v := range n.Children {
            g.AddNode("G", strconv.Itoa(n.ID), map[string]string{"label": n.getLabel(), "shape": n.getShape(), "fontsize": fontSize})
            g.AddNode("G", strconv.Itoa(v.ID), map[string]string{"label": v.getLabel(), "shape": v.getShape(), "fontsize": fontSize})
            g.AddEdge(strconv.Itoa(n.ID), strconv.Itoa(v.ID), true, nil)
            visitAll(v)
        }
    }
    visitAll(trie)

        // 略    

    return g.String(), nil
}