Python自然語言處理之切分算法詳解

一、前言

我們需要分析某句話,就必須檢測該條語句中的詞語。

一般來說,一句話肯定包含多個詞語,它們互相重疊,具體輸出哪一個由自然語言的切分算法決定。常用的切分算法有完全切分、正向最長匹配、逆向最長匹配以及雙向最長匹配。

本篇博文將一一介紹這些常用的切分算法。

二、完全切分

完全切分是指,找出一段文本中的所有單詞。

不考慮效率的話,完全切分算法其實非常簡單。隻要遍歷文本中的連續序列,查詢該序列是否在詞典中即可。上一篇我們獲取瞭詞典的所有詞語dic,這裡我們直接用代碼遍歷某段文本,完全切分出所有的詞語。代碼如下:

from pyhanlp import *


def load_dictionary():
    IOUtil = JClass('com.hankcs.hanlp.corpus.io.IOUtil')
    path = HanLP.Config.CoreDictionaryPath.replace('.txt', '.mini.txt')
    dic = IOUtil.loadDictionary([path])
    return set(dic.keySet())


def fully_segment(text, dic):
    list = []
    for i in range(len(text)):
        for j in range(i + 1, len(text) + 1):
            temp = text[i:j]
            if temp in dic:
                list.append(temp)
    return list


if __name__ == "__main__":
    dic = load_dictionary()
    print(fully_segment("在絕對實力面前,一切的說辭都是枉然", dic))

詞匯

可以看到,完全切分算法輸出瞭文本中所有的單字與詞匯。
這裡的算法原理是:開始遍歷單個字,以該字為首,將後面每個字依次組合到單個字中,分析出這些組合字句是否在詞典中。第二次,從第二個字開始,組合後面的字,以此類推。不懂的看下圖就明白瞭。

遍歷

三、正向最長匹配

雖然說完全切分能獲取到所有出現在字典中的單詞,單字,但是我們獲取語句中單字一般來說沒有任何意義,我們更希望獲取的是中文分詞,那種具有意義的詞語序列。

比如,上面我們希望“絕對實力”成為一整個詞,而不是“絕對”+“實力”之類的碎片。為瞭達到這個目的,我們需要完善一下我們的算法。考慮到越長的單詞表達的意義更加的豐富,於是我們定義單詞越長優先級越高。

具體來說,就是在某個下標為起點遞增查詞的過程中,優先輸出更長的單詞,這種規則被稱為最長匹配算法。該下標的掃描順序如果從前往後,則稱為正向最長匹配,反之則為逆向最長匹配。

下面,我們來實現正向最長匹配,代碼如下:

def forward_segment(text, dic):
    list = []
    i = 0
    while i < len(text):
        long_word = text[i]
        for j in range(i + 1, len(text) + 1):
            word = text[i:j]
            if word in dic:
                if len(word) > len(long_word):
                    long_word = word
        list.append(long_word)
        i += len(long_word)
    return list

算法的原理:首先通過while循環判斷i是否超出瞭字符串的大小,如果沒有,獲取當前第一個字符串為第一個最長匹配結果,接著遍歷第一個字符串的所有可能組合結尾,如果在字典中,判斷當前詞語是否大於前面的最長匹配結果,如果是替換掉最長。遍歷完成之後,將最長的結果添加到列表中,然後再獲取第二字符,遍歷所有結尾組合,獲取最長匹配。以此類推。

四、逆向最長匹配

既然瞭解瞭正向如何匹配,那麼逆向算法應該也很好寫。代碼如下:

def backward_segment(text, dic):
    list = []
    i = len(text) - 1
    while i >= 0:
        long_word = text[i]
        for j in range(0, i):
            word = text[j:i + 1]
            if word in dic:
                if len(word) > len(long_word):
                    long_word = word
                    break
        list.append(long_word)
        i -= len(long_word)
    return list

算法的原理:就是上面的正向反過來,但是這裡並不是倒推文字,文字還是按語句的順序,但是長度是從最長到最短,也就是遇到第一個就可以返回瞭添加瞭。比正向最長匹配算法節約時間。

五、雙向最長匹配

雖然逆向比正向節約時間,但本身有一個很大的漏洞。假如我現在的句子中有一段“項目的”字符串,那麼正向會出現“項目”,“的”兩個詞匯,而逆向會出現:“項”,“目的”兩個詞匯。

為此,我們的算法工程師提出瞭新的匹配規則,雙向最長匹配。這是一種融合兩種匹配方法的復雜規則,流程如下:

同時執行正向和逆向最長匹配,若兩者的詞數不同,則返回詞數更少的一個否則,返回兩者中單字更少的那一個。當單字也相同時,優先返回逆向最長匹配結果

具體代碼如下:

#統計單字個數
def count_single_char(list):
    return sum(1 for word in list if len(word) == 1)

#雙向匹配算法
def bidirectional_segment():
    f = forward_segment("在絕對實力面前,一切的說辭都是枉然", dic)
    b = backward_segment("在絕對實力面前,一切的說辭都是枉然", dic)
    if len(f) < len(b):
        return f
    elif len(f) > len(b):
        return b
    else:
        if count_single_char(f)<count_single_char(b):
            return f
        else:
            return b

到此這篇關於Python自然語言處理之切分算法詳解的文章就介紹到這瞭,更多相關python切分算法內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!

推薦閱讀: