图文精华

About云-梭伦科技»专题 › 技术学习(版主发帖区) › 大数据学习 › 实操演练› 中文分词算法 之 基于词典的正向最大匹配算法
分享

中文分词算法 之 基于词典的正向最大匹配算法

nettman 2014-9-20 19:48:45 发表于 实操演练 [显示全部楼层] 只看大图 回帖奖励 阅读模式 关闭右栏 3 38988
About云VIP帮助找工作和提升
问题导读
1.中文分词算法包含哪些流程？
2.DIC.contains(tryWord))词的作用是什么？
3.词典越来越大，内存占用越来越多怎么办？




基于词典的正向最大匹配算法（最长词优先匹配），算法会根据词典文件自动调整最大长度，分词的好坏完全取决于词典。

算法流程图如下：
1.png

Java实现代码如下：


  1. /**

  2.  * 基于词典的正向最大匹配算法

  3.  * @author 杨尚川

  4.  */

  5. public class WordSeg {

  6.     private static final List<String> DIC = new ArrayList<>();

  7.     private static final int MAX_LENGTH;

  8.     static{

  9.         try {

  10.             System.out.println("开始初始化词典");

  11.             int max=1;

  12.             int count=0;

  13.             List<String> lines = Files.readAllLines(Paths.get("D:/dic.txt"), Charset.forName("utf-8"));

  14.             for(String line : lines){

  15.                 DIC.add(line);

  16.                 count++;

  17.                 if(line.length()>max){

  18.                     max=line.length();

  19.                 }

  20.             }

  21.             MAX_LENGTH = max;

  22.             System.out.println("完成初始化词典，词数目："+count);

  23.             System.out.println("最大分词长度："+MAX_LENGTH);

  24.         } catch (IOException ex) {

  25.             System.err.println("词典装载失败:"+ex.getMessage());

  26.         }

  27.          

  28.     }

  29.     public static void main(String[] args){

  30.         String text = "杨尚川是APDPlat应用级产品开发平台的作者";  

  31.         System.out.println(seg(text));

  32.     }

  33.     public static List<String> seg(String text){        

  34.         List<String> result = new ArrayList<>();

  35.         while(text.length()>0){

  36.             int len=MAX_LENGTH;

  37.             if(text.length()<len){

  38.                 len=text.length();

  39.             }

  40.             //取指定的最大长度的文本去词典里面匹配

  41.             String tryWord = text.substring(0, 0+len);

  42.             while(!DIC.contains(tryWord)){

  43.                 //如果长度为一且在词典中未找到匹配，则按长度为一切分

  44.                 if(tryWord.length()==1){

  45.                     break;

  46.                 }

  47.                 //如果匹配不到，则长度减一继续匹配

  48.                 tryWord=tryWord.substring(0, tryWord.length()-1);

  49.             }

  50.             result.add(tryWord);

  51.             //从待分词文本中去除已经分词的文本

  52.             text=text.substring(tryWord.length());

  53.         }

  54.         return result;

  55.     }

  56. }
复制代码


词典文件下载地址dic.rar，简单吧，呵呵

实现功能是简单，不过这里的词典中词的数目为：427452，我们需要频繁执行DIC.contains(tryWord))来判断一个词是否在词典中，所以优化这行代码能够显著提升分词效率（不要过早优化、不要做不成熟的优化）。

上面的代码是利用了JDK的Collection接口的contains方法来判断一个词是否在词典中，而这个方法的不同实现，其性能差异极大，上面的初始版本是用了ArrayList：List<String> DIC = new ArrayList<>()。那么这个ArrayList的性能如何呢？还有更好性能的实现吗？

通常来说，对于查找算法，在有序列表中查找比在无序列表中查找更快，分区查找比全局遍历要快。

