`

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

阅读更多

在之前的博文中介绍了基于词典的正向最大匹配算法,用了不到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大的原因之一。

 

看一下改进的算法和原来的算法的对比:

 

正向最大匹配算法:

 

逆向最大匹配算法:

 

 

 

代码托管于GITHUB

 

参考资料:

1、中文分词十年回顾

2、中文信息处理中的分词问题

3、汉语自动分词词典机制的实验研究

4、由字构词_中文分词新方法

5、汉语自动分词研究评述

 

 

 

 

 

 

 

  • 大小: 137.4 KB
  • 大小: 192.4 KB
  • 大小: 245.9 KB
7
1
分享到:
评论

相关推荐

    中文分词程序-正向最大匹配算法及逆向最大匹配算法

    运用正向最大匹配算法进行分析,同时也实现了逆向最大匹配,内有分词词典。

    正向最大匹配中文分词算法

    但不管实现如何,目前而言的分词系统绝大多数都是基于中文词典的匹配算法。其中最为常见的是最大匹配算法 (Maximum Matching,以下简称MM算法) 。MM算法有三种:一种正向最大匹配,一种逆向最大匹配和双向匹配。本...

    中文分词工具word-1.0,Java实现的中文分词组件多种基于词典的分词算法

    2、中文分词算法 之 基于词典的逆向最大匹配算法 3、中文分词算法 之 词典机制性能优化与测试 4、中文分词算法 之 基于词典的正向最小匹配算法 5、中文分词算法 之 基于词典的逆向最小匹配算法 5、Java开源项目...

    正向最大匹配算法实现中文分词

    目前,分词系统绝大多数都是基于中文词典的匹配算法。其中最为常见的是最大匹配算法 (Maximum Matching,以下简称MM算法) 。MM算法有三种:一种正向最大匹配,一种逆向最大匹配和双向匹配。本程序实现了正向最大匹配...

    基于正向、逆向的最大分词算法实现

    里面包含完整代码,有词典,解压后是vs2017的工程文件,可直接运用测试。

    反向最大匹配算法实现中文分词

    目前,分词系统绝大多数都是基于中文词典的匹配算法。其中最为常见的是最大匹配算法 (Maximum Matching,以下简称MM算法) 。MM算法有三种:一种正向最大匹配,一种逆向最大匹配和双向匹配。本程序实现了反向最大匹配...

    python实现机械分词之逆向最大匹配算法代码示例

    逆向最大匹配分词是中文分词基本算法之一,因为是机械切分,所以它也有分词速度快的优点,且逆向最大匹配分词比起正向最大匹配分词更符合人们的语言习惯。逆向最大匹配分词需要在已有词典的基础上,从被处理文档的...

    基于逆向匹配的中文分词

    基于逆向匹配的中文分词算法实现,产生词典和测试数据,分词后具有结果分析功能,计算精确度,召回率,F值

    基于Hash结构的逆向最大匹配分词算法的改进_丁振国1

    (1) 首字 Hash 索引:首字 Hash 函数根据汉字的国标区位 (2)词索引:词索引的每个单元包括两项内容:①所有词长 (3)词典正文:以词为单位的有序表

    自然语言处理:中文分词

    (1)逆向最大匹配算法使用的分词词典是逆序词典,里面的每个词都将按逆序方式存放。在实际应用过程中,可以将待分词文本进行倒排处理,从而生成逆序文本,然后再根据逆序词典,对逆序文本用正向最大匹配算法进行...

    浅析常用分词算法的比较与设想

    基于文本匹配的算法又称之为“机械分词算法”,他是它是按照一定的策略将待分析的汉字串与一个“充分大的”机器词典中的词条进行配,若在词典中找到某个字符串,则匹配成功,可识别出一个词。按照扫描方向的不同,...

    python基础编程:python中文分词教程之前向最大正向匹配算法详解

    英文的分词由于单词间是以空格进行分隔的,所以分词要相对的容易些,而中文就不同了,中文中一个句子的分隔就是以字为单位的了,而所谓的正向最大匹配和逆向最大匹配便是一种分词匹配的方法,这里以词典匹配说明。...

    python中文分词教程之前向最大正向匹配算法详解

    英文的分词由于单词间是以空格进行分隔的,所以分词要相对的容易些,而中文就不同了,中文中一个句子的分隔就是以字为单位的了,而所谓的正向最大匹配和逆向最大匹配便是一种分词匹配的方法,这里以词典匹配说明。...

    基于Python实现三种中文分词方法的性能对比与评分【100011006】

    本学期,我们在自然语言处理课上学习了多种中文分词算法,在本次大作业中,我们选择了其中的三个算法:最大匹配的三种算法--正向、逆向、双向;基于统计的Uni-Gram模型;隐马尔可夫(HMM)统计模型。首先我们将会...

    中文分词切分技术研究

    本文分析了现有的基于词典的分词算法,在比较各种算法优缺点的基础上提出了将正向匹配算法与逆向匹配 算法所得到的结果集进行叠加,生成粗分结果集的新观点,再对生成的粗分结果集构造非负权有向图,最后应用最短...

    中分分词与分词性能评测代码及详细设计文档

    通过本资源了解中文分词的意义,在实现正向、逆向最大匹配分词算法的过程中,加深对自然语言理解原理的探讨兴趣。本资源内含详细的代码设计分档、测试语料、源代码以及多个自己制作的语料库词典,分别实现了正、逆向...

    中文分词开源项目 JAVA中文分词

    algorithmMenu.add(bmmItem = new JRadioButtonMenuItem("逆向最大匹配", false)); ButtonGroup algorithms = new ButtonGroup(); algorithms.add(fmmItem); algorithms.add(bmmItem); ...

    B-树实现的中文词典

    B-树作为查找作为查找存储结构,中文单词进行哈希,本中文词典规模在十万级别以上,最长逆向匹配算法实现中文分词。

Global site tag (gtag.js) - Google Analytics