中文分词算法 之 基于词典的逆向最大匹配算法
- - ITeye博客在之前的博文中介绍了 基于词典的正向最大匹配算法,用了不到50行代码就实现了,然后分析了词典查找算法的时空复杂性,最后使用前缀树来实现词典查找算法并做了3次优化. 下面我们看看基于词典的逆向最大匹配算法的实现,如下代码所示:. //取指定的最大长度的文本去词典里面匹配. //如果长度为一且在词典中未找到匹配,则按长度为一切分.
在之前的博文中介绍了 基于词典的正向最大匹配算法,用了不到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, 应用, 级, 产品开发, 平台, 的, 作者] 正向最大匹配: [研究生, 命, 的, 起源] 逆向最大匹配: [研究, 生命, 的, 起源] 正向最大匹配: [长春市, 长春, 节, 致辞] 逆向最大匹配: [长春, 市长, 春节, 致辞] 正向最大匹配: [他, 从, 马上, 下来] 逆向最大匹配: [他, 从, 马上, 下来] 正向最大匹配: [乒乓球拍, 卖完, 了] 逆向最大匹配: [乒乓球拍, 卖完, 了] 正向最大匹配: [咬, 死, 猎人, 的, 狗] 逆向最大匹配: [咬, 死, 猎人, 的, 狗] 正向最大匹配: [大学生, 活象, 白纸] 逆向最大匹配: [大学生, 活象, 白纸] 正向最大匹配: [他, 有, 各种, 才能] 逆向最大匹配: [他, 有, 各种, 才能] 正向最大匹配: [什么, 时候, 我, 才能, 克服, 这个, 困难] 逆向最大匹配: [什么, 时候, 我, 才, 能克服, 这个, 困难]