用正向和逆向最大匹配算法进行中文分词

2024-05-08 18:48

本文主要是介绍用正向和逆向最大匹配算法进行中文分词,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1.概述

        用正向和逆向最大匹配算法进行中文分词。

2.遇到的问题

        编码问题,Linux默认的编码是UTF-8编码,对于汉字,每个字占三个字节。而本文使用的语料为1998年1月的人民日报语料,为GB2312编码,每个汉字占两个字节。

        本文所用的Ubuntu Linux操作系统默认是不支持GB2312等中文编码的,因此需要对系统添加GB2312编码的支持。添加方式参见:

3.分词结果

        分词结果如下图所示:


        从图中可以看出,逆向最大匹配分词的准确率和召回率均大于正向最大匹配分词方法,但是幅度相差不是很大。

4.源代码

        源代码分为三个文件:

        segmentutil.cpp(对语料进行预处理),它是单独运行的,可以将原始语料制作成词典文件和测试文件。

        dictionary.h(词典头文件,初始化词典)和main.cpp(进行分词操作)这两个文件需要一起编译运行。可以对测试文件进行分词,该过程需要用到前面文件生成的词典文件和测试文件。

        (1)segmentutil.cpp(对语料进行预处理)

#include <string>
#include <iostream>
#include <fstream>
#include <cstdlib>using namespace std;/** 工具类* 功能:进行各种字符串操作、语料预处理操作*      含有2个字符串操作的函数 *      含有5个语料预处理相关的函数 */
class SegmentUtil{public:string removeLetters(string str_in);	//去掉字符串中的英文字母string& replace_all(string &str, string old_str, string new_str);	//置换字符串的特定字串void removeNum();			//去掉语料中的编号void spareLine();			//将语料进行分行void spareFile();			//将语料分为词典和测试语料void makeDict();			//构造词典void makeDict_2();			//构造词典
};/** 函数功能:删除词性标记(即去掉字符串中的英文字母)* 函数输入:含有词性标记的字符串* 函数输出:不含词性标记的字符串*/
string SegmentUtil::removeLetters(string str_in){char s[10000];int j = 0;for(int i = 0; i < str_in.length(); i++){if(!(str_in[i] >= 'a' && str_in[i] <= 'z' || str_in[i] >= 'A' && str_in[i] <= 'Z')){s[j] = str_in[i];j++;	}}s[j] = '\0';string str_out = s;return str_out;
}/** 函数功能:将字符串中的所有特定子串置换为新的字符串* 函数输入:str     需要进行操作的字符串*         old_str 旧的字符串*         new_str 新的字符串* 函数输出:置换完毕的字符串*/
string& SegmentUtil::replace_all(string &str, string old_str, string new_str){while(1){string::size_type pos(0);if((pos = str.find(old_str)) != string::npos){str.replace(pos, old_str.length(), new_str);}else{break;}}return str;
}/** 函数功能:去掉语料中每各段落前的编号* 函数输入:待处理的文件* 函数输出:处理完的文件*/
void SegmentUtil::removeNum(){ifstream fin("199801_1.txt");if(!fin){cerr << "removeNum : Unable open input file !" << endl;exit(-1);}ofstream fout("199801_2.txt");if(!fout){cerr << "removeNum : Unable open output file !" << endl;exit(-1);}string str_in = "";string str_out = "";while(getline(fin, str_in, '\n')){if(str_in.find('/') == 18){str_out = str_in.substr(22, str_in.length() - 22);}fout << str_out << endl;}fin.close();fout.close();
}/** 函数功能:将语料进行分行* 函数输入:待处理的文件,文件中多个句子在一个段落中,每个段落为一行* 函数输出:处理完的文件,每个句子为一行*/
void SegmentUtil::spareLine(){ifstream fin("199801_2.txt");if(!fin){cerr << "makeLine : Unable open input file !" << endl;exit(-1);}ofstream fout("199801_3.txt");if(!fout){cerr << "makeLine : Unable open output file !" << endl;exit(-1);}string str_in = "";string str_out = "";while(getline(fin, str_in, '\n')){if(str_in.find('/') == 18){str_out = str_in.substr(22, str_in.length() - 22);}fout << str_out << endl;}fin.close();fout.close();
}/** 函数功能:按照一定的比例,将原始语料分为词典语料和测试语料,默认比例为9:1。* 函数输入:分好行的语料文件,每个句子为一行* 函数输出:两个文件,文件1用于构造词典,文件2用于测试*/
void SegmentUtil::spareFile(){ifstream fin("199801_003.txt");if(!fin){cerr << "spareLine : Unable open input file !" << endl;exit(-1);}ofstream fout_1("dict_1.txt");if(!fout_1){cerr << "spareLine : Unable open output file : dict.txt !" << endl;exit(-1);}ofstream fout_2("test.txt");if(!fout_2){cerr << "spareLine : Unable open output file : test.txt !" << endl;exit(-1);}long count = 0;string str_in = "";string str_out = "";while(getline(fin, str_in, '\n')){//过滤掉词性标记,即英文字母str_out = removeLetters(str_in);//以句子为单位,将语料按比例分为两个文件if(count % 10 == 0){fout_2 << str_out << endl;}else{fout_1 << str_out << endl;}count++;}fin.close();fout_1.close();fout_2.close();
}/** 函数功能:构造词典,使每个词语为一行* 函数输入:分好行的语料文件,每个句子为一行* 函数输出:初步的词典文件,每个词语为一行,但可能有空行*/
void SegmentUtil::makeDict(){ifstream fin("dict_1.txt");if(!fin){cerr << "makeDict : Unable open input file !" << endl;exit(-1);}ofstream fout("dict_2.txt");if(!fout){cerr << "makeDict : Unable open output file !" << endl;exit(-1);}string line = "";while(getline(fin, line, '\n')){//将分词标记(/)和中文标点置换为回车for(int i = 0; i < line.length(); i++){unsigned char ch = (unsigned char) line[i];if(ch == '/'){line[i] = '\n';	}}line = replace_all(line, ",", "\n");line = replace_all(line, "。", "\n");line = replace_all(line, "?", "\n");line = replace_all(line, "!", "\n");line = replace_all(line, "《", "\n");line = replace_all(line, "》", "\n");line = replace_all(line, "”", "\n");line = replace_all(line, "“", "\n");line = replace_all(line, ":", "\n");line = replace_all(line, "、", "\n");line = replace_all(line, "(", "\n");line = replace_all(line, ")", "\n");line = replace_all(line, "[", "\n");line = replace_all(line, "]", "\n");fout << line << endl;}fin.close();fout.close();
}/** 函数功能:构造词典,使每个词语为一行(去掉词典中的空行)* 函数输入:初步的词典文件,每个词语为一行,但可能有空行* 函数输出:最终的语料文件,每个词语为一行,去掉了空行*/
void SegmentUtil::makeDict_2(){ifstream fin("dict_2.txt");if(!fin){cerr << "makeDict_2 : Unable open input file !" << endl;exit(-1);}ofstream fout("dict_3.txt");if(!fout){cerr << "makeDict_2 : Unable open output file !" << endl;exit(-1);}string line = "";//去掉空行while(getline(fin, line, '\n')){if(!line.empty()){fout << line << endl;}}fin.close();fout.close();
}int main(){SegmentUtil seg;//1.将原始语料分为词典语料和测试语料seg.spareFile();//2.构造词典seg.makeDict();seg.makeDict_2();
}


        (2)dictionary.h(词典头文件,初始化词典)

#include <iostream>
#include <string>
#include <fstream>
#include <sstream>
#include <set>
#include <cstdlib>using namespace std;class Dictionary{private:string strline;		//保存每行内容string word;		//保存一个词语set<string> word_set;	//词典,用集合表示public:Dictionary();		//构造函数,初始化词典~Dictionary();int findWord(string word);	//在词典中查找特定的词语
};Dictionary::Dictionary(){//读取词典文件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_set.insert(word);	//}
}Dictionary::~Dictionary(){}int Dictionary::findWord(string word){if(word_set.find(word) != word_set.end()){return 1;} else {return 0;}
}


        (3)main.cpp(进行分词操作)

#include <cstdlib>
#include "dictionary.h"
#include <vector>
#include <iomanip>
#include <map>const int MaxWordLength = 10;	//最大词长为10个字节(即5个汉字)
const char Separator = '/';	//词界标记Dictionary word_dict;		//初始化一个词典/** 函数功能:对字符串用最大匹配算法(正向)处理* 函数输入:汉字字符串* 函数输出:分好词的字符串*/
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 == 0){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 == 0){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;
}/** 函数功能:对句子进行最大匹配法处理,包含对特殊字符的处理* 函数输入: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{//调用逆向最大匹配s2 += SegmentSentence_2(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;
}/** 函数功能:获取单个句子切分的结果统计* 函数输入:1.vec_right 正确的分词标记位置集合*         2.vec_out   函数切分得到的分词标记位置集合* 函数输出:返回一个veceor,含有两个元素*         1.不该切分而切分的数量*         2.该切分而未切分的数量*/
vector<int> getCount(vector<int> vec_right, vector<int> vec_out){vector<int> vec;	//存放计算结果map<int, int> map_result;int length_1 = 0;	//map改变前的长度int length_2 = 0;	//map改变后的长度int count_1 = 0;	//不该切分而切分的数量int count_2 = 0;	//该切分而未切分的数量for(int i = 0; i < vec_right.size(); i++){map_result[vec_right[i]] = 0;}length_1 = map_result.size();for(int i = 0; i < vec_out.size(); i++){++map_result[vec_out[i]];}length_2 = map_result.size();count_1 = length_2 - length_1;for(int i = 0; i < vec_right.size(); i++){if(map_result[vec_right[i]] == 0){++count_2;}}vec.push_back(count_1);vec.push_back(count_2);return vec;
}/** 主函数:进行分词并统计分词结果****/
int main(int argc, char *argv[]){string strline_right;	//输入语料:用作标准分词结果string strline_in;	//去掉分词标记的语料(用作分词的输入)string strline_out_1;	//正向最大匹配分词完毕的语料string strline_out_2;	//逆向最大匹配分词完毕的语料ifstream fin("test.txt");	//打开输入文件if(!fin){cout << "Unable to open input file !" << argv[1] << endl;exit(-1);}ofstream fout("result.txt");	//确定输出文件if(!fout){cout << "Unable to open output file !" << endl;exit(-1);}long count = 0;	//句子编号long count_right_all = 0;	//准确的切分总数long count_out_1_all = 0;	//正向匹配切分总数long count_out_2_all = 0;	//逆向匹配切分总数long count_out_1_right_all = 0;	//正向匹配切分正确总数long count_out_2_right_all = 0;	//逆向匹配切分正确总数while(getline(fin, strline_right, '\n')){if(strline_right.length() > 1){//去掉分词标记strline_in = removeSeparator(strline_right);//正向最大匹配分词strline_out_1 = strline_right;strline_out_1 = SegmentSentenceMM(strline_in, 1);//逆向最大匹配分词strline_out_2 = strline_right;strline_out_2 = SegmentSentenceMM(strline_in, 2);//输出结果count++;cout << "----------------------------------------------" << endl;cout << "句子编号:" << count << endl;cout << endl;cout << "待分词的句子长度: " << strline_in.length() << "  句子:" << endl;cout << strline_in << endl;cout << endl;cout << "标准比对结果长度: " << strline_right.length() << "  句子:" << endl;cout << strline_right << endl;cout << endl;cout << "正向匹配分词长度: " << strline_out_1.length() << "  句子:" << endl;cout << strline_out_1 << endl;cout << endl;cout << "逆向匹配分词长度: " << strline_out_2.length() << "  句子:" << endl;cout << strline_out_2 << endl;cout << endl;//计算准确率、召回率//Rev()vector<int> vec_right = getPos(strline_right, strline_in);vector<int> vec_out_1 = getPos(strline_out_1, strline_in);vector<int> vec_out_2 = getPos(strline_out_2, strline_in);cout << "标准结果:" << endl;for(int i = 0; i < vec_right.size(); i++){cout << setw(4) << vec_right[i];}cout << endl;cout << "正向匹配结果:" << endl;for(int i = 0; i < vec_out_1.size(); i++){cout << setw(4) << vec_out_1[i];}cout << endl;cout << "逆向匹配结果:" << endl;for(int i = 0; i < vec_out_2.size(); i++){cout << setw(4) << vec_out_2[i];}cout << endl;vector<int> vec_count_1 = getCount(vec_right, vec_out_1);vector<int> vec_count_2 = getCount(vec_right, vec_out_2);//准确的切分数量int count_right = vec_right.size();//切分得到的数量int count_out_1 = vec_out_1.size();int count_out_2 = vec_out_2.size();//切分正确的数量int count_out_1_right = count_out_1 - vec_count_1[0] - vec_count_1[1];int count_out_2_right = count_out_2 - vec_count_2[0] - vec_count_2[1];cout << "正向最大匹配:" << endl;	cout << "  不该切分而切分的数量:" << vec_count_1[0] << endl;cout << "  该切分而未切分的数量:" << vec_count_1[1] << endl;cout << "逆向最大匹配:" << endl;	cout << "  不该切分而切分的数量:" << vec_count_2[0] << endl;cout << "  该切分而未切分的数量:" << vec_count_2[1] << endl;count_right_all += count_right;count_out_1_all += count_out_1;count_out_2_all += count_out_2;count_out_1_right_all += count_out_1_right;count_out_2_right_all += count_out_2_right;}}double kk_1 = (double)count_out_1_right_all / count_out_1_all;	//正向准确率double kk_2 = (double)count_out_1_right_all / count_right_all;	//正向召回率double kk_3 = (double)count_out_2_right_all / count_out_2_all;	//逆向准确率double kk_4 = (double)count_out_2_right_all / count_right_all;	//逆向召回率cout << "----------------------------------" << endl;cout << endl;cout << "统计结果:" << endl;cout << "正向准确率:" << kk_1*100 << "%    正向召回率:" << kk_2*100 << "%" << endl;cout << "逆向准确率:" << kk_3*100 << "%    逆向召回率:" << kk_4*100 << "%" << endl;return 0;
}



