Stellaqua - TOMの技術日記 このページをアンテナに追加 RSSフィード

2009年07月13日

[]MeCabマルコフ連鎖で文章生成をやってみた

何となく"マルコフ連鎖"という単語に魅かれて、ちょっとやってみました。

mecab でマルコフ連鎖をためしてみる。 - コードを舐める日々

まずスクレイピング

まぁ、当然(?)、PHPでやる訳ですが、まずスクレイピングをどうしようかなと思ったんですが、HTMLScrapingという素晴らしいPHPクラスがあるので、ありがたく使わせて頂く事にしました。

404 Not Found

<?php
try {
    $hs = new HTMLScraping();
    $url = 'http://www.asahi.com';
    $xml = $hs->getXmlObject($url);
    $li = $xml->xpath('//div[@id="HeadLine"]/ul[@class="Lnk FstMod"]/li[1]/a');
    $url_news = $url.$li[0]['href'];
    $news = $hs->getXmlObject($url_news);
    $texts = $news->xpath('//div[@class="BodyTxt"]/*');
} catch ( Exception $e ) {
    return false;
}
$text = implode('', $texts);
$text = preg_replace('/(\n| |\s)/', '', $text);
?>

こんな程度で、XPathで自由に欲しい部分が抜き出せてしまいます。素晴らしい。

MeCabによる分かち書き

これはもう、mecabコマンドに任せちゃえって事で、次のような1行だけで。

<?php
$words = explode(' ', `echo '${text}' | mecab -Owakati`);
?>

そしてマルコフ連鎖

そして、肝心のマルコフ連鎖の部分について。

まずは分かち書きで得られた単語リストを、頭から3単語ずつのかたまりにしたマルコフ連鎖用テーブルを作ります。

<?php
$table = array();
for ( $i = 0; $i < count($words) - 2; $i++ ) {
    $table[] = array($words[$i], $words[$i + 1], $words[$i + 2]);
}
?>

こんな感じですね。

あとはこのテーブルを使って、3単語の前2つをキーにして次の単語になる候補を探して、見つかった候補から乱数で選びながら連鎖を続けていけばOKですね。

<?php
$key[0] = $table_markov[0][0];
$key[1] = $table_markov[0][1];

$result = implode('', $key);
while ( true ) {
    $values = $this->_searchAvailableValues($table_markov, $key);
    $value = $values[array_rand($values)];
    if ( $value === '' ) {
        break;
    }
    $result .= $value;
    $key[0] = $key[1];
    $key[1] = $value;
}
?>

次の候補を探す_searchAvailableValuesメソッドは、次のような感じで。

<?php
function _searchAvailableValues ( $table, $key )
{
    $values = array();
    foreach ( $table as $row ) {
        if ( $row[0] === $key[0] && $row[1] === $key[1] ) {
            $values[] = $row[2];
        }
    }
    return $values;
}
?>

実際に試してみる

それぞれの処理をメソッドに分割してクラス化して、次のように順番に呼び出すようにしてやれば、マルコフ連鎖の出来上がりです。

<?php
require_once(dirname(__FILE__).'/lib/Markovchain.php');
$mc = new Lib_Markovchain();

// asahi.comからヘッドラインニュースの本文を取得する
$newstext = $mc->getNewsTextFromAsahicom();

// MeCabの分かち書きで単語に分解する
$words = $mc->wakatiText($newstext);

// 単語リストからマルコフ連鎖用単語テーブルを作る
$table = $mc->buildTable($words);

// マルコフ連鎖により文書を生成する
$sentense = $mc->buildSentense($table);

echo $newstext."\n";
echo ''."\n";
echo $sentense."\n";
?>

実際動かしてみたら、現時点で次のような感じでした。

民主、共産、社民、国民新の野党4党は13日、麻生首相と自公連立政権による国政運営は限界に来ているとして、衆院内閣不信任決議案を、参院首相問責決議案をそれぞれ提出した。内閣不信任案は14日の衆院本会議で否決されるが、首相問責決議案は参院野党が多数を占めているため、近く本会議で可決の見通し。参院での首相問責可決は昨年の福田首相に次いで2例目になる。

