筆記轉(zhuǎn)載于GitHub項目：https://github.com/NLP-LOVE/Introduction-NLP

2. 詞典分詞

• 中文分詞：指的是將一段文本拆分為一系列單詞的過程，這些單詞順序拼接后等于原文本。
• 中文分詞算法大致分為基于詞典規(guī)則與基于機器學(xué)習(xí)這兩大派。

2.1 什么是詞

• 在基于詞典的中文分詞中，詞的定義要現(xiàn)實得多：詞典中的字符串就是詞。

• 詞的性質(zhì)--齊夫定律：一個單詞的詞頻與它的詞頻排名成反比。

  image

2.2 詞典

互聯(lián)網(wǎng)詞庫(SogouW， 15萬個詞條)、清華大學(xué)開放中文詞庫(THUOCL)、HanLP詞庫(千萬級詞條)

這里以HanLP附帶的迷你核心詞典為例(本項目路徑)：data/dictionnary/CoreNatureDictionary.mini.txt

上升  v   98  vn  18
上升期 n   1
上升股 n   1
上午  t   147
上半葉 t   3
上半場 n   2
上半夜 t   1

HanLP中的詞典格式是一種以空格分隔的表格形式，第一列是單詞本身，之后每兩列分別表示詞性與相應(yīng)的詞頻。

2.3 切分算法

首先，加載詞典：

def load_dictionary():
    dic = set()

    # 按行讀取字典文件，每行第一個空格之前的字符串提取出來。
    for line in open("CoreNatureDictionary.mini.txt","r"):
        dic.add(line[0:line.find('  ')])
    
    return dic

1. 完全切分

   指的是，找出一段文本中的所有單詞。

   def fully_segment(text, dic):
       word_list = []
       for i in range(len(text)):                  # i 從 0 到text的最后一個字的下標(biāo)遍歷
           for j in range(i + 1, len(text) + 1):   # j 遍歷[i + 1, len(text)]區(qū)間
               word = text[i:j]                    # 取出連續(xù)區(qū)間[i, j]對應(yīng)的字符串
               if word in dic:                     # 如果在詞典中，則認(rèn)為是一個詞
                   word_list.append(word)
       return word_list
     
   dic = load_dictionary()
   print(fully_segment('就讀北京大學(xué)', dic))
   

   輸出：

   ['就', '就讀', '讀', '北', '北京', '北京大學(xué)', '京', '大', '大學(xué)', '學(xué)']
   

   輸出了所有可能的單詞。由于詞庫中含有單字，所以結(jié)果中也出現(xiàn)了一些單字。

2. 正向最長匹配

   上面的輸出并不是中文分詞，我們更需要那種有意義的詞語序列，而不是所有出現(xiàn)在詞典中的單詞所構(gòu)成的鏈表。比如，我們希望“北京大學(xué)”成為一整個詞，而不是“北京 + 大學(xué)”之類的碎片。具體來說，就是在以某個下標(biāo)為起點遞增查詞的過程中，優(yōu)先輸出更長的單詞，這種規(guī)則被稱為最長匹配算法。從前往后匹配則稱為正向最長匹配，反之則稱為逆向最長匹配。

   def forward_segment(text, dic):
       word_list = []
       i = 0
       while i < len(text):
           longest_word = text[i]                      # 當(dāng)前掃描位置的單字
           for j in range(i + 1, len(text) + 1):       # 所有可能的結(jié)尾
               word = text[i:j]                        # 從當(dāng)前位置到結(jié)尾的連續(xù)字符串
               if word in dic:                         # 在詞典中
                   if len(word) > len(longest_word):   # 并且更長
                       longest_word = word             # 則更優(yōu)先輸出
           word_list.append(longest_word)              # 輸出最長詞
           i += len(longest_word)                      # 正向掃描
       return word_list
   
   dic = load_dictionary()
   print(forward_segment('就讀北京大學(xué)', dic))
   print(forward_segment('研究生命起源', dic))
   

   輸出：

   ['就讀', '北京大學(xué)']
   ['研究生', '命', '起源']
   

   第二句話就會產(chǎn)生誤差了，我們是需要把“研究”提取出來，結(jié)果按照正向最長匹配算法就提取出了“研究生”，所以人們就想出了逆向最長匹配。

