common-prefix searchと形態素解析
doar実装関連雑記。
今日は、(形態素解析には必須の?)common-prefix-search関数の実装に取り組んでいた。
;; common-prefix-searchの動作を示すための例 (defvar *data* '("自転車" "自動車" "自動" "自" "時刻" "自動車免許" "免許" "車")) (defun common-prefix-search (key data-base) (loop for i from 1 to (length key) when (member (subseq key 0 i) data-base :test #'equal) collect (subseq key 0 i))) ;; データの内で、キーの先頭部分に含まれるものが集められる。 ;; DoubleArrayは、これ高速に行える。 ※ O(n): n=キーの長さ > (common-prefix-search "自動車免許" *data*) --> ("自" "自動" "自動車" "自動車免許")
これは、DoubleArrayの通常の検索に比べて(実装が)極端に複雑、とかいうことはないのだが、具体的な利用方法がいまいちピンとこないため関数のシグネチャをどうするかで悩んだ(ただ、これはあまり以降の内容とは関係ない）。
結局、実際に使ってみないと分からないということで、入力文字列に対してcommon-prefix-searchを行うコマンドを作成してみた。※ 正確には既存コマンドの機能拡張
DoubleArrayデータのソースとしては、MeCabのページから入手できるIPADICをUTF8に変換して利用した。※ 詳細は後述
このコマンドは、以下の2ステップを再帰的に繰り返して結果を出力する。
- 入力キーに対してcommon-prefix-searchを行う
- 入力キーに一致するデータが見つかった場合、その位置から再帰的にcommon-prefix-searchを呼び出す ※ 1でキーの先頭部分(common-prefix)が複数のデータに一致した場合、そのそれぞれの位置に対して、再帰的に呼び出す
この処理(コマンド)をはてなのブログ記事編集ページに表示されていた「マウスで手軽におえかきできる」という文字列に適用したら、以下のような出力が出てきた。
| 一致位置 | ID | キー文字列 ※一致部分は赤色表示. 開始位置が同じ単語群は、一回のcommon-prefix検索で見つかったもの |
|---|---|---|
| 00-09 | 04307A | マウスで手軽におえかきできる |
| 09-0C | 0383C2 | マウスで手軽におえかきできる |
| 0C-0F | 05C34A | マウスで手軽におえかきできる |
| 0C-12 | 05C6D1 | マウスで手軽におえかきできる |
| 0F-12 | 077811 | マウスで手軽におえかきできる |
| 12-15 | 03959D | マウスで手軽におえかきできる |
| 12-1B | 0395F0 | マウスで手軽におえかきできる |
| 15-18 | 030E7E | マウスで手軽におえかきできる |
| 15-1B | 030FA5 | マウスで手軽におえかきできる |
| 18-1B | 030CBC | マウスで手軽におえかきできる |
| 1B-1E | 031C50 | マウスで手軽におえかきできる |
| 1B-21 | 031E6F | マウスで手軽におえかきできる |
| 1E-21 | 032C3F | マウスで手軽におえかきできる |
| 21-24 | 0383C2 | マウスで手軽におえかきできる |
| 21-27 | 0383FD | マウスで手軽におえかきできる |
| 21-2A | 038412 | マウスで手軽におえかきできる |
| 24-27 | 032C3F | マウスで手軽におえかきできる |
| 24-2A | 033306 | マウスで手軽におえかきできる |
| 27-2A | 03E8F0 | マウスで手軽におえかきできる |
もとの文字列が「マウス/で/手/軽/におえ/かき/で/き/る」とか「マウス/で手軽/に/おえ/かき/でき/る」とかに分割できるということが分かる。
ただ、これだけだと、(上の場合だと100通り以上ある)どの分割が適切なものかを決定する方法がないので、ちゃんと形態素解析しようと思ったら、単語(の品詞?)間の連結可能性とか、コストの概念とかが(各々の分割方法に優先順位をつけるために)必要になるのだろうと思う。
しかし、上で挙げたような情報は、IPADICに既に納められているので、それを利用するようにすれば、今実装しているcommon-prefix-searchと合わせて、案外簡単に形態素解析器ができるのではないか、というのが今日の結論。未知語処理をどうするか、というのが大きな問題としてあるが。
手順とか
上に載せた表を出すまでの手順を一応メモおく。
IDPADIC関連
> # ... mecab-ipadic-2.7.0-20070801.tar.gzのダウンロード及び解凍 ... > cd mecab-ipadic-2.7.0-20070801 > cut -d',' -f1 *.csv | nkf -w > /tmp/utf8.ipadic > LC_ALL=C sort /tmp/utf8.ipadic | LC_ALL=C uniq > /tmp/sort.ipadic
doar関連
> # ... doar-0.0.5.tar.gz のダウンロード及び解凍 ... > doar-0.0.5 > make > bin/mkdoar /tmp/sort.ipadic /tmp/da.idx # DoubleArray構築 > > bin/doar /tmp/da.idx << EOS | sort | uniq > マウスで手軽におえかきできる~ # common-prefix search(再帰版) > EOS > # ... 出力 ...
