在之前的博文中介绍了基于词典的正向最大匹配算法，用了不到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, 应用, 级, 产品开发, 平台, 的, 作者] 正向最大匹配: [研究生, 命, 的, 起源] 逆向最大匹配: [研究, 生命, 的, 起源] 正向最大匹配: [长春市, 长春, 节, 致辞] 逆向最大匹配: [长春, 市长, 春节, 致辞] 正向最大匹配: [他, 从, 马上, 下来] 逆向最大匹配: [他, 从, 马上, 下来] 正向最大匹配: [乒乓球拍, 卖完, 了] 逆向最大匹配: [乒乓球拍, 卖完, 了] 正向最大匹配: [咬, 死, 猎人, 的, 狗] 逆向最大匹配: [咬, 死, 猎人, 的, 狗] 正向最大匹配: [大学生, 活象, 白纸] 逆向最大匹配: [大学生, 活象, 白纸] 正向最大匹配: [他, 有, 各种, 才能] 逆向最大匹配: [他, 有, 各种, 才能] 正向最大匹配: [有意, 见, 分歧] 逆向最大匹配: [有, 意见分歧]
下面看看实际的分词性能如何，对输入文件进行分词，然后将分词结果保存到输出文件，输入文本文件从这里下载，解压后大小为69M，词典文件从这里下载，解压后大小为4.5M，项目源代码托管在GITHUB：
/**
* 将一个文件分词后保存到另一个文件
* @author 杨尚川
*/
public class SegFile {
public static void main(String[] args) throws Exception{
String input = "input.txt";
String output = "output.txt";
if(args.length == 2){
input = args[0];
output = args[1];
}
long start = System.currentTimeMillis();
segFile(input, output);
long cost = System.currentTimeMillis()-start;
System.out.println("cost time:"+cost+" ms");
}
public static void segFile(String input, String output) throws Exception{
float max=(float)Runtime.getRuntime().maxMemory()/1000000;
float total=(float)Runtime.getRuntime().totalMemory()/1000000;
float free=(float)Runtime.getRuntime().freeMemory()/1000000;
String pre="执行之前剩余内存:"+max+"-"+total+"+"+free+"="+(max-total+free);
try(BufferedReader reader = new BufferedReader(new InputStreamReader(new FileInputStream(input),"utf-8"));
BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(new FileOutputStream(output),"utf-8"))){
int textLength=0;
long start = System.currentTimeMillis();
String line = reader.readLine();
while(line != null){
textLength += line.length();
writer.write(WordSeg.seg(line).toString()+"\n");
line = reader.readLine();
}
long cost = System.currentTimeMillis() - start;
float rate = textLength/cost;
System.out.println("文本字符："+textLength);
System.out.println("分词耗时："+cost+" 毫秒");
System.out.println("分词速度："+rate+" 字符/毫秒");
}
max=(float)Runtime.getRuntime().maxMemory()/1000000;
total=(float)Runtime.getRuntime().totalMemory()/1000000;
free=(float)Runtime.getRuntime().freeMemory()/1000000;
String post="执行之后剩余内存:"+max+"-"+total+"+"+free+"="+(max-total+free);
System.out.println(pre);
System.out.println(post);
}
}
测试结果如下（对比TrieV3和HashSet的表现）：
开始初始化词典 dic.class=org.apdplat.word.dictionary.impl.TrieV3 dic.path=dic.txt 完成初始化词典，耗时695 毫秒，词数目：427452 词典最大词长：16 词长 0 的词数为：1 词长 1 的词数为：11581 词长 2 的词数为：146497 词长 3 的词数为：162776 词长 4 的词数为：90855 词长 5 的词数为：6132 词长 6 的词数为：3744 词长 7 的词数为：2206 词长 8 的词数为：1321 词长 9 的词数为：797 词长 10 的词数为：632 词长 11 的词数为：312 词长 12 的词数为：282 词长 13 的词数为：124 词长 14 的词数为：116 词长 15 的词数为：51 词长 16 的词数为：25 词典平均词长：2.94809 字符数目：24960301 分词耗时：64014 毫秒 分词速度：389.0 字符/毫秒 执行之前剩余内存:2423.3901-61.14509+60.505272=2422.7505 执行之后剩余内存:2423.3901-961.08545+203.32925=1665.6339 cost time:64029 ms
开始初始化词典 dic.class=org.apdplat.word.dictionary.impl.HashSet dic.path=dic.txt 完成初始化词典，耗时293 毫秒，词数目：427452 词典最大词长：16 词长 0 的词数为：1 词长 1 的词数为：11581 词长 2 的词数为：146497 词长 3 的词数为：162776 词长 4 的词数为：90855 词长 5 的词数为：6132 词长 6 的词数为：3744 词长 7 的词数为：2206 词长 8 的词数为：1321 词长 9 的词数为：797 词长 10 的词数为：632 词长 11 的词数为：312 词长 12 的词数为：282 词长 13 的词数为：124 词长 14 的词数为：116 词长 15 的词数为：51 词长 16 的词数为：25 词典平均词长：2.94809 字符数目：24960301 分词耗时：77254 毫秒 分词速度：323.0 字符/毫秒 执行之前剩余内存:2423.3901-61.14509+60.505295=2422.7505 执行之后剩余内存:2423.3901-900.46466+726.91455=2249.84 cost time:77271 ms
在上篇文章基于词典的正向最大匹配算法中，我们已经优化了词典查找算法（DIC.contains(tryWord)）的性能（百万次查询只要一秒左右的时间），即使经过优化后TrieV3仍然比HashSet慢4倍，也不影响它在分词算法中的作用，从上面的数据可以看到，TrieV3的整体分词性能领先HashSet十五个百分点（15%），而且内存占用只有HashSet的80%。
如何来优化分词算法呢？分词算法有什么问题吗？
回顾一下代码：
public static List<String> seg(String text){
List<String> result = new ArrayList<>();
while(text.length()>0){
int len=MAX_LENGTH;
if(text.length()<len){
len=text.length();
}
//取指定的最大长度的文本去词典里面匹配
String tryWord = text.substring(0, 0+len);
while(!DIC.contains(tryWord)){
//如果长度为一且在词典中未找到匹配，则按长度为一切分
if(tryWord.length()==1){
break;
}
//如果匹配不到，则长度减一继续匹配
tryWord=tryWord.substring(0, tryWord.length()-1);
}
result.add(tryWord);
//从待分词文本中去除已经分词的文本
text=text.substring(tryWord.length());
}
return result;
}
分析一下算法复杂性，最坏情况为切分出来的每个词的长度都为一（即DIC.contains(tryWord)始终为false），因此算法的复杂度约为外层循环数*内层循环数（即 文本长度*最大词长）=25025017*16=400400272，以TrieV3的查找性能来说，4亿次查询花费的时间大约8分钟左右。
进一步查看算法，发现外层循环有2个substring方法调用，内层循环有1个substring方法调用，substring方法内部new了一个String对象，构造String对象的时候又调用了System.arraycopy来拷贝数组。
最坏情况下，25025017*2+25025017*16=50050034+400400272=450450306，需要构造4.5亿个String对象和拷贝4.5亿次数组。
怎么来优化呢？
除了我们不得不把切分出来的词加入result中外，其他的两个substring是可以去掉的。这样，最坏情况下我们需要构造的String对象个数和拷贝数组的次数就从4.5亿次降低为25025017次，只有原来的5.6%。
看看改进后的代码：
public static List<String> seg(String text){
List<String> result = new ArrayList<>();
//文本长度
final int textLen=text.length();
//从未分词的文本中截取的长度
int len=DIC.getMaxLength();
//剩下未分词的文本的索引
int start=0;
//只要有词未切分完就一直继续
while(start<textLen){
if(len>textLen-start){
//如果未分词的文本的长度小于截取的长度
//则缩短截取的长度
len=textLen-start;
}
//用长为len的字符串查词典
while(!DIC.contains(text, start, len)){
//如果长度为一且在词典中未找到匹配
//则按长度为一切分
if(len==1){
break;
}
//如果查不到，则长度减一后继续
len--;
}
result.add(text.substring(start, start+len));
//从待分词文本中向后移动索引，滑过已经分词的文本
start+=len;
//每一次成功切词后都要重置截取长度
len=DIC.getMaxLength();
}
return result;
}
public static List<String> segReverse(String text){
Stack<String> result = new Stack<>();
//文本长度
final int textLen=text.length();
//从未分词的文本中截取的长度
int len=DIC.getMaxLength();
//剩下未分词的文本的索引
int start=textLen-len;
//处理文本长度小于最大词长的情况
if(start<0){
start=0;
}
if(len>textLen-start){
//如果未分词的文本的长度小于截取的长度
//则缩短截取的长度
len=textLen-start;
}
//只要有词未切分完就一直继续
while(start>=0 && len>0){
//用长为len的字符串查词典
while(!DIC.contains(text, start, len)){
//如果长度为一且在词典中未找到匹配
//则按长度为一切分
if(len==1){
break;
}
//如果查不到，则长度减一
//索引向后移动一个字，然后继续
len--;
start++;
}
result.push(text.substring(start, start+len));
//每一次成功切词后都要重置截取长度
len=DIC.getMaxLength();
if(len>start){
//如果未分词的文本的长度小于截取的长度
//则缩短截取的长度
len=start;
}
//每一次成功切词后都要重置开始索引位置
//从待分词文本中向前移动最大词长个索引
//将未分词的文本纳入下次分词的范围
start-=len;
}
len=result.size();
List<String> list = new ArrayList<>(len);
for(int i=0;i<len;i++){
list.add(result.pop());
}
return list;
}
对于正向最大匹配算法，代码行数从23增加为33，对于逆向最大匹配算法，代码行数从28增加为51，除了代码行数的增加，代码更复杂，可读性和可维护性也更差，这就是性能的代价！所以，不要过早优化，不要做不成熟的优化，因为不是所有的场合都需要高性能，在数据规模未达到一定程度的时候，各种算法和数据结构的差异表现不大，至少那个差异对你无任何影响。你可能会说，要考虑到明天，要考虑将来，你有你自己的道理，不过，我还是坚持不过度设计，不过早设计，通过单元测试和持续重构来应对变化，不为遥不可及的将来浪费今天，下一秒会发生什么谁知道呢？更不用说明天！因为有单元测试这张安全防护网，所以在出现性能问题的时候，我们可以放心、大胆、迅速地重构来优化性能。
下面看看改进之后的性能（对比TrieV3和HashSet的表现）：
开始初始化词典 dic.class=org.apdplat.word.dictionary.impl.TrieV3 dic.path=dic.txt 完成初始化词典，耗时689 毫秒，词数目：427452 词典最大词长：16 词长 0 的词数为：1 词长 1 的词数为：11581 词长 2 的词数为：146497 词长 3 的词数为：162776 词长 4 的词数为：90855 词长 5 的词数为：6132 词长 6 的词数为：3744 词长 7 的词数为：2206 词长 8 的词数为：1321 词长 9 的词数为：797 词长 10 的词数为：632 词长 11 的词数为：312 词长 12 的词数为：282 词长 13 的词数为：124 词长 14 的词数为：116 词长 15 的词数为：51 词长 16 的词数为：25 词典平均词长：2.94809 字符数目：24960301 分词耗时：24782 毫秒 分词速度：1007.0 字符/毫秒 执行之前剩余内存:2423.3901-61.14509+60.505272=2422.7505 执行之后剩余内存:2423.3901-732.0371+308.87476=2000.2278 cost time:25007 ms
开始初始化词典 dic.class=org.apdplat.word.dictionary.impl.HashSet dic.path=dic.txt 完成初始化词典，耗时293 毫秒，词数目：427452 词典最大词长：16 词长 0 的词数为：1 词长 1 的词数为：11581 词长 2 的词数为：146497 词长 3 的词数为：162776 词长 4 的词数为：90855 词长 5 的词数为：6132 词长 6 的词数为：3744 词长 7 的词数为：2206 词长 8 的词数为：1321 词长 9 的词数为：797 词长 10 的词数为：632 词长 11 的词数为：312 词长 12 的词数为：282 词长 13 的词数为：124 词长 14 的词数为：116 词长 15 的词数为：51 词长 16 的词数为：25 词典平均词长：2.94809 字符数目：24960301 分词耗时：40913 毫秒 分词速度：610.0 字符/毫秒 执行之前剩余内存:907.8702-61.14509+60.505295=907.2304 执行之后剩余内存:907.8702-165.4784+123.30369=865.6955 cost time:40928 ms
可以看到分词算法优化的效果很明显，对于TrieV3来说，提升了2.5倍，对于HashSet来说，提升了1.9倍。我们看看HashSet的实现：
public class HashSet implements Dictionary{
private Set<String> set = new java.util.HashSet<>();
private int maxLength;
@Override
public int getMaxLength() {
return maxLength;
}
@Override
public boolean contains(String item, int start, int length) {
return set.contains(item.substring(start, start+length));
}
@Override
public boolean contains(String item) {
return set.contains(item);
}
@Override
public void addAll(List<String> items) {
for(String item : items){
add(item);
}
}
@Override
public void add(String item) {
//去掉首尾空白字符
item=item.trim();
int len = item.length();
if(len < 1){
//长度小于1则忽略
return;
}
if(len>maxLength){
maxLength=len;
}
set.add(item);
}
}
JDK的HashSet没有这里优化所使用的contains(String item, int start, int length)方法，所以用了substring，这是HashSet提速没有TrieV3大的原因之一。
看一下改进的算法和原来的算法的对比：
正向最大匹配算法：
逆向最大匹配算法：
参考资料：
1、中文分词十年回顾
相关推荐
在这个“中文分词程序”中，包含了两种常见的分词算法：正向最大匹配算法（Forward Maximum Matching, FMM）和逆向最大匹配算法（Backward Maximum Matching, BMM）。 正向最大匹配算法是一种自左向右的分词策略。...
逆向最大匹配分词算法（Reverse Maximum Matching，RMM）是一种常见的中文分词技术，广泛应用于自然语言处理、搜索引擎和信息检索等领域。该算法的基本思想是从待分词文本的末尾开始，向前寻找最长的已存在于词典中...
总之，“基于正向、逆向的最大分词算法实现”是一个涵盖了词典管理、搜索策略、歧义解决等多个方面的综合性任务。通过理解和运用这些算法，我们可以构建高效、准确的中文分词系统，为后续的自然语言处理任务提供强大...
通过与其他分词算法（如正向最大匹配法、双向最大匹配法等）进行对比，可以更直观地看出基于逆向匹配的中文分词算法的优势与不足。实验结果表明，RMM算法在处理未登录词方面表现更优，尤其是在处理长难句时能够保持...
### 基于逆向最大匹配算法的中文分词的设计与开发 #### 一、中文分词概述 中文分词是自然语言处理(NLP)领域中的一个基础且关键的环节，涉及将连续的中文文本切分成有意义的词汇单元。与英文等其他语言不同，中文...
需要注意的是，Python提供了许多现成的中文分词库，如jieba，它们已经实现了包括正向、逆向匹配在内的多种分词算法，并且优化了性能。但在学习和理解分词原理时，自己动手实现这些方法是非常有益的。 总的来说，...
在本文中，我们将讨论 Python 实现的正向最大匹配分词和逆向最大匹配分词算法，并提供完整的源代码。 正向最大匹配分词 正向最大匹配分词是一种常用的分词算法，它从左到右扫描输入字符串，并尽可能地找到最长的...
但不管实现如何，目前而言的分词系统绝大多数都是基于中文词典的匹配算法。其中最为常见的是最大匹配算法 (Maximum Matching，以下简称MM算法) 。MM算法有三种：一种正向最大匹配，一种逆向最大匹配和双向匹配。本...
2、中文分词算法 之 基于词典的逆向最大匹配算法 3、中文分词算法 之 词典机制性能优化与测试 4、中文分词算法 之 基于词典的正向最小匹配算法 5、中文分词算法 之 基于词典的逆向最小匹配算法 5、Java开源项目...
本文将详细介绍如何利用Java编程语言来实现两种常见的分词算法——正向最大匹配法（FMM）和逆向最大匹配法（BMM），并给出具体的代码示例。 #### 二、正向最大匹配法（FMM） 正向最大匹配法的基本思路是从待分析...
### 基于改进最大匹配快速中文分词算法的知识点 #### 一、中文分词技术概述 中文分词作为自然语言处理中的基础步骤，在文本分析、机器翻译、信息检索等多个领域发挥着至关重要的作用。它主要负责将连续的中文字符...
目前，分词系统绝大多数都是基于中文词典的匹配算法。其中最为常见的是最大匹配算法 (Maximum Matching，以下简称MM算法) 。MM算法有三种：一种正向最大匹配，一种逆向最大匹配和双向匹配。本程序实现了正向最大匹配...
在这个简单的分词系统中，提供了两种主要的分词算法：正向最大匹配（Forward Maximum Matching, FMM）和逆向最大匹配（Backward Maximum Matching, BMM）。下面我们将详细探讨这两种方法及其应用。 首先，正向最大...
**逆向最大匹配法**则与之相反，从文本末尾开始，每次尝试匹配词典中最长的词，直至无法匹配。逆向匹配可以较好地解决过分割问题，但在处理某些特定情况时可能会导致欠分割（merging），即将两个或更多词汇错误地...
基于逆向最大匹配（Reversed Maximum Matching，RMM）的分词方法是一种广泛应用的中文分词算法。本篇论文和Java代码正是针对这一主题进行探讨和实现的。 逆向最大匹配法是一种从右到左寻找最长词典词的策略，与传统...
总结，基于Hash结构的逆向最大匹配分词算法改进是一种有效的策略，它通过优化数据结构和算法设计，实现了分词速度和准确性的双重提升，为中文信息处理领域提供了有力的技术支持。这一改进对于处理大规模中文文本数据...
总结，最大正向逆向分词算法是中文分词的一种高效策略，它结合了正向和逆向匹配的优势，既能快速处理大部分常见情况，又能较好地处理复杂语境和多义词问题。在实际的自然语言处理系统中，如搜索引擎、文本分析和机器...
正向最大匹配（Forward Maximum Matching, 简称FMM）和逆向最大匹配（Backward Maximum Matching, 简称BMM）是两种广泛应用的分词算法，它们在C#环境下被实现并封装在一个名为"FMM&BMM_WordDivise"的压缩包中。...
### 最大逆向中文分词算法详解 #### 一、引言 中文分词作为自然语言处理中的基础任务之一，在信息检索、文本挖掘等领域扮演着重要角色。与英文等基于空格分隔的语言不同，中文词语之间没有明显的界限，因此需要...