craylea / tpop Goto Github PK

/* 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);
}

}