マルコフ連鎖による文章の自動生成

「PEAR::Net_SmartIRC を使って、一定間隔でニュースを配信する IRC BOT を作成する」で作成したごく簡単な BOT はしかし、外部のリソースをひっぱってきて、それを単にそのまま流すことしかできません（RSS をパースする処理はあるけど、本質的には垂れ流してるだけ）。通常 IRC BOT というと、チャンネルのメンバが喋った言葉を憶え、それらをアレンジしたデータを用いて、時には当意即妙に会話に介入することもあればまるで的はずれな発言で場を微妙な雰囲気に陥れることもあるといったものですし、また、なかには日記や Blog を書くすごい BOT さんもいます。

そうなると当然、次の目標は「おしゃべりをする、あるいは日記を書く BOT を作成する」というものになるわけですが、まぁ僕の頭ではいきなりそんなことを実現することは不可能ですし、また、そのような方向で BOT を作成するにしても、少なくないステップをひとつひとつクリアしていかなければなりません。そこで、前準備として任意の入力データをアレンジして文章を自動的に生成する仕組みを作ってみたいと思います。

「文章を自動的に生成する」と書くのは簡単ですが、さて実際にそれを実現しようとなると、どのようにすればいいのか。たとえばごくごく単純に、文字列を一文字ずつ分割して、それらの文字を適当な長さになるまでランダムに配置する、とまずは考えたのですが、まぁ考えるまでもなく、そのようにしてできあがった「文章」はほぼ確実に意味不明なものになるでしょう。とすれば、入力文字列をなんらかの方法で分割する必要はあるにしても、その分割のしかたが問題になるわけです。

そこであれこれ調べてみたところ、形態素解析なる手法を用いて文字列を分割するのがよさそうだということがわかりました。形態素解析 (Morphological Analysis) とは自然言語処理の基礎技術のひとつで、自然言語で書かれた文章を形態素 (Morpheme, おおまかにいえば「単語」) の列に分割し、品詞 (Part-of-speech) を見分ける作業であるとのことであり、つまりは先に考えた文字列を一文字ずつ分割するという手法とはまったく異なり、文法的な最小単位で分割するというものであり、この手法を用いれば文字列の分割についてはなんとかなりそうです。

その形態素解析を行ってくれるソフトウェアにはいくつかの種類があるようですが、ここでは「茶筌」を使うことにします（とはいえ、この選択には特に意味はなくて、単に最初にみつけたものをインストールしてみたらうまく動いたから使い続けているという、まぁアレな話）。ChaSen's Wiki - ソースからのインストール」を参考に、僕の環境では次のソフトのそれぞれ最新版らしきものを、以下の順序でインストールしました。

茶筌により、たとえば「僕は、電波を受信しません。受信するのはラジオです。僕はラジオではない。ラジオは僕の脳内にある。僕の脳は、電波を受信する。」を形態素に分割すると、以下のようになります（形態素ごとに、半角スペースで区切っています）。

$ echo 僕は、電波を受信しません。受信するのはラジオです。僕はラジオではない。ラジオは僕の脳内にある。僕の脳は、電波を受信する。 | chasen -F "%m "
$ 僕 は 、 電波 を 受信 し ませ ん 。 受信 する の は ラジオ です 。 僕 は ラジオ で は ない 。 ラジオ は 僕 の 脳 内 に ある 。 僕 の 脳 は 、 電波 を 受信 する 。

さて、文字列をなんかしら意味ある方法でもって分割することができました。「文章を自動生成する」ためには、この分割した形態素群を、なんらかの方法で再配置しなければなりません。その際、また単純な考えで形態素をランダムに配置するというのでは、先の一文字ずつをランダムに配置するよりはいくらかはマシとはいえ、そう変わりのない意味不明な文章になってしまうでしょう。どうすればいいか。

