双向最⼤匹配算法（含完整代码实现，ui界⾯）正向最⼤匹配算法，逆向最⼤匹
配算法
双向最⼤匹配算法（含完整代码实现，ui界⾯）正向最⼤匹配算法，逆向最⼤匹配算法
⼀、理论描述
中⽂分词(Chine Word Segmentation) 指的是将⼀个汉字序列切分成⼀个⼀个单独的词。分词就是将连续的字序列按照⼀定的规范重新组合成词序列的过程。
⼆、算法描述
本⽂实现双向匹配算法，具体算法描述如下：
正向最⼤匹配算法描述：
设MaxLen表⽰最⼤词长，D为分词词典
(1) 从待切分语料中按正向取长度为MaxLen的字串str，令
Len=MaxLen;
(2) 把str与D中的词从左往右相匹配;
(3) 若匹配成功，则认为该字串为词，指向待切分语料的指
针向前移Len个汉字，返回到（1）;
joanofarc(4) 若不成功：如果Len>1，则将Len减1，从待切分语料中
取长度为Len的字串str，返回到（2）。否则，得到长度为
2的单字词，指向待切分语料的指针向前移1个汉字，
返回（1）。
反向最⼤匹配**算法描述：
设MaxLen表⽰最⼤词长，D为分词词典
流行英文歌(1) 从待切分语料中按正向取长度为MaxLen的字串str，令
Len=MaxLen;
(2) 把str与D中的词从右往左相匹配;
(3) 若匹配成功，则认为该字串为词，指向待切分语料的指
针向后移Len个汉字，返回到（1）;
(4) 若不成功：如果Len>1，则将Len减1，从待切分语料中
取长度为Len的字串str，返回到（2）。否则，得到长度为
2的单字词，指向待切分语料的指针向后移1个汉字，
返回（1）。
三、详例描述
正向：
S1=“计算语⾔学课程是三个课时” ，设定最⼤词长MaxLen = 5 ,S2= " "
字典中含有三个词：[计算语⾔学]、[课程]、[课时]
（1）S2=""；S1不为空，从S1左边取出候选⼦串W=“计算语⾔学”；
（2）查词表，“计算语⾔学”在词表中，将W加⼊到S2中，S2=“计算语⾔学/ ”， 并将W从S1中去掉，此时S1=“课程是三个课时”；
（3）S1不为空，于是从S1左边取出候选⼦串W=“课程是三个”；
（4）查词表，W不在词表中，将W最右边⼀个字去掉，得到W=“课程是三”；
（5）查词表，W不在词表中，将W最右边⼀个字去掉，得到W=“课程是”；
（6）查词表，W不在词表中，将W最右边⼀个字去掉，得到W=“课程”
（7）查词表，W在词表中，将W加⼊到S2中，S2=“计算语⾔学/ 课程/ ”，并 将W从S1中去掉，此时S1=“是三个课时”；
（8）S1不为空，于是从S1左边取出候选⼦串W=“是三个课时”；
（9）查词表，W不在词表中，将W最右边⼀个字去掉，得到W=“是三个课”；
（10）查词表，W不在词表中，将W最右边⼀个字去掉，得到W=“是三个”；
（11）查词表，W不在词表中，将W最右边⼀个字去掉，得到W=“是三”
（12）查词表，W不在词表中，将W最右边⼀个字去掉，得到W=“是”，这时 W是单字，将W加⼊到S2中，S2=“计算语⾔学/ 课程/是/ ”，并将 W从S1中去掉，此时S1=“三个课时”；
（13）S1不为空，从S1左边取出候选⼦串W=“三个课时”；
（14）查词表，W不在词表中，将W最右边⼀个字去掉，得到W=“三个课”；
（15）查词表，W不在词表中，将W最右边⼀个字去掉，得到W=“三个”；
（16）查词表，W不在词表中，将W最右边⼀个字去掉，得到W=“三”，这时 W是单字，将W加⼊到S2中，S2=“计算语⾔学/ 课程/是/ 三/ ”，并 将W从S1中去掉，此时S1=“个课时”；
（17）S1不为空，从S1左边取出候选⼦串W=“个课时”；
（18）查词表，W不在词表中，将W最右边⼀个字去掉，得到W=“个课”；
（19）查词表，W不在词表中，将W最右边⼀个字去掉，得到W=“个”， 这时W是单字，将W加⼊到S2中，S2=“计算语⾔学/ 课程/是/ 三/ 个/ “，并将W从S1中去掉，此时S1=“课时”；
（20）S1不为空，从S1左边取出候选⼦串W=“课时”；
copyleft
（21）查词表，W在词表中，将W加⼊到S2中，S2=“计算语⾔学/ 课程/ 是/ 三/ 个/ 课时/ “，并将W从S1中去掉，此时S1=””。（22）S1为空，输出S2作为分词结果，分词过程结束。
逆向：
少儿英语口语 mp3
待分词句⼦： ntence[]={“计算语⾔学课程有意思”}
词表： dict[]={“计算”, “计算语⾔学”, “课程”, “有”, “意思”}
⾸先我们定义⼀个最⼤分割长度5，从右往左开始分割：
(1)⾸先取出来的候选词W是 “课程有意思”。
(2) 查词表，W不在词表中，将W最左边的第⼀个字去掉，得到W“程有意思”；
(3) 查词表，W也不在词表中，将W最左边的第⼀个字去掉，得到W“有意思”；
(4) 查词表，W也不在词表中，将W最左边的第⼀个字再去掉，得到W“意思”；
(5) 查词表，W在词表中，就将W从整个句⼦中拆分出来，此时原句⼦为“计算语⾔学课程有”
(6)根据分割长度5，截取句⼦内容，得到候选句W是“⾔学课程有”；
(7) 查词表，W不在词表中，将W最左边的第⼀个字去掉，得到W“⾔学课程有”；
(8) 查词表，W也不在词表中，将W最左边的第⼀个字去掉，得到W“学课程有”；
(9) 依次类推，直到W为“有”⼀个词的时候，这时候将W从整个句⼦中拆分出来，此时句⼦为“计算语⾔学课程”
(10)根据分割长度5，截取句⼦内容，得到候选句W是“算语⾔学课程”；
(11)查词表，W不在词表中，将W最左边的第⼀个字去掉，得到W“语⾔学课程”；
(12) 依次类推，直到W为“课程”的时候，这时候将W从整个句⼦中拆分出来，此时句⼦为“计算语⾔学”
(13)根据分割长度5，截取句⼦内容，得到候选句W是“计算语⾔学”；
(14) 查词表，W在词表，分割结束
四、软件演⽰
正向匹配：
逆向匹配：
正向匹配和逆向匹配的结果是⼀样的。⽽多次测试后，时间上总体来说是正向匹配算法⽐较长。逆向匹配算法时间稍少⼏毫秒。但也会出现逆向匹配算法时间较长的情况。两者的时间复杂度是⼀样的。
正向分词匹配代码
/*
* To change this licen header, choo Licen Headers in Project Properties.
* To change this template file, choo Tools | Templates
* and open the template in the editor.
*/
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.Map;
public class g {
String result;
String gstring;
int MaxLen;
int Len;
int indexpos;
Map <String,String> dict;//<"⽯柱",n>
public g(String inputstr,int maxlen)
{
gstring=inputstr;
MaxLen=maxlen;
Len=MaxLen;
indexpos=0;
result="";
dict=new HashMap<String,String>();
大哥成人导航}
public void ReadDic()throws FileNotFoundException, IOException
{
BufferedReader br =new BufferedReader(new InputStreamReader(new FileInputStream(""),"GBK")); String line = null;
while((line = br.readLine())!=null)
{
String[] im().split(",");//"⽯柱",n, words=["⽯柱","n"]
String word=words[0];
String cx=words[1];
2014年6月六级
dict.put(word, cx);
}
br.clo();
}
public String MM_Seg()throws IOException
{//正向最⼤匹配算法
ReadDic();//读⼊字典
placeAll(" ","");
MM(gstring,MaxLen,0);//正向最⼤分词
return result;
}
public void MM(String str,int len,int frompos)
{
if(frompos+1>str.length())
return;
String curstr="";
int llen=str.length()-(frompos);
if(llen<=len)
curstr=str.substring(frompos,frompos+llen);
el
curstr=str.substring(frompos,frompos+len);
ainsKey(curstr))
{
result=result+curstr+"/ ";
Len=MaxLen;hoisting
indexpos=frompos+len;
MM(str,Len,indexpos);
}
el
{gole
{
if(Len>1)
{
Len=Len-1;
MM(str,Len,frompos);
}
el
{
result=result+str+"/ ";
frompos=frompos+1;
Len=MaxLen;
MM(str,Len,frompos);
}
}
}
public String getResult()
we will rock you什么意思{
return result;
}
public static void main(String[] args)throws IOException, Exception
{
g s=new g("⼀把青菜勤奋勤政勤勤俭节约奇鸟怪物节",3);
String result=s.MM_Seg();
System.out.println(result);
}
}
逆向
/*
* To change this licen header, choo Licen Headers in Project Properties. * To change this template file, choo Tools | Templates
* and open the template in the editor.
*/
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
/**
*
* @author shelly
*/
public class RMM {
liudmila
String result;
String gstring;
int MaxLen;
int Len;
int indexpos;
Map <String,String> dict;//<"⽯柱",n>
public RMM(String inputstr,int maxlen)
{
gstring=inputstr;
MaxLen=maxlen;
Len=MaxLen;
