中文分詞的原理與實踐

中文分詞問題是絕大多數中文信息處理的基礎問題，在搜索引擎、推薦系統（尤其是相關主題推薦）、大量文本自動分類等方面，一個好的分詞系統是整個系統成功的關鍵。

主流的分詞思路有三種，分別是“規則分詞”、“統計分詞”和“混合分詞（統計+規則）”，本問會依次介紹到這三種方式。

一、基于規則的分詞

基于規則的思路其實很自然，直白的說其實就是預先設計一個詞典，把待分詞的句子按照某種規則進行切割，切出來的詞如果在詞典里出現，那就算分出來一個詞。

具體到句子的切割方式，主流的有以下三種：

1）正向最大匹配

假設我們現有一個詞典，該詞典中的最長詞的長度為5，這個5就是“正向最大匹配”中的“最大”的含義，這個詞典中存在“長江大橋”和“南京市長”兩個詞。

現在，我們要對“ 南京市長江大橋 ”這個句子進行分詞，根據正向最大匹配的原則：

1. 先從句子中拿出前5個字符“ 南京市長江 ”，把這5個字符到詞典中匹配，發現沒有這個詞，那就縮短取字個數，取前四個“ 南京市長 ”，發現詞庫有這個詞，就把該詞切下來；
2. 對剩余三個字“ 江大橋 ”再次進行正向最大匹配，會切成“ 江 ”、“ 大橋 ”；
3. 整個句子切分完成為： 南京市長、江、大橋 ；

我們可以很明顯的看到，這么分詞其實有很明顯的缺陷，即沒有把“南京市”給分出來，而且這個句子的原意顯然與“南京市長”沒有任何關系。

2）逆向最大匹配

后來人們發現，中文經常會把要描述的主體對象放到句子的后面（不絕對），于是就有人提出了逆向最大匹配，從句子的后面開始最大匹配：

1. 取出“ 南京市長江大橋 ”的后四個字“ 長江大橋 ”，發現詞典中有匹配，切割下來；
2. 對剩余的“南京市”進行分詞，整體結果為： 南京市、長江大橋

要注意的是，對于這個句子雖然效果好了一些，但并不代表逆向的匹配一定正確，也許某個句子真的是在討論“ 南京市長 ”呢？

3）雙向最大匹配

如果不能準確把握分詞的效果，有人提出了雙向的最大匹配，即把所有可能的最大詞都分出來，上面的句子可以分為： 南京市、南京市長、長江大橋、江、大橋

具體到實踐中，如果只是簡單的系統而不是復雜的數據挖掘，使用這種基于規則的匹配非常方便，幾十行代碼也就搞定了。

從分詞的實際效果來說，逆向最大匹配通常效果要略好于正向的最大匹配（沒有嚴謹的證明，只是大家的感覺……）。

下面的通過代碼，對逆向最大匹配做一個簡單的體驗：

#!/usr/bin/python
# coding:utf-8
"""
  Inverse Maximum Matching Words Spliting.
"""
class IMM(object):
  def __init__(self, dictionary_file):
    self.dictionary = {}
    self.maximum = 0
    # 讀取詞典文件
    with open(dictionary_file,'r') as f:
      line = f.readline().strip()
      while line:
        self.dictionary[line] = 1
        if len(line) > self.maximum:
          # 設置詞典的最大單詞長度
          self.maximum = len(line)
        line = f.readline().strip()
  def split_words(self, text):
    result = []
    # 最大匹配
    index = len(text)
    while index > 0:
      word = None
      for length in range(self.maximum, 0, -1):
        if index - length < 0:
          continue
        piece = text[(index - length):index]
        if piece in self.dictionary:
          word = piece
          result.append(word)
          index = index - length
          break
      if word is None:
        index -= 1
    return result
def main():
  text = "中華人民共和國中央政府今天，成立了"
  # 輸出： 了   成立   今天   中央政府   中華人民共和國
  splitter = IMM('dict.txt')
  result = splitter.split_words(text)
  for r in result:
    print r,' ',
if __name__ == '__main__':
  main()

二、基于統計的分詞

