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

[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); 
        } 
    } 

[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; 
}