民主、共産、社民、国民新の野党4党は13日、麻生首相と自公連立政権による国政運営は限界に来ているため、近く本会議で否決されるが、首相問責決議案を、参院首相問責決議案を、参院首相問責決議案をそれぞれ提出した。内閣不信任案は14日の衆院本会議で否決されるが、首相問責決議案は参院野党が多数を占めているため、近く本会議で可決の見通し。参院野党が多数を占めているとして、衆院内閣不信任案は参院での首相問責決議案を、参院首相問責決議案を、参院首相問責可決は昨年の福田首相に次いで2例目になる。

ちなみに元記事で、"マルコフ連鎖で要約"という事が書かれているんですが、マルコフ連鎖って原理的に要約になるとは限らないんじゃないかなと。特に長い文章が元になっていると、ループが発生する可能性が増えるので、上記みたいに、むしろ文章が伸びる方が多い気がします。

…と思って、リンクを辿っていっていたら、マルコフ連鎖でちゃんと要約っぽくやっているブックマークレットを作っている方がいました。

選択範囲を要約する人工無能ブックマークレット(680バイト) | うえぽんSW局(旧)

これがうまく要約になっているのは、短い文章のそれぞれの終りが終了条件になっているから、割と短く文章が終わる可能性が高いからでしょうね。まぁ、マルコフ連鎖が一番威力を発揮するのは、チャットのログなんかを元にして文章を生成するタイプの人工無脳とかなんではないかなと思います。

そういえば、人工無脳は昔、結構興味があって、まだあんまりプログラムがまともに書けない頃に試行錯誤していたんですが、結局思ったモノができなくてあきらめてしまった…なんて事を思い出しました…。*1

TDDのススメ

今回、テストファーストでテストを書きながら実装したんですが、やっぱりTDDだと安心して実装に取り組めて良いですね。

特にDocTestでやっていると、

  • メソッド名と引数を決める
  • コメントで簡単な説明を書く
  • テストを書く
  • 実装する

っていう一連の流れが、ウィンドウ切り替えとかが一切無しで同じファイル内でできるので、非常にスムーズになりますね。

もし「TDD? 何それ、こわい…」という方がいらっしゃったら、テスト講座をぜひ見てみて下さいね〜。(と、何となく宣伝してみるテスト。)

最後に、せっかくなので、完成したクラスのソースを、テスト付きで載せておきたいと思います。↓

今回作ったクラスのソース

<?php
require_once(dirname(__FILE__).'/HTMLScraping.class.php');

class Lib_Markovchain
{
    /**
     * getNewsTextFromAsahicom
     *
     * asahi.comからヘッドラインニュースの本文を取得する
     *
     * #test 返り値がfalseやnullでない事
     * <code>
     * $result = #f();
     * #ne(false, $result);
     * #ne(null, $result);
     * </code>
     * #test HTMLタグを含まず改行・空白の無い1行のテキストである事
     * <code>
     * $result = #f();
     * #true(preg_match('/<.*>/', $result) !== 1);
     * #true(preg_match('/\n/', $result) !== 1);
     * #true(preg_match('/(\s| )/', $result) !== 1);
     * </code>
     *
     * @access public
     * @return string ニュース本文
     */
    function getNewsTextFromAsahicom ( )
    {
        try {
            $hs = new HTMLScraping();
            $url = 'http://www.asahi.com';
            $xml = $hs->getXmlObject($url);
            $url_news = $url.$li[0]['href'];
            $news = $hs->getXmlObject($url_news);
            $texts = $news->xpath('//div[@class="BodyTxt"]/*');
        } catch ( Exception $e ) {
            return false;
        }
        $text = implode('', $texts);
        $text = preg_replace('/(\n| |\s)/', '', $text);
        return $text;
    }

    /**
     * wakatiText
     *
     * MeCabを使って文章を単語に分解する
     * 文章の終りを示す為、最後の要素は空文字列とする
     *
     * #test 正しく分かち書きされた単語リストが得られる事
     * <code>
     * #eq(array('これ','は','ペン','です','。',''), #f('これはペンです。'));
     * </code>
     * #test 引数が空文字列の時は空文字列を1つだけ含む配列を返す事
     * <code>
     * #eq(array(''), #f(''));
     * </code>
     *
     * @param string $text
     * @access public
     * @return array 分かち書きした単語リスト
     */
    function wakatiText ( $text )
    {
        $words = explode(' ', `echo '${text}' | mecab -Owakati`);
        $words[count($words)-1] = '';
        return $words;
    }

