MAGAZINE

ルーターマガジン

データ/フォーマット

マルコフ連鎖での文章自動生成

2018.11.16
Pocket

初めまして、ルーターの学生アルバイトのhashimotoです。

9月中旬からルーターに入り、研修を終えて、少しずつ業務をさせていただいています。

今回は、その中で最初にやらせていただいた、マルコフ連鎖を用いた文章自動生成についてご紹介させていただきたいと思います

マルコフ連鎖のロジック

今回使用するマルコフ連鎖のロジックは以前のルーターブログで紹介しているロジックと基本的に同じものになります。

「マルコフ連鎖の文章生成について検証してみた」

このロジックで行っていることを説明します。

まず、文章を形態素解析して単語に分割します。そして、2つの単語をkeyとして、それに続く単語をvalueとするハッシュを作成します。(初期値として"BEGIN"を2つ、終値として"END"を登録しています。)あとはこのハッシュに従って次の単語の予測を繰り返すことで文章が自動生成されます。

今回はこの方法はそのまま用いて、前処理である形態素解析や後処理として文章の長さや元の文章との類似度を測るといったことについて書いていきます。

テキストの前処理

今回はサンプルとしてRubyのwikipediaの概要の部分を使ってみようと思います。
Ruby は1993年2月24日に生まれ、1995年12月にfj上で発表された。名称の Ruby は、プログラミング言語 Perl が6月の誕生石である Pearl(真珠)と同じ発音をすることから、まつもとの同僚の誕生石(7月)のルビーを取って名付けられた。競合言語として Perl の他に Python があり、「Matz(まつもと) が Python に満足していれば Ruby は生まれなかったであろう」と公式のリファレンスの用語集で言及されている。機能として、クラス定義、ガベージコレクション、強力な正規表現処理、マルチスレッド、例外処理、イテレータ、クロージャ、Mixin、利用者定義演算子などがある。Perl を代替可能であることが初期の段階から重視されている。Perlと同様にグルー言語としての使い方が可能で、C言語プログラムやライブラリを呼び出す拡張モジュールを組み込むことができる。Ruby 処理系は、主にインタプリタとして実装されている(詳しくは#実装を参照)。可読性を重視した構文となっている。Ruby においては整数や文字列なども含めデータ型はすべてがオブジェクトであり、純粋なオブジェクト指向言語といえる。長らく言語仕様が明文化されず、まつもとによる実装が言語仕様に準ずるものとして扱われて来たが、2010年6月現在、JRuby や Rubinius といった互換実装の作者を中心に機械実行可能な形で明文化する RubySpec という試みが行われている。公的規格としては2011年3月22日にJIS規格(JIS X 3017)が制定され、その後2012年4月1日に日本発のプログラム言語では初めてISO/IEC規格(ISO/IEC 30170)として承認された。フリーソフトウェアとしてバージョン1.9.2までは Rubyライセンス(Ruby License や Ruby'sと表記されることもある。GPLかArtisticに似た独自ライセンスを選択するデュアルライセンス)で配布されていたが、バージョン1.9.3以降は2-clause BSDLで配布されている。

https://ja.wikipedia.org/wiki/Ruby

この文章をそのままmecabで形態素解析し、文章を生成すると以下のようなものが生成されます。

Rubyは生まれなかったであろう」と公式のリファレンスの用語集で言及された。フリーソフトウェアとしてバージョン1.9.3以降は2-clauseBSDLで配布されている。Ruby処理系は、プログラミング言語Perlが6月の誕生石であることができる。Rubyにおいては整数や文字列なども含めデータ型はすべてがオブジェクトであり、「Matz(まつもと)がPythonに満足していればRubyは1993年2月24日に生まれ、1995年12月にfj上で発表されず、まつもとによる実装が言語仕様に準ずるものとして扱われている。機能として、クラス定義、ガベージコレクション、強力な正規表現処理、マルチスレッド、例外処理、イテレータ、クロージャ、Mixin、利用者定義演算子などがある。GPLかArtisticに似た独自ライセンスを選択するデュアルライセンス)で配布されている。

文章の内容が支離滅裂であることはさておき、括弧が閉じられていない部分が多いです。これを解決するために、mecabには指定した正規表現のパターンを1単語とみなしてくれるメソッドとして、enum_parseというメソッドがあります。このメソッドを利用して括弧で囲まれている部分を1単語にして文章を生成してみます。

