n-gramとマルコフ連鎖の理論と実装、もちろんScalaを使って。
n-gramとは
n-gramとは形態素解析のように辞書を使って文章を品詞分解していくのではなく「文字単位で文章を分割していく」手法のこと。
なので、形態素解析のように辞書を必要とするわけではない。
またn-gramのnが何を指すかというとn文字で分割するという意味である。
1-gramは１文字ずつ分割する。
2-gramは２文字ずつ分割する。
3-gramは３文字ずつ分割する。
…
みたいに。
実際には次のように分割していく。
文章:今日は雨のようだ。 条件:n = 2とする 分割: 今日 日は は雨 雨の のよ よう うだ だ。
ただここで問題なのがnが小さすぎるとその自然言語にもよるが不適切な結果を生むことに成る。
文章:東京都庁 条件:n = 2 分割: 東京 京都 都庁
n-gramを使って文字列分割を行うと本来想定している最適解とは異なる場合がある。
今回で言えば、「東京都庁」という意味を持つのに本来の意味とかけ離れた「京都」が出てしまうなど。
そこで日本語の文章を分割するときはn=3を想定するっぽい。
簡単故にこれを実際の会話で使う文章生成に使うと割と精度が下がる。
n-gramのサンプル
今回は、「青空文庫」さんから夏目漱石の「こころ」をお借りしました。
事前にutf-8にしてあれこれ邪魔な記述を抜かして使用します。
これに対してn = 3の時のn-gram、つまりtri-gramで分割しました。
ソースコードは次の通り。
import scala.io.Source import scala.io.BufferedSource import scala.collection.mutable.Map object Ngram{ //3文字ずつ分割していく private [this] val n:Int = 3 def main(args:Array[String]):Unit = { //文字列とその出現頻度を格納 var ngramMap:Map[String,Int] = Map[String,Int]() //ファイルを読み込む val source = Source.fromFile("kokoro.dat","utf-8") //１行ずつ読み込む val lines:Iterator[String] = source.getLines //ngramで分割し格納 for(line <- lines){ var tmp_line:String = line while(tmp_line.length >= this.n){ var subString:String = tmp_line.take(this.n) //切り出した文字列が今までに出てないなら追加 //出現しているなら出現回数の更新 if(!ngramMap.contains(subString)){ ngramMap += (subString -> 1) }else{ var count:Int = ngramMap(subString) + 1 ngramMap.update(subString, count) } //先頭文字の除去 tmp_line = tmp_line.tail } } val result_key:Iterable[String] = ngramMap.keys for(key <- result_key){ println(s"${key} ${ngramMap(key)}") } } }
これをコンパイルして次のように実行する。
$ scala Ngram | sort -r -nk2 | head
そうすると、よく使われる部分文字列ベスト10が切り出せた。
| 部分文字列 | 出現回数 |
| した。 | 1464 |
| ました | 1026 |
| った。 | 856 |
| です。 | 789 |
| のです | 776 |
| かった | 593 |
| たので | 562 |
| なかっ | 470 |
| ってい | 397 |
| 奥さん | 386 |
語尾とか接続詞的なあれこれは頻度高いのわかるが「奥さん」…。
マルコフ連鎖とは
マルコフ連鎖とは、ある事象がその直近の事象のみに影響を受けて確率的に変化するという考えかた。
これにはマルコフ性という、次に起こる事象が過去に起きた事象の影響を受けないという性質がなければならない。
もっと言えば、マルコフ性を備えた確率過程のことをマルコフ過程といい、その中でも状態空間が連続ではなく離散的である場合を特にマルコフ連鎖という。
身近な例を上げるなら、すごろくや人生ゲームといったものが一種のマルコフ連鎖の例と言える。
n-gramとマルコフ連鎖を使った文章生成
本来は確率を使ってどうこうするけど、Scalaでそれをやってしまうと処理速度的に心配なので次に出てくる文字列をひたすら追加しそこからランダムで選択することにした。
それが次のコード
import scala.io.{Source,BufferedSource} import scala.collection.mutable.{Map,ArrayBuffer} import scala.util.Random object Markov{ //tri-gramを想定 private [this] val n:Int = 3 def main(args:Array[String]):Unit = { //ngramの分割結果と次に続く文字列を格納する var ngramMap:Map[String,ArrayBuffer[String]] = Map[String,ArrayBuffer[String]]() //ファイルから一行ずつ読み込む val source:BufferedSource = Source.fromFile("kokoro.dat","utf-8") val lines:Iterator[String] = source.getLines //ngramで分割 for(line <- lines){ var tmp_line:String = line var split_str:String = tmp_line.take(this.n) //先頭文字列だけ独立して追加 if(!ngramMap.contains(tmp_line.take(this.n))) ngramMap += ( split_str -> ArrayBuffer.empty[String] ) tmp_line = tmp_line.tail while(tmp_line.length >= this.n){ var ngramArray:ArrayBuffer[String] = ngramMap(split_str) ngramArray += tmp_line.take(this.n) ngramMap.update(split_str,ngramArray) if( !ngramMap.contains(tmp_line.take(this.n)) ) ngramMap += (tmp_line.take(this.n) -> ArrayBuffer.empty[String]) split_str = tmp_line.take(this.n) tmp_line = tmp_line.tail } } //先頭文字列選択を行う val rnd:Random = new Random var result_str:String = ngramMap.keys.toList(rnd.nextInt(ngramMap.size)) var tmp_str:String = result_str while(!result_str.contains("。")){ var next_wordArray:ArrayBuffer[String] = ngramMap(tmp_str) tmp_str = next_wordArray(rnd.nextInt(next_wordArray.size)) result_str += tmp_str.last } println(result_str) } }
これを実行することによって得たいくつかの文章は次の通り
ひどい文もできていたので比較的ましなものを選択した。
叔父だの叔母だの、その性質としてよかった。 耳に異様な調子をもっと底の方に沈んだ心を大事そうに聞いた。 端書を受けない事はできないかと疑ってみました。 かも彼らは、退屈のために箒で背中を向けた。 今東京へ出て来たといって褒めるのですから、私には分りませんでした。 生と異なる点を明白に述べなければ純白でなくっちゃなるまですでに妻を迎えたらしい。 父に万事をやっ付けて離さない悠長な田舎にありませんでした。 思うかと、奥さんをどうしてもいいました 酸にも聞こえる試しはまるで頼りにするのは定めていた私が、それは迷惑そうな顔をちょっと顔だけ向け直して来て、いつの間にか暮れて春になりました。 まだ起きているのであった。
ngramだと単語が意味を持たないので、計算コストは低いけど出来上がる文が時折変な文になってしまう。
マルコフ連鎖を採用しているのも原因の一つであるけど。
