雙向最大比對算法——基于詞典規則的中文分詞(Java實作)

這篇将使用Java實作基于規則的中文分詞算法，一個中文詞典将實作準确率高達85%的分詞結果。經典算法：正向最大比對和反向最大比對算法，然後雙劍合璧，雙向最大比對。

一、中文分詞理論描述

二、算法描述

1、正向最大比對算法

2、反向最大比對算法

3、雙劍合璧

三、案例描述

四、JAVA實作完整代碼

五、組裝UI

六、總結

前言

這篇将使用Java實作基于規則的中文分詞算法，一個中文詞典将實作準确率高達85%的分詞結果。使用經典算法：正向最大比對和反向最大比對算法，然後雙劍合璧，雙向最大比對。

一、中文分詞理論描述

根據相關資料，中文分詞概念的理論描述，我總結如下：

中文分詞是将一個漢字序列切分成一個一個單獨的詞，将連續的字序列按照一定的規範重新組合成詞序列的過程，把字與字連在一起的漢語句子分成若幹個互相獨立、完整、正确的單詞，詞是最小的、能獨立活動的、有意義的語言成分。

中文分詞應用廣泛，是文本挖掘的基礎，在中文文本進行中意義重大，對于輸入的一段中文，成功的進行中文分詞，可以達到電腦自動識别語句含義的效果。目前，常用流行的以及分次效果好的工具庫包括：jieba、HanLP、LTP、FudanNLP等。

我們知道，調用工具友善容易，但是如果自己實作寫一個算法實作，那不是更加有成就感^_^。

接下來将一步步介紹最容易了解，最簡單，效果還很不錯的中文分詞算法，據說準确率能達到85%！！

二、算法描述

1、正向最大比對算法

所謂正向，就是從文本串左邊正向掃描，取出子串與詞典進行比對。

算法我分為兩步來了解：

假設初始化取最大比對長度為MaxLen，目前位置pos=0，處理結果result=””，每次取詞str，取詞長度len，待處理串segstr。

len=MaxLen，取字元串0到len的子串，查找詞典，若比對到則指派str，加到result，在保證pos+len<=segstr.length()情況下，pos=pos+len,向後比對，直到字元串掃描完成，結束算法。
若詞典未找到，若len>1,減小比對長度同時len=MaxLen-1,執行步驟（1），否則，取出剩餘子串,執行步驟（1）。

算法代碼如下：

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);//substring擷取的子串是下标frompos~frompos+llen-1
        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;
            } else {
                result = result + str + "/ ";
                frompos = frompos + 1;
                Len = MaxLen;
            }
            MM(str, Len, frompos);
        }
    }

從算法代碼看出，很容易了解，細節部分在于邊界處理。

測試一下，我輸入文本，"我愛自然語言處理，贊賞評論收藏我的文章是我的動力！趕緊關注！"

分詞結果：

2、反向最大比對算法

反向，則與正向相反，從文本串末向左進行掃描。

假設初始化取最大比對長度為MaxLen，目前位置pos為字元串尾部，處理結果result=””，每次取詞str，取詞長度len，待處理串segstr。

len=MaxLen，取字元串pos-len到pos的子串，查找詞典，若比對到則指派str，加到result，同時pos=pos-len,保證pos-len>=0,向前移動比對，直到字元串掃描完成，結束算法。
若詞典未找到，若len>1,減小比對長度同時len=MaxLen-1,執行步驟（1），否則，取出剩餘子串,執行步驟（1）。

算法邏輯類似，取相反方向處理。

public void RMM(String str, int len, int frompos) {
        if (frompos < 0)
            return;
        String curstr = "";
        //此處可以設定斷點
        if (frompos - len + 1 >= 0)//句末邊界處理
            curstr = str.substring(frompos - len + 1, frompos + 1);//substring擷取的子串是下标frompos~frompos+llen-1
        else
            curstr = str.substring(0, frompos + 1);//到達句首
 
        if (dict.containsKey(curstr)) {
            RmmResult = curstr + "/ " + RmmResult;
            Len = MaxLen;
            indexpos = frompos - len;
            RMM(str, Len, indexpos);
        } else {
            if (Len > 1) {
                Len = Len - 1;
            } else {
                RmmResult = RmmResult + str + "/ ";
                frompos = frompos - 1;
                Len = MaxLen;
            }
            RMM(str, Len, frompos);
        }
    }

同樣，細節部分在于邊界處理，其他基本相同。

3、雙劍合璧

這裡所說的是正向與反向結合，實作雙向最大比對。

雙向最大比對算法，基于正向、反向最大比對，對分詞結果進一步處理，比較兩個結果，做的工作就是遵循某些原則和經驗，篩選出兩者中更确切地分詞結果。原則如下：

