Pure Go な形態素解析器で実行バイナリに辞書埋め込んだヤツを作ってみた (1)

はじめに

DoubleArray を作ったこともあって，ついでに形態素解析器も作ってみようと思い立ち kuromoji を参考に形態素解析器を実装してみました．目標としては，Pure Go で kuromoji みたいな感じ（辞書内包，検索モードあり，スレッドセーフ）を目指します．

サンプルプログラム

参考

下記を参考にさせていただきました．

• kuromoji
• 日本語入力を支える技術
• Mecab
  • 品詞IDの定義

形態素解析のちょー適当な説明

「形態素」が何であるかを議論し出すと面倒なことに巻き込まれそうなので，ここでは MeCab-IPADIC で定義されているものとします．形態素解析のアルゴリズムについては下記の資料などをあたってください．

• 日本語入力を支える技術
• 日本語解析ツール MeCab, CaboCha の紹介

用意するもの

• DoubleArray #前に作ったものを id が記録できるようにちょっと改造
• 学習済みの形態素解析モデル MeCab-IPADIC

MeCab-IPADIC の中身をのぞいて見てみる

内容物は以下のようになっていました (mecab-ipadic-2.7.0-20070801)

mecab-ipadic-2.7.0-20070801

AUTHORS            Conjunction.csv    Noun.adjv.csv      Noun.org.csv       Postp.csv          aclocal.m4         dicrc              pos-id.def
Adj.csv            Filler.csv         Noun.adverbal.csv  Noun.others.csv    Prefix.csv         char.def           feature.def        rewrite.def
Adnominal.csv      INSTALL            Noun.csv           Noun.place.csv     README             config.guess*      install-sh*        right-id.def
Adverb.csv         Interjection.csv   Noun.demonst.csv   Noun.proper.csv    RESULT             config.log         left-id.def        unk.def
Auxil.csv          Makefile.am        Noun.nai.csv       Noun.verbal.csv    Suffix.csv         config.sub*        matrix.def
COPYING            Makefile.in        Noun.name.csv      Others.csv         Symbol.csv         configure*         missing*
ChangeLog          NEWS               Noun.number.csv    Postp-col.csv      Verb.csv           configure.in       mkinstalldirs*

とりあえず必要なのは csv ファイルと，matrix.def です．
csv ファイルは形態素のリスト，matrix.def は形態素の連接コストを管理しているようです．
ちなみに unk.def はう〇こではなく，unknown で未知語の定義ファイルです．

形態素リスト

csvファイルの内容は下記のようになっています．ファイルごとに品詞でまとめられているようです．

※ csvファイルは euc-jp で書かれているので，何気なく読み込むと文字化けします．euc-jp の csvファイルを読み込む方法はこちらを参照ください
→ Goでeuc-jpやsjisのcsvファイルを読み込むには変換用のリーダーを1つかませるだけでよかった

Verb.csv

引き込む,762,762,7122,動詞,自立,*,*,五段・マ行,基本形,引き込む,ヒキコム,ヒキコム

内容は，左から，

表層形,左文脈ID,右文脈ID,コスト,品詞,品詞細分類1,品詞細分類2,品詞細分類3,活用形,活用型,原形,読み,発音

の形式．ラティスを作るときに最低限必要なのは，上の

• 表層形 … 形態素の表記
• 左文脈ID … ラティスノードの左側に対応する品詞ID
• 右文脈ID … ラティスノードの右側に対応する品詞ID
• コスト … 単語の生起コスト

だけなので，すくなくともこれを管理するようにします．表層形を DoubleArray に登録して，入力文字列を CommonPrefixSearch 出来るようにしておけば，ラティスを構築することが出来ます．ただ，表層形が同じ形態素（品詞異なりとか）があるので注意する必要があります．

連接コスト表

matrix.def は形態素の連接コストを管理しています．
中身を見てみるとこんな感じで (★以降は僕のコメントです) 行列を定義しています．
行列のインデックスは文脈IDに対応しています．コストは short int で管理されているので，golang なら int16 で管理すれば十分です．一次元の配列を1316x1316で用意して，行と列で引けるようにして管理します．