3. 逆向最長匹配

   def backward_segment(text, dic):
       word_list = []
       i = len(text) - 1
       while i >= 0:                                   # 掃描位置作為終點
           longest_word = text[i]                      # 掃描位置的單字
           for j in range(0, i):                       # 遍歷[0, i]區(qū)間作為待查詢詞語的起點
               word = text[j: i + 1]                   # 取出[j, i]區(qū)間作為待查詢單詞
               if word in dic:
                   if len(word) > len(longest_word):   # 越長優(yōu)先級越高
                       longest_word = word
                       break
           word_list.insert(0, longest_word)           # 逆向掃描，所以越先查出的單詞在位置上越靠后
           i -= len(longest_word)
       return word_list
   
   dic = load_dictionary()
   print(backward_segment('研究生命起源', dic))
   print(backward_segment('項目的研究', dic))
   

   輸出：

   ['研究', '生命', '起源']
   ['項', '目的', '研究']
   

   第一句正確了，但下一句又出錯了，可謂拆東墻補西墻。另一些人提出綜合兩種規(guī)則，期待它們?nèi)￠L補短，稱為雙向最長匹配。

4. 雙向最長匹配

   這是一種融合兩種匹配方法的復(fù)雜規(guī)則集，流程如下：

   • 同時執(zhí)行正向和逆向最長匹配，若兩者的詞數(shù)不同，則返回詞數(shù)更少的那一個。
   • 否則，返回兩者中單字更少的那一個。當(dāng)單字?jǐn)?shù)也相同時，優(yōu)先返回逆向最長匹配的結(jié)果。

   def count_single_char(word_list: list):  # 統(tǒng)計單字成詞的個數(shù)
       return sum(1 for word in word_list if len(word) == 1)
   
   
   def bidirectional_segment(text, dic):
       f = forward_segment(text, dic)
       b = backward_segment(text, dic)
       if len(f) < len(b):                                  # 詞數(shù)更少優(yōu)先級更高
           return f
       elif len(f) > len(b):
           return b
       else:
           if count_single_char(f) < count_single_char(b):  # 單字更少優(yōu)先級更高
               return f
           else:
               return b                                     # 都相等時逆向匹配優(yōu)先級更高
           
   
   print(bidirectional_segment('研究生命起源', dic))
   print(bidirectional_segment('項目的研究', dic))
   

   輸出：

   ['研究', '生命', '起源']
   ['項', '目的', '研究']
   

通過以上幾種切分算法，我們可以做一個對比：

image

上圖顯示，雙向最長匹配的確在2、3、5這3種情況下選擇出了最好的結(jié)果，但在4號句子上選擇了錯誤的結(jié)果，使得最終正確率 3/6 反而小于逆向最長匹配的 4/6 ， 由此，規(guī)則系統(tǒng)的脆弱可見一斑。規(guī)則集的維護有時是拆東墻補西墻，有時是幫倒忙。

2.4 字典樹

匹配算法的瓶頸之一在于如何判斷集合(詞典)中是否含有字符串。如果用有序集合TreeMap)的話，復(fù)雜度是o(logn) ( n是詞典大小);如果用散列表( Java的HashMap. Python的dict )的話，賬面上的時間復(fù)雜度雖然下降了，但內(nèi)存復(fù)雜度卻上去了。有沒有速度又快、內(nèi)存又省的數(shù)據(jù)結(jié)構(gòu)呢？這就是字典樹。

1. 什么是字典樹

   字符串集合常用宇典樹(trie樹、前綴樹)存儲，這是一種字符串上的樹形數(shù)據(jù)結(jié)構(gòu)。字典樹中每條邊都對應(yīng)一個字， 從根節(jié)點往下的路徑構(gòu)成一個個字符串。字典樹并不直接在節(jié)點上存儲字符串， 而是將詞語視作根節(jié)點到某節(jié)點之間的一條路徑，并在終點節(jié)點(藍色) 上做個標(biāo)記“該節(jié)點對應(yīng)詞語的結(jié)尾”。字符串就是一 條路徑，要查詢一個單詞，只需順著這條路徑從根節(jié)點往下走。如果能走到特殊標(biāo)記的節(jié)點，則說明該字符串在集合中，否則說明不存在。一個典型的字典樹如下圖所示所示。

   image

   其中，藍色標(biāo)記著該節(jié)點是一個詞的結(jié)尾，數(shù)字是人為的編號。按照路徑我們可以得到如下表所示：

   詞語	路徑
   入門	0-1-2
   自然	0-3-4
   自然人	0-3-4-5
   自然語言	0-3-4-6-7
   自語	0-3-8

   當(dāng)詞典大小為 n 時，雖然最壞情況下字典樹的復(fù)雜度依然是O(logn) (假設(shè)子節(jié)點用對數(shù)復(fù)雜度的數(shù)據(jù)結(jié)構(gòu)存儲，所有詞語都是單字)，但它的實際速度比二分查找快。這是因為隨著路徑的深入，前綴匹配是遞進的過程，算法不必比較字符串的前綴。

