マルコフ連鎖実装してみた

2021-02-15

こんにちは

どうも，僕です．

今回はみんな大好きマルコフ連鎖についてです．

コードは[これ](https://github.com/takurinton/ts_markov)．

与えられた文章をもとにして新しい文章を生成するやつを実装しました．ではやっていきます．

マルコフ連鎖って何？

マルコフ連鎖とはどうやら離散マルコフ過程の別称のようです．知らんかった．Twitterで見かけてググってみたら出てきてほへーってなりました．

今回は文章を自動生成するためのマルコフ連鎖を実装していきます．また，何段階にもなるマルコフ連鎖があるようですが（全く知らん）今回は何も手を加えていないものを実装しました．これから勉強していきたいな．

今回実装するアルゴリズムは[このサイト](https://www.pc-koubou.jp/magazine/4238)に出てくる図がわかりやすくて良きだと思ったので参考にしてみてください．

実装する

実装していきたいと思います．

上で説明した通りに実装していきます．

また，使用するライブラリはtiny-segmenterという形態素解析をしてくれるライブラリを使用します．どうやらめちゃくちゃ軽量らしいです．文章を分割したいだけならこれで十分なのでこれを使用します．

文章の整形

まずは文章を整形します．

文章には記号や句読点が含まれているのでそれを replace していきます．

const arrangeText = (text: string): string => {
    text = text.replace(/\n/g, '。');
    text = text.replace(/[\?\!？！]/g, '。');
    text = text.replace(/[-|｜:：・]/g, '。');
    text = text.replace(/[「」（）\(\)\[\]【】]/g, ' ');
    return text;
};

一応関数にしてみました．

難しくはないのでスルーします．

辞書の作成

次は辞書の作成をしていきます．

これも関数に区切って実装していきます．

const TinySegmenter = require('tiny-segmenter');
const segmenter = new TinySegmenter();  // インスタンスを作成

interface Morpheme {
    [key: string]: string[];
};

const START = '__START__';
const END   = '__END__';

const makeDict = (text: string): Morpheme => {
    const sentences = text.split('。');
    const morpheme: Morpheme = {};
    for(var i = 0; i < sentences.length; i++) {
        let tokenized: string[] = segmenter.segment(sentences[i]) // ここでわかち書きを行っている
        if (!morpheme[START]) morpheme[START] = [];
        if (tokenized[0]) morpheme[START].push(tokenized[0]); // 文の先頭の判断
        for (var w = 0; w < tokenized.length; w++) {
            const now: string = tokenized[w];
            const next: string = tokenized[w+1] ?? END; 
            if (!morpheme[now]) morpheme[now] = [];
            morpheme[now].push(next);

            if (now === '、') morpheme[START].push(next); // 、はstartの要素として使えるっぽい
        };
    };
    return morpheme;
};

こんな感じです．　

部分的に説明していきます．

ここでは辞書を格納するためのインターフェイスを定義しています．

interface Morpheme {
    [key: string]: string[];
};

この変数は文章の開始判定と終了判定を判断するための変数として使用しています．TSでの一般的な書き方がいまいち分からなくてPythonっぽくなっちゃったけど気にしない．

const START = '__START__';
const END   = '__END__';

ここでは文章ごとで区切った後に形態素解析を行なっています．

sentencesには文章が，tokenizedには形態素解析された単語が入ります．

const sentences = text.split('。');
const morpheme: Morpheme = {};
for(var i = 0; i < sentences.length; i++) {
        let tokenized: string[] = segmenter.segment(sentences[i]) 
...

形態素解析をしたら次は対応する単語の辞書を作成していきます．

最初のif文では開始判定をしています．開始ではなかったら開始記号を入れてからのリストを入れます．

また，下のfor文では終了までそれぞれの単語に対して辞書を作成しています．

現在の単語と次の単語まで調べて次の単語が存在しなかったら終了記号を入れて次のループに移動します.

if (!morpheme[START]) morpheme[START] = [];
if (tokenized[0]) morpheme[START].push(tokenized[0]); // 文の先頭の判断
for (var w = 0; w < tokenized.length; w++) {
    const now: string = tokenized[w]; 
    const next: string = tokenized[w+1] ?? END; 
    if (!morpheme[now]) morpheme[now] = [];
    morpheme[now].push(next);

関数の最後にあるここの部分は '、' を判定しています．'、' も開始記号として使用することができるのでそこを判断しています．

if (now === '、') morpheme[START].push(next);

辞書の作成はこんな感じです．

文章の生成

次は先ほど作成した辞書を使用して文章の生成を行なっていきます．

文章を生成する関数は以下のような感じになりました．

const makeSentence = (dict: Morpheme): string => {
    let now: string = '';
    let result: string = '';
    now = dict[START][Math.floor(Math.random() * dict[START].length)]; // いい感じにしてる(ぇ
    result += now;
    while (now !== END) {
        now = dict[now][Math.floor(Math.random() * dict[now].length)];
        result += now;
    };
    result = result.replace(END, '。')
    return result;
};

まずは現在の文字列と結果の文字列をそれぞれ定義します．現在の文字列に単語を再代入しまくって文末になったら結果に代入していくみたいな感じのイメージですね．

また，マルコフ連鎖では最初の単語を決めてあげたりすることが多いのですが今回は完全にランダムでやっていきたいと思います．

let now: string = '';
let result: string = '';
now = dict[START][Math.floor(Math.random() * dict[START].length)]; // いい感じにしてる(ぇ
result += now;

次に文末がくるまで while で繰り返し処理を行なっていきます．

ここでもランダムにして取り出していきます．

while (now !== END) {
    now = dict[now][Math.floor(Math.random() * dict[now].length)];
    result += now;
};

最後に文末の記号を '。' に置き換えて戻してあげればおけまるです．

result = result.replace(END, '。')

実行

実行するためのmαin関数を簡単に実装します．

main()関数では1つの文章を生成していますが今回はざっと5個くらい文章を生成したいので5回実行してあげます．

const main = () => {
    const _text: string = arrangeText(text);
    const dict: Morpheme = makeDict(_text);
    const sentence: string = makeSentence(dict);
    console.log(sentence);
};

for (var i = 0; i < 5; i++) {
    main();
};

全部まとめると

全部まとめると以下のような感じになります．

import text from './text';
const TinySegmenter = require('tiny-segmenter');

const segmenter = new TinySegmenter();  // インスタンスを作成
// const segmenter = require('tiny-segmenter'); だと any になってしまうのでクラスを呼んでインスタンスを作成してその中の関数を使用する必要がある

interface Morpheme {
    [key: string]: string[];
};

const START = '__START__';
const END   = '__END__';

const arrangeText = (text: string): string => {
    text = text.replace(/\n/g, '。');
    text = text.replace(/[\?\!？！]/g, '。');
    text = text.replace(/[-|｜:：・]/g, '。');
    text = text.replace(/[「」（）\(\)\[\]【】]/g, ' ');
    return text;
};

const makeDict = (text: string): Morpheme => {
    const sentences = text.split('。');
    const morpheme: Morpheme = {};
    for(var i = 0; i < sentences.length; i++) {
        let tokenized: string[] = segmenter.segment(sentences[i]) // ここでわかち書きを行っている
        if (!morpheme[START]) morpheme[START] = [];
        if (tokenized[0]) morpheme[START].push(tokenized[0]); // 文の先頭の判断
        for (var w = 0; w < tokenized.length; w++) {
            const now: string = tokenized[w];
            const next: string = tokenized[w+1] ?? END; 
            if (!morpheme[now]) morpheme[now] = [];
            morpheme[now].push(next);

            if (now === '、') morpheme[START].push(next); // 、はstartの要素として使えるっぽい
        };
    };
    return morpheme;
};

const makeSentence = (dict: Morpheme): string => {
    let now: string = '';
    let result: string = '';
    now = dict[START][Math.floor(Math.random() * dict[START].length)]; // いい感じにしてる(ぇ
    result += now;
    while (now !== END) {
        now = dict[now][Math.floor(Math.random() * dict[now].length)];
        result += now;
    };
    result = result.replace(END, '。')
    return result;
};

const main = () => {
    const _text: string = arrangeText(text);
    const dict: Morpheme = makeDict(_text);
    const sentence: string = makeSentence(dict);
    console.log(sentence);
};

for (var i = 0; i < 5; i++) {
    main();
};

実行

一応実装は終わったので実行してみます．

npm start

で簡単に実行できます．

npm start

寒さは漸く此頃 の顔の崩れた所でも御臺所で薬罐 つた。
澤山居つた。
其後猫に這つて居る。
下女は遂に遭遇しさうにした。
第一毛を暫く眺めて居 あが を見た。

こんな感じで文章が表示されればおけまるです．なんか怪しい，しっかり日本語になってるか微妙ですがまあ元にしてる文章が吾輩は猫であるだから現代っぽくないだけかもしれません．知らんけど．

とりあえず実行できてるようでよきですね.

まとめ

今回はめちゃくちゃ簡単にですが文章自動生成のスクリプトを書いてみました．

文章になっているかどうかは微妙な感じでしたが，まあなんとかなったかなと思っています．

これからはN階マルコフ連鎖についての理解をしたり自然言語処理の分野についての理解も深めることができるように頑張っていきたいと思いました．