形態素に分割した文字列を再配置することで文章を生成する手法にはどういったものがあるのでしょうか。僕は文系っつか、まぁ算数的な方面にはまるで疎くて、どのようにすればいい具合に文章を作成することができるのか、その方法を思いつくこともできませんし、また、すでにあるのだろうそのような手法も知りませんでした。そこで、いつも楽しませてもらっている読兎さんや、またなまこさんという IRC BOT が採用しているらしい「マルコフ連鎖」なる手法を使ってみることにしました。このマルコフ連鎖、信州大学サイト内の確率論について述べた文章中に 1 章を使って説明されている（「確率論 - 第 4 章「マルコフ連鎖」」）のですが、なんつーか、まったく理解できません！理屈を述べられてもどうしようもないので、とりあえず実装例をくれ！というわけで検索してみたところ、markov.pl なる、いかにもソレっぽい perl スクリプトを見つけました。が、まぁ…それでもよくわかりません。そこで、このスクリプトについて教えを請うつもりで「#順列都市」に質問を投げるつもりが、間違えてつい前日に初めて参加させていただいたばかりの「#yomiusa」（読兎さんがいらっしゃるチャンネルです。楽しい）に誤爆してしまいました…。わけのわからないやつが不躾なことをしでかしたにも関わらず、親切な方が、マルコフ連鎖について知りたければ「Namako Project - bots/Markov1.pm」を見るといいんじゃないか、という感じで教えてくださいました！そうです。僕がそもそもわけわかってないのは、そもわかち書きした後の形態素群をどのような構造のデータにすればいいのかということで、上にリンクしたページにはその辺りを含めてばっちり書かれてあります。いけそうな気がしてきました。

さてマルコフ連鎖とは、JMarkov という、マルコフ連鎖による文章の自動生成を行う Java アプレットに付された解説によれば文章を、複数語からなるプレフィクス(接頭語句)と、プレフィクスに続く1語のサフィックス(接尾語)に分割します。そしてオリジナルのテキストの統計に基づいてプレフィクスの後ろにくるサフィックスをランダムに選び、文章を出力するというものであるとのこと。具体的には以下の通りになります。

プレフィクス(接頭語句)を 2 語とすると、先に茶筌により形態素群に分割した例（「僕は、電波を受信しません。受信するのはラジオです。僕はラジオではない。ラジオは僕の脳内にある。僕の脳は、電波を受信する。」）をまずは次のようなペアに分割します（長くなるので、適当なところで端折ってます）。

接頭語句	接尾語
（開始）僕は	ラジオ
はラジオ	で
ラジオで	は
では	ラジオ
ない	。
省略	省略
受信する	。
する。	（終了）

このようにして得た「接頭語句 + 接尾語」のペア群を文章として再配置するにあたり、「接頭語句 + ランダムに選ばれた接尾語」 -> 「直前の接尾語を含む接頭語句 + その接尾語からランダムに選ばれた語」 -> 「さらにまたその直前の接尾語を含む接頭語句 + その接尾語からランダムに選ばれた語」…というふうに連鎖させていきます。イメージ的にいうと「2 歩進んで 1 歩下がり、また 2 歩進んで 1 歩下がる」という感じで、その 2 歩進む際の語をランダムに選択することで、元の文章をアレンジしていくわけです。また、ここでは接頭語句を 2 語としましたが、3 語、4 語と増やしていけばさらに意味のある文章を生成することもできますが、ただ単純に語数を増やすだけでは、元とあまり変わりのない文章が生成されるだけで、あまり面白くないことになってしまいます。まぁ、いろいろ考えればもっと面白くできるのでしょうが、僕の頭の限界がここら辺にあるようなので、このままいくことにします。

それではマルコフ連鎖による文章の自動生成の概要をなんとなく理解したところで、PHP により実装してみたいと思います。以下にスクリプトを示します。僕の目論見としては、「Namako Project - bots/Markov2.pm」と同様のやり方で文章を生成するようにしたつもりです。まぁ、perl スクリプトを読んだわけじゃない（perl わかんない…）ので、実際はどうなのかはわからないけどｗ

markov.php

<?php

/**
 * 入力文字列を形態素解析し、マルコフ連鎖アルゴリズムを用いて文章を生成する
 *
 *  入力文字列:     $text
 *  生成された文章: $data
 *
 **/

