分詞算法(Segmentation Method)

在文本處理流程中，對(duì)語(yǔ)句進(jìn)行分詞（Segmentation）操作對(duì)于計(jì)算機(jī)認(rèn)識(shí)并理解人類語(yǔ)言是基礎(chǔ)且重要的。

對(duì)于中文來(lái)講，不同于英文直接采用空格符進(jìn)行分隔，并且中文詞語(yǔ)內(nèi)涵豐厚，語(yǔ)義豐富，所以只有采用合適的分詞算法，才能準(zhǔn)確迅速地向計(jì)算機(jī)表達(dá)原有的意思，提高工作效率。

最大匹配算法(Maximum Matching)

最大匹配算法是基于詞表進(jìn)行分詞操作的，主要包括正向正向最大匹配算法、逆向最大匹配算法、雙向最大匹配算法等。 其主要原理都是切分出單字串(詞語(yǔ))，然后和詞庫(kù)進(jìn)行比對(duì)，如果對(duì)比成功就記錄下來(lái)，從整句切除下來(lái)， 否則減少一個(gè)單字，繼續(xù)比較，直到字符串全部切除完畢，即分詞成功，數(shù)組中的所有詞語(yǔ)即是分詞結(jié)果。

以下詳細(xì)介紹算法的主要思想及具體代碼實(shí)現(xiàn)。

需要的前提

進(jìn)行匹配算法的執(zhí)行前，一定自己要設(shè)定一個(gè)字典庫(kù)，通常作為測(cè)試即可。
這里我自己使用
字典庫(kù)

ch_dict = [‘我們’,‘經(jīng)?！?‘有’,‘有意見(jiàn)’,‘意見(jiàn)’,‘分歧’]

測(cè)試語(yǔ)句

sentence = ‘我們經(jīng)常有意見(jiàn)分歧’

最大匹配值

max_match_len = 5

正向最大匹配算法(Forwards Maximum Match，F(xiàn)MM)

算法主要思想

從字符串的正方向出發(fā)，先截取前5個(gè)字符，與詞典庫(kù)中的詞語(yǔ)進(jìn)行對(duì)比。若比對(duì)不成功，則截取前4個(gè)字符進(jìn)行對(duì)比，依次類推，直到僅剩第一個(gè)字符，自動(dòng)進(jìn)行截取，此次截取結(jié)束；若對(duì)比成功，則將該詞語(yǔ)記錄下來(lái)，并從句子中截取下來(lái)。直至句子全部被拆分為詞語(yǔ)，以數(shù)組進(jìn)行存儲(chǔ)。

算法思想示意圖

具體代碼實(shí)現(xiàn)

'''
(分詞算法)正向最大匹配算法
'''
if __name__ == '__main__':

    ch_dict = ['我們','經(jīng)常','有','有意見(jiàn)','意見(jiàn)','分歧']       #中文的詞典庫(kù)，用于匹配句子中的詞語(yǔ)
    sentence = '我們經(jīng)常有意見(jiàn)分歧'          #例句，需要進(jìn)行分詞
    segment_list = []                      #存放分詞后的分詞詞組

    #例句不為空時(shí)，循環(huán)地進(jìn)行分詞操作
    while len(sentence) >= 1:
        # 最大匹配單詞的長(zhǎng)度為5，當(dāng)然實(shí)際意義從3開始即可，因?yàn)樵~典最大單詞長(zhǎng)度為3
        max_match_len = 5
        #當(dāng)匹配單詞長(zhǎng)度大于1時(shí)，循環(huán)判斷分詞
        while max_match_len > 1:

            #判斷前 max_match_len 個(gè)字符是否存在于字典
            if sentence[0:max_match_len] in ch_dict:
                segment_list.append(sentence[0:max_match_len])              #追加到分詞詞組中
                sentence = sentence[max_match_len:len(sentence)]            #將符合的詞語(yǔ)從原例句中截取
                break                   #退出循環(huán)，重新從max_match_len最長(zhǎng)匹配數(shù)開始匹配截取

            max_match_len -= 1          #max_match_len累減，開始匹配4個(gè)字符，3個(gè)字符，，，

        #只剩下一個(gè)漢字時(shí)，說(shuō)明當(dāng)前不再存在任何符合的詞語(yǔ)，直接截取一個(gè)漢字作為詞組
        if max_match_len == 1:
            segment_list.append(sentence[0:1])          #追加單個(gè)漢字詞語(yǔ)
            sentence = sentence[1:len(sentence)]        #截取例句

	#輸出存放分詞的列表
    print(segment_list)
    #輸出進(jìn)行分詞后的例句
    print('/'.join(segment_list))               #我們/經(jīng)常/有意見(jiàn)/分歧