通过查看ArrayList、LinkedList、HashSet的contains方法的源代码，发现ArrayList和LinkedList采用全局遍历的方式且未利用有序列表的优势，HashSet使用了分区查找，如果hash分布均匀冲突少，则需要遍历的列表就很少甚至不需要。理论归理论，还是写个代码来测测更直观放心，测试代码如下：

  1. /**

  2.  * 比较词典查询算法的性能

  3.  * @author 杨尚川

  4.  */

  5. public class SearchTest {

  6.     //为了生成随机查询的词列表

  7.     private static final List<String> DIC_FOR_TEST = new ArrayList<>();

  8.     //通过更改这里DIC的实现来比较不同实现之间的性能

  9.     private static final List<String> DIC = new ArrayList<>();

  10.     static{

  11.         try {

  12.             System.out.println("开始初始化词典");

  13.             int count=0;

  14.             List<String> lines = Files.readAllLines(Paths.get("D:/dic.txt"), Charset.forName("utf-8"));

  15.             for(String line : lines){

  16.                 DIC.add(line);

  17.                 DIC_FOR_TEST.add(line);

  18.                 count++;

  19.             }

  20.             System.out.println("完成初始化词典，词数目："+count);

  21.         } catch (IOException ex) {

  22.             System.err.println("词典装载失败:"+ex.getMessage());

  23.         }        

  24.     }

  25.     public static void main(String[] args){

  26.         //选取随机值

  27.         List<String> words = new ArrayList<>();

  28.         for(int i=0;i<100000;i++){

  29.             words.add(DIC_FOR_TEST.get(new Random(System.nanoTime()+i).nextInt(427452)));

  30.         }

  31.         long start = System.currentTimeMillis();

  32.         for(String word : words){

  33.             DIC.contains(word);

  34.         }

  35.         long cost = System.currentTimeMillis()-start;

  36.         System.out.println("cost time:"+cost+" ms");

  37.     }

  38. }
复制代码
#分别运行10次测试，然后取平均值
LinkedList     10000次查询       cost time:48812 ms
ArrayList      10000次查询       cost time:40219 ms
HashSet        10000次查询       cost time:8 ms
HashSet        1000000次查询     cost time:258 ms
HashSet        100000000次查询   cost time:28575 ms



我们发现HashSet性能最好，比LinkedList和ArrayList快约3个数量级！这个测试结果跟前面的分析一致，LinkedList要比ArrayList慢一些，虽然他们都是全局遍历，但是LinkedList需要操作下一个数据的引用，所以会多一些操作，LinkedList因为需要保存前驱和后继引用，占用的内存也要高一些。

虽然HashSet已经有不错的性能了，但是如果词典越来越大，内存占用越来越多怎么办？如果有一个数据结构，有接近HashSet性能的同时，又能对词典的数据进行压缩以减少内存占用，那就完美了。

前缀树（Trie）有可能可以实现“鱼与熊掌兼得”的好事，自己实现一个Trie的数据结构，代码如下：

  1. /**

  2.  * 前缀树的Java实现

  3.  * 用于查找一个指定的字符串是否在词典中

  4.  * @author 杨尚川

  5.  */

  6. public class Trie {

  7.     private final TrieNode ROOT_NODE = new TrieNode('/');

  8.  

  9.     public boolean contains(String item){

  10.         //去掉首尾空白字符

  11.         item=item.trim();

  12.         int len = item.length();

  13.         if(len < 1){

  14.             return false;

  15.         }

  16.         //从根节点开始查找

  17.         TrieNode node = ROOT_NODE;

  18.         for(int i=0;i<len;i++){

  19.             char character = item.charAt(i);

  20.             TrieNode child = node.getChild(character);

  21.             if(child == null){

  22.                 //未找到匹配节点

  23.                 return false;

  24.             }else{

  25.                 //找到节点，继续往下找

  26.                 node = child;

  27.             }

  28.         }

  29.         if(node.isTerminal()){

  30.             return true;

  31.         }

  32.         return false;

  33.     }

  34.     public void addAll(List<String> items){

  35.         for(String item : items){

  36.             add(item);

  37.         }

  38.     }

  39.     public void add(String item){

  40.         //去掉首尾空白字符

  41.         item=item.trim();

  42.         int len = item.length();

  43.         if(len < 1){

  44.             //长度小于1则忽略

  45.             return;

  46.         }

  47.         //从根节点开始添加

  48.         TrieNode node = ROOT_NODE;

  49.         for(int i=0;i<len;i++){

  50.             char character = item.charAt(i);

  51.             TrieNode child = node.getChildIfNotExistThenCreate(character);

  52.             //改变顶级节点

  53.             node = child;

  54.         }

  55.         //设置终结字符，表示从根节点遍历到此是一个合法的词

  56.         node.setTerminal(true);

  57.     }

  58.     private static class TrieNode{

  59.         private char character;

  60.         private boolean terminal;

  61.         private final Map<Character,TrieNode> children = new ConcurrentHashMap<>();        

  62.         public TrieNode(char character){

  63.             this.character = character;

  64.         }

  65.         public boolean isTerminal() {

  66.             return terminal;

  67.         }

  68.         public void setTerminal(boolean terminal) {

  69.             this.terminal = terminal;

  70.         }        

  71.         public char getCharacter() {

  72.             return character;

  73.         }

  74.         public void setCharacter(char character) {

  75.             this.character = character;

  76.         }

  77.         public Collection<TrieNode> getChildren() {

  78.             return this.children.values();

  79.         }

  80.         public TrieNode getChild(char character) {

  81.             return this.children.get(character);

  82.         }        

  83.         public TrieNode getChildIfNotExistThenCreate(char character) {

  84.             TrieNode child = getChild(character);

  85.             if(child == null){

  86.                 child = new TrieNode(character);

  87.                 addChild(child);

  88.             }

  89.             return child;

  90.         }

  91.         public void addChild(TrieNode child) {

  92.             this.children.put(child.getCharacter(), child);

  93.         }

  94.         public void removeChild(TrieNode child) {

  95.             this.children.remove(child.getCharacter());

  96.         }        

  97.     }

  98.      

  99.     public void show(){

  100.         show(ROOT_NODE,"");

  101.     }

  102.     private void show(TrieNode node, String indent){

  103.         if(node.isTerminal()){

  104.             System.out.println(indent+node.getCharacter()+"(T)");

  105.         }else{

  106.             System.out.println(indent+node.getCharacter());

  107.         }

  108.         for(TrieNode item : node.getChildren()){

  109.             show(item,indent+"\t");

  110.         }

  111.     }

  112.     public static void main(String[] args){

  113.         Trie trie = new Trie();

  114.         trie.add("APDPlat");

  115.         trie.add("APP");

  116.         trie.add("APD");

  117.         trie.add("Nutch");

  118.         trie.add("Lucene");

  119.         trie.add("Hadoop");

  120.         trie.add("Solr");

  121.         trie.add("杨尚川");

  122.         trie.add("杨尚昆");

  123.         trie.add("杨尚喜");

  124.         trie.add("中华人民共和国");

  125.         trie.add("中华人民打太极");

  126.         trie.add("中华");

  127.         trie.add("中心思想");

  128.         trie.add("杨家将");        

  129.         trie.show();

  130.     }

  131. }
