思享工具箱

最大概率法分词及性能測试

摘要：
最大概率分词的原理是将概率最高的一个作为字符串的分词结果。有意/可见/发散/最大概率分词需要Max（P（w1|s），w3）=P（w1）P（w2）。。。P（w3）（公式2），即字符串出现的概率是组成字符串的单词的概率的乘积。单词的概率可以通过将出现的次数除以语料库中的单词总数来获得。


        最大概率分词是一种最主要的统计方法分词。一个待切割的字符串有多种分词结果，最大概率分词的原则是将当中概率最大的那个作为该字符串的分词结果。


第一部分 理论基础


        如对一个字符串：

        S：有意见分歧

        分词结果1： w1:有/ 意见/ 分歧/

        分词结果2： w2:有意/ 见/ 分歧/

        最大概率分词就是要求得 Max(P(w1|s),P(w2|s)) 。

        依据贝叶斯公式：

                P(w|s)=P(s|w)P(w)/P(s)                                                                      （公式1）

        在公式1中，由于P(s)和P(w|s)都基本一样。因此，就求最大的P(w)就可以。

依据一元语法。词之间出现的概率互相独立，因此有以下的公式成：

                P(w)=P(w1,w2,…,w3)=P(w1)P(w2)…P(w3)                                   （公式2）

        即字符串出现的概率就是构成字符串的各个词的概率之积。而一个词的概率能够依照其出现的次数除以语料中总的词数得到。

        分析以下的样例，我们能够计算得到各个词的概率为：

                有：0.018

                有意：0.0005

                意见：0.001

                见：0.0002

                分歧：0.0001

        则依据公式2有：

                P(w1)=p(有)P(意见)P(分歧)=0.018*0.001*0.0001=1.8*10^(-9)

                P(w2)=P(有意)P(见)P(分歧)=0.0005*0.0002*0.0001=1*10^(-11)

        因为P(w1)>P(w2)，故w1为该字符串的分词结果。


        当然，在实际操作过程中，假设字符串比較长，分词的形式就会许多，计算量和长度呈指数增长关系，因此须要採用一定的算法来降低运算量，我们能够看到字符串的概率是累计相乘的，因此能够採用动态规划的方法来降低运算量。

        这里记P`(w)为到达候选词wi时的累计概率。则

                P`(wi)=P`(wi-1)P(wi)                                             （公式3）

        依据公式3。有P`(意见)=P`(有)P(意见)


第二部分 算法实现


        在算法的实现思路上。基本上是先记录全部可能出现的词。以及其相应的概率，也就是分段的代价函数，同一时候寻找每个词的最佳的前趋词。然后就是回溯，从字符串的尾部向前搜索最优路径就可以。

这也是动态规划的一般实现方法。


        1.思路说明

        （1）获取候选词

        获取句子中可能出现的全部词作为候选词，但要满足下列条件：假设是长度大于1的词。则必须在词典中出现。假设是长度等于1，即为单字，能够不在词典中出现。

        （2）构造前趋词:

        假定字符串从左到右进行扫描，能够得到w1,w2,…,wi-1,wi,….等若干候选词。假设wi-1的尾字根wi的首字邻接。就称wi-1为wi的前趋词。比方上面例中。候选词“有”就是候选词“意见”的前趋词，“意见”和“见”都是“分歧”的前趋词。

字串最左边的词没有前趋词。

        （3）寻找最佳前趋词：

        假设某个候选词wi有若干个前趋词wj,wk,…..等等。当中累计概率最大的候选词称为wi的最佳前趋词。比方候选词“意见”仅仅有一个前趋词“有”，因此“有”同一时候也就是“意见”的最佳前趋词；候选词“分歧”有两个前趋词“意见”和“见”，当中“意见”的累计概率大于“见”累计概率，因此“意见”是“分歧”的最佳前趋词。

        （4）确定最优路径

        回溯，从字符串的尾部依照最佳前趋词的指引，向前搜索最优路径。


        2.详细步骤

        （1）对一个待分词的字串S。依照从左到右的顺序取出所有候选词w1,w2,….,wi,…,wn;

        （2）到词典中查出每一个候选词的概率值P(wi)。

        （3）依照公式3计算每一个候选词的累计概率，同一时候比較得到每一个词的最佳前趋词。

        （4）假设当前词wn是字符串S的尾词。且累计概率P’(wn)最大，则wn就是S的终点词。

        （5）从wn開始，依照从右到左的顺序。因此将每一个词的最佳前趋输出，即为S的分词结果。

         样例： 

        （1）对“有意见分歧”。从左到右进行一遍扫描，得到所有候选词：“有”。“有意”。“意见”，“见”，“分歧”；

        （2）对每一个候选词，记录下它的概率值，并将累计概率赋初值为0；

        （3）顺次计算各个候选词的累计概率值，同一时候记录每一个候选词的最佳前趋词：

                P`(有)=P(有)，

                P`(意见)=P(意见),

                P`(意见)=P`(有)P(意见)，(“意见”的最佳前趋词为“有”)

                P`(见)=P`(有意)P(见)，(“见”的最佳前趋词为“有意”)

                P`(意见) > P`(见)

        （4） “分歧”是尾词，“意见”是“分歧”的最佳前趋词，分词过程结束。

最大概率法分词及性能測试第1张



第三部分 结果展示


        对1998年1月《人民日报》进行分析，当中构造词典和測试用的语料比例为9：1。分别用三种方法进行分词：正向最大概率匹配、逆向最大概率匹配、最大概率法。对它们的分词结果进行比較。结果例如以下：

最大概率法分词及性能測试第2张



第四部分 源码


        源码分为三个文件，各自是：dictionary_2.h（词典头文件）、segmentwords.cpp（三种分词方法所在的文件）、main.cpp（结果输出、正确性比对等功能）。

        1.dictionary_2.h（词典头文件）

#include <iostream>
#include <string>
#include <fstream>
#include <sstream>
#include <map>
#include <cstdlib>

using namespace std;

/*
 * 词典的定义。用于最大概率分词
 */
class Dictionary{
	private:
		string strline;			//保存每行内容
		string word;			//保存一个词语
		map<string, int> word_map;	//词典。用map表示
	
	public:
		long size;			//词典规模
		long freq_all;
		long arr_1[20];
		double arr_2[20];
		Dictionary();			//构造函数，初始化词典
		~Dictionary();
		int findWord(string word);	//在词典中查找特定的词语
};

Dictionary::Dictionary(){
	freq_all = 0;
	for(int i = 0; i < 20; i++){
		arr_1[i] = 0;
		arr_2[i] = 0.0;
	}
	//读取词典文件
	fstream fin("dict_3.txt");
	if(!fin){
		cerr << "open file error !" << endl;
		exit(-1);
	}
	//将每一个词语增加集合
	while(getline(fin, strline, '
')){
		istringstream istr(strline);
		istr >> word;		//从流中读取单词
		++word_map[word];	//
		++arr_1[word.size()];
		++freq_all;
	}
	fin.close();
	//初始化词典大小
	size = word_map.size();
	for(int i = 0; i < 20; i++){
		arr_2[i] = (double)arr_1[i]/freq_all;
	}
}

Dictionary::~Dictionary(){
	
}

int Dictionary::findWord(string word){
	map<string, int>::iterator p_cur = word_map.find(word); 
	if(p_cur != word_map.end()){
		return p_cur -> second;
	}else{
		return -1;
	}
}


        2.segmentwords.cpp（三种分词方法所在的文件）

#include <cmath>
#include <string>
#include <iostream>
#include "dictionary_2.h"

const short MaxWordLength = 20;	//词典中最大词的长度
const char Separator = '/';     //词界标记

Dictionary word_dict;           //初始化一个词典
 
/*
 * 类定义：候选词的结构
 */
class Candidate{
	public:
		short pos;	//候选词在输入串中的起点
		short length;	//输入串的长度
		short bestPrev;	//最佳前趋词的序号
		float fee;	//候选词的费用
		float sumFee;	//候选词路径上的累计费用
		string word;	//候选词
		int freq;	//候选词的频数（不能用short，否则有可能溢出）
};


/*
 * 函数功能：取出字符串中的所有候选词
 * 函数输入：字符串的引用
 * 函数输出：该字符串中含有的所有的存在与词典中的词（或者单字，单字能够在词典中不存在）
 */
vector<Candidate> getTmpWords(const string &s){
	int freq = 0;			//词典中词的频率
	short n = s.length();		//字符串的长度
	string word = "";		//存放候选词
	Candidate cand;			//存放候选词属性
	vector<Candidate> vec_cd;	//候选词队列

	//以每一个汉字为起点
	for(short i = 0; i < n; i += 2){
		//词的长度为 1～MaxWordLength/2 个汉字
		for(short len = 2; len <= MaxWordLength; len += 2){
			word = s.substr(i, len);
			freq = word_dict.findWord(word);//去词典中查找出现频率
			if(len > 2 && freq == -1){
				//若不止一字且词表中找不到则不予登录
				continue;
			}
			if(freq == -1){
				//假设为单字词，且词表中找不到
				freq = 0;
			}
			cand.pos = i;			//该候选词在汉字串中的起点
			cand.length = len;		//该候选词的长度
			cand.word = word;
			cand.fee = -log((double)(freq*1 + 1)/word_dict.freq_all);//该候选词的费用
			cand.sumFee = 0.0f;		//该候选词的累计费用置初值
			cand.freq = freq;
			//将获取的候选词增加队列
			vec_cd.push_back(cand);	
		}
	}

	return vec_cd;
}

/*
 * 函数功能：获取最佳前趋词序号
 * 函数输入：候选词列表的引用
 * 函数输出：无
 */
void getPrew(vector<Candidate> &vec_cd){
	short min_id = -1;				//最佳前趋词编号
	short j = -1;
	short size = (short)vec_cd.size();		//计算队列长度
	for(short i = 0; i < size; i++){
		if(vec_cd[i].pos == 0){
			//假设候选词是汉字串中的首词
			vec_cd[i].bestPrev = -1;	//无前趋词
			vec_cd[i].sumFee = vec_cd[i].fee;	//累计费用为该词本身费用
		}else{
			//假设候选词不是汉字串中的首词
			min_id = -1;			//初始化最佳前趋词编号
			j = i - 1;			//从当前对象向左找
			while(j >= 0){
				//向左寻找所遇到的所有前趋词
				if(vec_cd[j].pos + vec_cd[j].length == vec_cd[i].pos){
					if(min_id == -1 || vec_cd[j].sumFee < vec_cd[min_id].sumFee){
						min_id = j;
					}
				}
				--j;
			}

			vec_cd[i].bestPrev = min_id;	//登记最佳前趋编号
			vec_cd[i].sumFee = vec_cd[i].fee + vec_cd[min_id].sumFee;//登记最小累计费用
		}
	}
}


/*
 * 函数功能：最大概率法分词
 * 函数输入：待切分的字符串
 * 函数输出：切分好的字符串
 */
string segmentSentence_MP(string s1){
	short len = s1.length();
	short min_id = -1;		//最小费用路径的终点词的序号
	
	//取出s1中的所有候选词
	vector<Candidate> vec_cd = getTmpWords(s1);

	//获得最佳前趋词序号、当前词最小累计费用
	getPrew(vec_cd);

	//确定最小费用路径的终点词的序号
	short n = (short)vec_cd.size();
	for(short i = 0; i < n; i++){
		if(vec_cd[i].pos + vec_cd[i].length == len){
			//假设当前词是s1的尾词
			if(min_id == -1 || vec_cd[i].sumFee < vec_cd[min_id].sumFee){
				//假设是第一个遇到的尾词。或者是当前尾词的最小累计费用小于
				//已经遇到过的任一尾词的最小累计费用，则将其序号赋给min_id
				min_id = i;
			}
		}
	}

	//构造输出串
	string s2 = "";		//输出串初始化
	for(short i = min_id; i >= 0; i = vec_cd[i].bestPrev){
		//注意：是先取后面的词
		s2 = s1.substr(vec_cd[i].pos, vec_cd[i].length) + Separator + s2;
	}
		
	return s2;
}



/*
 * 函数功能：对字符串用最大匹配算法（正向）处理
 * 函数输入：汉字字符串
 * 函数输出：分好词的字符串
 */
string segmentSentence_1(string s1){
	string s2 = "";		//用s2存放分词结果
	
	while(!s1.empty()){
		int len = s1.length();	//取输入串长度
		if(len > MaxWordLength){
			len = MaxWordLength;	//仅仅在最大词长范围内进行处理
		}
		
		string w = s1.substr(0, len);
		int n = word_dict.findWord(w);	//在词典中查找对应的词
		while(len > 2 && n == -1){
			len -= 2;	//从候选词右边减掉一个汉字。将剩下的部分作为候选词
			w = s1.substr(0, len);
			n = word_dict.findWord(w);
		}

		s2 = s2 + w + Separator;
		s1 = s1.substr(w.length(), s1.length() - w.length());
	}
	
	return s2;
}


/*
 * 函数功能：对字符串用最大匹配算法（逆向）处理
 * 函数输入：汉字字符串
 * 函数输出：分好词的字符串
 */
string segmentSentence_2(string s1){
	string s2 = "";		//用s2存放分词结果
	
	while(!s1.empty()){
		int len = s1.length();	//取输入串长度
		if(len > MaxWordLength){
			len = MaxWordLength;	//仅仅在最大词长范围内进行处理
		}
		
		string w = s1.substr(s1.length() - len, len);
		int n = word_dict.findWord(w);	//在词典中查找对应的词
		while(len > 2 && n == -1){
			len -= 2;	//从候选词左边减掉一个汉字，将剩下的部分作为候选词
			w = s1.substr(s1.length() - len, len);
			n = word_dict.findWord(w);
		}

		w = w + Separator;
		s2 = w + s2;
		s1 = s1.substr(0, s1.length() - len);
	}
	
	return s2;
}


        3.main.cpp（结果输出、正确性比对等功能）

#include <cstdlib>
#include <vector>
#include <iomanip>
#include <map>
#include <algorithm>
#include <sys/time.h>
#include <sys/stat.h>
#include "segmentwords.cpp"

const long MaxCount = 50000;	//须要切分的最大句子数量。若该值大于文件里
				//实际的句子数量，以实际句子数量为准。

//获取当前时间(ms)
long getCurrentTime(){
	struct timeval tv;
	gettimeofday(&tv, NULL);
	return tv.tv_sec*1000 + tv.tv_usec/1000;
}

//获取文件大小
unsigned long getFileSize(string file_path){
	unsigned long filesize = -1;
	struct stat statbuff;
	if(stat(file_path.c_str(), &statbuff) < 0){
		return filesize;
	}else{
		filesize = statbuff.st_size;
	}
		return filesize;
}



/*
 * 函数功能：对句子进行最大匹配法处理，包括对特殊字符的处理
 * 函数输入：1.含有汉字、英文符号的字符串
 *         2.flag=1调用正向最大匹配算法。flag=2调用逆向最大匹配算法
 * 函数输出：分好词的字符串
 */
string SegmentSentenceMM(string s1, int flag){
	string s2 = "";	//用s2存放分词结果
	int i;
	int dd;
	while(!s1.empty()){
		unsigned char ch = (unsigned char)s1[0];
		if(ch < 128){
			//处理西文字符
			i = 1;
			dd = s1.length();

			while(i < dd && ((unsigned char)s1[i] < 128) && (s1[i] != 10) && (s1[i] != 13)){
				//s1[i]不能是换行符或回车符
				i++;
			}//中止循环条件：出现中文字符、换行或者回车

			if(i == 1 && (ch == 10 || ch == 13)){
				//假设是换行或回车符，将它拷贝给s2输出
				s2 += s1.substr(0, i);
			}else{
				s2 += s1.substr(0, i) + Separator;
			}
			
			s1 = s1.substr(i, dd);
			continue;
		}else{
			if(ch < 176){
				//中文标点等非汉字字符
				i = 0;
				dd = s1.length();
			
				//获取中文双字节特殊字符（非汉字、非中文标点），中止循环条件：超过长度、出现中文标点符号、出现汉字
				while(i < dd && ((unsigned char)s1[i] < 176) && ((unsigned char)s1[i] >= 161)
					&& (!((unsigned char)s1[i] == 161 && ((unsigned char)s1[i+1] >= 162 && (unsigned char)s1[i+1] <= 168)))
					&& (!((unsigned char)s1[i] == 161 && ((unsigned char)s1[i+1] >= 171 && (unsigned char)s1[i+1] <= 191)))
					&& (!((unsigned char)s1[i] == 163 && ((unsigned char)s1[i+1] == 161 || (unsigned char)s1[i+1] == 168
					||   (unsigned char)s1[i+1] == 169 || (unsigned char)s1[i+1] == 172 || (unsigned char)s1[i+1] == 186 
					||   (unsigned char)s1[i+1] == 187 || (unsigned char)s1[i+1] == 191)))){
					//假定没有半个汉字
					i = i + 2;
				}
				
				//出现中文标点
				if(i == 0){
					i = i + 2;
				}

				//中文标点每一个加一个分词标记；其它非汉字双字节字符连续输出，仅仅加一个分词标记
				s2 += s1.substr(0, i) + Separator;
				

				s1 = s1.substr(i, dd);
				continue;
			}
		}
		
		//下面处理汉字串
		i = 2;
		dd = s1.length();
		while(i < dd && (unsigned char)s1[i] >= 176){
			i += 2;
		}

		if(flag == 1){
			//调用正向最大匹配
			s2 += segmentSentence_1(s1.substr(0, i));
		}else if(flag == 2){
			//调用逆向最大匹配
			s2 += segmentSentence_2(s1.substr(0, i));
		}else if(flag == 3){
			//调用最大概率匹配
			s2 += segmentSentence_MP(s1.substr(0, i));
		}

		s1 = s1.substr(i, dd); 
	}

	return s2;
}


/*
 * 函数功能：删除分词标记（即去掉字符串中的/）
 * 函数输入：含有分词标记的字符串
 * 函数输出：不含分词标记的字符串
 */
string removeSeparator(string str_in){
	char s[10000];
	int j = 0;
	for(int i = 0; i < str_in.length(); i++){
		if(!(str_in[i] == '/')){
			s[j] = str_in[i];
			j++;
		}
	}
	s[j] = '

标签：#词#概率#词典#分词 | 浏览：117 | 发布日期：

免责声明：内容来源于网络，仅用于学习参考。如对内容有疑问，请及时联系本站处理。

上篇Build WebKit On Windows 白果果白的专栏 博客频道 CSDN.NETJava读写锁下篇

宿迁高防，2C2G15M，22元/月；香港BGP，2C5G5M，25元/月 雨云优惠码：MjYwNzM=

相关文章

NLP常用Python开发工具

一、Numpy NumPy系统是Python的一种开源的数值计算包。 包括： 1、一个强大的N维数组对象Array； 2、比较成熟的（广播）函数 库； 3、用于整合C/C++和Fortran代码的工具包； 4、实用的线性代数、傅里叶变换和随机数生成函数。 numpy和稀疏矩阵运算包scipy配合使用更加方便。 安装： pip install numpy 二...

基于IKAnalyzer搭建分词服务

背景 前端高亮需要分词服务，nlp团队提供的分词服务需要跨域调用，而且后台数据索引使用的IK分词。综合评价，前端分词也需要基于IK分词器。IKAnalyzer服务已经停止更新，且对Lucene支持仅测试到4.x.x版本（6.x.x会出现异常），因此使用IK分词器时需要解决一些异常。 依赖 项目以及maven构建，需要指定IK依赖以及Lucene依赖如下：...

拉普拉斯平滑（Laplace Smoothing）

拉普拉斯平滑（Laplace Smoothing）又称 加1平滑，常用平滑方法。解决零概率问题。 背景:为什么要做平滑处理? 零概率问题：在计算实例的概率时，如果某个量x，在观察样本库（训练集）中没有出现过，会导致整个实例的概率结果是0。 在文本分类的问题中，当一个词语没有在训练样本中出现，该词语调概率为0，使用连乘计算文本出现概率时也为0。 这是不合理的...

中文分词组件：thulac及jieba试用手记

一、THULAC THULAC由《清华大学自然语言处理与社会人文计算实验室》研制推出的一套中文词法分析工具包。官网地址：http://thulac.thunlp.org，该项目提供了多种语言，本文以java版为例，先下载以下二个组件：1、THULAC_lite_v1_2分词java版可执行的jar包：THULAC_lite_java_v1_2_run.ja...

13.solr学习速成之IK分词器

IKAnalyzer简介 IKAnalyzer是一个开源的，基于java语言开发的轻量级的中文分词工具包。 IKAnalyzer特性 a. 算法采用“正向迭代最细粒度切分算法”，支持细粒度和最大词长两种分词方式，速度最大支持80W字/秒（1600KB/秒）。   b. 支持多子处理器分析模式：中文、数字、字母，并兼容日文、韩文。  c. 较小的...

R语言自然语言处理：关键词提取（TF-IDF）

作者：黄天元，复旦大学博士在读，热爱数据科学与开源工具（R/Python），致力于利用数据科学迅速积累行业经验优势和科学知识发现，涉猎内容包括但不限于信息计量、机器学习、数据可视化、应用统计建模、知识图谱等，著有《R语言高效数据处理指南》、《文本数据挖掘——基于R语言》（《文本数据挖掘 基于R语言》(黄天元)【摘要 书评 试读】- 京东图书）。知乎专栏：R...

最新文章

随机推荐

思享工具箱导航