【学习】深度解析中文分词器算法(最大正向/逆向匹配)

中文分词算法概述:

1:非基于词典的分词(人工智能领域)

相当于人工智能领域计算。一般用于机器学习,特定领域等方法,这种在特定领域的分词可以让计算机在现有的规则模型中,推理如何分词。在某个领域(垂直领域)分词精度较高。但是实现比较复杂。

例:比较流行的语义网:基于本体的语义检索。

大致实现:用protege工具构建一个本体(在哲学中也叫概念,在80年代开始被人工智能),通过jena的推理机制和实现方法。

实现对Ontology的语义检索。

Ontology语义检索这块自己和一朋友也还在琢磨,目前也只处于初级阶段。这一块有兴趣的朋友可以留言一起共享资源。

2:基于词典的分词(最为常见)

这类分词算法比较常见,比如正向/逆向匹配。例如: mmseg分词器 就是一种基于词典的分词算法。以最大正向匹配为主,多种 消除歧义算法为辅。但是不管怎么分。该类分词方法,分词精度不高。由于中文比较复杂,不推荐采用正向最大匹配算法的中文分词器。。逆向最大匹配算法在处理中文往往会比正向要准确。

接下来分析第2种:基于词典的分词算法(最长的词优先匹配)。 先分析最大正向匹配算法

一: 具体流程图如下:

一:以下代码片段为最大正向匹配算法:

[html] view plaincopy
package hhc.forwardAlgorithm; 
 
import java.net.URL; 
import java.nio.charset.Charset; 
import java.nio.file.Files; 
import java.nio.file.Path; 
import java.nio.file.Paths; 
import java.util.ArrayList; 
import java.util.List; 
import java.util.Stack; 
 
/** 
 * @Description:   
 * @Date: 2015-2-7上午02:00:51 
 * @Author 胡慧超 
 * @Version 1.0 
 */ 
@SuppressWarnings("unchecked") 
public class TokenizerAlgorithm { 
    private static final List<String> DIC=new ArrayList<String>(); 
    private static int MAX_LENGTH; 
 
    /** 
     * 把词库词典转化成dic对象,并解析词典信息 
     */ 
    static { 
        try { 
            System.out.println("开始初始化字典..."); 
            int max=1; 
            int count=0; 
            //读取词典中的每一个词 
            URL url=TokenizerAlgorithm.class.getClassLoader().getResource("hhc/dic.txt"); 
            Path path=Paths.get(url.toString().replaceAll("file:/", "")); 
            List<String> list=Files.readAllLines(path, Charset.forName("UTF-8")); 
            System.out.println("读取词典文件结束,词总数为:"+list.size()); 
            for(String line:list){ 
                DIC.add(line); 
                count++; 
                //获取词库中 ,最大长度的词的长度 
                if(line.length()>max){ 
 max=line.length(); 
                } 
            } 
 MAX_LENGTH=max; 
            System.out.println("初始化词典结束,最大分词长度为:"+max+"  !!"); 
            System.out.println("------------------------------------------------------------------------"); 
        } catch (Exception e) { 
            // TODO Auto-generated catch block 
            e.printStackTrace(); 
        } 
    } 
 
    /** 
     * 正向分词算法 
     * @param text   
     * @return 
     */ 
    public static List forwardSeg(String text){ 
        List result=new ArrayList(); 
        while(text.length()>0){ 
            int len=MAX_LENGTH;       
            if(text.length()<MAX_LENGTH){ 
 len=text.length(); 
            } 
            //取指定的最大长度 文本去字典中匹配 
            String tryWord=text.substring(0, len); 
            while(!DIC.contains(tryWord)){//如果词典中不包含该段文本 
                //如果长度为1 的话,且没有在字典中匹配,返回 
                if(tryWord.length()==1){ 
                    break; 
                } 
                //如果匹配不到,则长度减1,继续匹配 
                /** 
                 * --这里就是最关键的地方,把最右边的词去掉一个,继续循环 
                 */       
 tryWord=tryWord.substring(0, tryWord.length()-1);                             
            } 
            result.add(tryWord); 
            //移除该次tryWord,继续循环 
 text=text.substring(tryWord.length()); 
        } 
        return result; 
    } 
 
 
 
