学习《程序设计实践》第三章。
把输入想像成由一些互相重叠的短语构成的序列,该算法把每个短语分成两部分:一部分由多个词构成的前缀,另一部分是只包含一个词的后缀。马尔可夫链算法能够生成输出短语的序列,其方法是依据(在我们的情况下)原文本的统计性质,随机性地选择跟在前缀后面的特定后缀。采用三个词的短语就能够工作得很好——利用连续两个词构成的前缀来选择作为后缀的一个词:
设置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。不过这样改随机取词的方法要修改。
另外可以试下中文词语,有空再试吧。
分享到:
相关推荐
C#版本的马尔可夫算法,代码能正常运行,下载即可研究。该代码并非本人原创,是整理学习资料时偶然发现以前研究过的算法共享出来给大家
语音机器人隐马尔可夫算法探究.pdf
This chapter is roughly divided into two sections: Hidden Markov Models followed by Maximum Entropy Markov Models. Our discussion of the Hidden Markov Model extends what we said about HMM part-of-...
本项目是进阶教程,可以作为入门的教程。内含数据集和训练脚本
本项目是进阶教程,可以作为入门的教程。内含数据集和训练脚本
这是关于马尔可夫链预测的文章。对计算机算法开发有很大的帮助。
隐马尔可夫模型前向算法matlab程序-forward algorithm.m 这个是隐马尔可夫模型前向算法程序,根据一个示例用matlab编写的,希望对大家有用。由于在线时间不够,所以图贴不上来,我只能以附件的形式发上来了。。。
马尔可夫的教程说的很多,但是基本都没有代码实例,这个预测算法的文章,基本只有大学的论文才能找到比较详细的资料,但是都没有代码实例,特别是边际概率,离散型变量,检验'马氏性',自相关系数,滞时权重等说的不尽...
基于隐马尔可夫算法的不完全信息动态Stackelberg博弈资源分配
MATLAB算法-马尔可夫链蒙特卡洛算法详解,附代码
基于C++实现马尔可夫聚类算法用于对图进行聚类,使用karate等数据集进行了实验。 基于C++实现马尔可夫聚类算法用于对图进行聚类,使用karate等数据集进行了实验。 基于C++实现马尔可夫聚类算法用于对图进行聚类,...
该算法用于matlab,主要用于马尔可夫算法
文档对马尔可夫聚类算法进行了详细的描述,并且有图例进一步解释,易于理解。
垫逻辑实验室(图灵机,邮政机,普通马尔可夫算法) 每个目录都包含任务1(在纸上执行)和任务2(在与机器相对应的程序中执行)的文件。 另外,为方便起见,在实验室的每个存储库中,都有一些程序可以用来启动任务...
基于马尔可夫链的电动汽车充电需求计算.pdf
隐马尔科夫 前向算法 实例 算法粗糙,见谅!
适用范围:该资源是一份基于java语言使用eclipse平台对隐马尔可夫算法的导入和封装,方便非算法专业的java开发人员快速学习隐马尔可夫模型,也可以作为算法专业人员将隐马尔科夫模型应用于Java环境下的工程落地实践...
对经典隐马尔可夫模型学习算法的改进 改进了两个基本假设。
隐马尔可夫HMM算法 包括前后向算法、viterbi算法、bw算法等另外包括内存申请