🏠home
😊about

Go / NLP

Go製ダブル配列パッケージと最長一致法を使った形態素解析の実装

形態素解析本の4章をGoでなぞってみたので解説と実装を共有します。

2020 / 07 / 24

Overview

NLP初心者ですが、形態素解析本の4章をGoでなぞってみたので解説と実装を共有します。

形態素解析の理論と実装 (実践・自然言語処理シリーズ)

超シンプルな形態素解析実装の流れ

1: 辞書からダブル配列の構築 2: ダブル配列に対して共通接頭辞検索を実装する 3: 共通接頭辞検索を使った最長一致法の実装

1と2はGo製のダブル配列パッケージであるikawaha/dartscloseが実装しているので今回はこれを使いましょう。

img1

Go製ダブル配列パッケージ

ダブル配列の解説は下記のブログが最もわかりやすいと思います。

情報系修士にもわかるダブル配列

Goにもダブル配列のパッケージがあるのでそちらを使います。エラーハンドリングは省略していますが、下記のコードでダブル配列を構築でき、ファイルに保存もできます。

package main

import (
	"os"

	"github.com/ikawaha/dartsclone"
)

func main() {
	keys := []string{
		"データ指向アプリケーションデザイン",
		"データ指向アプリケーション",
		"データ指向",
		"データ",
		"指向",
		"指",
		"アプリケーションデザイン",
		"アプリ",
		"デザイン",
		"本",
		"読む",
		"の",
		"は",
		"を",
	}

	// Build
	builder := dartsclone.NewBuilder(nil)
	_ = builder.Build(keys, nil)

	// Save
	f, _ := os.Create("my-double-array-file")
	defer f.Close()
	builder.WriteTo(f)

	// ...
}

共通接頭辞検索をやってみる

ダブル配列が構築できたので、次に共通接頭辞検索をやってみましょう。

ちなみに、ダブル配列を利用する際にはメモリに乗っかるので、省メモリ&高速に扱う為にmmapを利用したいところです。ちなみにこのパッケージはすでにmmap対応している為、今回はその機能を使います。ドキュメント通り、mmapを利用するにはGoのビルドタグで指定できます。

export GOFLAGS="-tags=mmap"

共通接頭辞検索はtrie.CommonPrefixSearchメソッドが行います。実際に試してみましょう。

"データ指向アプリケーションデザイン"というkeyで共通接頭辞検索をしてみます。

// ...

func main() {
	// ...

	trie, _ := dartsclone.OpenMmaped("my-double-array-file")
	defer trie.Close()

	ret, _ := trie.CommonPrefixSearch("データ指向アプリケーションデザイン", 0)
	for i := 0; i < len(ret); i++ {
		fmt.Printf("id=%d, common prefix=%s\n", ret[i][0], "データ指向アプリケーションデザイン"[0:ret[i][1]])
	}

	// ...
}

結果は下記のようになります。ちゃんと共通接頭辞検索ができています。

go run main.go
id=6, common prefix=データ
id=7, common prefix=データ指向
id=8, common prefix=データ指向アプリケーション
id=9, common prefix=データ指向アプリケーションデザイン

最長一致法

最長一致方は貪欲的アルゴリズムの一種で、文頭から一文字ずつ共通接頭辞検索を行なっていき、その中で最も長い単語を貪欲に選んでtokenとします。最も長い単語が見つかったらその終わりをoffsetとして再度検索を行なっていきます。

// ...

func main() {
	// ...

	var offset int
	tokens := make([]string, 0)
	var unknown string
	s := "ponはデータ指向アプリケーションデザインの本を読む"

	for {
		ret, err := trie.CommonPrefixSearch(s, offset)
		if err != nil {
			panic(err)
		}

		// 見つからなかったらoffset更新して次へ
		if len(ret) == 0 {
			s := string([]rune(s)[offset])
			unknown += s
			offset += len(s)
			continue
		}

		// 辞書に無い未知語を1単語として処理
		if unknown != "" {
			tokens = append(tokens, unknown)
			unknown = ""
		}

		// 最も長い文字列を探す
		var maxIndex int
		var max int
		for i, r := range ret {
			if max < r[1] {
				max = r[1]
				maxIndex = i
			}
		}

		// token追加
		token := s[offset:ret[maxIndex][1]]
		tokens = append(tokens, token)

		// offset更新
		id := ret[maxIndex][0]
		k := keys[id]
		offset += len(k)

		// 脱出条件
		if len(s) <= offset {
			break
		}
	}

	fmt.Printf("%#v", tokens)
}

出力はこちらです。こんなシンプルな最長一致法でもそれっぽく形態素解析ができています。

[]string{
	"pon",
	"は",
	"データ指向アプリケーションデザイン",
	"の",
	"本",
	"を",
	"読む",
}

形態素解析の本によると、単純なアルゴリズムにも関わらず90%以上の分割精度が得られるそうです。また、辞書引き回数が少ないのも特徴のようです。

まとめ

今回は最長一致法を使った辞書ベースの形態素解析の作り方を紹介しました。今後はGoでラティス&ビタビアルゴリズムをやってみようと思います。もし時間があればダブル配列も実装したい。。

Go
NLP

🔍 more !!