Python與自然語言處理——中文分詞
- 中文分詞技術（一）
-
- 規則分詞
-
-
- 正向最大比對法（MM法）
- 逆向最大比對法（RMM法）
- 雙向最大比對法
-
- 統計分詞
-
-
- 語言模型
- HMM模型
- 其他統計分詞算法
-
- 混合分詞
-
-
-
-
- 完整代碼與資料集
- 參考文獻
-
-
-
中文分詞技術（一）
中文分詞問題主要來源于：在漢語中，句子是以字為機關的，但是語義了解仍然是需要以詞為機關，是以也就存在了中文分詞問題。
主要的技術可以分為：規則分詞、統計分詞以及混合分詞（規則+統計）
規則分詞
基于規則的分詞是一種機械分詞，主要依賴于維護詞典，在切分時将與劇中的字元串與詞典中的詞進行比對。
主要的切分方法包括三種：正向最大比對法、逆向最大比對法以及雙向最大比對法。
正向最大比對法（MM法）
-
基本思想
假設分詞詞典中最長詞由 i i i個漢字組成，則用被處理文檔目前前 i i i個字作為比對字段，若字典中存在這樣的詞則比對成功，否則去掉最後一個字再進行查找。
- 代碼示例
#定義正向最大比對法類
class MM(object):
def __init__(self):
self.window_size=3 #詞典中最長字元串包含的字數
def cut(self,text):
result=[]
index=0
text_length=len(text)
dic=['研究','研究所學生','生命','命','的','起源'] #詞典
while text_length>index: #隻要還有字就進行比對
for size in range(self.window_size+index,index,-1): #生成可能長度
piece=text[index:size]
if piece in dic:
index=size-1 #比對成功将index設定為比對成功的最後一個字的位置
break
index=index+1 #開始下一個字元串的比對
result.append(piece+'----')
print(result)
if __name__=='__main__':
text='研究所學生命的起源'
tokenizer=MM()
tokenizer.cut(text)
結果如下所示：
[‘研究所學生----’, ‘命----’, ‘的----’, ‘起源----’]
逆向最大比對法（RMM法）
-
基本思路
基本思路與正向相同，隻是切分方向正好與MM法相反。從文檔末尾開始處理，每次去除第一個字進行比對，維護的也是逆序詞典，每個詞都按逆序方式存放。
RMM比MM的誤差小。
- 代碼示例
#定義逆向最大比對法類
class RMM(object):
def __init__(self):
self.window_size=3
def cut(self,text):
result=[]
index=len(text) #從文本末尾開始
dic=['研究','研究所學生','生命','命','的','起源']
while index>0:
for size in range(index-self.window_size,index):
piece=text[size:index] #找到最後幾個字組成的字元串
if piece in dic:
index=size+1 #将位置更新為比對到的最後一個字的位置
break
index=index-1 #開始新的位置
result.append(piece+'----')
result.reverse() #由于從最後進行比對，是以順序是反的，需要颠倒過來
print(result)
if __name__=='__main__':
text='研究所學生命的起源'
tokenizer=RMM()
tokenizer.cut(text)
結果如下所示：
[‘研究----’, ‘生命----’, ‘的----’, ‘起源----’]
雙向最大比對法
-
基本思想
雙向最大比對法将正向和逆向的結果進行比較，按照最大比對原則，選擇詞數切分最少的作為結果。
- 雙向最大比對規則
- 如果結果詞數不同，傳回分詞數量較少的一個；
- 如果結果詞數相同
- 分詞結果相同，任意傳回一個
- 分詞結果不同，傳回單個字較少的一個
- 代碼示例
#定義雙向最大比對法的類
class BMM(object):
def __init__(self):
self.window_size=3
self.result_MM=[]
self.result_RMM=[]
self.num_MM=0
self.num_RMM=0
#正向最大
def MM(self,text):
index=0
text_length=len(text)
dic=['研究','研究所學生','生命','命','的','起源'] #詞典
while text_length>index: #隻要還有字就進行比對
for size in range(self.window_size+index,index,-1): #生成可能長度
piece=text[index:size]
if piece in dic:
index=size-1 #比對成功将index設定為比對成功的最後一個字的位置
break
index=index+1 #開始下一個字元串的比對
self.result_MM.append(piece+'----')
if len(piece)==1:
self.num_MM+=1
#逆向最大
def RMM(self,text):
index=len(text) #從文本末尾開始
dic=['研究','研究所學生','生命','命','的','起源']
while index>0:
for size in range(index-self.window_size,index):
piece=text[size:index] #找到最後幾個字組成的字元串
if piece in dic:
index=size+1 #将位置更新為比對到的最後一個字的位置
break
index=index-1 #開始新的位置
self.result_RMM.append(piece+'----')
if len(piece)==1:
self.num_RMM+=1
self.result_RMM.reverse() #由于從最後進行比對，是以順序是反的，需要颠倒過來
def cut(self,text):
if len(self.result_MM)>len(self.result_RMM):
result=self.result_RMM
elif len(self.result_MM)<len(self.result_RMM):
result=self.result_MM
elif len(self.result_MM)==len(self.result_RMM):
if self.result_MM==self.result_RMM:
result=self.result_RMM
else:
if self.num_MM>self.num_RMM:
result=self.result_RMM
else:
result=self.result_MM
print(result)
if __name__=='__main__':
text='研究所學生命的起源'
tokenizer=BMM()
tokenizer.MM(text)
tokenizer.RMM(text)
tokenizer.cut(text)
結果如下所示：
[‘研究----’, ‘生命----’, ‘的----’, ‘起源----’]
統計分詞
主要思想：将每個詞視作由字組成，如果相連的字在不同文本中出現次數越多，就越可能是一個詞。
基于統計的分詞一般有以下兩步：
- 建立統計語言模型
- 對句子進行單詞劃分，對劃分結果進行機率計算（隐馬爾可夫【HMM】、條件随機場【CRF】等）
語言模型
-
語言模型
為長度為 m m m的字元串确定其機率分布 P ( x 1 , x 2 , ⋯   , x m ) P\left( {{x_1},{x_2}, \cdots ,{x_m}} \right) P(x1,x2,⋯,xm)，其中 x 1 , x 2 , ⋯   , x m {{x_1},{x_2}, \cdots ,{x_m}} x1,x2,⋯,xm為文本中的各個詞語，計算公式如下：
P ( x 1 , x 2 , ⋯   , x m ) = P ( x 1 ) P ( x 2 ∣ x 1 ) P ( x 3 ∣ x 1 , x 2 ) ⋯ P ( x m ∣ x 1 , x 2 , ⋯   , x m − 1 ) P\left( {{x_1},{x_2}, \cdots ,{x_m}} \right) = P\left( {{x_1}} \right)P\left( {{x_2}\left| {{x_1}} \right.} \right)P\left( {{x_3}\left| {{x_1},{x_2}} \right.} \right) \cdots P\left( {{x_m}\left| {{x_1},{x_2}, \cdots ,{x_{m - 1}}} \right.} \right) P(x1,x2,⋯,xm)=P(x1)P(x2∣x1)P(x3∣x1,x2)⋯P(xm∣x1,x2,⋯,xm−1)
-
n n n元模型（ n − g r a m n-gram n−gram）
将上式進行簡化，認為其機率僅與其前面 n − 1 n-1 n−1個詞相關，是以為：
P ( x i ∣ x 1 , x 2 , ⋯   , x i − 1 ) ≈ P ( x i ∣ x i − ( n − 1 ) , x i − ( n − 2 ) , ⋯   , x i − 1 ) P\left( {{x_i}\left| {{x_1},{x_2}, \cdots ,{x_{i - 1}}} \right.} \right) \approx P\left( {{x_i}\left| {{x_{i - \left( {n - 1} \right)}},{x_{i - \left( {n - 2} \right)}}, \cdots ,{x_{i - 1}}} \right.} \right) P(xi∣x1,x2,⋯,xi−1)≈P(xi∣∣xi−(n−1),xi−(n−2),⋯,xi−1)
-
計算 n n n元條件機率
使用頻率計數比例計算：
P ( x i ∣ x i − ( n − 1 ) , x i − ( n − 2 ) , ⋯   , x i − 1 ) = c o u n t ( x i − ( n − 1 ) , x i − ( n − 2 ) , ⋯   , x i − 1 , x i ) c o u n t ( x i − ( n − 1 ) , x i − ( n − 2 ) , ⋯   , x i − 1 ) P\left( {{x_i}\left| {{x_{i - \left( {n - 1} \right)}},{x_{i - \left( {n - 2} \right)}}, \cdots ,{x_{i - 1}}} \right.} \right) = \frac{{count\left( {{x_{i - \left( {n - 1} \right)}},{x_{i - \left( {n - 2} \right)}}, \cdots ,{x_{i - 1}},{x_i}} \right)}}{{count\left( {{x_{i - \left( {n - 1} \right)}},{x_{i - \left( {n - 2} \right)}}, \cdots ,{x_{i - 1}}} \right)}} P(xi∣∣xi−(n−1),xi−(n−2),⋯,xi−1)=count(xi−(n−1),xi−(n−2),⋯,xi−1)count(xi−(n−1),xi−(n−2),⋯,xi−1,xi)
HMM模型
HMM将分詞作為字在字串中的序列标注任務來實作的。
-
基本思路
每個字在構造一個特定詞語時都占據一個确定的構詞結構：B（詞首）、M（詞中）、E（詞尾）和S（單獨成詞）。
一個簡單的例子：
中文分詞是文本處理不可或缺的一步！
中/B 文/E 分/B 詞/E 是/S 文/E 本/M 處/M 理/E 不/B 可/M 或/M 缺/E 的/S 一/B 步/E ！/S
-
抽象表示
用 λ = λ 1 λ 2 ⋯ λ n \lambda = {\lambda _1}{\lambda _2} \cdots {\lambda _n} λ=λ1λ2⋯λn代表輸入的句子， n n n為句子長度， λ i \lambda_i λi表示字， o = o 1 o 2 ⋯ o n o = {o_1}{o_2} \cdots {o_n} o=o1o2⋯on表示輸出的标簽，那麼理想輸出為：
max = max P ( o 1 o 2 ⋯ o n ∣ λ 1 λ 2 ⋯ λ n ) \max = \max P\left( {{o_1}{o_2} \cdots {o_n}\left| {{\lambda _1}{\lambda _2} \cdots {\lambda _n}} \right.} \right) max=maxP(o1o2⋯on∣λ1λ2⋯λn)
其中 o o o為B、M、E、S這四種标記。
- 通過HMM計算
-
通過貝葉斯公式能夠得到：
P ( o ∣ λ ) = P ( o , λ ) P ( λ ) = P ( λ ∣ o ) P ( o ) P ( λ ) P\left( {o\left| \lambda \right.} \right) = \frac{{P\left( {o,\lambda } \right)}}{{P\left( \lambda \right)}} = \frac{{P\left( {\lambda \left| o \right.} \right)P\left( o \right)}}{{P\left( \lambda \right)}} P(o∣λ)=P(λ)P(o,λ)=P(λ)P(λ∣o)P(o)
其中 λ \lambda λ為給定的輸出，是以 P ( λ ) P\left( \lambda \right) P(λ)為常數，是以最大化 P ( o ∣ λ ) P\left( {o\left| \lambda \right.} \right) P(o∣λ)等價于最大化 P ( λ ∣ o ) P ( o ) {P\left( {\lambda \left| o \right.} \right)P\left( o \right)} P(λ∣o)P(o)。
-
對 P ( λ ∣ o ) P ( o ) {P\left( {\lambda \left| o \right.} \right)P\left( o \right)} P(λ∣o)P(o)作馬爾可夫假設：
P ( λ ∣ o ) = P ( λ 1 ∣ o 1 ) P ( λ 2 ∣ o 2 ) ⋯ P ( λ n ∣ o n ) P\left( {\lambda \left| o \right.} \right) = P\left( {{\lambda _1}\left| {{o_1}} \right.} \right)P\left( {{\lambda _2}\left| {{o_2}} \right.} \right) \cdots P\left( {{\lambda _n}\left| {{o_n}} \right.} \right) P(λ∣o)=P(λ1∣o1)P(λ2∣o2)⋯P(λn∣on)
同時：
P ( o ) = P ( o 1 ) P ( o 2 ∣ o 1 ) P ( o 3 ∣ o 1 , o 2 ) ⋯ P ( o n ∣ o 1 , o 2 , ⋯   , o n − 1 ) P\left( o \right) = P\left( {{o_1}} \right)P\left( {{o_2}\left| {{o_1}} \right.} \right)P\left( {{o_3}\left| {{o_1},{o_2}} \right.} \right) \cdots P\left( {{o_n}\left| {{o_1},{o_2}, \cdots ,{o_{n - 1}}} \right.} \right) P(o)=P(o1)P(o2∣o1)P(o3∣o1,o2)⋯P(on∣o1,o2,⋯,on−1)
-
HMM做了齊次馬爾可夫假設，每個輸出僅與上一個輸出有關，是以：
P ( o ) = P ( o 1 ) P ( o 2 ∣ o 1 ) P ( o 3 ∣ o 2 ) ⋯ P ( o n ∣ o n − 1 ) P\left( o \right) = P\left( {{o_1}} \right)P\left( {{o_2}\left| {{o_1}} \right.} \right)P\left( {{o_3}\left| {{o_2}} \right.} \right) \cdots P\left( {{o_n}\left| {{o_{n - 1}}} \right.} \right) P(o)=P(o1)P(o2∣o1)P(o3∣o2)⋯P(on∣on−1)
于是：
P ( λ ∣ o ) P ( o ) ∼ P ( λ 1 ∣ o 1 ) P ( o 2 ∣ o 1 ) P ( λ 2 ∣ o 2 ) P ( o 3 ∣ o 2 ) ⋯ P ( o n ∣ o n − 1 ) P ( λ n ∣ o n ) P\left( {\lambda \left| o \right.} \right)P\left( o \right) \sim P\left( {{\lambda _1}\left| {{o_1}} \right.} \right)P\left( {{o_2}\left| {{o_1}} \right.} \right)P\left( {{\lambda _2}\left| {{o_2}} \right.} \right)P\left( {{o_3}\left| {{o_2}} \right.} \right) \cdots P\left( {{o_n}\left| {{o_{n - 1}}} \right.} \right)P\left( {{\lambda _n}\left| {{o_n}} \right.} \right) P(λ∣o)P(o)∼P(λ1∣o1)P(o2∣o1)P(λ2∣o2)P(o3∣o2)⋯P(on∣on−1)P(λn∣on)
将 P ( λ k ∣ o k ) P\left( {\lambda_k \left| o_k \right.} \right) P(λk∣ok)稱為發射機率， P ( o k ∣ o k − 1 ) P\left( {o_k \left| o_{k-1} \right.} \right) P(ok∣ok−1)稱為轉移機率。
此時的馬爾可夫假設就是一個二進制語言模型，當齊次馬爾可夫假設改為每個輸出與前兩個有關時就是三元語言模型。
-
- 通過Veterbi求解 max P ( λ ∣ o ) P ( o ) \max{P\left( {\lambda \left| o \right.} \right)P\left( o \right)} maxP(λ∣o)P(o)
-
核心思想
如果最終的最優路徑經過某個 o i o_i oi，那麼從初始結點到 o i − 1 o_{i-1} oi−1點的路徑必然也是一個最優路徑——因為每個結點 o i o_i oi隻會影響前後兩個結點 P ( o i − 1 ∣ o i ) P\left( {{o_{i-1}}\left| {{o_{i}}} \right.} \right) P(oi−1∣oi)和 P ( o i ∣ o i + 1 ) P\left( {{o_i}\left| {{o_{i + 1}}} \right.} \right) P(oi∣oi+1)。
-
-
代碼示例
使用的訓練集來自：https://github.com/canshang/python-nlk/blob/master/trainCorpus.txt_utf8.txt
class HMM(object):
def __init__(self):
import os
# 主要是用于存取算法中間結果，不用每次都訓練模型
self.model_file = 'hmm_model.pkl'
# 狀态值集合
self.state_list = ['B', 'M', 'E', 'S']
# 參數加載,用于判斷是否需要重新加載model_file
self.load_para = False
# 用于加載已計算的中間結果，當需要重新訓練時，需初始化清空結果
def try_load_model(self, trained):
if trained:
import pickle
with open(self.model_file, 'rb') as f:
self.A_dic = pickle.load(f)
self.B_dic = pickle.load(f)
self.Pi_dic = pickle.load(f)
self.load_para = True
else:
# 狀态轉移機率（狀态->狀态的條件機率）
self.A_dic = {}
# 發射機率（狀态->詞語的條件機率）
self.B_dic = {}
# 狀态的初始機率
self.Pi_dic = {}
self.load_para = False
# 計算轉移機率、發射機率以及初始機率
def train(self, path):
# 重置幾個機率矩陣
self.try_load_model(False)
# 統計狀态出現次數，求p(o)
Count_dic = {}
# 初始化參數
def init_parameters():
for state in self.state_list:
self.A_dic[state] = {s: 0.0 for s in self.state_list}
self.Pi_dic[state] = 0.0
self.B_dic[state] = {}
Count_dic[state] = 0
def makeLabel(text):
out_text = []
if len(text) == 1:
out_text.append('S')
else:
out_text += ['B'] + ['M'] * (len(text) - 2) + ['E']
return out_text
init_parameters()
line_num = -1
# 觀察者集合，主要是字以及标點等
words = set()
with open(path, encoding='utf8') as f:
for line in f:
line_num += 1
line = line.strip()
if not line:
continue
word_list = [i for i in line if i != ' ']
words |= set(word_list) # 更新字的集合
linelist = line.split()
line_state = []
for w in linelist:
line_state.extend(makeLabel(w))
assert len(word_list) == len(line_state)
for k, v in enumerate(line_state):
Count_dic[v] += 1
if k == 0:
self.Pi_dic[v] += 1 # 每個句子的第一個字的狀态，用于計算初始狀态機率
else:
self.A_dic[line_state[k - 1]][v] += 1 # 計算轉移機率
self.B_dic[line_state[k]][word_list[k]] = \
self.B_dic[line_state[k]].get(word_list[k], 0) + 1.0 # 計算發射機率
self.Pi_dic = {k: v * 1.0 / line_num for k, v in self.Pi_dic.items()}
self.A_dic = {k: {k1: v1 / Count_dic[k] for k1, v1 in v.items()}
for k, v in self.A_dic.items()}
#加1平滑
self.B_dic = {k: {k1: (v1 + 1) / Count_dic[k] for k1, v1 in v.items()}
for k, v in self.B_dic.items()}
#序列化
import pickle
with open(self.model_file, 'wb') as f:
pickle.dump(self.A_dic, f)
pickle.dump(self.B_dic, f)
pickle.dump(self.Pi_dic, f)
return self
def viterbi(self, text, states, start_p, trans_p, emit_p):
V = [{}]
path = {}
for y in states:
V[0][y] = start_p[y] * emit_p[y].get(text[0], 0)
path[y] = [y]
for t in range(1, len(text)):
V.append({})
newpath = {}
#檢驗訓練的發射機率矩陣中是否有該字
neverSeen = text[t] not in emit_p['S'].keys() and \
text[t] not in emit_p['M'].keys() and \
text[t] not in emit_p['E'].keys() and \
text[t] not in emit_p['B'].keys()
for y in states:
emitP = emit_p[y].get(text[t], 0) if not neverSeen else 1.0 #設定未知字單獨成詞
(prob, state) = max(
[(V[t - 1][y0] * trans_p[y0].get(y, 0) *
emitP, y0)
for y0 in states if V[t - 1][y0] > 0])
V[t][y] = prob
newpath[y] = path[state] + [y]
path = newpath
if emit_p['M'].get(text[-1], 0)> emit_p['S'].get(text[-1], 0):
(prob, state) = max([(V[len(text) - 1][y], y) for y in ('E','M')])
else:
(prob, state) = max([(V[len(text) - 1][y], y) for y in states])
return (prob, path[state])
def cut(self, text):
import os
if not self.load_para:
self.try_load_model(os.path.exists(self.model_file))
prob, pos_list = self.viterbi(text, self.state_list, self.Pi_dic, self.A_dic, self.B_dic)
begin, next = 0, 0
for i, char in enumerate(text):
pos = pos_list[i]
if pos == 'B':
begin = i
elif pos == 'E':
yield text[begin: i+1]
next = i+1
elif pos == 'S':
yield char
next = i+1
if next < len(text):
yield text[next:]
測試如下：
#####測試
hmm=HMM()
hmm.train('trainCorpus.txt_utf8.txt')
text='這是一個很棒的方案！'
res=hmm.cut(text)
print(text)
print(str(list(res)))
結果如下所示：
這是一個很棒的方案！
[‘這是’, ‘一個’, ‘很’, ‘棒’, ‘的’, ‘方案’, ‘！’]
其他統計分詞算法
-
條件随機場（CRF）
每個狀态不止與其前面的狀态有關，也與其後面的狀态有關。
- 神經網絡分詞算法
混合分詞
最常見的是先基于詞典進行分詞，再用統計分詞進行輔助。
完整代碼與資料集
規則分詞：https://github.com/canshang/python-nlk/blob/master/規則分詞.ipynb
資料集（HMM訓練集）：https://github.com/canshang/python-nlk/blob/master/trainCorpus.txt_utf8.txt
統計分詞（HMM）：https://github.com/canshang/python-nlk/blob/master/trainCorpus.txt_utf8.txt
參考文獻
《Python自然語言處理實戰》