基于字典的中文分词算法RMM,MM实现

3/8/2017来源:ASP.NET技巧人气:2490

引言:目前针对中文分词一般有基于字典,基于统计(HMM等),基于规则的分词方法,然而其中基于字典的中文分词是最基础,同时也是最高效的方式,但分词精度取决与字典的规模。 一.基于字典的中文算法简介 1.定义:按照一定策略将带分析的汉字串与一个大机器字典中的词条进行匹配,若在词典中找到某个字符串,则匹配成功.所以也称为机械匹配。 按照扫描方向的不同:正向匹配和逆向匹配 按照长度不同:最长匹配和最小匹配 2.正向最大匹配算法MM 1)从左向右取待切分汗语句的m个字符作为匹配字段,m为大机器字典中最长词条个数。 2)查找打机器词条并进行匹配, 若匹配成功,则将这个匹配字段作为一个词切分出来。 3)若匹配不成功,则将这个匹配字段的最后一个字去掉,剩下来的字符串作为新的匹配字段, 继续进行再次匹配,重复以上过程,直到切分出所有词为止. 3.逆向最大匹配算法RMM 该算法是正向最大匹配的逆向思维(最大匹配的顺序不是从首字母开始,而是从末尾开始),匹配不成功, 将匹配自大un的最前一个字去掉,实验表明,逆向最大匹配算法要优于正向匹配算法。 (RMM产生歧义的可能性比MM低,你将会从以下案例中体会)

4.更多关于中文分词算法,查看中文分词常用算法

二.中文分词算法RMM,MM实现

1.定义分词器的基类和一些公有方法和相关接口

package myAnalyzer;
import java.util.*;
public abstract class Analyzer {
public String Words;
//匹配的最大长度
public int max_length=4;
//模拟字典
PRivate HashSet<String> dict=new HashSet();
//存放分词后的序列
public ArrayList<String> analyzerResult=new ArrayList<String>();
public Analyzer(String words){
        this.words=words;
        System.out.println("加载字典");
        dict.add("服装");
        dict.add("有限公司");
        dict.add("公司");
        dict.add("和服");
    }
//完成分词工作
public void splitWords(){
    while(!"".equals(words)){
        splitWordsbyOneStep();
    }
}
//进行一次切分,将切分的单词放入分词结果中,并更新原始的目标串
public abstract void splitWordsbyOneStep();
//返回分词结果
public  List<String> getSplitResult(){
    splitWords();
    return analyzerResult;
}
//判断该词是否在字典中
public boolean find(String str){
    if(dict.contains(str))
    return true;
    return false;
}
public void printResult(){
    if(analyzerResult.size()==0)
        analyzerResult=(ArrayList<String>)getSplitResult();
    Iterator<String> it=analyzerResult.iterator();
    System.out.println("分词结果为:");
    while(it.hasNext()){
        System.out.print(it.next()+"-");
    }
}
}
2.RMM算法实现
package myAnalyzer;

import java.util.ArrayList;
import java.util.List;
public class RmmAnalyzer extends Analyzer{
    public RmmAnalyzer(String words) {
        super(words);
    }
    //进行一次切分,将切分的单词放入分词结果中,并更新原始的目标串
    @Override
    public void splitWordsbyOneStep() {
         int words_len=words.length();
         if (words_len==0){
             return ;
         }
         String si="";
         //判断匹配的最大长度
         int pattern_len=words_len>=max_length?max_length:words_len;
         System.out.println("patter_len"+pattern_len);
             for(int i=pattern_len;i>=1;i--){
                 //可能切分出来的词语
                  si=words.substring(words_len-i);
                 if(find(si)||(i==1)){
                     //更新带切分的目标串
                     words=words.substring(0,words_len-i);
                     //将分词后的单词加入分词结果中
                     analyzerResult.add(si);
                     break;
                 }
             }
             return;
    }
    //对分词结果进行反转
    @Override
    public void splitWords() {
        super.splitWords();
        analyzerResult=(ArrayList<String>) reverseSplitResult();
    }
    //RMM需要对分词结果进行反逆操作
    private List<String> reverseSplitResult() {
        // TODO Auto-generated method stub
        List<String> copyresult=new ArrayList();
        for(int i=analyzerResult.size()-1;i>=0;i--){
            copyresult.add(analyzerResult.get(i));
        }
        return copyresult;
    }
}3.MM算法实现

package myAnalyzer;

import java.util.ArrayList;
import java.util.List;

import javax.swing.text.DefaultEditorKit.CopyAction;

public class MmAnalyzer extends Analyzer{
    public MmAnalyzer(String words) {
        super(words);
    }
    //进行一次切分,将切分的单词放入分词结果中,并更新原始的目标串
    @Override
    public void splitWordsbyOneStep() {
         int words_len=words.length();
         //结束
         if (words_len==0){
             return;
         }
         //匹配的最大长度
          int pattern_len=words_len>=max_length?max_length:words_len;
          int bestPosition=1;
          //可能找到的词语字串
          String si="";
             for(int i=pattern_len;i>=1;i--){
                   si=words.substring(0,i);
                   //找到即返回
                 if(find(si)){
                     bestPosition=i;
                     break;
                 }
             }
             //加入分词结果中
             si=words.substring(0,bestPosition);
             analyzerResult.add(si);
             //防止数组下表越界
             if(bestPosition<words_len){
            //更新待切分的目标串
             words=words.substring(bestPosition);
             }
             else{
                 words="";
                 }
    }
    }
三, 测试

1.测试代码

package myAnalyzer;

import java.util.List;

import org.junit.Test;

public class test {
    @Test
public void test(){
	String content="永和服装有限公司";
	System.out.println("逆向最大匹配算法RMM")
        RmmAnalyzer rmm=new RmmAnalyzer(content);
        rmm.printResult();
        System.out.println(“正向最大匹配算法MM")
        MmAnalyzer mm=new MmAnalyzer(content);
        mm.printResult();
    }
}2.分析比对

待分词的字符串序列为永和服装有限公司 逆向最大匹配算法执行结果为:永,和,服装,有限公司 正向最大匹配算法的结果为:永,和服,装,有限公司 由此可知,RMM比MM在处理歧义等语言方面更有优势,出错率更低。 算法无绝对的好坏,大家私下可以了解相关的算法,比如双向最大匹配算法(结合逆向和正向最大匹配算法),最小匹配算法等,学习下相关理论。