首页 > 代码库 > 最大概率法分词及性能测试
最大概率法分词及性能测试
最大概率分词是一种最基本的统计方法分词。一个待分割的字符串有多种分词结果，最大概率分词的原则是将其中概率最大的那个作为该字符串的分词结果。
第一部分 理论基础
如对一个字符串：
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，即为单字，可以不在词典中出现。
（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） “分歧”是尾词，“意见”是“分歧”的最佳前趋词，分词过程结束。
第三部分 结果展示
对1998年1月《人民日报》进行分析，其中构造词典和测试用的语料比例为9：1。分别用三种方法进行分词：正向最大概率匹配、逆向最大概率匹配、最大概率法。对它们的分词结果进行比较，结果如下：
第四部分 源代码
源代码分为三个文件，分别是：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, '\n')){
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] = '\0';
string str_out = s;
return str_out;
}
/*
* 函数功能：计算切分标记的位置
* 函数输入：1.strline_in未进行切分的汉字字符串
2.strline_right进行切分后的汉字字符串
* 函数输出：vecetor，其中存放了strline_in中哪些位置放置了分词标记
* 注意：vector中不包含最后标记的位置，但是包含位置0。
*/
vector<int> getPos(string strline_right, string strline_in){
int pos_1 = 0;
int pos_2 = -1;
int pos_3 = 0;
string word = "";
vector<int> vec;
int length = strline_right.length();
while(pos_2 < length){
//前面的分词标记
pos_1 = pos_2;
//后面的分词标记
pos_2 = strline_right.find('/', pos_1 + 1);
if(pos_2 > pos_1){
//将两个分词标记之间的单词取出
word = strline_right.substr(pos_1 + 1, pos_2 - pos_1 - 1);
//根据单词去输入序列中查出出现的位置
pos_3 = strline_in.find(word, pos_3);
//将位置存入数组
vec.push_back(pos_3);
pos_3 = pos_3 + word.size();
}else{
break;
}
}
return vec;
}
/*
* 获取标准切分和程序切分的结果
*/
string getString(string word, int pos, vector<int> vec_right){
char ss[1000];
int i = 0;
int k = 0;
while(vec_right[i] < pos){
i++;
}
for(int j = 0; j < word.size(); j++){
if(j == vec_right[i] - pos){
if(j != 0){
ss[k] = '/';
++k;
}
++i;
}
ss[k] = word[j];
++k;
}
ss[k] = '\0';
string word_str = ss;
return word_str;
}
/*
* 函数功能：获取单个句子切分的结果统计
* 函数输入：1.vec_right 正确的分词标记位置集合
* 2.vec_out 函数切分得到的分词标记位置集合
* 函数输出：返回一个veceor，含有4个元素，分别为：
* 切分正确、组合型歧义、未登录词、交集型歧义的数量
*
*/
vector<int> getCount_2(string strline, vector<int> vec_right, vector<int> vec_out, vector<string> &vec_err){
vector<int> vec(4, 0); //存放计算结果
//建立map
map<int, int> map_result;
for(int i = 0; i < vec_right.size(); i++){
map_result[vec_right[i]] += 1;
}
for(int i = 0; i < vec_out.size(); i++){
map_result[vec_out[i]] += 2;
}
//统计map中的信息
//若value=http://www.mamicode.com/1，只在vec_right中>
最大概率法分词及性能测试