双向最大匹配算法（含完整代码实现，ui界面）正向最大匹配算法，逆向最大匹配算法

双向最大匹配算法（含完整代码实现，ui界面）正向最大匹配算法，逆向最大匹配算法

一、理论描述

中文分词(Chinese Word Segmentation) 指的是将一个汉字序列切分成一个一个单独的词。分词就是将连续的字序列按照一定的规范重新组合成词序列的过程。

二、算法描述

本文实现双向匹配算法，具体算法描述如下：

正向最大匹配算法描述：

设MaxLen表示最大词长，D为分词词典

(1) 从待切分语料中按正向取长度为MaxLen的字串str,令

Len=MaxLen;

(2) 把str与D中的词从左往右相匹配;

(3) 若匹配成功，则认为该字串为词，指向待切分语料的指

针向前移Len个汉字，返回到（1）;

(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=“课时”；
（21）查词表，W在词表中，将W加入到S2中，S2=“计算语言学/ 课程/ 是/ 三/ 个/ 课时/ “，并将W从S1中去掉，此时S1=””。
（22）S1为空，输出S2作为分词结果，分词过程结束。

逆向：

待分词句子： sentence[]={“计算语言学课程有意思”}

词表： 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 license header, choose License Headers in Project Properties.
 * To change this template file, choose 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;


public class seg {
   
    
    String result;
    String segstring;
    int MaxLen;
    int Len;
    int indexpos;
    Map <String,String> dict; //<"石柱",n>
    
    public seg(String inputstr, int maxlen)
    {
   
        segstring=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("chineseDic.txt"),"GBK"));
        String line = null; 
        while((line = br.readLine())!=null)
        {
   
            String[] words=line.trim().split(",");//"石柱",n,  words=["石柱","n"]
            String word=
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46