Rubyは1993年2月24日に生まれ、1995年12月にfj上で発表され、その後2012年4月1日に日本発のプログラム言語では初めてISO/IEC規格(ISO/IEC 30170)として承認された。フリーソフトウェアとしてバージョン1.9.2まではRubyライセンス(Ruby License や Ruby'sと表記されることもある。GPLかArtisticに似た独自ライセンスを選択するデュアルライセンス)で配布された。名称のRubyは1993年2月24日に生まれ、1995年12月にfj上で発表されて来たが、2010年6月現在、JRubyやRubiniusといった互換実装の作者を中心に機械実行可能な形で明文化するRubySpecという試みが行われている。

いかがでしょうか。元の文章と似ているということもありますが、括弧が閉じられているだけで少し読みやすくなったのではないかと思います。

テキストの後処理

このマルコフ連鎖での自動生成をそのまま行うと、次のように、同じ短い文章が何度も生成されてしまいます。(文章の後の数字は文章の文字数を表しています。)

Rubyは1993年2月24日に生まれ、1995年12月にfj上で発表されている。
42
Rubyは1993年2月24日に生まれ、1995年12月にfj上で発表されている。
42
Rubyは、主にインタプリタとして実装され、その後2012年4月1日に日本発のプログラム言語では初めてISO/IEC規格(ISO/IEC 30170)として承認されず、まつもとによる実装が言語仕様に準ずるものとして扱われていたが、2010年6月現在、JRubyやRubiniusといった互換実装の作者を中心に機械実行可能な形で明文化するRubySpecという試みが行われていたが、2010年6月現在、JRubyやRubiniusといった互換実装の作者を中心に機械実行可能な形で明文化するRubySpecという試みが行われている。
265
Rubyは1993年2月24日に生まれ、1995年12月にfj上で発表されている。
42
Rubyは1993年2月24日に生まれ、1995年12月にfj上で発表されず、まつもとによる実装が言語仕様が明文化されている。
64

ある程度の長さの文章のみ生成したい場合、文字数が指定の範囲内となる文が出てくるまでloop文を回すという処理を付け加えることで解決することができます。以下では、200~400文字で指定して生成してみました。

Rubyは1993年2月24日に生まれ、1995年12月にfj上で発表されていたが、バージョン1.9.3以降は2-clauseBSDLで配布されて来たが、バージョン1.9.2まではRubyライセンス(Ruby License や Ruby'sと表記されることもある。GPLかArtisticに似た独自ライセンスを選択するデュアルライセンス)で配布されている(詳しくは#実装を参照)。可読性を重視した構文となっている。
209
Rubyは1993年2月24日に生まれ、1995年12月にfj上で発表されず、まつもとの同僚の誕生石(7月)のルビーを取って名付けられた。競合言語としてPerlの他にPythonがあり、純粋なオブジェクト指向言語といえる。長らく言語仕様が明文化されて来たが、バージョン1.9.2まではRubyライセンス(Ruby License や Ruby'sと表記されることもある。GPLかArtisticに似た独自ライセンスを選択するデュアルライセンス)で配布されている。
232
Rubyは、プログラミング言語Perlが6月の誕生石であることができる。Ruby処理系は、プログラミング言語Perlが6月の誕生石であることが初期の段階から重視され、その後2012年4月1日に日本発のプログラム言語では初めてISO/IEC規格(ISO/IEC 30170)として承認された。名称のRubyは、プログラミング言語Perlが6月の誕生石であることができる。Ruby処理系は、プログラミング言語Perlが6月の誕生石であるPearl(真珠)と同じ発音をすることから、まつもとによる実装が言語仕様が明文化されて来たが、2010年6月現在、JRubyやRubiniusといった互換実装の作者を中心に機械実行可能な形で明文化するRubySpecという試みが行われている。
338
Rubyは1993年2月24日に生まれ、1995年12月にfj上で発表されていたが、2010年6月現在、JRubyやRubiniusといった互換実装の作者を中心に機械実行可能な形で明文化するRubySpecという試みが行われていたが、バージョン1.9.2まではRubyライセンス(Ruby License や Ruby'sと表記されることもある。GPLかArtisticに似た独自ライセンスを選択するデュアルライセンス)で配布された。名称のRubyは1993年2月24日に生まれ、1995年12月にfj上で発表された。名称のRubyは、主にインタプリタとして実装されていたが、2010年6月現在、JRubyやRubiniusといった互換実装の作者を中心に機械実行可能な形で明文化するRubySpecという試みが行われている。
363
Rubyは、プログラミング言語Perlが6月の誕生石であることができる。Ruby処理系は、プログラミング言語Perlが6月の誕生石であることが初期の段階から重視され、その後2012年4月1日に日本発のプログラム言語では初めてISO/IEC規格(ISO/IEC 30170)として承認されず、まつもとの同僚の誕生石(7月)のルビーを取って名付けられた。名称のRubyは1993年2月24日に生まれ、1995年12月にfj上で発表された。フリーソフトウェアとしてバージョン1.9.3以降は2-clauseBSDLで配布されて来たが、バージョン1.9.3以降は2-clauseBSDLで配布されている(詳しくは#実装を参照)。可読性を重視した構文となっている。
328

また、元の文章と生成した文がどれくらい似ているのかを評価する指標としてcos類似度を測定することもできます。cos類似度は複数の文章において単語の使われる回数から類似度を計算するものです。

cos類似度を見てみるために、Rubyの文章に加え、pythonのwikipediaの概要も形態素解析して文章を生成し、それぞれの類似度を計算してみました。

文法を極力単純化してコードの可読性を高め、読みやすく、また書きやすくしてプログラマの作業性とコードの信頼性を高めることを重視してデザインされた、汎用の高水準言語である。核となる本体部分は必要最小限に抑えられている。一方で標準ライブラリやサードパーティ製のライブラリ、関数など、さまざまな領域に特化した豊富で大規模なツール群が用意され、インターネット上から無料で入手でき、自らの使用目的に応じて機能を拡張してゆくことができる。またPythonは多くのハードウェアとOS (プラットフォーム) に対応しており、複数のプログラミングパラダイムに対応している。Pythonはオブジェクト指向、命令型、手続き型、関数型などの形式でプログラムを書くことができる。動的型付け言語であり、参照カウントベースの自動メモリ管理(ガベージコレクタ)を持つ。これらの特性によりPythonは広い支持を獲得し、Webアプリケーションやデスクトップアプリケーションなどの開発はもとより、システム用の記述 (script) や、各種の自動処理、理工学や統計・解析など、幅広い領域における有力なプログラム言語となった。プログラミング作業が容易で能率的であることは、ソフトウェア企業にとっては投入人員の節約、開発時間の短縮、ひいてはコスト削減に有益であることから、産業分野でも広く利用されている。Googleなど主要言語に採用している企業も多い。Pythonのリファレンス実装であるCPythonは、フリーかつオープンソースのソフトウェアであり、コミュニティベースの開発モデルを採用している。CPythonは、非営利団体であるPythonソフトウェア財団が管理している。その他の実装としては、PyPyやIronPythonなどが有名である。Pythonは、オランダ人のグイド・ヴァンロッサムが開発した。名前の由来は、イギリスのテレビ局 BBC が製作したコメディ番組『空飛ぶモンティ・パイソン』である。Pythonという英単語が意味する爬虫類のニシキヘビがPython言語のマスコットやアイコンとして使われている。

https://ja.wikipedia.org/wiki/Python

結果がこちら

Rubyは1993年2月24日に生まれ、1995年12月にfj上で発表された。プログラミング作業が容易で能率的であることができる。またPythonは広い支持を獲得し、Webアプリケーションやデスクトップアプリケーションなどの形式でプログラムを書くことができる。Rubyにおいては整数や文字列なども含めデータ型はすべてがオブジェクトであり、コミュニティベースの開発モデルを採用してデザインされ、インターネット上から無料で入手でき、自らの使用目的に応じて機能を拡張してコードの信頼性を高めることを重視した構文となった。競合言語としてPerlの他にPythonがあり、コミュニティベースの自動メモリ管理(ガベージコレクタ)を持つ。これらの特性によりPythonはオブジェクト指向、命令型、関数型などの開発はもとより、システム用の記述(script)や、各種の自動処理、マルチスレッド、例外処理、イテレータ、クロージャ、Mixin、利用者定義演算子などがある。Perlを代替可能で、C言語プログラムやライブラリを呼び出す拡張モジュールを組み込むことができる。またPythonは多くのハードウェアとOS(プラットフォーム)に対応している。
515
rubyとのcos類似度:0.45067594598575533
pythonとのcos類似度:0.5874024741747915

rubyとpythonの概要が混ざった文章が生成でき、少しpythonの方に近いものになりました。

まとめ

今回使用したマルコフ連鎖では、文章が生成できるものの、自然とは言いづらいものでした。deeplearningなどではもっと自然な文章が生成できるのかもしれません。

他の方法で自動生成する場合でも、今回ご紹介した前処理、後処理は使えることもあると思います。

ルーターに入りこのようなテキスト処理やWebスクレイピングをさせていただきながら仕事としてプログラミングに触れられることで貴重な体験ができています。

プログラミングに興味のある方や、学んだプログラミングを生かしてみたい方はぜひこちらからアルバイトに応募してみてください。

ソース

require 'natto'
require 'pp'
require 'enumerator'
require 'matrix'

$markov_model = {}
# ----------------形態素解析
# ----------------辞書的なものの作成
def parse_text(text)
    mecab = Natto::MeCab.new
    text = text.strip
    # 形態素解析したデータを配列に分けて突っ込む
    # 先頭にBEGIN、最後にENDを追加
    data = ["BEGIN","BEGIN"]
    mecab.parse(text) do |a|
        if a.surface != nil
            data << a.surface
        end
    end
    data << "END"
    data.each_cons(3).each do |a|
        suffix = a.pop
        prefix = a
        $markov_model[prefix] ||= []
        $markov_model[prefix] << suffix
    end
end

#括弧を1単語とする
def parse_text_array(text)
    nm = Natto::MeCab.new
    # 形態素解析したデータを配列に分けて突っ込む
    # 先頭にBEGIN、最後にENDを追加
    data = ["BEGIN","BEGIN"]

    nm = Natto::MeCab.new('-F%m')
    pattern = /「.*?」|<.*?>|\(.*?\)|【.*?】|≪.*?≫|(.*?)|『.*?』|“.*?”/

    # boundary_constraintsでパターンに当てはまるものは一つの単語として扱える

    if text.match(pattern)
        enum = nm.enum_parse(text, boundary_constraints: pattern)
    else
        enum = nm.enum_parse(text)
    end

    enum.each do |n|
        data << n.feature if !(n.is_bos? || n.is_eos?)
    end

    data << "END"
    #2語をkeyとして続く単語をvalueとしてハッシュに入れる
    data.each_cons(3).each do |a|
        suffix = a.pop
        prefix = a
        $markov_model[prefix] ||= []
        $markov_model[prefix] << suffix
    end
end

# ----------------マルコフ連鎖
def markov()
    # ランダムインスタンスの生成
    random = Random.new
    # スタートは begin,beginから
    prefix = ["BEGIN","BEGIN"]
    ret = ""
    $indexes = []
    loop{
        n = $markov_model[prefix].length
        prefix = [prefix[1] , $markov_model[prefix][random.rand(0..n-1)]]
        if prefix[0] != "BEGIN"
          ret += prefix[0]
      end
        if $markov_model[prefix].last == "END"
            ret += prefix[1]
            break
        end
    }
    return ret
end

# cos類似度の計算
def calc_score(str1,str2)
  vector = []
  vector1 = []
  vector2 = []
  frag_vector1 = []
  frag_vector2 = []

    mecab = Natto::MeCab.new

    mecab.parse(str1) do |a|
        if a.surface != nil
            vector1 << a.surface
        end
    end

    mecab.parse(str2) do |a|
        if a.surface != nil
            vector2 << a.surface
        end
    end

  vector += vector1
  vector += vector2

  vector.uniq!.delete("")
  vector1.delete("")
  vector.delete("")
  vector2.delete("")

  vector.each do |word|
    if vector1.include?(word) then
      frag_vector1.push(1)
    else
      frag_vector1.push(0)
    end

    if vector2.include?(word) then
      frag_vector2.push(1)
    else
      frag_vector2.push(0)
    end
  end

  vector1_final = Vector.elements(frag_vector1, copy = true)
  vector2_final = Vector.elements(frag_vector2, copy = true)

  return vector2_final.inner_product(vector1_final)/(vector1_final.norm() * vector2_final.norm())

end

File.open('ruby.txt',"r") do |file|
    file.each_line do |line|
        parse_text_array(line)
        $str1 =''
        $str1 += line.to_s
    end
end
File.open('python.txt',"r") do |file|
    file.each_line do |line|
        parse_text_array(line)
        $str2 =''
        $str2 += line.to_s
    end
end

count = 0
#文章の長さを指定
max = 600
min = 400
loop{ article = markov()
    if article.length > min && article.length < max
            puts article
            puts article.length
            cos1 = calc_score(article,$str1)
            cos2 = calc_score(article,$str2)
          puts "rubyとのcos類似度:" + cos1.to_s
            puts "pythonとのcos類似度:" + cos2.to_s
            count += 1
  end
    if count >= 1 #生成したい数を指定
        break
    end
 }
Pocket

CONTACT

お問い合わせ・ご依頼はこちらから