这篇关于用正向和逆向最大匹配算法进行中文分词的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/971139

相关文章

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

中文分词jieba库的使用与实景应用(一)

知识星球:https://articles.zsxq.com/id_fxvgc803qmr2.html 目录 一.定义: 精确模式(默认模式): 全模式: 搜索引擎模式: paddle 模式(基于深度学习的分词模式): 二 自定义词典 三.文本解析   调整词出现的频率 四. 关键词提取 A. 基于TF-IDF算法的关键词提取 B. 基于TextRank算法的关键词提取

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,阿里云开发者社区专家博主,CSDN全栈领域优质创作者,掘金优秀博主,51CTO博客专家等。 🏆《博客》:Python全栈,前后端开发,小程序开发,人工智能,js逆向,App逆向,网络系统安全,数据分析,Django,fastapi

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

业务中14个需要进行A/B测试的时刻[信息图]

在本指南中,我们将全面了解有关 A/B测试 的所有内容。 我们将介绍不同类型的A/B测试,如何有效地规划和启动测试,如何评估测试是否成功,您应该关注哪些指标,多年来我们发现的常见错误等等。 什么是A/B测试? A/B测试(有时称为“分割测试”)是一种实验类型,其中您创建两种或多种内容变体——如登录页面、电子邮件或广告——并将它们显示给不同的受众群体,以查看哪一种效果最好。 本质上,A/B测

秋招最新大模型算法面试,熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候,不知道面试完会不会复盘、总结,做笔记的习惯,这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助,都附有完整答案,熬夜也要看完,祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN,还有完整版的大模型 AI 学习资料,朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费