Skip to content

Instantly share code, notes, and snippets.

@suchi
Created May 25, 2011 12:44
Show Gist options
  • Save suchi/990894 to your computer and use it in GitHub Desktop.
Save suchi/990894 to your computer and use it in GitHub Desktop.
「プログラミング作法」The Practice of Programming MarkovChainのC#実装例(Generics不使用)
/* PoP 3 Markov Chain in C# */
/* 2003/02/17: suchi -- */
using System;
using System.IO;
using System.Collections;
using System.Text.RegularExpressions;
class Prefix {
const int MULTIPLIER = 31; // for hashcode
public ArrayList pref;
//
public Prefix(Prefix p) // copy ctor
{
pref = (ArrayList)p.pref.Clone();
}
public Prefix(int n, String str)
{
pref = new ArrayList();
for (int i = 0; i < n; i++) {
pref.Add(str);
}
}
// compare prefix
public override bool Equals(Object o)
{
Prefix p = (Prefix)o;
for (int i = 0; i < pref.Count; i++) {
if (!pref[i].Equals(p.pref[i])) {
return false;
}
}
return true;
}
public override int GetHashCode()
{
int h = 0;
for (int i = 0; i < pref.Count; i++) {
h = MULTIPLIER * h + pref[i].GetHashCode();
}
return h;
}
}
class Chain {
const int NPREF = 2;
const String NONWORD = "\n";
Hashtable statetab = new Hashtable();
Prefix prefix = new Prefix(NPREF, NONWORD);
Random rand = new Random();
//
public void build(TextReader sr)
{
Regex rex = new Regex("[ \t]+");
String line;
while (sr.Peek() > -1) {
line = sr.ReadLine();
String[] fields = rex.Split(line);
for (int i = 0; i < fields.Length; ++i) {
add(fields[i]);
}
}
add(NONWORD);
}
public void add(String word)
{
ArrayList suf = (ArrayList)statetab[prefix];
if (suf == null) {
suf = new ArrayList();
Prefix p = new Prefix(prefix);
statetab[p] = suf;
}
suf.Add(word);
prefix.pref.RemoveAt(0);
prefix.pref.Add(word);
}
public void generate(int nwords)
{
prefix = new Prefix(NPREF, NONWORD);
for (int i = 0; i < nwords; i++) {
ArrayList s = (ArrayList)statetab[prefix];
int r = rand.Next() % s.Count;
String suf = (String)s[r];
if (suf.Equals(NONWORD)) {
break; // for(i)
}
Console.WriteLine(suf);
prefix.pref.RemoveAt(0);
prefix.pref.Add(suf);
}
}
}
class Markov {
const int MAXGEN = 10000;
public static void Main(String[] args)
{
Chain chain = new Chain();
int nwords = MAXGEN;
chain.build(Console.In);
chain.generate(nwords);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment