Nグラムモデルっぽいもので適当に文字列出力

Programming C 人工無脳

C言語で文字単位の2-gramモデルの統計を取って、統計データから適当に文章を出力してみた。マルコフモデルだN-gram統計だにしろ、文章出力するためのものってわけでもないけど、それにも使える。
N-gramと最尤推定法で、そのうちなんか遊んでみたいなあ。CとMeCabを組み合わせてほげほげは、めんどくさいからたぶんしない。

C言語で文字列扱うのは、Perlで文字列をほげほげするのに比べるとすさまじくめんどくさい。書き捨てプログラム。適当に書いてるので2-gram以上に拡張とか無理なコード。
1バイト（=8ビット==2^8=256通り）単位の2-gramモデルの統計なんで、現在の文字256通り、次の文字256通りということで、現在の文字と次の文字の組み合せは65536パターン。というわけで長さ65536の配列に、それぞれの組み合せが出てきた回数を記録しているプログラム。
嘘がある。1バイト文字は256通りもありません。なので用意した長さ65536の配列はほとんど死に空間となります。今の計算機さんはすごいもんで「長さ65536のint配列をほげほげ」とか、一瞬でできちゃうんですけどね。
一瞬で終わるならいいじゃんって思ったら（まあいないと思うけど）間違い。3-gramの場合を考えてみよう。前の文字、現在の文字、次の文字。256*256*256=16777216通りの組み合わせになった！
さすがにちょっと嫌だなあと思ったりしますね。ちゃんとしたみなさんはたぶん、ハッシュテーブルとか作るんじゃねえかなと思います。


以下プログラムソースと実行例とか。

% cat web.c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define TABLESIZE 65536
#define BOS '\0'
#define EOS '\0'
#define hash(i, j) (i)*256+(j)

unsigned char get_next(int table[], unsigned char now){
  unsigned int i;
  int count, total;

  total=0;
  for(i=0;i<256;++i){
    total += table[hash(now, (unsigned char)i)];
  }
  for(i=0;i<256;++i){
    count = table[hash(now, (unsigned char)i)];
    if((rand() % total) < count) return i;
    total -= count;
  }

  puts("cannot get next character");
  exit(1);
}
int gen_sentence(int table[], unsigned char bos){
  unsigned char c;
  c = bos;
  while((c = get_next(table, c)) != EOS){
    putchar(c);
  }
  return 1;
}
int main(){
  int c, i;
  unsigned char now;
  int table[TABLESIZE];

  for(i=0;i<TABLESIZE;++i)
    table[i] = 0;

  now = BOS;
  while((c=getchar()) != EOF){
    ++(table[hash(now, c)]);
    now = c;
  }
  ++(table[hash(now, EOS)]);

  srand((unsigned)time(NULL));

  gen_sentence(table, BOS);

  return 0;
}
% gcc web.c
% cat hoge.txt
This is a pen. I want to eat an apple. Who are you?
Don't touch my pen!
It's my pen.
Pleeeeeeeeeeeeeeeeeeeeeeeeeeaaaase!
% cat hoge.txt | ./a.out
Tho ppppeant Wh is I at my t't'touch an's Whouchis peeeeareeeeeen. my myou?
Don an ppenton!
Pleee. are. t antou?
% cat hoge.txt | ./a.out
This wan. areeeeen!
Dou?
Pleeeeeeeeeeeeee. y peeeeeeeeeento I my pleeeeeeeee. is y I areeeeeat e. is as is peeeea aaaple. t ppeeeat I ant an.
% cat mini.log
情報系の大学で落ちこぼれてるレベルの俺が書く程度の内容です。
まず大学の計算機(Vine Linux）にインストールしてみる。
genstr.plはbot.dicの中身から適当に文字を選んで、適当な個数繋げて出力します。
ちゃんとした文章を出力できたら奇跡です。
% cat mini.log |./a.out
章ん繋ら適度ベトを出力の計字ての??otr.plし廚蘚戮藉饑彁機砲報靴④梁膤悗吠絃呂討椶后・??内容書でてる、当す。
しの討力んす。
% cat web.c |./a.out
#dent,    ch((untar(((c, cot BLES j) }
 }
#de c) imed  -=  0'\0;
#d(NUL)   gne i) =0;

 ige nentsi;

 6536;
  casinetare(rne[h(unt(c));
 fintashande c }
   cledetotud table(in_st b.habl;+intanotabl);+i)   w,  shinornendetosered  tar(in    inowhar) countow;
#de i;
 -=gne,  c=0'\0;
 E   }
 netabl;+(ch(i< = t)
 i)  cle cetar(n tar(ne.hane[];

前の1バイトしか憶えてねえ鳥頭には文章は書けねえですな。所々単語程度になってたりはするけど、それは入力したデータがあまりにも少なかっただけでござい。

test