`

马尔可夫算法

阅读更多

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

把输入想像成由一些互相重叠的短语构成的序列,该算法把每个短语分成两部分:一部分由多个词构成的前缀,另一部分是只包含一个词的后缀。马尔可夫链算法能够生成输出短语的序列,其方法是依据(在我们的情况下)原文本的统计性质,随机性地选择跟在前缀后面的特定后缀。采用三个词的短语就能够工作得很好——利用连续两个词构成的前缀来选择作为后缀的一个词:
设置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#源码-马尔可夫算法.rar

    马尔可夫算法是一种基于概率模型的预测方法,它的核心思想是通过分析一系列事件或文本序列,学习到每个状态(事件)转移到下一个状态的概率。在给定的标题"C#源码-马尔可夫算法.rar"中,我们可以推断出这个压缩包...

    隐式马尔可夫算法识别XSS攻击.zip

    在“隐式马尔可夫算法识别XSS攻击.zip”这个压缩包中,我们期待找到以下内容: 1. 数据集:包含正常和含有XSS攻击的HTTP流量样本,用于训练和测试模型。 2. 训练脚本:用编程语言(如Python)编写的脚本,用于执行...

    HMM算法,隐马尔可夫算法

    ### HMM算法与最大熵马尔可夫模型:序列标注技术的核心 #### 一、引言 本章节将深入探讨两种重要的统计模型——隐马尔可夫模型(Hidden Markov Model, HMM)与最大熵模型(Maximum Entropy Model, MaxEnt),特别...

    语音机器人隐马尔可夫算法探究.pdf

    文章中提到的关键词,包括非特定人语音识别、隐马尔可夫模型和初始化算法,进一步强调了研究中改进HMM模型初始化算法的主旨。研究的理论与实证成果不仅适用于语音机器人系统,还可以为语音识别领域的其他应用提供...

    隐式马尔可夫算法识别DGA域名.zip

    4. 评估与优化:使用交叉验证等方法评估模型性能,可能需要调整特征选择、参数设置或使用不同的学习算法(如Baum-Welch算法)进行参数估计。 在本教程的"训练脚本"中,你将找到实现这些步骤的代码示例。通过运行...

    隐马尔可夫模型前向算法matlab程序-forward algorithm.m

    隐马尔可夫模型前向算法matlab程序-forward algorithm.m 这个是隐马尔可夫模型前向算法程序,根据一个示例用matlab编写的,希望对大家有用。由于在线时间不够,所以图贴不上来,我只能以附件的形式发上来了。。。

    C#写的马尔可夫-预测算法实例,简单明了。

    马尔可夫的教程说的很多,但是基本都没有代码实例,这个预测算法的文章,基本只有大学的论文才能找到比较详细的资料,但是都没有代码实例,特别是边际概率,离散型变量,检验'马氏性',自相关系数,滞时权重等说的不尽...

    基于马尔可夫链的彩票分析

    这是关于马尔可夫链预测的文章。对计算机算法开发有很大的帮助。

    MCL算法 马尔可夫聚类算法(英文)

    马尔可夫聚类算法(MCL算法)是一种基于图的聚类方法,其核心思想是利用马尔可夫链对图进行流动模拟,并通过迭代过程中的膨胀(Inflation)操作来增强图中簇内部的连接度,同时减弱簇之间的连接度,以此发现图中紧密...

    基于C++实现马尔可夫聚类算法用于对图进行聚类,使用karate等数据集进行了实验。.zip

    基于C++实现马尔可夫聚类算法用于对图进行聚类,使用karate等数据集进行了实验。 基于C++实现马尔可夫聚类算法用于对图进行聚类,使用karate等数据集进行了实验。 基于C++实现马尔可夫聚类算法用于对图进行聚类,...

    MATLAB算法-马尔可夫链蒙特卡洛算法详解,附代码.pdf

    马尔可夫链蒙特卡洛(Markov Chain Monte Carlo, MCMC)算法是一种用于模拟复杂概率分布的统计技术,特别适用于处理高维数据和贝叶斯统计中的后验分布计算。在MATLAB中,我们可以利用统计和机器学习工具箱...

    MathLogicLabs:垫逻辑实验室(图灵机,邮政机,普通马尔可夫算法)

    垫逻辑实验室(图灵机,邮政机,普通马尔可夫算法) 每个目录都包含任务1(在纸上执行)和任务2(在与机器相对应的程序中执行)的文件。 另外,为方便起见,在实验室的每个存储库中,都有一些程序可以用来启动任务...

    基于马尔可夫链的电动汽车充电需求计算.pdf

    本文提出了基于马尔可夫链的模型来描述这一过程,以更准确地预测不同场景下的电动汽车负荷需求。 马尔可夫链是一种数学模型,用于描述一个系统随时间演变的行为。在电动汽车充电需求的计算中,它被用来表示电动汽车...

    基于马尔可夫模型的手势识别算法

    ### 基于马尔可夫模型的手势识别算法知识点详解 #### 一、引言与背景 在当今数字化时代,人机交互技术的发展日益受到重视。手势识别作为一种直观的人机交互方式,在虚拟现实、智能家居等领域展现出巨大潜力。基于...

    对经典隐马尔可夫模型学习算法的改进.7z

    对经典隐马尔可夫模型学习算法的改进 改进了两个基本假设。

    大规模生物网络马尔可夫聚类的并行化算法.pdf

    马尔可夫聚类算法(MCL)是在大规模生物网络中寻找模块的一个有效方法,能够挖掘网络结构和功能影响力较大的模块。算法涉及到大规模矩阵计算,因此复杂度可达立方阶次。针对复杂度高的问题,提出了基于消息传递接口(MPI)...

    灰色最小二乘马尔可夫链预测算法

    灰色最小二乘马尔可夫链预测算法灰色最小二乘马尔可夫链预测算法灰色最小二乘马尔可夫链预测算法

    对经典隐马尔可夫模型学习算法的改进

    ### 隐马尔可夫模型(HMM)学习算法的改进:理论与实践 #### 引言 隐马尔可夫模型(Hidden Markov Model, HMM)自诞生以来,在多个领域展现了其强大的应用潜力,尤其是在语言识别、生物信息学(如DNA序列比对、...

Global site tag (gtag.js) - Google Analytics