多數情況下，反向最大比對效果更好，若分詞結果相同，則傳回RMM結果；
遵循切分最少詞原則，更大比對詞為更好地分詞結果，比較之後傳回最少詞的切分結果；
根據切分後詞長度的大小，選擇詞長度大者為最終結果。

具體也需要看開始給定的最大比對長度為多少。以下代碼隻實作了原則（1）、（2）。

public String BMM() throws IOException {
        String Mr = MM_Seg();
        String RMr = RMM_Seg();
        if (Mr.equals(RMr)) {
            return "雙向比對相同，結果為：" + Mr;
        } else {
            List<String> MStr;
            List<String> RStr;
            MStr = Arrays.asList(Mr.trim().split("/"));
            RStr = Arrays.asList(RMr.trim().split("/"));
 
            if (MStr.size() >= RStr.size()) {//多數情況下，反向比對正确率更高
                return "雙向比對不同，最佳結果為：" + RMr;
            } else
                return "雙向比對不同，最佳結果為：" + Mr;
        }
    }

另外，這與使用的詞典大小有關，是否包含常用詞。

三、案例描述

如果上面還不能完全了解，下面的例子可以更好的了解算法執行過程。

正向最大比對算法：

取MaxLen=3，SegStr=”對外經濟技術合作與交流不斷擴大”,maxNum=3,len=3,result=””,pos=0,curstr=””.

第一次，curstr=”對外經”，查找詞典，未找到，将len-1，得到curstr=”對外”，此時比對到詞典，将結果加入result=”對外/ ”.pos=pos+len.

第二次，curstr=”經濟技”，查找詞典，未找到，将len-1，得到curstr=”經濟”，此時比對到詞典，将結果加入result=”對外/ 經濟/ ”.pos=pos+len.

以此類推...

最後一次，邊界，pos=13，因為隻剩下”擴大”兩個字，是以取出全部，查找詞典并比對到，将結果加入result=”對外/ 經濟/ 技術/ 合作/ 與/ 交流/ 不斷/ 擴大/ ”.此時pos+1>SegStr.length(),結束算法。

反向最大比對算法：

取MaxLen=3，SegStr=”對外經濟技術合作與交流不斷擴大”,maxNum=3,len=3,result=””,pos=14,curstr=””.

第一次，curstr=”斷擴大”，查找詞典，未找到，将len-1，得到curstr=”擴大”，此時比對到詞典，将結果加入result=”擴大/ ”.pos=pos-len.

第二次，MaxLen=3，curstr=”流不斷”，查找詞典，未找到，将len-1，得到curstr=”不斷”，此時比對到詞典，将結果加入result=”不斷/ 擴大/ ”.pos=pos-len.

以此類推...

最後一次，邊界，pos=1，因為隻剩下”對外”兩個字，是以取出全部，查找詞典并比對到，将結果加入result=”對外/ 經濟/ 技術/ 合作/ 與/ 交流/ 不斷/ 擴大/ ”.此時pos-1<0,結束算法。

四、JAVA實作完整代碼

除了分詞算法實作，還需要讀入詞典，對詞典進行預處理，具體如下：

雙向最大比對算法——基于詞典規則的中文分詞(Java實作)

package ex1;
 
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
 
public class seg {
 
    String result;
    String RmmResult;
    String segstring;
    int MaxLen;
    int Len;
    int indexpos;
    Map<String, String> dict; 
 
    public seg(String inputstr, int maxlen) {//構造函數
        segstring = inputstr;
        MaxLen = maxlen;
        Len = MaxLen;
        indexpos = 0;
        result = "";
        RmmResult = "";
        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(",");//詞典包含詞性标注，需要将詞與标注分開，放入清單
            String word = words[0];
            String cx = words[1];
            dict.put(word, cx);
        }
        br.close();
    }
 
    public String MM_Seg() throws IOException {//正向最大比對算法
        try {
            ReadDic();//讀入字典
            MM(segstring, MaxLen, 0);//正向最大分詞
            return result;
        } catch (IOException e) {
            return "Read Error!";
        }
    }
 
    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);//substring擷取的子串是下标frompos~frompos+llen-1
        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;
            } else {
                result = result + str + "/ ";
                frompos = frompos + 1;
                Len = MaxLen;
            }
            MM(str, Len, frompos);
        }
    }
 
    public String RMM_Seg() throws IOException {//正向最大比對算法
        try {
            ReadDic();//讀入字典
            RMM(segstring, MaxLen, segstring.length() - 1);//正向最大分詞
            return RmmResult;
        } catch (IOException e) {
            return "Read Error!";
        }
    }
 
    public void RMM(String str, int len, int frompos) {
        if (frompos < 0)
            return;
        String curstr = "";
        //此處可以設定斷點
        if (frompos - len + 1 >= 0)//句末邊界處理
            curstr = str.substring(frompos - len + 1, frompos + 1);//substring擷取的子串是下标frompos~frompos+llen-1
        else
            curstr = str.substring(0, frompos + 1);//到達句首
 
        if (dict.containsKey(curstr)) {
            RmmResult = curstr + "/ " + RmmResult;
            Len = MaxLen;
            indexpos = frompos - len;
            RMM(str, Len, indexpos);
        } else {
            if (Len > 1) {
                Len = Len - 1;
            } else {
                RmmResult = RmmResult + str + "/ ";
                frompos = frompos - 1;
                Len = MaxLen;
            }
            RMM(str, Len, frompos);
        }
    }
 
    public String BMM() throws IOException {
        String Mr = MM_Seg();
        String RMr = RMM_Seg();
        if (Mr.equals(RMr)) {
            return "雙向比對相同，結果為：" + Mr;
        } else {
            List<String> MStr;
            List<String> RStr;
            MStr = Arrays.asList(Mr.trim().split("/"));
            RStr = Arrays.asList(RMr.trim().split("/"));
 
            if (MStr.size() >= RStr.size()) {//多數情況下，反向比對正确率更高
                return "雙向比對不同，最佳結果為：" + RMr;
            } else
                return "雙向比對不同，最佳結果為：" + Mr;
        }
    }
 
    public String getResult() {
        return result;
    }
 
    public static void main(String[] args) throws IOException, Exception {
        seg s = new seg("我愛自然語言處理，贊賞評論收藏我的文章是我的動力！趕緊關注！", 3);
//        String result = s.MM_Seg();
        String result = s.RMM_Seg();
        System.out.println(result);
 
    }
}