matrix.def

1316 1316           ★ ← 1316x1316 の行列であることを宣言
0 0 -434            ★ ← 行列の 0行 0列 の連接コストが -434 の意味
0 1 1
0 2 -1630
0 3 -1671
0 4 24
0 5 111
0 6 -2752
0 7 -589
0 8 -589
…snip

連接コストを管理する

package dic

type connectionTable struct {
    rowSize, colSize int
    vec []int16
}

func (this *connectionTable) At(a_row, a_col int) (cost int16, err error) {
    defer func() {
        if e := recover(); e != nil {
            err = e.(error)
        }
    }()
    pos := this.colSize*a_row + a_col
    return this.vec[pos], nil
}

辞書をどうするのか問題

kuromoji の辞書ってどうなってるんでしたっけ？ということで調査．拾ってきた jar を解凍して中見てみる．

kuromoji の辞書

kuromoji のよいところは，辞書を内包しているというところ．辞書を内包してくれていると，実行系と辞書のバージョンが合わなくて動かないよーとか無くていいし，管理も楽．向こうの環境から持ってきた辞書の文字コードが違って動かんとか云うこともない！

kuromoji-0.7.7
│
├── META-INF
│   ├── maven
│   │   └── org.atilika.kuromoji
│   │       └── kuromoji
│   │           ├── pom.properties
│   │           └── pom.xml
│   └── MANIFEST.MF
├── org
│   └── atilika
│       └── kuromoji
│           ├── dict
│           │   ├── CharacterDefinition$CharacterClass.class
│           │   ├── CharacterDefinition.class
│           │   ├── ConnectionCosts.class
│           │   ├── Dictionaries.class
│           │   ├── Dictionary.class
│           │   ├── TokenInfoDictionary.class
│           │   ├── UnknownDictionary.class
│           │   └── UserDictionary.class
│           ├── trie
│           │   ├── DoubleArrayTrie.class
│           │   ├── Trie$Node.class
│           │   └── Trie.class
│           ├── util
│           │   ├── CSVUtil.class
│           │   ├── ConnectionCostsBuilder.class
│           │   ├── DictionaryBuilder$DictionaryFormat.class
│           │   ├── DictionaryBuilder.class
│           │   ├── DoubleArrayTrieBuilder.class
│           │   ├── TokenInfoDictionaryBuilder$1.class
│           │   ├── TokenInfoDictionaryBuilder.class
│           │   └── UnknownDictionaryBuilder.class
│           ├── viterbi
│           │   ├── Viterbi$1.class
│           │   ├── Viterbi.class
│           │   ├── ViterbiFormatter.class
│           │   ├── ViterbiNode$Type.class
│           │   └── ViterbiNode.class
│           ├── DebugTokenizer$Builder.class
│           ├── DebugTokenizer.class
│           ├── Token.class
│           ├── Tokenizer$Builder.class
│           ├── Tokenizer$Mode.class
│           ├── Tokenizer.class
│           └── TokenizerRunner.class
├── cc.dat
├── cd.dat
├── dat.dat
├── kuromoji-0.7.7.jar
├── tid.dat
├── tid_map.dat
├── unk.dat
└── unk_map.dat

*.dat というのが辞書関連データっぽい．

-rw-r--r--  1 3.3M  1 30  2012 cc.dat
-rw-r--r--  1 321K  1 30  2012 cd.dat
-rw-r--r--  1 17M  1 30  2012 dat.dat
-rw-r--r--  1 28M  1 30  2012 tid.dat
-rw-r--r--  1 6.3M  1 30  2012 tid_map.dat
-rw-r--r--  1 1.7K  1 30  2012 unk.dat
-rw-r--r--  1 325B  1 30  2012 unk_map.dat

全部合わせて辞書容量は55MB程度というところ．結構大きいですね．

golang でどうするか？

golang でも辞書を一緒に配布したいんですが，どうしたもんでしょうか．github のディレクトリに一緒に入れておけばいいでしょうか．でも，それだと結局辞書の位置を管理しなければならないのでバイナリだけでがんばりたいところです．