基于規則的統計很大程度上是看運氣來的，因為你無法猜測原文的意思是表達什么，但是統計學家想出了好辦法，如果某兩個詞的組合，在概率統計上出現的幾率非常大，那么我們就認為分詞正確。

比如： “南京市“后緊跟”長江大橋”的在各種資料的統計結果中，概率非常大，那么我們就認為這個詞應該分成這樣，而“南京市長”和“江大橋”這兩個詞的組合，相信概率會非常低，也就認為不正確了。

要使用基于統計的分詞，一共需要做兩步操作：1、建立統計語言模型，2、對句子進行單詞劃分，對劃分結果進行概率計算，獲得概率最大的分詞方式。

1）建立統計語言模型

這一步比較復雜，我們首先需要來看一下全概率公式。現在假如我們現在要預測未來四天的天氣是以下序列的概率：

我們已經知道，這幾種天氣獨立出現的概率分別是：

我們現在要計算整個序列出現的概率，可以使用全概率公式：

我們可以看到，對于天氣來說，只需要統計出以前各種天氣獨立出現的概率，然后使用全概率公式計算即可，這個道理同樣可以用于分詞統計上，即根據每個詞以前獨立出現的概率，計算出整個句子出現的概率。

所以為了解決這個問題，需要引入“ 馬爾科夫模型 ”，這個模型的的本質是，假設某一時刻的狀態，只與該狀態之前的$N$個狀態有關，這個$N$是有限的，整個狀態鏈稱為 N階馬爾科夫鏈 。比如，對于以上天氣預測使用1階馬爾科夫鏈，當天的天氣只與之前一天有關，與更早的天氣沒有關系，那么全概率就變成了：

所有的概率都只有兩個參數，只需要計算$N^2$個概率即可，同時也適用于更長的天氣預測鏈，這種兩個參數的一階馬爾科夫鏈用在統計語言模型上就稱為二元語言模型。一般的小公司，用到二元的模型就夠了，像Google這種巨頭，也只是用到了大約四元的程度，它對計算能力和空間的需求都太大了。

現在，我們已經從全概率公式引入了語言模型，那么真正用起來如何用呢？

舉個簡單的例子，我們要計算 “南京 市長 江 大橋” 這種分詞情況出現的概率就可以這么算：

對于任一一個條件概率，我們都可以用最大似然估計來簡單計算，如：

其中$Count(w {2},w {1})$表示這兩個單詞同時出現且2在1前面的次數，這種估算方式非常使用有效，基本上各大公司都是這么來做的。但是問題在于假如這兩個單詞壓根沒出現過，那豈不是概率為0了？這在概率上和計算方便上都是不允許的，畢竟再稀有的詞也是有出現概率的嘛，所以這就需要我們使用一些“平滑方法”來保證所有概率都不能為0。

最簡單的平滑方式莫過于加一平滑了，即把所有單詞組合出現的次數都加一：

其中$V$是詞表單詞的數量（唯一單詞數），保證整體概率加起來還是1。當然，實際使用中用的最多的是“katz平滑”，這種平滑方式稍微復雜一些，本篇暫不詳述，我們先用加一平滑就行（目的都是一樣的）。

現在，我們的語言模型輪廓已經出來了，即：

計算相鄰兩個單詞共同出現的概率，用最大似然估計的話，也就是詞組的頻率（二元模型，多遠模型需要計算三個連續單詞連續出現的頻率）。

說起來可能不太好理解，看代碼最容易了：

#!/usr/bin/env python
# coding:utf-8
class LanguageModel(object):
  def __init__(self, corpus_file):
    self.words = []
    self.freq = {}
    print 'loading words'
    with open(corpus_file,'r') as f:
      line = f.readline().strip()
      while line:
        self.words.append('<s>')
        self.words.extend(line.split())
        self.words.append('</s>')
        line = f.readline().strip()
    print 'hashing bi-gram keys'
    for i in range(1,len(self.words)):
      # 條件概率
      key = self.words[i] + '|' + self.words[i-1]
      if key not in self.freq:
        self.freq[key] = 0
      self.freq[key] += 1
    print 'hashing single word keys'
    for i in range(0,len(self.words)):
      key = self.words[i]
      if key not in self.freq:
        self.freq[key] = 0
      self.freq[key] += 1
  def get_trans_prop(self, word, condition):
    """獲得轉移概率"""
    key = word + '|' + condition
    if key not in self.freq:
      self.freq[key] = 0
    if condition not in self.freq:
      self.freq[condition] = 0
    C_2 = (float)(self.freq[key] + 1.0)
    C_1 = (float)(self.freq[condition] + len(self.words))
    return C_2/C_1
  def get_init_prop(self, word):
    """獲得初始概率"""
    return self.get_trans_prop(word,'<s>')
  def get_prop(self, *words):
    init = self.get_init_prop(words[0])
    product = 1.0
    for i in range(1,len(words)):
      product *= self.get_trans_prop(words[i],words[i-1])
    return init*product
