#SP2LCとの関わり
2年生からSP2LCと全国高専プログラミングプロジェクトに入って，現在4年生です．
主に自然言語処理に手を出しています．
#はじめに
チャットボット（人工無脳）に使われる方法である，
__形態素解析__と__マルコフ連鎖__を使って新たな文を作るアルゴリズムについてまとめました．
今回の手法を使った有名なチャットボットとしてしゅうまい君などがあります．
#形態素解析とは
形態素解析とは、文法的な情報の注記の無い自然言語のテキストデータ（文）から、対象言語の文法や、辞書と呼ばれる単語の品詞等の情報にもとづき、__形態素（おおまかにいえば、言語で意味を持つ最小単位）の列に分割__し、それぞれの形態素の品詞等を判別する作業である。（Wikipediaより）
簡単にいうと，文を解析して単語ごとに区切ったり，品詞や読み等の情報を得ることです．
今回は__単語ごとに区切る__ために使用します．
#マルコフ連鎖とは
マルコフ連鎖は、__未来の挙動が現在の値__だけで決定され、__過去の挙動と無関係__である。各時刻において起こる状態変化（遷移または推移）に関して、マルコフ連鎖は遷移確率が過去の状態によらず、現在の状態のみによる系列である（Wikipediaより）
今回の現在の値とは__単語ごとに区切った１つの塊__を指し，
未来の挙動とは__その単語に続く単語ごとの塊__を示します．
#新たな文を作ってみる
それでは文生成の仕組みについて説明します．
以下の2つの文があるとします．
（１）私はラーメンが好きです。
（２）俺はラーメンが嫌いだ。
これらの文を，形態素解析によって単語ごとに区切ると，以下のようになります．
（１）私 は ラーメン が 好き です 。
（２）俺 は ラーメン が 嫌い です 。
ここから，共通の単語をまとめて有向グラフを生成すると以下のようになります．
あとはこのグラフの全ての経路をたどっていけば，入力の2文とそれ以外の文が生成されます．
全て列挙すると，以下のようになります．
（１）私 は ラーメン が 好き です 。
（２）俺 は ラーメン が 嫌い です 。
（３）私 は ラーメン が 嫌い です 。(New)
（４）俺 は ラーメン が 好き です 。(New)
仕組みは以上です．
プログラム上の動きとしては，
まず，形態素解析によって分けた単語を数個の塊にします．今回は3単語で1つの塊としています．
（１）
(BOS) 私 は
私 は ラーメン
は ラーメン が
ラーメン が 好き
が 好き です
好き です 。
です 。（EOS）
（２）
(BOS) 俺 は
俺 は ラーメン
は ラーメン が
ラーメン が 嫌い
が 嫌い です
嫌い です 。
です 。（EOS）
BOS（Begin of sentence）は文の始まり，
EOS(End of sentence)は文の終わりを示します．
あとは，
BOSを始点，EOSを終点として，
しりとりのように，各グループの最後の単語を探索していくことでグラフをたどることができます．
#おわりに
今回は2つの文を入力とした単純な例でした．
多くの違う構造の文を入力すればするほど，グラフのネットワークは複雑になり，探索時間は増大しますが，
その分面白い文も生成されるので，ぜひやってみてください！