運(yùn)行結(jié)果

['我們', '經(jīng)常', '有意見(jiàn)', '分歧']
我們/經(jīng)常/有意見(jiàn)/分歧

Process finished with exit code 0

逆向最大匹配算法(Reverse Maximum Match，RMM)

算法主要思想

剛好與正向最大匹配算法相反，該算法旨在從句子末尾對(duì)句子進(jìn)行分詞操作，基本原理同正向最大匹配算法。

算法思想示意圖

具體代碼實(shí)現(xiàn)

'''
(分詞算法)后向最大匹配算法
'''

if __name__ == '__main__':

    ch_dict = ['我們','經(jīng)常','有','有意見(jiàn)','意見(jiàn)','分歧']       #中文的詞典庫(kù)，用于匹配句子中的詞語(yǔ)
    sentence = '我們經(jīng)常有意見(jiàn)分歧'          #例句，需要進(jìn)行分詞
    segment_list = []                      #存放分詞后的分詞詞組

    #例句不為空時(shí)，循環(huán)地進(jìn)行分詞操作
    while len(sentence) >= 1:
        # 最大匹配單詞的長(zhǎng)度為5，當(dāng)然實(shí)際意義從3開始即可，因?yàn)樵~典最大單詞長(zhǎng)度為3
        max_match_len = 5
        #當(dāng)匹配單詞長(zhǎng)度大于1時(shí)，循環(huán)判斷分詞
        while max_match_len > 1:

            #判斷前 max_match_len 個(gè)字符是否存在于字典
            if sentence[-max_match_len:] in ch_dict:
                segment_list.append(sentence[-max_match_len:])              #追加到分詞詞組中
                sentence = sentence[:-max_match_len]            #將符合的詞語(yǔ)從原例句中截取
                break                   #退出循環(huán)，重新從max_match_len最長(zhǎng)匹配數(shù)開始匹配截取

            max_match_len -= 1          #max_match_len累減，開始匹配4個(gè)字符，3個(gè)字符，，，

        #只剩下一個(gè)漢字時(shí)，說(shuō)明當(dāng)前不再存在任何符合的詞語(yǔ)，直接截取一個(gè)漢字作為詞組
        if max_match_len == 1:
            segment_list.append(sentence[-1:])          #追加單個(gè)漢字詞語(yǔ)
            sentence = sentence[:-1]                    #截取例句

    # 輸出進(jìn)行分詞后的例句
    print('/'.join(segment_list))               #分歧/有意見(jiàn)/經(jīng)常/我們

    #對(duì)分詞列表進(jìn)行倒序
    segment_list = segment_list[::-1]
    #再次輸出進(jìn)行分詞后的例句
    print('/'.join(segment_list))               # 我們/經(jīng)常/有意見(jiàn)/分歧

運(yùn)行結(jié)果

分歧/有意見(jiàn)/經(jīng)常/我們
我們/經(jīng)常/有意見(jiàn)/分歧

Process finished with exit code 0

雙向最大匹配算法

算法的主要思想

雙向最大匹配算法是同時(shí)采用正向最大匹配算法和逆向最大匹配算法，根據(jù)對(duì)比不同的執(zhí)行結(jié)果，選擇最優(yōu)解。

有以下幾種選擇方案：

1. 如果分詞數(shù)量結(jié)果不同：選擇數(shù)量較少的那個(gè)。
2. 如果分詞數(shù)量結(jié)果相同。
   A. 分詞結(jié)果相同，返回任意一個(gè)。
   B. 分詞結(jié)果不同，返回單個(gè)字?jǐn)?shù)較少的一個(gè)。
   C. 若單個(gè)字?jǐn)?shù)也相同，任意返回一個(gè)。

小結(jié)

最大匹配算法在簡(jiǎn)單場(chǎng)景往往能夠發(fā)揮出較好的分詞效果，但其算法的時(shí)間復(fù)雜度較高，理解中文歧義問(wèn)題不夠準(zhǔn)確，故存在一定的局限性，僅作為低級(jí)的分詞算法使用。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-843265.html

到了這里，關(guān)于分詞算法----正向和逆向最大匹配算法(含Python代碼實(shí)現(xiàn))的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！