View Code

五、組裝UI

我是用的開發軟體為是IDEA，一個友善之處可以拖動元件組裝UI界面。也可以自行寫JavaFX實作簡單布局。

這是簡單頁面的設計：

UI界面可以有更好的使用者體驗，通過UI界面的元素調用方法，減少每次測試運作算法腳本的繁瑣。

實驗示範：

每次可以觀察不同最大比對長度分詞後的結果。

"年中"詞語解析：

在詞典中，是這樣的，可以發現滿足最大比對。

雙向最大比對算法，結果提示：

六、總結

這篇介紹了使用Java實作基于規則的中文分詞算法，使用經典算法：正向最大比對和反向最大比對算法，然後雙劍合璧，雙向最大比對。最後設計簡單UI界面，實作稍微高效的中文分詞處理，結果傳回。

雙向最大比對算法原則，希望句子最長詞保留完整、最短詞數量最少、單字詞問題，目前隻解決了句子切分最少詞問題。
正向反向比對算法可以進一步優化結構，提高執行效率，目前平均耗時20ms。
UI界面增加輸入輸出提示語，友善使用者使用，在正确的區域輸入内容。
将最大比對長度設定為可輸入，實作每次可以觀察不同MaxLen得到的切分結果。
雙向最大比對按鈕點選之後，傳回結果同時傳回MM和RMM結果是否一樣的提示，友善檢視。

我的部落格園：https://www.cnblogs.com/chenzhenhong/p/13748042.html

我的CSDN部落格： https://blog.csdn.net/Charzous/article/details/108817914

本文連結：https://blog.csdn.net/Charzous/article/details/108817914

雙向最大比對算法——基于詞典規則的中文分詞(Java實作)

前言

一、中文分詞理論描述

二、算法描述

1、正向最大比對算法

2、反向最大比對算法

3、雙劍合璧

三、案例描述

四、JAVA實作完整代碼

五、組裝UI

六、總結

繼續閱讀

Surprise：一個Python推薦系統算法庫一、基本子產品二、實作推薦算法

pytorch動态調整學習率之Multistep政策

tensorflow學習——keras進階API——序列模型Sequential

SVD原理和案例(奇異值分解)

連續兩年入圍全球Gartner ABI魔力象限，Quick BI在商業智能領域究竟有何魔力？1、互動式的分析和可視化2、建構資料故事3、釘釘內建4、增強分析Quick BI

技術解密｜阿裡雲多媒體 AI 團隊是憑借什麼拿下 CVPR2021 5冠1亞的？頂級挑戰賽戰績顯赫四大挑戰的關鍵技術探索基于視訊了解技術打造多媒體 AI 雲産品

算法專家解讀 | 開放搜尋教育搜題能力和實踐

Keras使用分批疊代（fit_generate）的方式訓練資料

圖像分割UNet系列------UNet3+（UNet3plus）詳解

圖像分割UNet系列------UNet詳解

特征：什麼是特征和特征選擇？

Pytorch(二) Tensor Tensor的建立Tensor是什麼Tensor的建立

VGGNet------超經典神經網絡結構與PyTorch實作

tensorflow學習——（imdb資料集）文本分類first_2.py

Matlab深度學習-手寫體數字識别Matlab深度學習前言一、MNIST手寫體數字資料二、用到的深度學習架構-LeNet5三、代碼最後

K-近鄰算法以及圖像分類應用