というわけで，苦し紛れに思いついたのは， 辞書を golang のコードに変換してコンパイル時に一緒に構築してバイナリに含めてもらおう！ という方法です．

辞書をプログラム定数として埋め込む

golang で Webアプリケーションを書くときに使う（といってもWebアプリとか作ったことないけど） http/template のテキスト版，text/template を利用します．これは，テンプレートとして用意したひな形にデータを埋め込むためのライブラリです．まさにコードを生成してくれと云わんばかりのライブラリ！（違）．これを用いて，先の連接表をプログラム定数としてコードの中に埋め込んでしまいます．

こんな感じで使います．smarty みたいなものかと思ってましたが，smarty ほど便利ではないので，埋め込むデータはテンプレートに渡す前に文字列でほぼほぼ整形しておく必要があります．

matrix.defをgolangのコードに置き換えるジェネレータ

package main

import (
    "bufio"
    "fmt"
    "log"
    "os"
    "strconv"
    "strings"
    "text/template"
)

type TemplateData struct {
    RowSize, ColSize int
    Matrix           []string
}

func loadMatrixDef(file *os.File) (rowSize, colSize int, matrix [][]int16, err error) {
    scanner := bufio.NewScanner(file)
    scanner.Scan()
    line := scanner.Text()
    dim := strings.Split(line, " ")
    if len(dim) != 2 {
        err = fmt.Errorf("invalid format: %s", line)
        return
    }
    rowSize, err = strconv.Atoi(dim[0])
    if err != nil {
        err = fmt.Errorf("invalid format: %s, %s", err, line)
        return
    }
    colSize, err = strconv.Atoi(dim[1])
    if err != nil {
        err = fmt.Errorf("invalid format: %s, %s", err, line)
        return
    }
    // fmt.Printf("rowSize %d, ColSize %d\n", rowSize, colSize)
    matrix = make([][]int16, rowSize)
    for i := 0; i < colSize; i++ {
        matrix[i] = make([]int16, colSize)
    }
    for scanner.Scan() {
        line := scanner.Text()
        ary := strings.Split(line, " ")
        if len(ary) != 3 {
            err = fmt.Errorf("invalid format: %s", line)
            return
        }
        row, e := strconv.Atoi(ary[0])
        if e != nil {
            err = fmt.Errorf("invalid format: %s, %s", e, line)
            return
        }
        col, e := strconv.Atoi(ary[1])
        if e != nil {
            err = fmt.Errorf("invalid format: %s, %s", e, line)
            return
        }
        val, e := strconv.Atoi(ary[2])
        if e != nil {
            err = fmt.Errorf("invalid format: %s, %s", e, line)
            return
        }
        matrix[row][col] = int16(val)
    }
    if err = scanner.Err(); err != nil {
        err = fmt.Errorf("invalid format: %s, %s", err, line)
        return
    }
    return
}

func main() {
    var in *os.File
    if len(os.Args) < 2 {
        log.Fatal("no input file")
    }
    in, err := os.Open(os.Args[1])
    if err != nil {
        log.Fatalf("cannot open file: %s", err)
    }
    defer in.Close()
    row, col, matrix, err := loadMatrixDef(in)
    if err != nil {
        log.Fatalf("matrix converter: %s", err)
    }
    data := TemplateData{RowSize: row, ColSize: col}
    data.Matrix = make([]string, row)
    for i := 0; i < row; i++ {
        data.Matrix[i] = ""
        for j := 0; j < col; j++ {
            val := strconv.Itoa(int(matrix[i][j]))
            data.Matrix[i] += fmt.Sprintf("%5s,", val)
            if (i*row+j+1)%20 == 0 {
                data.Matrix[i] += "\n"
            }
        }
    }

    out, err := os.OpenFile("../connection.go", os.O_RDWR|os.O_TRUNC|os.O_CREATE, 0666)
    if err != nil {
        log.Fatalf("matrix converter: %s", err)
    }
    defer out.Close()
    tpl := template.Must(template.ParseFiles("matrix.tpl"))
    tpl.Execute(out, data)
}

テンプレート

package dic