复制代码


修改前面的测试代码，把List<String> DIC = new ArrayList<>()改为Trie DIC = new Trie()，使用Trie来做词典查找，最终的测试结果如下：
  1. #分别运行10次测试，然后取平均值

  2. LinkedList     10000次查询       cost time:48812 ms

  3. ArrayList      10000次查询       cost time:40219 ms

  4. HashSet        10000次查询       cost time:8 ms

  5. HashSet        1000000次查询     cost time:258 ms

  6. HashSet        100000000次查询   cost time:28575 ms

  7. Trie           10000次查询       cost time:15 ms

  8. Trie           1000000次查询     cost time:1024 ms

  9. Trie           100000000次查询   cost time:104635 ms
复制代码

可以发现Trie和HashSet的性能差异较小，在半个数量级以内，通过jvisualvm惊奇地发现Trie占用的内存比HashSet的大约2.6倍，如下图所示：

HashSet:

2.png

Trie:

3.png

词典中词的数目为427452，HashSet是基于HashMap实现的，所以我们看到占内存最多的是HashMap$Node、char[]和String，手动执行GC多次，这三种类型的实例数一直在变化，当然都始终大于词数427452。Trie是基于ConcurrentHashMap实现的，所以我们看到占内存最多的是ConcurrentHashMap、ConcurrentHashMap$Node[]、ConcurrentHashMap$Node、Trie$TrieNode和Character，手动执行GC多次，发现Trie$TrieNode的实例数一直保持不变，说明427452个词经过Trie处理后的节点数为603141。

很明显地可以看到，这里Trie的实现不够好，选用ConcurrentHashMap占用的内存相当大，那么我们如何来改进呢？把ConcurrentHashMap替换为HashMap可以吗？HashSet不是也基于HashMap吗？看看把ConcurrentHashMap替换为HashMap后的效果，如下图所示：

