辞書なし形態素解析

現在辞書なしで形態素解析(厳密には単語切りだしのみ)をするプログラムを作っている。

方法は、文字列の共通部分と差異部分に注目して文字列を抽出する。
例えば次の文章を解析する場合は

Humpty Dumpty sat on a wall. Humpty Dumpty had a great fall. All the king's horses and all the king's men Couldn't put Humpty together again.
ハンプティ・ダンプティ

1. 文字列中に複数回出現する文字列(Segment 2)を抽出する(この例では長さ5以上のもの。実際は1以上でいけるはず)

"Humpty Dumpty ", "Humpty ", " Humpty ", "all. ", "umpty ", "ll the king's "

2. Segment 2の文字列同士を比較し共通部分(Segment 1)、差異部分(Segment 3)を抽出する(例では長さ1以上)

文字列1	文字列2	Segment 1	Segment 3
"Humpty Dumpty "	"Humpty "	"Humpty "	"Dumpty "
"Humpty Dumpty "	" Humpty "	"Humpty "	"Dumpty ", " "
"Humpty Dumpty "	"all. "	" "	"Humpty Dumpty", "all."
"Humtpy Dumpty "	"umpty "	"umpty "	"Humpty D", "H", "Dumpty "

(以下略)

3. Segment 1に対して2. の手順を繰り返す( ここはなくてもいいかも )
4. 切り出した文字列達を保存する
5. 単語切り出しを行う際はSegment 1 > 2 > 3の順に切り出す

一部、参考書と違う所もあるけどこんな感じ。
「こんなんでうまく切り出せるのか?」という疑問もあるけど参考書によれば90%程度まで認識ができたという結果がある。

さて、問題はこのアルゴリズムをどう実装するかだな....(本には一切書いてない)
力技でいくか、ハッシュマップでも使おうか..うーん。

参考:

• AI開発ノート 形態素解析 part2*1

• 自然言語処理ことはじめ―言葉を覚え会話のできるコンピュータ

追記

今思ったけど、空白ってのは人間の視覚・聴覚にとっては「区切り」の意味しかないから切り出した文字列の両端の空白・改行はトリムしちゃったほうがいいか。
でもそうすると文を生成するときに単語間に空白を入れるかどうかの知識が必要になる。
こういう知識は絶対にハードコーディングしないで、学習によって獲得させたいなぁ。

悩むけどとりあえず、空白のトリムは後回し。

*1:これ書いたのもう半年以上前だorz ..なにやってたんだろ(笑)