def main():
    lm = LanguageModel('RenMinData.txt')
    print 'total words: ', len(lm.words)
    print 'total keys: ', len(lm.freq)
    print 'P(各族|全國) = ', lm.get_trans_prop('各族','全國')
    print 'P(黨|堅持) = ', lm.get_trans_prop('黨','堅持')
    print 'P(以來|建國) = ', lm.get_trans_prop('以來','建國')
    print 'init(全國) = ', lm.get_init_prop('全國')
    print "P('全國','各族','人民')", lm.get_prop('全國','各族','人民')
if __name__ == '__main__':
    main()

2）劃分句子求出概率最高的分詞方式

現在，我們有了統計語言模型，下一步要做的就是對句子進行劃分，最原始直接的方式，就是對句子的所有可能的分詞方式進行遍歷然后求出概率最高的分詞組合。但是這種窮舉法顯而易見非常耗費性能，所以我們要想辦法用別的方式達到目的。

仔細思考一下，假如我們把每一個字當做一個節點，每兩個字之間的連線看做邊的話，對于句子“中國人民萬歲”，我們可以構造一個如下的分詞結構：

我們要找概率最大的分詞結構的話，可以看做是一個動態規劃問題， 也就是說，要找整個句子的最大概率結構，對于其子串也應該是最大概率的，我們只需要找到這個狀態轉移函數即可，關于動態規劃的轉移函數，可以參考這篇文章。

對于句子任意一個位置$t$上的字，我們要從詞典中找到其所有可能的詞組形式，如上圖中的第一個字，可能有：中、中國、中國人三種組合，第四個字可能只有民，經過整理，我們的分詞結構可以轉換成以下的有向圖模型:

我們要做的就是找到一個概率最大的路徑即可。我們假設$C_{t}(k)$表示第t個字的位置可能的詞是k，那么可以寫出狀態轉移方程：

其中k是當前位置的可能單詞，l是上一個位置的可能單詞，M是l可能的取值，有了狀態轉移返程，寫出遞歸的動態規劃代碼就很容易了（這個方程其實就是著名的viterbi算法，通常在隱馬爾科夫模型中應用較多）：

#!/usr/bin/python
# coding:utf-8
"""
  @author royguo1988@gmail.com
  @date 2012-12-23
"""
from lm import LanguageModel
class Node(object):
  """有向圖中的節點"""
  def __init__(self,word):
    # 當前節點作為左右路徑中的節點時的得分
    self.max_score = 0.0
    # 前一個最優節點
    self.prev_node = None
    # 當前節點所代表的詞
    self.word = word
class Graph(object):
  """有向圖"""
  def __init__(self):
    # 有向圖中的序列是一組hash集合
    self.sequence = []