4.png
内存占用虽然少了10M左右，但仍然是HashSet的约2.4倍，本来是打算使用Trie来节省内存，没想反正更加占用内存了，既然使用HashMap来实现Trie占用内存极高，那么试试使用数组的方式，如下代码所示：



  1. /**

  2.  * 前缀树的Java实现

  3.  * 用于查找一个指定的字符串是否在词典中

  4.  * @author 杨尚川

  5.  */

  6. public class TrieV2 {

  7.     private final TrieNode ROOT_NODE = new TrieNode('/');

  8.  

  9.     public boolean contains(String item){

  10.         //去掉首尾空白字符

  11.         item=item.trim();

  12.         int len = item.length();

  13.         if(len < 1){

  14.             return false;

  15.         }

  16.         //从根节点开始查找

  17.         TrieNode node = ROOT_NODE;

  18.         for(int i=0;i<len;i++){

  19.             char character = item.charAt(i);

  20.             TrieNode child = node.getChild(character);

  21.             if(child == null){

  22.                 //未找到匹配节点

  23.                 return false;

  24.             }else{

  25.                 //找到节点，继续往下找

  26.                 node = child;

  27.             }

  28.         }

  29.         if(node.isTerminal()){

  30.             return true;

  31.         }

  32.         return false;

  33.     }

  34.     public void addAll(List<String> items){

  35.         for(String item : items){

  36.             add(item);

  37.         }

  38.     }

  39.     public void add(String item){

  40.         //去掉首尾空白字符

  41.         item=item.trim();

  42.         int len = item.length();

  43.         if(len < 1){

  44.             //长度小于1则忽略

  45.             return;

  46.         }

  47.         //从根节点开始添加

  48.         TrieNode node = ROOT_NODE;

  49.         for(int i=0;i<len;i++){

  50.             char character = item.charAt(i);

  51.             TrieNode child = node.getChildIfNotExistThenCreate(character);

  52.             //改变顶级节点

  53.             node = child;

  54.         }

  55.         //设置终结字符，表示从根节点遍历到此是一个合法的词

  56.         node.setTerminal(true);

  57.     }

  58.     private static class TrieNode{

  59.         private char character;

  60.         private boolean terminal;

  61.         private TrieNode[] children = new TrieNode[0];

  62.         public TrieNode(char character){

  63.             this.character = character;

  64.         }

  65.         public boolean isTerminal() {

  66.             return terminal;

  67.         }

  68.         public void setTerminal(boolean terminal) {

  69.             this.terminal = terminal;

  70.         }        

  71.         public char getCharacter() {

  72.             return character;

  73.         }

  74.         public void setCharacter(char character) {

  75.             this.character = character;

  76.         }

  77.         public Collection<TrieNode> getChildren() {

  78.             return Arrays.asList(children);            

  79.         }

  80.         public TrieNode getChild(char character) {

  81.             for(TrieNode child : children){

  82.                 if(child.getCharacter() == character){

  83.                     return child;

  84.                 }

  85.             }

  86.             return null;

  87.         }        

  88.         public TrieNode getChildIfNotExistThenCreate(char character) {

  89.             TrieNode child = getChild(character);

  90.             if(child == null){

  91.                 child = new TrieNode(character);

  92.                 addChild(child);

  93.             }

  94.             return child;

  95.         }

  96.         public void addChild(TrieNode child) {

  97.             children = Arrays.copyOf(children, children.length+1);

  98.             this.children[children.length-1]=child;

  99.         }

  100.     }

  101.      

  102.     public void show(){

  103.         show(ROOT_NODE,"");

  104.     }

  105.     private void show(TrieNode node, String indent){

  106.         if(node.isTerminal()){

  107.             System.out.println(indent+node.getCharacter()+"(T)");

  108.         }else{

  109.             System.out.println(indent+node.getCharacter());

  110.         }        

  111.         for(TrieNode item : node.getChildren()){

  112.             show(item,indent+"\t");

  113.         }

  114.     }

  115.     public static void main(String[] args){

  116.         TrieV2 trie = new TrieV2();

  117.         trie.add("APDPlat");

  118.         trie.add("APP");

  119.         trie.add("APD");

  120.         trie.add("杨尚川");

  121.         trie.add("杨尚昆");

  122.         trie.add("杨尚喜");

  123.         trie.add("中华人民共和国");

  124.         trie.add("中华人民打太极");

  125.         trie.add("中华");

  126.         trie.add("中心思想");

  127.         trie.add("杨家将");        

  128.         trie.show();

  129.     }

  130. }
复制代码


内存占用情况如下图所示：

5.png
现在内存占用只有HashSet方式的80%了，内存问题总算是解决了，进一步分析，如果词典够大，词典中有共同前缀的词足够多，节省的内存空间一定非常客观。那么性能呢？看如下重新测试的数据：

#分别运行10次测试，然后取平均值
LinkedList     10000次查询       cost time:48812 ms
ArrayList      10000次查询       cost time:40219 ms
HashSet        10000次查询       cost time:8 ms
HashSet        1000000次查询     cost time:258 ms
HashSet        100000000次查询   cost time:28575 ms
Trie           10000次查询       cost time:15 ms
Trie           1000000次查询     cost time:1024 ms
Trie           100000000次查询   cost time:104635
TrieV1         10000次查询       cost time:16 ms
TrieV1         1000000次查询     cost time:780 ms
TrieV1         100000000次查询   cost time:90949 ms
TrieV2         10000次查询       cost time:50 ms
TrieV2         1000000次查询     cost time:4361 ms
TrieV2         100000000次查询   cost time:483398


