😷

Vim script でマルコフ連鎖

2020/12/15に公開

はじめに

この記事は Vim Advent Calendar 2020 の記事、 ではありません

ふと Vim script でマルコフ連鎖させたら面白いんじゃないかと思ってチョロっと作ってみました。

マルコフ連鎖とは

文章に現れる語句とそれに連なる語句でツリーを構成する場合、その枝には頻出度が出来上がります。例えば「吾輩も」という文章が2つ、「吾輩は」という文章が1つある場合、「吾輩」から「も」に進む確率は「吾輩」から「は」に行く確率よりも高くなります。この様に現在の状態(吾輩)の次の状態(も|は)が、吾輩の前の語句に依存せず決定される状態を マルコフ性 といい、一連の確立変数の列を マルコフ連鎖 と呼びます。

P(X_{t+1}∣X_{t},X_{t−1},…,X_{1})=P(X_{t+1}∣X_{t})

図で表すと以下の様になります。

引用: シェルスクリプトで作る Twitter bot 作成入門

簡単だろうと思ったけど

簡単だと思ったのですが、よく考えたら Vim script で分かち書きするのがしんどかった。ライブラリもない。トークナイザが欲しい...

しょうがないので Unicode 文字クラスで区切るのを作った。

let s:classes = [
\ [0x037e, 0x037e, 1],
\ [0x0387, 0x0387, 1],
\ [0x055a, 0x055f, 1],
  ......
\ [0xff1a, 0xff20, 1],
\ [0xff3b, 0xff40, 1],
\ [0xff5b, 0xff65, 1],
\ [0x20000, 0x2a6df, 0x4e00],
\ [0x2a700, 0x2b73f, 0x4e00],
\ [0x2b740, 0x2b81f, 0x4e00],
\ [0x2f800, 0x2fa1f, 0x4e00],
\]

let s:emoji = [
\ [0x203c, 0x203c],
\ [0x2049, 0x2049],
\ [0x2122, 0x2122],
  ......
\ [0x1f5fb, 0x1f640],
\ [0x1f645, 0x1f64f],
\ [0x1f680, 0x1f6c5],
\]

function! s:is(r) abort
  if a:r < 0x100
    if index([0x20, 0x14, 0x00, 0xa0], a:r) != -1
      return 0
    endif
    return index([0x2c, 0x3001, 0x3002], a:r) != -1 ? 1 : 2
  endif
  for l:v in s:classes
    if l:v[0] <= a:r && a:r <= l:v[1]
      return l:v[2]
    endif
  endfor
  for l:v in s:emoji
    if l:v[0] <= a:r && a:r <= l:v[1]
      return 3
    endif
  endfor
  return 2
endfunction

function! s:split(s) abort
  let l:result = []
  let [l:pos, l:cur, l:old] = [0, 0, 0]
  let l:rs = split(a:s, '\zs')
  for l:r in map(copy(l:rs), 'char2nr(v:val)')
    let l:new = s:is(l:r)
    if l:cur != 0 && l:new != l:old
      call add(l:result, join(l:rs[l:pos : l:cur - 1], ''))
      let l:pos = l:cur
    endif
    let l:old = l:new
    let l:cur += 1 
  endfor
  call add(l:result, join(l:rs[l:pos :], ''))
  return l:result
endfunction

この s:split私の名前は中野です を渡すと

['私', 'の', '名前', 'は', '中野', 'です']

が返る。正しい形態素解析のトークナイザではないけど、ごまかす事はできる。

本題のマルコフ連鎖

更新する為の update メソッド

let s:markov = {'tbl': {}}

function markov#new() abort
  return s:markov
endfunction

function! s:markov.update(s) abort
  let l:words = s:split(a:s)
  call filter(l:words, {_, v -> (char2nr(v) < 255 && v =~ '\w') || index(['、', '。'], v) ==# -1})
  let l:size = len(words)

  if l:size ==# 1
    if !has_key(self.tbl, l:words[0])
      let self.tbl[l:words[0]] = []
    endif
    return
  endif
  let l:last = ''
  for l:i in range(0, l:size - 2)
    if !has_key(self.tbl, l:words[l:i])
      let l:second = []
      let self.tbl[l:words[l:i]] = l:second
    else
      let l:second = self.tbl[l:words[l:i]]
    endif
    let l:last = l:words[i+1]
    call add(l:second, l:last)
  endfor
  if has_key(self.tbl, l:last)
    let self.tbl[l:last] += repeat([''], len(l:words))
  endif
endfunction

先頭を作り出す first

let s:bad = ['し', 'が', 'の', 'を', 'に', 'へ', 'と', 'から', 'より', 'やら', 'か', 'で', 'なり', 'だの', 'する', 'であり', 'く', 'において', 'う', 'い', 'え']

function! s:markov.first() abort
  let l:keys = keys(self.tbl)
  if len(l:keys) == 0
    return ''
  endif
  while 1
    let l:first = s:randi(l:keys)
    if index(s:bad, l:first) ==# -1
      return l:first
    endif
  endwhile
endfunction

一応、助詞ぽいのは避けてる。(苦しい)

そして連鎖を作る chain

function! s:markov.chain(s) abort
  let l:first = a:s
  let l:text = l:first
  while l:first != ''
    let l:size = len(get(self.tbl, l:first, []))
    if l:size == 0
      break
    endif
    let l:next = s:randi(self.tbl[l:first])
    let l:text .= l:next
    let l:first = l:next
  endwhile
  return l:text
endfunction

工夫した所としては update のお尻で空のアイテムを要素数ぶん足しているところ。「行動する様に」の様に「する」で終わらない文章と「行動する」の様に「する」で終わる文章により、「する」が末尾で無くなってしまう為、意図的に、かつ高確率となる様に意図的に追加してある。

おためし

Vim プラグイン化しておいた。

https://github.com/mattn/vim-markov

このプラグインを導入し、日本語が沢山書いてある文章を開いて :Markov を実行すると要約された文章ができる。以下は日本国憲法前文をバッファに開いて数回試した結果

専制とわが国全土にわたって自由のもたらす恵沢を地上から永遠に従うことは自国の責務であると信ずる

決意した

ある地位を支配する

政府の関係を維持しわれらとわれらの子孫のために諸国民の関係を通じて行動しこの憲法は国家の公正と対等関係に除去しようと努めている国際社会において名誉にかけて全力をあげて崇高な理想を愛する

よく分からない文章が沢山できた。

おわりに

また、くだらない物を作ってしまった。Qiita Advent Calendar 2020 の 25 日を予定しており、まだ記事を書き始めても、ネタを考えてもないのだけど、そっちはもうちょっとマシな記事を書こうと思う。

Discussion