type connectionTable struct {
    rowSize, colSize int
    vec []int16
}

func (this *connectionTable) At(a_row, a_col int) (cost int16, err error) {
    defer func() {
        if e := recover(); e != nil {
            err = e.(error)
        }
    }()
    pos := this.colSize*a_row + a_col
    return this.vec[pos], nil
}

var Connection *connectionTable = &connectionTable {
    rowSize: {{.RowSize}},
    colSize: {{.ColSize}},
    vec:     []int16{
{{range $key, $line := .Matrix}}{{$line}}{{end}}     // ← ここに matrix.def の値を埋め込みます
             },
}

生成された連接コスト表は次のようになります．

生成された連接コスト表のコード

package dic

type connectionTable struct {
    rowSize, colSize int
    vec              []int16
}

func (this *connectionTable) At(a_row, a_col int) (cost int16, err error) {
    defer func() {
        if e := recover(); e != nil {
            err = e.(error)
        }
    }()
    pos := this.colSize*a_row + a_col
    return this.vec[pos], nil
}

var Connection *connectionTable = &connectionTable{
    rowSize: 1316,
    colSize: 1316,
    vec: []int16{
        -434, 1, -1630, -1671, 24, 111, -2752, -589, -589, -294, -155, 475, 945, -467, -155, -461, -148, -461, -148, -2409,
        -3230, -558, -246, -510, -198, -461, -148, -462, -150, -461, -149, -114, 197, -590, -278, 27, 1003, -1205, 30, -351,
        -62, -59, -59, -800, -131, 609, -59, -60, -59, 113, -127, 213, -903, 478, 478, 504, 70, 70, 96, 72,
        72, 99, 72, 72, 99, -552, -552, -526, 40, 40, 66, 92, 92, 118, 72, 72, 99, 72, 72, 98,
// …snip
        66, 66, 66, 66, 124, 124, 124, 124, 61, 61, 61, 61, 87, 87, 87, 87, 61, 61, 61, 61,
        78, 78, 78, 78, -192, -192, -192, -192, 114, 114, 114, 114, 217, 217, 217, 217, 79, 79, 79, 79,
        132, 132, 132, 132, 100, 100, 100, 100, 91, 91, 91, 91, -166, -166, -166, -166, 101, 199, 125, 87,
        -192, 130, -61, -1401, -939, -1154, -911, -1265, -287, -934, -605, -614, -344, 62, 446, 61, -902, 792, 1436, 754,
        1123, 758, 752, 853, 810, 1147, -775, -843, -911, -889, -3785, -3261, -3209, -4369, -1712, -129,
    },
}

生成したコードの大きさ

種類	元ファイルのサイズ	変換されたgolangコード
連接表	22MB	10MB
形態素リスト	33MB	74MB (DoubleArray含む)

変換したコードが結構大きかったので，ドキドキしながらビルド・・・・・ （超重い，メモリ超喰う）・・・・通りました．
連接表と形態素リスト関連のコードが dic パッケージとして1つにまとめられて，そのサイズは，

ライブラリ(.a)	サイズ
dic.a	232MB

232MB! でかい orz．でもまだ中間ファイルですしね・・・．

解析部分を作る

辞書が出来て，ここまで来ればほぼできあがったようなものです．
ラティスを構築し，Viterbi で探索します．ラティスはこんな感じのコードになりました．

ラティスの構築とViterbiでの検索

package tokenizer

import (
    "github.com/ikawaha/tokenizer/dic"

    "fmt"
    "unicode/utf8"
)

const (
    _INTMAX = 1<<31-1
)

type Lattice struct {
    input  []rune
    list   [][]Node
    output []*Node
}