总结一下，ArrayList和LinkedList方式实在太慢，跟最快的HashSet比将近慢约3个数量级，果断抛弃。Trie比HashSet慢约半个数量级，内存占用多约2.6倍，改进的TrieV1比Trie稍微节省一点内存约10%，速度差不多。进一步改进的TrieV2比Trie大大节省内存，只有HashSet的80%，不过速度比HashSet慢约1.5个数量级。

TrieV2实现了节省内存的目标，节省了约70%，但是速度也慢了，慢了约10倍，可以对TrieV2做进一步优化，TrieNode的数组children采用有序数组，采用二分查找来加速。

下面看看TrieV3的实现：

6.png
使用了一个新的方法insert来加入数组元素，从无到有构建有序数组，把新的元素插入到已有的有序数组中，insert的代码如下：

  1.         /**

  2.          * 将一个字符追加到有序数组

  3.          * @param array 有序数组

  4.          * @param element 字符

  5.          * @return 新的有序数字

  6.          */

  7.         private TrieNode[] insert(TrieNode[] array, TrieNode element){

  8.             int length = array.length;

  9.             if(length == 0){

  10.                 array = new TrieNode[1];

  11.                 array[0] = element;

  12.                 return array;

  13.             }

  14.             TrieNode[] newArray = new TrieNode[length+1];

  15.             boolean insert=false;

  16.             for(int i=0; i<length; i++){

  17.                 if(element.getCharacter() <= array[i].getCharacter()){

  18.                     //新元素找到合适的插入位置

  19.                     newArray[i]=element;

  20.                     //将array中剩下的元素依次加入newArray即可退出比较操作

  21.                     System.arraycopy(array, i, newArray, i+1, length-i);

  22.                     insert=true;

  23.                     break;

  24.                 }else{

  25.                     newArray[i]=array[i];

  26.                 }

  27.             }

  28.             if(!insert){

  29.                 //将新元素追加到尾部

  30.                 newArray[length]=element;

  31.             }

  32.             return newArray;

  33.         }
复制代码

有了有序数组，在搜索的时候就可以利用有序数组的优势，重构搜索方法getChild：

7.png
  
数组中的元素是TrieNode，所以需要自定义TrieNode的比较方法：

8.png
好了，一个基于有序数组的二分搜索的性能提升重构就完成了，良好的单元测试是重构的安全防护网，没有单元测试的重构就犹如高空走钢索却没有防护垫一样危险，同时，不过早优化，不做不成熟的优化是我们应该谨记的原则，要根据应用的具体场景在算法的时空中做权衡。


OK，看看TrieV3的性能表现，当然了，内存使用没有变化，和TrieV2一样：

  1. TrieV2         10000次查询       cost time:50 ms

  2. TrieV2         1000000次查询     cost time:4361 ms

  3. TrieV2         100000000次查询   cost time:483398 ms

  4. TrieV3         10000次查询       cost time:21 ms

  5. TrieV3         1000000次查询     cost time:1264 ms

  6. TrieV3         100000000次查询   cost time:121740 ms
复制代码


提升效果很明显，约4倍。性能还有提升的空间吗？呵呵......










加微信w3aboutyun，可拉入技术爱好者群
回复

使用道具 举报

自定义广告语

已有(3)人评论

跳转到指定楼层
正序浏览
漂泊一剑客 发表于 2015-8-4 11:34:34
好文，还有其他的吗，例如最小切分什么的
回复

使用道具 举报

HaydnSyx 发表于 2016-8-4 20:19:30
写的非常棒，已拜读
回复

使用道具 举报

zhanmsl 发表于 2017-4-26 11:13:54
好帖，很详细，学习了
回复

使用道具 举报

高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

发表新帖
nettman

超级版主

关注

  • 2849

    主题

  • 3142

    帖子

  • 477

    粉丝

TA的主题
关闭

推荐上一条 /2 下一条

关于我们· 联系我们· 加入我们· 小黑屋· 合作伙伴   

Copyright © 2001-2024 About云-梭伦科技 Powered by Discuz! X3.4 Licensed Discuz Team.

简书 / Smrz 京ICP备2020039040号 Wxb 简书网举报电话：021-34700000