2. 字典樹的實現(xiàn)

   由上圖可知，每個節(jié)點都應(yīng)該至少知道自己的子節(jié)點與對應(yīng)的邊，以及自己是否對應(yīng)一個詞。如果要實現(xiàn)映射而不是集合的話，還需要知道自己對應(yīng)的值。我們約定用值為None表示節(jié)點不對應(yīng)詞語，雖然這樣就不能插人值為None的鍵了，但實現(xiàn)起來更簡潔。那么字典樹的實現(xiàn)參見項目路徑(與書上略有不同，我寫的比較簡潔)：code/ch02/trie.py

   通過debug運行 trie.py 代碼，可以觀察到 trie 類的字典樹結(jié)構(gòu)：

   image

2.5 基于字典樹的其它算法

字典樹的數(shù)據(jù)結(jié)構(gòu)在以上的切分算法中已經(jīng)很快了，但厲害的是作者通過自己的努力改進了基于字典樹的算法，把分詞速度推向了千萬字每秒的級別，這里不一一詳細(xì)介紹，詳情見書，主要按照以下遞進關(guān)系優(yōu)化：

• 首字散列其余二分的字典樹
• 雙數(shù)組字典樹
• AC自動機(多模式匹配)
• 基于雙數(shù)組字典樹的AC自動機

2.6 HanLP的詞典分詞實現(xiàn)

1. DoubleArrayTrieSegment

   DoubleArrayTrieSegment分詞器是對DAT最長匹配的封裝，默認(rèn)加載hanlp.properties中CoreDictionaryPath制定的詞典。

   from pyhanlp import *
   
   # 不顯示詞性
   HanLP.Config.ShowTermNature = False
   
   # 可傳入自定義字典 [dir1, dir2]
   segment = DoubleArrayTrieSegment()
   # 激活數(shù)字和英文識別
   segment.enablePartOfSpeechTagging(True)
   
   print(segment.seg("江西鄱陽湖干枯，中國最大淡水湖變成大草原"))
   print(segment.seg("上海市虹口區(qū)大連西路550號SISU"))
   

   輸出：

   [江西, 鄱陽湖, 干枯, ，, 中國, 最大, 淡水湖, 變成, 大草原]
   [上海市, 虹口區(qū), 大連, 西路, 550, 號, SISU]
   

2. 去掉停用詞

   停用詞詞典文件：data/dictionnary/stopwords.txt

   該詞典收錄了常見的中英文無意義詞匯(不含敏感詞)，每行一個詞。

   def load_from_file(path):
       """
       從詞典文件加載DoubleArrayTrie
       :param path: 詞典路徑
       :return: 雙數(shù)組trie樹
       """
       map = JClass('java.util.TreeMap')()  # 創(chuàng)建TreeMap實例
       with open(path) as src:
           for word in src:
               word = word.strip()  # 去掉Python讀入的\n
               map[word] = word
       return JClass('com.hankcs.hanlp.collection.trie.DoubleArrayTrie')(map)
   
   
   ## 去掉停用詞
   def remove_stopwords_termlist(termlist, trie):
       return [term.word for term in termlist if not trie.containsKey(term.word)]
   
   
   trie = load_from_file('stopwords.txt')
   termlist = segment.seg("江西鄱陽湖干枯了，中國最大的淡水湖變成了大草原")
   print('去掉停用詞前：', termlist)
   
   print('去掉停用詞后：', remove_stopwords_termlist(termlist, trie))
   

   輸出：

   去掉停用詞前： [江西, 鄱陽湖, 干枯, 了, ，, 中國, 最大, 的, 淡水湖, 變成, 了, 大草原]
   去掉停用詞后： ['江西', '鄱陽湖', '干枯', '中國', '最大', '淡水湖', '變成', '大草原']
   

2.7 GitHub項目

HanLP何晗--《自然語言處理入門》筆記：

https://github.com/NLP-LOVE/Introduction-NLP

項目持續(xù)更新中......

目錄