マルコフ連鎖

1.Markov.mkd

マルコフ連鎖

1. マルコフ連鎖とは

    マルコフ連鎖とは、確率過程の一種であるマルコフ過程のうち、とりうる状態が離散的（有限または可算）なもの（離散状態マルコフ過程）をいう。
    また特に、時間が離散的なもの（時刻は添え字で表される）を指すことが多い（他に連続時間マルコフ過程というものもあり、これは時刻が連続である）。
    マルコフ連鎖は、未来の挙動が現在の値だけで決定され、過去の挙動と無関係である（マルコフ性）。
    各時刻において起こる状態変化（遷移または推移）に関して、マルコフ連鎖は遷移確率が過去の状態によらず、現在の状態のみによる系列である。
    特に重要な確率過程として、様々な分野に応用される。
    
    Wikipedia [マルコフ連鎖](http://tinyurl.com/yv87qa/) より
   

2. tiarra にて収集した TimeLine Log からゴミを取り除き plain な文字列とする.

    $ find ~/path/to/tiarra/log/ -name '*.txt' | xargs -n 10 sed -e 's/^.*>//g' | sort | uniq > full.txt
   

3. Log を一行ずつ MeCab により parse していく

4. 今回は 2 階マルコフ連鎖とする.

5. 2 階マルコフ連鎖とは

    2 つの単語のつながりを見て次に出現する単語を確定する方法
   
    例) すもももももももものうち
    ID| Word1 | Word2 | after
    -------------------------
    1 | すもも | も     | もも
    2 | も    | もも    | も
    3 | もも   | も     | もも
    4 | も    | もも    | の
    5 | もも   | の     | うち
    
    といった Chain テーブルができる.
    これにより Word1 と Word2 の 2 つのつながりをみて次に出現する単語がきまるため
    "すもも" からスタートした場合 ID 1 - 2 の繋がりと ID 1 - 3 のつながりの2パターンが生まれる事となります.
   

6. Parse して DB に格納する Script として Markov.rb を作成した.

    ./Markov.rb /path/to/full.log
   

7. Markov.rb では助動詞の連続性を排除しており，助動詞が続く場合は結合してひとつの助動詞とみなしている．

8. テーブルは Word と Chain と分けておき，単語と品詞によって一意としている．

9. また，出現回数を保持することにより確立を加味する事ができるようにしておく．

10. 上記処理にてマルコフ連鎖用のデータの生成が完了した．

11. 上記データを利用してマルコフ連鎖を生成するす Script として Markov2.rb を作成した.

12. 初回抽出データは名詞とする 13． データ量が膨大なため負荷軽減のため抽出幅を毎回ランダムに設定している.

---

上記をもってマルコフ連鎖を生成する.

2.Markov.rb

require 'rubygems'
require 'active_record'
require 'MeCab'
require 'rss'
require 'feed-normalizer'
require 'kconv'

ActiveRecord::Base.establish_connection(
  :adapter => "mysql",
  :database => "twit",
  :host => "localhost",
  :user => "root",
  :timeout => 5000
)


class Word < ActiveRecord::Base
end

class Chain < ActiveRecord::Base
end

def textRead(path)

  File::open(path) {|f|
    f.each {|line| mecab(line.strip) }
  }

end

def word_insert_update(string,type)
  word = Word.find(:first, :conditions=>[ "spell=? and typed=?", string,type])
  if word.nil?
    word = Word.new
    word.spell = string
    word.typed = type
    word.save
    word = Word.find(:first, :conditions=>[ "spell=? and typed=?", string,type])
  end
  word
end

def chain_insert_update(first_word,second_word,word)
  chain = Chain.find(:first, :conditions=>["first_id=? and second_id=? and to_id=?",first_word.id,second_word.id,word.id])
  if chain.nil?
    chain = Chain.new
    chain.first_id = first_word.id
    chain.second_id = second_word.id
    chain.to_id = word.id
    chain.count = 1
    chain.save
  else
    chain.count = chain.count + 1
    chain.save
  end
  chain
end

def mecab(line)
  puts line
  first_word = nil
  second_word = nil
  words = []
  flg = false

  parse = MeCab::Tagger.new.parse(line.gsub(/http[s]?\:\/\/[\w\+\$\;\?\.\%\,\!\#\~\*\/\:\@\&\\\=\_\-]+/,""))
  parse.split(/\n/).each { |word|
    word.gsub(/^(.+?)[\t|\s]+(.+?),.+,(.+),.+$/){

      if $1 != "助動詞" || !flg
        words[words.length] = [$1,$2]
        flg = false
      else 
        words[words.length - 1][0].concat!($1)
      end

      flg = true if $2 == "動詞"
    }
  }

  words.each { |word,types|
    word = word_insert_update(word,types)
    if !first_word.nil? && !second_word.nil?
      chain_insert_update(first_word,second_word,word)
    end
    first_word = second_word
    second_word = word
  }

  if !first_word.nil? && !second_word.nil?
    chain = Chain.find(:first, :conditions => ["first_id=? and second_id=? and to_id is NULL",first_word.id,second_word.id])
    if chain .nil?
      chain = Tie.new
      chain .first_id = first_word.id
      chain second_id = second_word.id
      chain .count = 1
      chain .save
    else
      chain .count = tie.count + 1
      chain .save
    end
  end
end

textRead(ARGV[0])

3.Markov2.rb

require 'rubygems'
require 'active_record'

ActiveRecord::Base.logger = Logger.new(STDOUT)

ActiveRecord::Base.establish_connection(
  :adapter => "mysql",
  :database => "twit",
  :host => "localhost",
  :user => "root",
  :timeout => 5000
)

class Word < ActiveRecord::Base
end

class Chain < ActiveRecord::Base
end

class Markov


  def make

    array = []
    word = Word.find(:first, :conditions => ["id < ? and typed = ?",(1..410000).to_a.shuffle.take(1),"名詞"], :order => 'rand()')
    chain = Chain.find(:first, :conditions => ["id < ? and first_id = ?", (1..25518223).to_a.shuffle.take(1), word.id], :order => 'rand()')
    array << word
    word = Word.find(chain.second_id)
    array << word
    word = Word.find(chain.to_id)
    array << word

    loop do
      chain = Chain.find(:first, :conditions => ["first_id = ? and second_id = ? ", array.reverse[0].id, array.reverse[1].id], :order => 'rand()')
      break if chain.nil? || chain.to_id.nil?
      array << Word.find(chain.to_id)
    end

    array.map!{ |m| m.spell }.join
  end

end

m = Markov.new
puts m.make