Go で DoubleArray を実装して Common Prefix Search する

概要

キーワードマッチするのに必要になったので作ってみました．

コード

凝ったことは特にしていません．素朴な実装です．
構築は静的におこないます．一旦ダブル配列を作ったらキーワードの追加は出来ません．
キーワードリストを与えると，それらをソートして 0 から順に id を振って，検索時にこの id を返します．

go get github.com/ikawaha/trie

参考

takuya-aさんのjsによるDoubleArray: https://github.com/takuyaa/doublearray
Atsushi KOMIYA さんのブログ: Trie が提供すべき操作について検討してみる
Higashiyama Masahiko さんのスライド: ダブル配列の実装方法
書籍: 日本語入力を支える技術

使い方

キーワードのリストを用意して構築する．キーワードのリストはソートしてなくてもokです．

package main

import (
        "github.com/ikawaha/trie"

        "fmt"
 )

 func main() {
      keywords :=[]string{
                 "hello",
                 "world",
                 "関西",
                 "国際",
                 "国際空港",
                 "関西国際空港",
      }
      t, err := trie.NewDoubleArrayTrie(keywords)
      if err != nil {
         panic(err)
      }
      fmt.Println(t.Search("hello"))
      fmt.Println(t.Search("world"))
      fmt.Println(t.Search("goodby"))
      fmt.Println(t.CommonPrefixSearch("関西国際空港"))
}

結果

0 true
1 true
0 false
[関西 関西国際空港] [4 5]

ファイルを用意して構築する．1行1キーワードのファイルを用意します．

入力ファイル

逓信大
電気通信大学
東京電気大学
電通大
電気通信大学大学院
電気通信大学大学院大学

package main

import (
        "github.com/ikawaha/trie"

        "fmt"
        "os"
 )

 func main() {
      file, err := os.Open("keyword_list.txt")
      if err != nil {
         panic(err)
      }
      defer file.Close()
      t, err := trie.NewDoubleArrayTrie(file)
      if err != nil {
          panic(err)
      }
      fmt.Println(t.CommonPrefixSearch("電気通信大学大学院大学"))
}

結果

[電気通信大学 電気通信大学大学院] [3 4]