双向最大匹配方法

双向最大匹配方法是一种基于词典的分词方法。

基于词典的分词方法是依照一定策略将待分析的汉字串与一个“大机器词典”中的词条进行匹配，若在词典中找到某个字符串。则匹配成功。

依照扫描方向的不同：正向匹配和逆向匹配

依照长度的不同：最大匹配和最小匹配

正向最大匹配思想FMM

1.从左向右取待切分汉语句的m个字符作为匹配字段，m为大机器词典中最长词条个数。

2.查找大机器词典并进行匹配。若匹配成功，则将这个匹配字段作为一个词切分出来。

若匹配不成功。则将这个匹配字段的最后一个字去掉，剩下的字符串作为新的匹配字段，进行再次匹配，反复以上过程，直到切分出全部词为止。

逆向最大匹配算法BMM

该算法是正向最大匹配的逆向思维。匹配不成功，将匹配字段的最前一个字去掉，实验表明。逆向最大匹配算法要优于正向最大匹配算法。

双向最大匹配法(Bi-directction Matching method,BM)

双向最大匹配法是将正向最大匹配法得到的分词结果和逆向最大匹配法的到的结果进行比較，从而决定正确的分词方法。据SunM.S. 和 Benjamin K.T.（1995）的研究表明，中文中90.0％左右的句子。正向最大匹配法和逆向最大匹配法全然重合且正确，仅仅有大概9.0％的句子两种切分方法得到的结果不一样。但当中必有一个是正确的（歧义检測成功）。仅仅有不到1.0％的句子，或者正向最大匹配法和逆向最大匹配法的切分虽重合却是错的，或者正向最大匹配法和逆向最大匹配法切分不同但两个都不正确（歧义检測失败）。

这正是双向最大匹配法在有用中文信息处理系统中得以广泛使用的原因所在。

在本文实现的方法中，是综合考虑了正向和逆向最大匹配的结果，增加了一些启示式的规则来对分词结果进行进一步消歧的。

启示式规则：

1.假设正反向分词结果词数不同，则取分词数量较少的那个。

2.假设分词结果词数同样

a.分词结果同样，就说明没有歧义，可返回随意一个。

b.分词结果不同。返回当中单字较少的那个。

以下是详细实现

package Segment;
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
import java.util.Vector;


public class FBSegment {
	private static Set<String> seg_dict;
	
	//载入词典
	public static void Init(){
		seg_dict = new HashSet<String>();
		String dicpath = "data/worddic.txt";
		String line = null;
		
		BufferedReader br;
		try{
			br = new BufferedReader( new InputStreamReader( new FileInputStream(dicpath)));	
			while((line = br.readLine()) != null){
				line = line.trim();
				if(line.isEmpty())
					continue;	
				seg_dict.add(line);
			}
			br.close();
		}catch(IOException e){
			e.printStackTrace();
		}
		
	}
	/**
	 * 前向算法分词
	 * @param seg_dict 分词词典
	 * @param phrase 待分词句子
	 * @return 前向分词结果
	 */
	private static Vector<String> FMM2( String  phrase){
		int maxlen = 16;
		Vector<String> fmm_list = new Vector<String>();
		int len_phrase = phrase.length();
		int i=0,j=0;
		
		while(i < len_phrase){
			int end = i+maxlen;
			if(end >= len_phrase)
				end = len_phrase;
			String phrase_sub = phrase.substring(i, end);
			for(j = phrase_sub.length(); j >=0; j--){
				if(j == 1)
					break;
				String key =  phrase_sub.substring(0, j);
				if(seg_dict.contains(key)){
					fmm_list.add(key);
					i +=key.length() -1;
					break;
				}
			}
			if(j == 1)
				fmm_list.add(""+phrase_sub.charAt(0));
			i+=1;
		}
		return fmm_list;
	}
	
	/**
	 * 后向算法分词
	 * @param seg_dict 分词词典
	 * @param phrase 待分词句子
	 * @return 后向分词结果
	 */
	private static Vector<String> BMM2( String  phrase){
		int maxlen = 16;
		Vector<String> bmm_list = new Vector<String>();
		int len_phrase = phrase.length();
		int i=len_phrase,j=0;
		
		while(i > 0){
			int start = i - maxlen;
			if(start < 0)
				start = 0;
			String phrase_sub = phrase.substring(start, i);
			for(j = 0; j < phrase_sub.length(); j++){
				if(j == phrase_sub.length()-1)
					break;
				String key =  phrase_sub.substring(j);
				if(seg_dict.contains(key)){
					bmm_list.insertElementAt(key, 0);
					i -=key.length() -1;
					break;
				}
			}
			if(j == phrase_sub.length() -1)
				bmm_list.insertElementAt(""+phrase_sub.charAt(j), 0);
			i -= 1;
		}
		return bmm_list;
	}
		
	/**
	 * 该方法结合正向匹配和逆向匹配的结果，得到分词的终于结果
	 * @param FMM2 正向匹配的分词结果
	 * @param BMM2 逆向匹配的分词结果
	 * @param return 分词的终于结果
	 */
	public static Vector<String> segment( String phrase){
		Vector<String> fmm_list = FMM2(phrase);
		Vector<String> bmm_list = BMM2(phrase);
		//假设正反向分词结果词数不同。则取分词数量较少的那个
		if(fmm_list.size() != bmm_list.size()){
			if(fmm_list.size() > bmm_list.size())
				return bmm_list;
			else return fmm_list;
		}
		//假设分词结果词数同样
		else{
			//假设正反向的分词结果同样，就说明没有歧义。可返回随意一个
			int i ,FSingle = 0, BSingle = 0;
			boolean isSame = true;
			for(i = 0; i < fmm_list.size();  i++){
				if(!fmm_list.get(i).equals(bmm_list.get(i)))
					isSame = false;
				if(fmm_list.get(i).length() ==1)
					FSingle +=1;
				if(bmm_list.get(i).length() ==1)
					BSingle +=1;
			}
			if(isSame)
				return fmm_list;
			else{
				//分词结果不同，返回当中单字较少的那个
				if(BSingle > FSingle)
					return fmm_list;
				else return bmm_list;
			}
		}
	}
	public static void main(String [] args){
		String test = "我是一个学生";
		FBSegment.Init();
		System.out.println(FBSegment.segment(test));
	}
}

输出：[我, 是, 一个, 学生]

了解更具体的信息。能够到这里https://github.com/talentlei

參考：

中文分词算法笔记 http://www.cnblogs.com/lvpei/archive/2010/08/04/1792409.html;

中文分词算法总结 http://blog.csdn.net/chenlei0630/article/details/40710325;