$max_cnt = 100;       // ループの最大回数
$EOS = "EOS";         // 終端文字列
$break_mark = "。";   // 改行に変換する目印
$break_frequency = 2; // 改行の頻度

// 入力文字列を整形
$text = mb_convert_kana($text, "R");                   // 半角英字を全角に変換
$text = htmlspecialchars($text);
$patterns = array("/[\n\r]/", "/　+/");
$replacements = array("", "");
$text = preg_replace($patterns, $replacements, $text); // ウザい文字列を置換

// 茶筅で分かち書きした結果を配列に格納
$escaped_text = EscapeShellCmd($text);
exec("/bin/echo $escaped_text | /usr/local/bin/chasen -e -F \"%m\n\"", $parsed_text);

$cnt = count($parsed_text);
$ary = array();

// perfix と suffix のペアに分割
for ($i = 0; $i < $cnt; $i++) {

  if ($i == 0) {
    $prefix1 = $parsed_text[$i];
    $prefix2 = $parsed_text[($i + 1)];
    $suffix = $parsed_text[($i + 2)];
    $ary[$prefix1] = array($prefix2 => array($suffix));
  } elseif ($i < ($cnt - 1)) {
    $prefix1 = $parsed_text[($i - 1)];
    $prefix2 = $parsed_text[$i];
    $suffix = $parsed_text[($i + 1)];
    if (!(isset($ary[$prefix1]))) {
      $ary[$prefix1] = array($prefix2 => array($suffix));
    } elseif (isset($ary[$prefix1]) && !(isset($ary[$prefix1][$prefix2]))) {
      $ary[$prefix1][$prefix2] = array($suffix);
    } else {
      if (!in_array($suffix, $ary[$prefix1][$prefix2])) {
        $ary[$prefix1][$prefix2] = array_merge($ary[$prefix1][$prefix2], array($suffix));
      }
    }
  } elseif ($i == ($cnt - 1)) {
    $prefix1 = $parsed_text[($i - 1)];
    $prefix2 = $parsed_text[$i];
    $suffix = $parsed_text[$i];
    if (!(isset($ary[$prefix1]))) {
      $ary[$prefix1] = array($prefix2 => array($suffix));
    } else {
      $ary[$prefix1][$prefix2] = array($suffix);
    }
  }

}

// スタート文字列は 1 番目の文字
// 2, 3 番目は配列からランダムにキー・値を取得
$first = key($ary);
$second = array_rand($ary[$first]);
srand();
$num = rand(0, (count($ary[$first][$second]) - 1));
$third = $ary[$first][$second][$num];
$data .= $first . $second;

// マルコフ連鎖により、文章を生成
for ($i = 0; $i < $max_cnt; $i++) {

  // 1 番目の文字列
  $first = $third;

  // 2 番目の文字列
  $second = array_rand($ary[$first]);

  // 3 番目の文字列
  srand();
  $num = rand(0, (count($ary[$first][$second]) - 1));
  $third = $ary[$first][$second][$num];

  // 文字列の終端にぶちあたったら、ループ終わり
  if ( ($second == $EOS) || ($third == $EOS) ) {
    break;
  }

  // $break_frequency な頻度で $break_mark に改行文字(\n)を付す
  srand();
  $num = rand(1, $break_frequency);
  if ((($break_frequency - $num) == 0) && ($first == $break_mark)) {
    $data .= $first . "\n" . $second;
  } else {
    $data .= $first . $second;
  }

}

$data = mb_convert_kana($data, "a");  // 全角英字を半角に変換

?>

…とまぁ、スクリプトをぼこんと置かれてもなんのことやらという感じでしょうから、ともあれ Web から試してみることができるようにしたページを用意したので、実際にいろいろやってみていただきたいと思います。また、スクリプトの実行後、入力文字列がどのような構造のデータに変換されるのかを表示するようにしましたので、実際にどのような処理が行われているのかを理解したいという奇特な方は、御利用下さい。