在之前的博文中介绍了基于词典的正向最大匹配算法,用了不到50行代码就实现了,然后分析了词典查找算法的时空复杂性,最后使用前缀树来实现词典查找算法,并做了3次优化。
下面我们看看基于词典的逆向最大匹配算法的实现,如下代码所示:
- public static List<String> segReverse(String text){
- Stack<String> result = new Stack<>();
- while(text.length()>0){
- int len=MAX_LENGTH;
- if(text.length()<len){
- len=text.length();
- }
- //取指定的最大长度的文本去词典里面匹配
- String tryWord = text.substring(text.length() - len);
- while(!DIC.contains(tryWord)){
- //如果长度为一且在词典中未找到匹配,则按长度为一切分
- if(tryWord.length()==1){
- break;
- }
- //如果匹配不到,则长度减一继续匹配
- tryWord=tryWord.substring(1);
- }
- result.push(tryWord);
- //从待分词文本中去除已经分词的文本
- text=text.substring(0, text.length()-tryWord.length());
- }
- int len=result.size();
- List<String> list = new ArrayList<>(len);
- for(int i=0;i<len;i++){
- list.add(result.pop());
- }
- return list;
- }
算法跟正向相差不大,重点是使用Stack来存储分词结果,具体差异如下图所示:
下面看看正向和逆向的分词效果,使用如下代码:
- public static void main(String[] args){
- List<String> sentences = new ArrayList<>();
- sentences.add("杨尚川是APDPlat应用级产品开发平台的作者");
- sentences.add("研究生命的起源");
- sentences.add("长春市长春节致辞");
- sentences.add("他从马上下来");
- sentences.add("乒乓球拍卖完了");
- sentences.add("咬死猎人的狗");
- sentences.add("大学生活象白纸");
- sentences.add("他有各种才能");
- sentences.add("有意见分歧");
- for(String sentence : sentences){
- System.out.println("正向最大匹配: "+seg(sentence));
- System.out.println("逆向最大匹配: "+segReverse(sentence));
- }
- }
运行结果如下:
- 开始初始化词典
- 完成初始化词典,词数目:427452
- 最大分词长度:16
- 正向最大匹配: [杨尚川, 是, APDPlat, 应用, 级, 产品开发, 平台, 的, 作者]
- 逆向最大匹配: [杨尚川, 是, APDPlat, 应用, 级, 产品开发, 平台, 的, 作者]
- 正向最大匹配: [研究生, 命, 的, 起源]
- 逆向最大匹配: [研究, 生命, 的, 起源]
- 正向最大匹配: [长春市, 长春, 节, 致辞]
- 逆向最大匹配: [长春, 市长, 春节, 致辞]
- 正向最大匹配: [他, 从, 马上, 下来]
- 逆向最大匹配: [他, 从, 马上, 下来]
- 正向最大匹配: [乒乓球拍, 卖完, 了]
- 逆向最大匹配: [乒乓球拍, 卖完, 了]
- 正向最大匹配: [咬, 死, 猎人, 的, 狗]
- 逆向最大匹配: [咬, 死, 猎人, 的, 狗]
- 正向最大匹配: [大学生, 活象, 白纸]
- 逆向最大匹配: [大学生, 活象, 白纸]
- 正向最大匹配: [他, 有, 各种, 才能]
- 逆向最大匹配: [他, 有, 各种, 才能]
- 正向最大匹配: [有意, 见, 分歧]
- 逆向最大匹配: [有, 意见分歧]
参考资料:
1、中文分词十年回顾
相关推荐
运用正向最大匹配算法进行分析,同时也实现了逆向最大匹配,内有分词词典。
但不管实现如何,目前而言的分词系统绝大多数都是基于中文词典的匹配算法。其中最为常见的是最大匹配算法 (Maximum Matching,以下简称MM算法) 。MM算法有三种:一种正向最大匹配,一种逆向最大匹配和双向匹配。本...
2、中文分词算法 之 基于词典的逆向最大匹配算法 3、中文分词算法 之 词典机制性能优化与测试 4、中文分词算法 之 基于词典的正向最小匹配算法 5、中文分词算法 之 基于词典的逆向最小匹配算法 5、Java开源项目...
目前,分词系统绝大多数都是基于中文词典的匹配算法。其中最为常见的是最大匹配算法 (Maximum Matching,以下简称MM算法) 。MM算法有三种:一种正向最大匹配,一种逆向最大匹配和双向匹配。本程序实现了正向最大匹配...
里面包含完整代码,有词典,解压后是vs2017的工程文件,可直接运用测试。
目前,分词系统绝大多数都是基于中文词典的匹配算法。其中最为常见的是最大匹配算法 (Maximum Matching,以下简称MM算法) 。MM算法有三种:一种正向最大匹配,一种逆向最大匹配和双向匹配。本程序实现了反向最大匹配...
逆向最大匹配分词是中文分词基本算法之一,因为是机械切分,所以它也有分词速度快的优点,且逆向最大匹配分词比起正向最大匹配分词更符合人们的语言习惯。逆向最大匹配分词需要在已有词典的基础上,从被处理文档的...
基于逆向匹配的中文分词算法实现,产生词典和测试数据,分词后具有结果分析功能,计算精确度,召回率,F值
(1) 首字 Hash 索引:首字 Hash 函数根据汉字的国标区位 (2)词索引:词索引的每个单元包括两项内容:①所有词长 (3)词典正文:以词为单位的有序表
(1)逆向最大匹配算法使用的分词词典是逆序词典,里面的每个词都将按逆序方式存放。在实际应用过程中,可以将待分词文本进行倒排处理,从而生成逆序文本,然后再根据逆序词典,对逆序文本用正向最大匹配算法进行...
基于文本匹配的算法又称之为“机械分词算法”,他是它是按照一定的策略将待分析的汉字串与一个“充分大的”机器词典中的词条进行配,若在词典中找到某个字符串,则匹配成功,可识别出一个词。按照扫描方向的不同,...
3 逆向最大匹配 跟正向最大匹配的唯一不同是从右到左尽可能划分出一段连续字符。 4 双向最大匹配 歧义指对于一个句子有多个分词结果。汉语文本中 90.0%左右的句子,FMM 和 BMM 的切分完全重合且正确,9.0%左右的...
英文的分词由于单词间是以空格进行分隔的,所以分词要相对的容易些,而中文就不同了,中文中一个句子的分隔就是以字为单位的了,而所谓的正向最大匹配和逆向最大匹配便是一种分词匹配的方法,这里以词典匹配说明。...
英文的分词由于单词间是以空格进行分隔的,所以分词要相对的容易些,而中文就不同了,中文中一个句子的分隔就是以字为单位的了,而所谓的正向最大匹配和逆向最大匹配便是一种分词匹配的方法,这里以词典匹配说明。...
本学期,我们在自然语言处理课上学习了多种中文分词算法,在本次大作业中,我们选择了其中的三个算法:最大匹配的三种算法--正向、逆向、双向;基于统计的Uni-Gram模型;隐马尔可夫(HMM)统计模型。首先我们将会...
本文分析了现有的基于词典的分词算法,在比较各种算法优缺点的基础上提出了将正向匹配算法与逆向匹配 算法所得到的结果集进行叠加,生成粗分结果集的新观点,再对生成的粗分结果集构造非负权有向图,最后应用最短...
通过本资源了解中文分词的意义,在实现正向、逆向最大匹配分词算法的过程中,加深对自然语言理解原理的探讨兴趣。本资源内含详细的代码设计分档、测试语料、源代码以及多个自己制作的语料库词典,分别实现了正、逆向...
algorithmMenu.add(bmmItem = new JRadioButtonMenuItem("逆向最大匹配", false)); ButtonGroup algorithms = new ButtonGroup(); algorithms.add(fmmItem); algorithms.add(bmmItem); ...