双向最大匹配算法（含完整代码实现，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=words[0];
? ? ? ? ? ? String cx=words[1];?
? ? ? ? ? ? dict.put(word, cx);
? ? ? ? }?
? ? ? ? br.close();
? ? }
? ??
? ? public String MM_Seg() throws IOException
? ? {//正向最大匹配算法
? ? ? ? ReadDic();//讀入字典
? ? ? ? segstring=segstring.replaceAll(" ", "");
? ? ? ? MM(segstring,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);
? ? ? ? else
? ? ? ? ? ? curstr=str.substring(frompos,frompos+len);
? ? ? ? ? ??
? ? ? ? if(dict.containsKey(curstr))
? ? ? ? {
? ? ? ? ? ? result=result+curstr+"/ ";
? ? ? ? ? ? Len=MaxLen;
? ? ? ? ? ? indexpos=frompos+len;
? ? ? ? ? ? MM(str,Len,indexpos);
? ? ? ? }
? ? ? ? else
? ? ? ? {
? ? ? ? ? ? if(Len>1)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? Len=Len-1;
? ? ? ? ? ? ? ? MM(str,Len,frompos);
? ? ? ? ? ? }
? ? ? ? ? ? else
? ? ? ? ? ? {
? ? ? ? ? ? ? ? result=result+str+"/ ";
? ? ? ? ? ? ? ? frompos=frompos+1;
? ? ? ? ? ? ? ? Len=MaxLen;
? ? ? ? ? ? ? ? MM(str,Len,frompos);
? ? ? ? ? ? }
? ? ? ? }
? ? }
? ??
? ??
? ? public String getResult()
? ? {
? ? ? ? return result;
? ? }
? ? ? ? ? ??
? ? public static void main(String[] args) throws IOException, Exception
? ? {
? ? ? ? seg s=new seg("一把青菜勤奮勤政勤勤儉節約奇鳥怪物節",3);
? ? ? ? String result=s.MM_Seg();
? ? ? ? System.out.println(result);
? ? ? ??
? ? }
? ? ? ? ? ??
? ??
}
逆向
/*
?* 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;
/**
?*
?* @author shelly
?*/
public class RMM {
? ? String result;
? ? String segstring;
? ? int MaxLen;
? ? int Len;
? ? int indexpos;
? ? Map <String,String> dict; //<"石柱",n>
? ? public RMM(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=words[0];
? ? ? ? ? ? String cx=words[1];
? ? ? ? ? ? dict.put(word, cx);
? ? ? ? }
? ? ? ? br.close();
? ? }
? ? public String RMM_Seg() throws IOException
? ? {//反向最大匹配算法
? ? ? ? ReadDic();//讀入字典
// ? ? ? ?segstring=segstring.trim();
? ? ? ? segstring=segstring.replaceAll(" ", "");
? ? ? ? MM(segstring,MaxLen,segstring.length()-1);//反向最大分詞
? ? ? ? return result;
? ? }
? ? public void MM(String str,int len,int frompos)
? ? {
? ? ? ? if(frompos<0)
? ? ? ? ? ? return;
? ? ? ? String curstr="";
? ? ? ? int llen=frompos+1-len;
? ? ? ? if(llen>=0)
? ? ? ? ? ? curstr=str.substring(frompos-len+1,frompos+1);
? ? ? ? else
? ? ? ? ? ? curstr=str.substring(0,frompos+1);
? ? ? ? if(dict.containsKey(curstr))
? ? ? ? {
? ? ? ? ? ? result=curstr+"/ "+result;
? ? ? ? ? ? Len=MaxLen;
? ? ? ? ? ? indexpos=frompos-len;
? ? ? ? ? ? MM(str,Len,indexpos);
? ? ? ? }
? ? ? ? else
? ? ? ? {
? ? ? ? ? ? if(Len>1)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? Len=Len-1;
? ? ? ? ? ? ? ? MM(str,Len,frompos);
? ? ? ? ? ? }
? ? ? ? ? ? else
? ? ? ? ? ? {
? ? ? ? ? ? ? ? result=result+str+"/ ";
? ? ? ? ? ? ? ? frompos=frompos-1;
? ? ? ? ? ? ? ? Len=MaxLen;
? ? ? ? ? ? ? ? MM(str,Len,frompos);
? ? ? ? ? ? }
? ? ? ? }
? ? }
? ? public String getResult()
? ? {
? ? ? ? return result;
? ? }
? ? public static void main(String[] args) throws IOException, Exception
? ? {
? ? ? ? RMM rm=new RMM("一你是的 ? ? ? ? ? ? 是打多 ? ? ? ?分艾菲奧德賽",3);
? ? ? ? String result=rm.RMM_Seg();
? ? ? ? System.out.println(result);
? ? }
}
UI界面代碼
import javafx.application.Application;
import javafx.geometry.Insets;
import javafx.geometry.Pos;
import javafx.scene.Scene;
import javafx.scene.control.Button;
import javafx.scene.control.TextArea;
import javafx.scene.control.TextField;
import javafx.scene.layout.BorderPane;
import javafx.scene.layout.HBox;
import javafx.scene.layout.VBox;
import javafx.stage.Stage;
import java.io.IOException;
public class ui extends Application {
? ? private Button zheng=new Button("正向匹配");
? ? private Button ni=new Button("逆向匹配");
? ? private TextField time = new TextField();
? ? private TextField time1 = new TextField();
? ? private TextArea tffen = new TextArea();
? ? private TextArea tfconsult = new TextArea();
? ? private TextArea tfconsultni = new TextArea();
? ? public static void main(String[] args) {
? ? ? ? launch(args);
? ? }
? ? @Override
? ? public void start(Stage primaryStage) {
? ? ? ? tffen.setWrapText(true);
? ? ? ? tfconsult.setWrapText(true);
? ? ? ? tfconsultni.setWrapText(true);
? ? ? ? BorderPane mainpane = new BorderPane();
? ? ? ? HBox hBox = new HBox();
? ? ? ? hBox.setSpacing(30);
? ? ? ? hBox.setAlignment(Pos.CENTER);
? ? ? ? hBox.getChildren().addAll(zheng,time);
? ? ? ? HBox hBox1 = new HBox();
? ? ? ? hBox1.setSpacing(30);
? ? ? ? hBox1.setAlignment(Pos.CENTER);
? ? ? ? hBox1.getChildren().addAll(ni,time1);
? ? ? ? VBox vBox = new VBox();
? ? ? ? vBox.setSpacing(5);
? ? ? ? vBox.setPadding(new Insets(10,20,10,20));
? ? ? ? vBox.getChildren().addAll(tffen,hBox,tfconsult,hBox1,tfconsultni);
? ? ? ? mainpane.setCenter(vBox);
? ? ? ? Scene scene = new Scene(mainpane,500,500);
? ? ? ? primaryStage.setScene(scene);
? ? ? ? primaryStage.show();
? ? ? ? zheng.setOnAction(event -> {
? ? ? ? ? ? tfconsult.clear();
? ? ? ? ? ? time.clear();
? ? ? ? ? ? String msg = tffen.getText();
? ? ? ? ? ? seg se = new seg(msg,4);
? ? ? ? ? ? try {
? ? ? ? ? ? ? ? long startTime = System.currentTimeMillis();
? ? ? ? ? ? ? ? String re = se.MM_Seg();
? ? ? ? ? ? ? ? long endTime = System.currentTimeMillis();
? ? ? ? ? ? ? ? time.appendText(String.valueOf(endTime-startTime)+"ms");
? ? ? ? ? ? ? ? tfconsult.appendText(re);
? ? ? ? ? ? } catch (IOException e) {
? ? ? ? ? ? ? ? e.printStackTrace();
? ? ? ? ? ? }
? ? ? ? });
? ? ? ? ni.setOnAction(event -> {
? ? ? ? ? ? tfconsultni.clear();
? ? ? ? ? ? time1.clear();
? ? ? ? ? ? String msg = tffen.getText();
? ? ? ? ? ? RMM rm = new RMM(msg,4);
? ? ? ? ? ? try {
? ? ? ? ? ? ? ? long startTime = System.currentTimeMillis();
? ? ? ? ? ? ? ? String re = rm.RMM_Seg();
? ? ? ? ? ? ? ? long endTime = System.currentTimeMillis();
? ? ? ? ? ? ? ? time1.appendText(String.valueOf(endTime-startTime)+"ms");
? ? ? ? ? ? ? ? tfconsultni.appendText(re);
? ? ? ? ? ? } catch (IOException e) {
? ? ? ? ? ? ? ? e.printStackTrace();
? ? ? ? ? ? }
? ? ? ? });
? ? }
}
?
總結
以上是生活随笔為你收集整理的双向最大匹配算法（含完整代码实现，ui界面）正向最大匹配算法，逆向最大匹配算法的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 单链表倒数第K个节点的查找和显示
- 下一篇： 逆向最大匹配分词算法