読者です 読者をやめる 読者になる 読者になる

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ステップを再帰的に繰り返して結果を出力する。

  1. 入力キーに対してcommon-prefix-searchを行う
  2. 入力キーに一致するデータが見つかった場合、その位置から再帰的にcommon-prefix-searchを呼び出す ※ 1でキーの先頭部分(common-prefix)が複数のデータに一致した場合、そのそれぞれの位置に対して、再帰的に呼び出す


この処理(コマンド)はてなのブログ記事編集ページに表示されていた「マウスで手軽におえかきできる」という文字列に適用したら、以下のような出力が出てきた。

一致位置IDキー文字列 ※一致部分は赤色表示. 開始位置が同じ単語群は、一回のcommon-prefix検索で見つかったもの
00-0904307Aマウスで手軽におえかきできる
09-0C0383C2マウス手軽におえかきできる
0C-0F05C34Aマウスで軽におえかきできる
0C-1205C6D1マウスで手軽におえかきできる
0F-12077811マウスで手におえかきできる
12-1503959Dマウスで手軽おえかきできる
12-1B0395F0マウスで手軽におえかきできる
15-18030E7Eマウスで手軽にえかきできる
15-1B030FA5マウスで手軽におえかきできる
18-1B030CBCマウスで手軽におかきできる
1B-1E031C50マウスで手軽におえきできる
1B-21031E6Fマウスで手軽におえかきできる
1E-21032C3Fマウスで手軽におえかできる
21-240383C2マウスで手軽におえかききる
21-270383FDマウスで手軽におえかきでき
21-2A038412マウスで手軽におえかきできる
24-27032C3Fマウスで手軽におえかきで
24-2A033306マウスで手軽におえかきできる
27-2A03E8F0マウスで手軽におえかきでき
これは、IPADIC内の単語を単純に(common-prefix-searchで)拾っているだけだが、それだけで思いのほか形態素解析っぽい(気がしないでもない)結果がでてきた。
もとの文字列が「マウス/で/手/軽/におえ/かき/で/き/る」とか「マウス/で手軽/に/おえ/かき/でき/る」とかに分割できるということが分かる。
ただ、これだけだと、(上の場合だと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
> # ... 出力 ...