/* Copyright (C) 1999 Lucent Technologies / / Excerpted from 'The Practice of Programming' / / by Brian W. Kernighan and Rob Pike */
import java.io.; import java.util.;
class Chain { static final int NPREF = 2; // size of prefix static final String NONWORD = "\n"; // "word" that can't appear Hashtable statetab = new Hashtable(); // key = Prefix, value = suffix Vector Prefix prefix = new Prefix(NPREF, NONWORD); // initial prefix Random rand = new Random();
// Chain build: build State table from input stream void build(InputStream in) throws IOException { StreamTokenizer st = new StreamTokenizer(in);
st.resetSyntax(); // remove default rules
st.wordChars(0, Character.MAX_VALUE); // turn on all chars
st.whitespaceChars(0, ' '); // except up to blank
while (st.nextToken() != st.TT_EOF)
add(st.sval);
add(NONWORD);
}
// Chain add: add word to suffix list, update prefix void add(String word) { Vector suf = (Vector) statetab.get(prefix); if (suf == null) { suf = new Vector(); statetab.put(new Prefix(prefix), suf); } suf.addElement(word); prefix.pref.removeElementAt(0); prefix.pref.addElement(word); }
// Chain generate: generate output words void generate(int nwords) { prefix = new Prefix(NPREF, NONWORD); for (int i = 0; i < nwords; i++) { Vector s = (Vector) statetab.get(prefix); if (s == null) { System.err.println("Markov: internal error: no state"); System.exit(1); } int r = Math.abs(rand.nextInt()) % s.size(); String suf = (String) s.elementAt(r); if (suf.equals(NONWORD)) break; System.out.println(suf); prefix.pref.removeElementAt(0); prefix.pref.addElement(suf); } } }
class Prefix { public Vector pref; // NPREF adjacent words from input static final int MULTIPLIER = 31; // for hashCode()
// Prefix constructor: duplicate existing prefix Prefix(Prefix p) { pref = (Vector) p.pref.clone(); }
// Prefix constructor: n copies of str Prefix(int n, String str) { pref = new Vector(); for (int i = 0; i < n; i++) pref.addElement(str); }
// Prefix hashCode: generate hash from all prefix words public int hashCode() { int h = 0;
for (int i = 0; i < pref.size(); i++)
h = MULTIPLIER * h + pref.elementAt(i).hashCode();
return h;
}
// Prefix equals: compare two prefixes for equal words public boolean equals(Object o) { Prefix p = (Prefix) o;
for (int i = 0; i < pref.size(); i++)
if (!pref.elementAt(i).equals(p.pref.elementAt(i)))
return false;
return true;
}
}
class Markov { static final int MAXGEN = 10000; // maximum words generated public static void main(String[] args) throws IOException { Chain chain = new Chain(); int nwords = MAXGEN;
chain.build(System.in);
chain.generate(nwords);
}
}