    /**
     * buildTable
     *
     * 単語リストからマルコフ連鎖用単語テーブルを作る
     *
     * #test 単語リストが単語3つ+終端の場合
     * <code>
     * $expects = array(
     *     array('私', 'は', 'カモメ'),
     *     array('は', 'カモメ', ''),
     * );
     * #eq($expects, #f(array('私', 'は', 'カモメ', '')));
     * </code>
     *
     * @param array $words 単語リスト
     * @access public
     * @return array マルコフ連鎖用単語テーブル
     */
    function buildTable ( $words )
    {
        $table = array();
        for ( $i = 0; $i < count($words) - 2; $i++ ) {
            $table[] = array($words[$i], $words[$i + 1], $words[$i + 2]);
        }
        return $table;
    }

    /**
     * buildSentense
     *
     * 単語テーブルを元にマルコフ連鎖で文字列を構築する
     *
     * #test 単語の組み合わせが1通りだけの場合
     * <code>
     * $table_markov = array(
     *     array('私', 'は', 'カモメ'),
     *     array('は', 'カモメ', ''),
     * );
     * #eq('私はカモメ', #f($table_markov));
     * $table_markov = array(
     *     array('私', 'は', 'カモメ'),
     *     array('は', 'カモメ', 'を'),
     *     array('カモメ', 'を', '見た'),
     *     array('を', '見た', ''),
     * );
     * #eq('私はカモメを見た', #f($table_markov));
     * </code>
     * #test 単語の組み合わせが2通りの場合
     * <code>
     * $table_markov = array(
     *     array('私', 'は', 'カモメ'),
     *     array('私', 'は', 'ウミドリ'),
     *     array('は', 'カモメ', ''),
     *     array('は', 'ウミドリ', ''),
     * );
     * $result = #f($table_markov);
     * #true($result === '私はカモメ' || $result === '私はウミドリ');
     * </code>
     *
     * @param array $table_markov マルコフ連鎖用単語テーブル
     * @access public
     * @return string マルコフ連鎖で構築された文字列
     */
    function buildSentense ( $table_markov )
    {
        $key[0] = $table_markov[0][0];
        $key[1] = $table_markov[0][1];

        $result = implode('', $key);
        while ( true ) {
            $values = $this->_searchAvailableValues($table_markov, $key);
            $value = $values[array_rand($values)];
            if ( $value === '' ) {
                break;
            }
            $result .= $value;
            $key[0] = $key[1];
            $key[1] = $value;
        }
        return $result;
    }

    /**
     * _searchAvailableValues
     *
     * マルコフ連鎖で次の値となる候補を検索する
     *
     * #test 候補が1つだけの場合
     * <code>
     * $table = array(
     *     array('私', 'は', 'カモメ'),
     *     array('は', 'カモメ', ''),
     * );
     * $expects = array('カモメ');
     * #eq($expects, #f($table, array('私', 'は')));
     * </code>
     * #test 候補が2つの場合
     * <code>
     * $table = array(
     *     array('私', 'は', 'カモメ'),
     *     array('私', 'は', 'ウミドリ'),
     *     array('は', 'カモメ', ''),
     *     array('は', 'ウミドリ', ''),
     * );
     * $expects = array('カモメ', 'ウミドリ');
     * #eq($expects, #f($table, array('私', 'は')));
     *
     * @param array $table マルコフ連鎖用単語テーブル
     * @param array $key 検索キー
     * @access private
     * @return array マルコフ連鎖の値候補リスト
     */
    function _searchAvailableValues ( $table, $key )
    {
        $values = array();
        foreach ( $table as $row ) {
            if ( $row[0] === $key[0] && $row[1] === $key[1] ) {
                $values[] = $row[2];
            }
        }
        return $values;
    }
}
?>

*1:当時、チャットのログからマルコフ連鎖用単語テーブルを作ってDBに放り込んで、SQLでゴニョゴニョしながら文書生成する実装を、LLではなく、シェルスクリプトで書いた事があったような覚えがおぼろげながら…。

spespe 2015/02/06 04:13 変数thisは何ですか?

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証

トラックバック - http://d.hatena.ne.jp/stellaqua/20090713/1247487382