class DPSplit(object):
  """動態規劃分詞"""
  def __init__(self):
    self.lm = LanguageModel('RenMinData.txt')
    self.dict = {}
    self.words = []
    self.max_len_word = 0
    self.load_dict('dict.txt')
    self.graph = None
    self.viterbi_cache = {}
  def get_key(self, t, k):
    return '_'.join([str(t),str(k)])
  def load_dict(self,file):
    with open(file, 'r') as f:
      for line in f:
        word_list = [w.encode('utf-8') for w in list(line.strip().decode('utf-8'))]
        if len(word_list) > 0:
          self.dict[''.join(word_list)] = 1
          if len(word_list) > self.max_len_word:
            self.max_len_word = len(word_list)
  def createGraph(self):
    """根據輸入的句子創建有向圖"""
    self.graph = Graph()
    for i in range(len(self.words)):
      self.graph.sequence.append({})
    word_length = len(self.words)
    # 為每一個字所在的位置創建一個可能詞集合
    for i in range(word_length):
      for j in range(self.max_len_word):
        if i+j+1 > len(self.words):
          break
        word = ''.join(self.words[i:i+j+1])
        if word in self.dict:
          node = Node(word)
          # 按照該詞的結尾字為其分配位置
          self.graph.sequence[i+j][word] = node
    # 增加一個結束空節點，方便計算
    end = Node('#')
    self.graph.sequence.append({'#':end})
    # for s in self.graph.sequence:
    #   for i in s.values():
    #     print i.word,
    #   print ' - '
    # exit(-1)
  def split(self, sentence):
    self.words = [w.encode('utf-8') for w in list(sentence.decode('utf-8'))]
    self.createGraph()
    # 根據viterbi動態規劃算法計算圖中的所有節點最大分數
    self.viterbi(len(self.words), '#')
    # 輸出分支最大的節點
    end = self.graph.sequence[-1]['#']
    node = end.prev_node
    result = []
    while node:
      result.insert(0,node.word)
      node = node.prev_node
    print ''.join(self.words)
    print ' '.join(result)
  def viterbi(self, t, k):
    """第t個位置，是單詞k的最優路徑概率"""
    if self.get_key(t,k) in self.viterbi_cache:
      return self.viterbi_cache[self.get_key(t,k)]
    node = self.graph.sequence[t][k]
    # t = 0 的情況,即句子第一個字
    if t == 0:
      node.max_score = self.lm.get_init_prop(k)
      self.viterbi_cache[self.get_key(t,k)] = node.max_score
      return node.max_score
    prev_t = t - len(k.decode('utf-8'))
    # 當前一個節點的位置已經超出句首，則無需再計算概率
    if prev_t == -1:
      return 1.0
    # 獲得前一個狀態所有可能的漢字
    pre_words = self.graph.sequence[prev_t].keys()
    for l in pre_words:
      # 從l到k的狀態轉移概率
      state_transfer = self.lm.get_trans_prop(k, l)
      # 當前狀態的得分為上一個最優路徑的概率乘以當前的狀態轉移概率
      score = self.viterbi(prev_t, l) * state_transfer
      prev_node = self.graph.sequence[prev_t][l]
      cur_score = score + prev_node.max_score
      if cur_score > node.max_score:
        node.max_score = cur_score
        # 把當前節點的上一最優節點保存起來，用來回溯輸出
        node.prev_node = self.graph.sequence[prev_t][l]
    self.viterbi_cache[self.get_key(t,k)] = node.max_score
    return node.max_score
def main():
  dp = DPSplit()
  dp.split('中國人民銀行')
  dp.split('中華人民共和國今天成立了')
  dp.split('努力提高居民收入')
if __name__ == '__main__':
  main()

需要特別注意的幾點是：

1. 做遞歸計算式務必使用緩存，把子問題的解先暫存起來，參考動態規劃入門實踐。
2. 當前位置的前一位置應當使用當前位置單詞的長度獲得。
3. 以上代碼只是作為實驗用，原理沒有問題，但性能較差，生產情況需要建立索引以提高性能。
4. 本分詞代碼忽略了英文單詞、未登錄詞和標點符號，但改進并不復雜，讀者可自行斟酌。

代碼的輸出結果為：

中國人民銀行 中國 人民 銀行 中華人民共和國今天成立了 中華人民共和國 今天 成立 了 努力提高居民收入 努力 提高 居民 收入

三、統計+規則分詞

有時候我們不單單需要準確的把原句的意思分出來，同時也希望能盡可能多的把符合原句意思的詞抽取出來，比如 “中國人民銀行”，按照統計分詞可以得到：中國、人民、銀行 三個詞，但在某些領域，我們可能還需要 “人民銀行”、“中國人民“ 這些詞。

所以為了盡可能多的提取句子中的詞，大多數分詞工具的實現都會結合規則和統計，把結果進行合并。

后記

水平有限，以上內容只是我作為業余愛好者的研究了解，如有錯誤，求不吝指正。