    public static void main(String[] args) { 
        // TODO Auto-generated method stub 
        List<String> lst=new ArrayList(); 
        lst.add("研究生命起源"); 
        lst.add("食物和服装"); 
        lst.add("乒乓球拍卖完了"); 
        for(String str:lst){ 
            List<String> list=forwardSeg(str); 
            String word=""; 
            for(String s:list){ 
                s+="/"; 
                word+=s; 
            } 
            System.out.println(word); 
        } 
    } 

执行正向分词结果:

二:最大逆向分词算法

考虑到逆向,为了 区分分词的数据的连贯性。我们采用Stack(栈对象,数据结果,后进先出,不同于Queue和ArrayList有顺序的先进先出) 这个对象来存储分词结果。。

[java] view plaincopy
/** 
 * 逆向分词算法 
 * @param text  
 * @return 
 */ 
public static List reverseSeg(String text){ 
    Stack<String> result=new Stack(); 
 while(text.length()>0){ 
 int len=MAX_LENGTH;       
 if(text.length()<MAX_LENGTH){ 
            len=text.length(); 
        } 
 //取指定的最大长度 文本去字典中匹配 
        String tryWord=text.substring(text.length()-len); 
 while(!DIC.contains(tryWord)){//如果词典中不包含该段文本 
 //如果长度为1 的话,且没有在字典中匹配,返回 
 if(tryWord.length()==1){ 
 break; 
            } 
 //如果匹配不到,则长度减1,继续匹配 
 /** 
             * --这里就是最关键的地方,把最左边的词去掉一个,继续循环 
             */ 
            tryWord=tryWord.substring(1);                             
        } 
        result.add(tryWord); 
 //移除该次tryWord,继续循环 
        text=text.substring(0,text.length()-tryWord.length());       
    } 
 int size=result.size(); 
    List list =new ArrayList(size); 
 for(int i=0;i<size;i++){ 
        list.add(result.pop()); 
    } 
 return list; 
} 

执行逆向分词结果

以上代码实现了两种正向和逆向的算法,可以很明显的比较中文分词结果。

但是效率,,呵呵!确实不咋的。欢迎打脸。

比如:数据结构就先不提。text.substring(0, 0+len)会导致产生大量的新的字符串的产生,消耗CPU的同时还会促发垃圾回收频繁发生导致性能下降。随着最大长度的增加,性能会严重下降。

像之前介绍的采取正向最大匹配算法的mmseg分词器,内部设置了4个消除歧义的过滤算法,这四个歧义解析规则表明是相当有效率的。总体来讲。mmseg的分词精度还是值得推荐的。。。

原文发布于微信公众号 - PPV课数据科学社区(ppvke123)

原文发表时间:2015-02-09

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏杨建荣的学习笔记

使用贪心算法解决集合覆盖问题

有的同学可能对这些州没概念,这个简称就跟京代表北京,鲁代表山东,甘代表甘肃一样,细细一看,都是西部的一些州。

1352
来自专栏chenjx85的技术专栏

leetcode-453-Minimum Moves to Equal Array Elements

3246
来自专栏WOLFRAM

九宫格数独游戏

2388
来自专栏测试开发架构之路

数据库系统关系模型概念

关系模型简述 关系模型就是处理TABLE,它由三部分组成:  描述DB各种数据的基本结构形式(Table/Relation)  描述Table与Table之...

4504
来自专栏落影的专栏

程序员进阶之算法练习(二十二)

前言 时间来到6月,又是一年高考时。 几年之前是坐在教室怀念高考,现在是上班敲着代码怀念学生时代。 正文 1、Lakes in Berland 题目链接 ...

4899
来自专栏进击的程序猿

理解数据结构和算法背景数据本质算法的来源应用总结参考

在我看来应该是先有数据结构,只有当有了数据,我们才会考虑算法,针对不同的数据结构会有不同的算法。

1224
来自专栏落影的专栏

程序员进阶之算法练习(三十)附基础教程

BAT常见的算法面试题解析:程序员算法基础——动态规划程序员算法基础——贪心算法工作闲暇也会有在线分享,算法基础教程-。

2503
来自专栏落影的专栏

程序员进阶之算法练习(六)

前言 这次只有四个题目,E题是个奇奇怪怪的数学题,就不去啃这个硬骨头了,我们来分析下A/B/C/D: A题是简单的找规律题; B题是博弈的入门题; C题是简单的...

3616
来自专栏Golang语言社区

使用 Go 实现快速排序

快速排序(quick sort)号称是二十世纪最伟大的十大算法之一(The Best of the 20th Century: Editors Name Top...

1592
来自专栏前端儿

九九乘法表

小时候学过的九九乘法表也许将会扎根于我们一生的记忆,现在让我们重温那些温暖的记忆,请编程输出九九乘法表.

2271

扫码关注云+社区

领取腾讯云代金券