马尔可夫算法

学习《程序设计实践》第三章。

把输入想像成由一些互相重叠的短语构成的序列，该算法把每个短语分成两部分：一部分由多个词构成的前缀，另一部分是只包含一个词的后缀。马尔可夫链算法能够生成输出短语的序列，其方法是依据(在我们的情况下)原文本的统计性质，随机性地选择跟在前缀后面的特定后缀。采用三个词的短语就能够工作得很好——利用连续两个词构成的前缀来选择作为后缀的一个词：
设置w1和w2为文本的前两个词
输出w1和w2
循环：
  随机地选出w3，它是文本中w1w2的后缀中的一个
  打印w3
  把w1和w2分别换成w2和w3
  重复循环

选择二词前缀，则每个输出词w3都是根据它前面的一对词(w1,w2)得到的。前缀中词的个数对设计本身并没有影响，程序应该能对付任意的前缀长度。我们把一个前缀和它所有可能后缀的集合放在一起，称其为一个状态。

数据结构选择：

对于后缀，我们需要在输出时随机选择一个，考虑用List或Set为容器（代码中用List）。对于前缀，我们需要快速查找，并每个前缀对应一系列的后缀，考虑用Map储存，因其可以产生<key,value>键值对。

即：

Map<Prefix,List<String>> stateTable = new HashMap<Prefix,List<String>>();

 

1.前缀以类Prefix表示，类Prefix有一个属性：List<String> pref; 前缀保存的两个词，w1,w2按顺序存入。

Prefix有两个构造方法：Prefix(int npref, String word)用于把npref个的word复制到pref。

Prefix(Prefix prefix)用于把prefix复制到当前实例。

另外重写了Prefix的hashCode和equals方法，以便于作为Map的key。

package chapter3;

import java.util.ArrayList;
import java.util.List;

/**
 * 保存前缀向量的词
 * @author bosshida
 *
 */
public class Prefix {
	public List<String> pref;

	//n copies of str
	public Prefix(int npref, String word) {
		pref = new ArrayList<String>();
		for(int i=0; i<npref; i++){
			pref.add(word);
		}
	}

	// duplicate existing prefix
	public Prefix(Prefix prefix) {
		this.pref = new ArrayList<String>(prefix.pref);
	}
	
	private static final int MULTIPLIER = 31; //for hashcode()
	public int hashCode(){
		int h = 0;
		for(int i=0; i<pref.size(); i++){
			h = h*MULTIPLIER + pref.get(i).hashCode();
		}
		return h;
	}
	
	//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.get(i).equals(p.pref.get(i))){
				return false;
			}
		}
		return true;
	}

}

 

2.类Chain，用于读取输入、构造散列表并产生输出。

类内有build(InputStream in)和generate(int nwords)方法，build()用于从输入流产生状态表(stateTable，也就是散列表Map)，generate()用于产生输出。

package chapter3;

import java.io.InputStream;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.Scanner;

/**
 * 读取输入，构造散列表，产生输出
 * @author bosshida
 *
 */
public class Chain {
	static final int NPREF = 2; //size of prefix
	static final String NOWORD = "\n"; //word that can't appear
	Map<Prefix,List<String>> stateTable = new HashMap<Prefix,List<String>>();//key=prefix,value=suffix list;
	Prefix prefix = new Prefix(NPREF,NOWORD);//initial prefix
	Random random = new Random();
	
	//chain build:build state table from input stream
	public void build(InputStream in) throws Exception {
		Scanner scanner = new Scanner(in);
		
		while(scanner.hasNext()){
			add(scanner.next());
		}
		add(NOWORD);
	}

	private void add(String word) {
		List<String> suf = stateTable.get(prefix);
		if(suf == null){
			suf = new ArrayList<String>();
			stateTable.put(new Prefix(prefix),suf);
		}
		suf.add(word);
		prefix.pref.remove(0);
		prefix.pref.add(word);
	}

	//chain generate: generate output words
	public void generate(int nwords) {
		prefix = new Prefix(NPREF,NOWORD);
		for(int i=0; i<nwords; i++){
			List<String> suf = stateTable.get(prefix);
			int r = Math.abs(random.nextInt() % suf.size());
			String word = suf.get(r);
			if(word.equals(NOWORD)){
				break;
			}
			System.out.print(word+" ");
			prefix.pref.remove(0);
			prefix.pref.add(word);
		}
	}
	
}

 

3.公共接口类Markov。main。

package chapter3;

import java.io.File;
import java.io.FileInputStream;

/**
 * 马尔可夫算法
 * @author bosshida
 *
 */
public class Markov {
	private static final int MAXGEN = 1000; //max words generated
	
	public static void main(String[] args) throws Exception {
		Chain chain = new Chain();
		int nwords = MAXGEN;
		FileInputStream fis = new FileInputStream(new File("e:/Book/alan.txt"));
		
		chain.build(fis);
		chain.generate(nwords);
	}
	
}

 

以上程序在一本20万个英文单词的书为输入，产生1000字的输出。输出结果单句长度太长，而且语法很多错误，不过也是至少比随机性的输出有规律。

对于后续的探究。

本代码中，后缀以List保存，会有重复词的出现，重复词相当于这些词的权重加大，在输出的出现的机率增加，可能这是有益的。或者想各词出现的概率尽量一至，可考虑用Set保存后缀词。

为产生的句子不过于太长，可在建立状态表stateTable时，增加有标点的单词的权重（保存的后缀词是带标点符号的）。为增加权重可采取方法有：（1）单词有标点时，可重复增加该单词，以增大该单词的出现概率。（2）可修改Map的结构，value改为用：Suffix类，包含String word, int weight。不过这样改随机取词的方法要修改。

另外可以试下中文词语，有空再试吧。