func (this *Lattice) build(a_input string) {
    runes := []rune(a_input)
    this.input = runes
    this.list = make([][]Node, len(runes)+2)

    this.list[0] = append(this.list[0], Node{id: BOSEOS, class: KNOWN, start: 0})
    this.list[len(this.list)-1] = append(this.list[len(this.list)-1], Node{id: BOSEOS, class: KNOWN, start: len(this.list) - 2})

    for i, _ := range runes {
        prefixs, ids := dic.Index.CommonPrefixSearch(string(runes[i:]))
        for key, substr := range prefixs {
            id := ids[key]
            dup := dic.Counts[id]
            if dup == 0 {
                dup = 1
            }
            for x := 0; x < dup; x++ {
                cost := dic.Costs[id+x]
                p := i + utf8.RuneCountInString(substr)
                surface := this.input[i:p]
                node := Node{
                    id:      id + x,
                    start:   i,
                    cost:    0,
                    class:   KNOWN,
                    left:    int32(cost.Left),
                    right:   int32(cost.Right),
                    weight:  int32(cost.Weight),
                    surface: surface,
                }
                this.list[p] = append(this.list[p], node)
            }
        }
    }
}

func (this *Lattice) String() string {
    str := ""
    for i, nodes := range this.list {
        str += fmt.Sprintf("[%v] :\n", i)
        for _, node := range nodes {
            str += fmt.Sprintf("%v\n", node)
        }
        str += "\n"
    }
    return str
}

func (this *Lattice) forward() (err error) {
    for i, size := 1, len(this.list); i < size; i++ {
        currentList := this.list[i]
        for index, target := range currentList {
            prevList := this.list[target.start]
            if len(prevList) == 0 {
                this.list[i][index].cost = _INTMAX
                continue
            }
            for j, n := range prevList {
                var c int16
                c, err = dic.Connection.At(int(n.right), int(target.left))
                if err != nil {
                    return
                }
                totalCost := int32(c) + int32(target.weight) + n.cost
                if j == 0 || totalCost < this.list[i][index].cost {
                    this.list[i][index].cost = totalCost
                    this.list[i][index].prev = &this.list[target.start][j]
                }
            }
        }
    }
    return
}

func (this *Lattice) backward() {
    size := len(this.list)
    stack := make([]*Node, 0, size)
    p := &this.list[size-1][0]

    stack = append(stack, p)
    for p != nil {
        stack = append(stack, p)
        p = p.prev
    }

    this.output = make([]*Node, 0, len(stack))
    for i := len(stack) - 1; i > 0; i-- {
        this.output = append(this.output, stack[i])
    }
}

実行

実行プログラムを用意して，標準入力に入力された文字列を1文として解析します．
＃ net/http/pprof を入れておくとメモリの監視とか出来て便利です．

main

package main

import (
    "github.com/ikawaha/tokenizer"

    "bufio"
    "fmt"
    "log"
    _ "net/http/pprof"
    "net/http"
    "os"
)

func main() {

    go func() {
        log.Println(http.ListenAndServe("localhost:6060", nil)) // ★ ← これ入れておくと，メモリ使用量とかを監視できて便利
    }()

    var fp *os.File
    if len(os.Args) < 2 {
        fp = os.Stdin
    } else {
        fp, err := os.Open(os.Args[1])
        if err != nil {
            panic(err)
        }
        defer fp.Close()
    }

    scanner := bufio.NewScanner(fp)
    for scanner.Scan() {
        line := scanner.Text()
        morphs, err := tokenizer.Tokenize(line)
        if err != nil {
            log.Println(err)
        }
        for i, m := range morphs {
            content, e := m.Content()
            if e != nil {
                log.Println(e)
            }
            fmt.Printf("%2d: %v(%v, %v)\t%v\n", i, m.Surface, m.Start, m.End, content)
        }
    }
    if err := scanner.Err(); err != nil {
        log.Println(err)
    }
}

やったー＼(^o^)／ 最終的なバイナリのサイズは 105MB．バイナリが大きくなりがちな golang にしては上出来ではないでしょうか(?!)

問題点

未知語の処理をしていないので，ラティスが末尾から先頭まで辿れなくなることがあります．

トトロが辞書にないので，そこの連結がなくなってしまいます．そうしないためには，辞書引けなかったときに，ある適当な範囲（たとえばカタカナ連続部分とか）を新しいノードとしてラティスに追加してやる必要があります．

次回は未知語処理を実装してみたいと思います．あと，kuromoji の検索モードの対応とか．（つづく・・・・のか？）

つづき：(２)未知語処理編