1.前向最大匹配算法
例子：我們經(jīng)常有意見分歧
詞典：['我們', '經(jīng)常', '有', '有意見', '意見', '分歧']
對于上面的例子我們應(yīng)用前向最大匹配算法怎么分詞呢，步驟如下：
- 確定最大長度max_len, 也就是說我們是在max_len這個(gè)長度內(nèi)尋找匹配的字符串，這里我們不妨令max_len=5。
- 將例子分割為
[我們經(jīng)常有] 意見分歧,看前面5個(gè)詞'我們經(jīng)常有'是否在詞典庫中，我們查看發(fā)現(xiàn)不在。 - 接著分割為
[我們經(jīng)常] 有意見分歧,看這4個(gè)詞'我們經(jīng)常'是否在詞典庫中，查看發(fā)現(xiàn)依然不在。 - 繼續(xù)分割為
[我們經(jīng)] 常有意見分歧,看這3個(gè)詞'我們經(jīng)'是否在詞典庫中，查看發(fā)現(xiàn)不在。 - 繼續(xù)分割為
[我們] 經(jīng)常有意見分歧,看這2個(gè)詞'我們'是否在詞典庫中，查看發(fā)現(xiàn)在詞典庫，那么'我們'就被分割出來,原例子變成我們 | 經(jīng)常有意見分歧。 - 然后從'經(jīng)'字開始往后數(shù)max_len個(gè)單詞重復(fù)前面步驟。
- 最后分割完的句子為
我們 | 經(jīng)常 | 有意見 | 分歧。
python實(shí)現(xiàn)如下：
s = '我們經(jīng)常有意見分歧'
dic = ['我們', '經(jīng)常', '有', '有意見', '意見', '分歧']
def forward_max_seg(s, dic, max_len):
p1, p2 = 0, min(max_len-1, len(s)-1)
res = []
while p1 <= p2:
if s[p1:p2+1] in dic:
res.append(s[p1:p2+1])
p1 = p2 + 1
p2 = min(p1 + max_len-1, len(s)-1)
else:
p2 -= 1
return res
res = forward_max_seg(s, dic, 5)
print('|'.join(res))
輸出為：
我們|經(jīng)常|有意見|分歧
2.后向最大匹配算法
例子：我們經(jīng)常有意見分歧
詞典：['我們', '經(jīng)常', '有', '有意見', '意見', '分歧']
后向匹配跟前向匹配方向相反，過程如下：
- 同樣需要確定最大長度max_len, 這里我們也令max_len=5。
- 從后往前看將例子分割為
我們經(jīng)常 [有意見分歧],看后面5個(gè)詞'有意見分歧'是否在詞典庫中，我們查看發(fā)現(xiàn)不在。 - 接著分割為
我們經(jīng)常有 [意見分歧],看這4個(gè)詞'意見分歧'是否在詞典庫中，查看發(fā)現(xiàn)依然不在。 - 繼續(xù)分割為
我們經(jīng)常有意 [見分歧],看這3個(gè)詞'見分歧'是否在詞典庫中，查看發(fā)現(xiàn)不在。 - 繼續(xù)分割為
我們經(jīng)常有意見 [分歧],看這2個(gè)詞'分歧'是否在詞典庫中，查看發(fā)現(xiàn)在詞典庫，那么'分歧'就被分割出來,原例子變成我們經(jīng)常有意見 | 分歧。 - 然后從'見'字開始往前數(shù)max_len個(gè)單詞重復(fù)前面步驟。
- 最后分割完的句子為
我們 | 經(jīng)常 | 有意見 | 分歧。
python實(shí)現(xiàn)如下：
def backward_max_seg(s, dic, max_len):
p1, p2 = max(len(s)-max_len, 0), len(s)-1
res = []
while p1 <= p2:
if s[p1:p2+1] in dic:
res.insert(0, s[p1:p2+1])
p2 = p1-1
p1 = max(p2-max_len+1, 0)
else:
p1 += 1
return res
res = backward_max_seg(s, dic, 5)
print('|'.join(res))
輸出：
我們|經(jīng)常|有意見|分歧
3.雙向最大匹配法
算法流程：
比較正向最大匹配和反向最大匹配結(jié)果：
- 如果分詞數(shù)量結(jié)果不同，那么取分詞數(shù)量較少的那個(gè)
- 如果分詞數(shù)量結(jié)果相同：
- 分詞結(jié)果相同，可以返回任何一個(gè)
- 分詞結(jié)果不同，返回單字?jǐn)?shù)比較少的那個(gè)
上面的例子兩種分法一致，所以選任何一個(gè)都可以，下面看另一個(gè)例子：
例子：北京大學(xué)生前來應(yīng)聘
詞典：['北京大學(xué)', '北京', '大學(xué)生','生前', '來', '應(yīng)聘']
正向匹配最終切分結(jié)果為：北京大學(xué) | 生前 | 來 | 應(yīng)聘，分詞數(shù)量為 4，單字?jǐn)?shù)為 1
反向匹配最終切分結(jié)果為：”北京 | 大學(xué)生 | 前來 | 應(yīng)聘，分詞數(shù)量為 4，單字?jǐn)?shù)為 0
因此選擇反向匹配的結(jié)果作為最終結(jié)果
最大匹配算法缺點(diǎn)：
- 找到的是局部最優(yōu)解
- 嚴(yán)重依賴于max_len的大小，當(dāng)max_len特別大時(shí)，效率會(huì)很低
- 無法考慮語義信息
3. 考慮語義的分割-維特比(viterbi)算法
例子：經(jīng)常有意見分歧
詞典：['有', '有意見', '意見', '分歧', '見', '意']
前面講到最大匹配算法是無法考慮語義信息的，那么如果要考慮語義信息應(yīng)該怎么做呢？
最直接的想法是分成兩步，step1:將句子的所有可能分割方式分割出來，step2:選出這些分法中哪個(gè)最好最合乎常理的，過程表示如下：
比如step1得到了所有可能的分割：
s1 = 經(jīng)常 | 有 | 意見 | 分歧
s2 = 經(jīng)常 | 有| 意 | 見 | 分歧
s3 = 經(jīng)常 | 有意見 | 分歧
......
那么step2如何選出最好的呢，,最簡單的一種方式是 unigram，拿s1和s2的比較舉例：
p(s1) = p(經(jīng)常, 有, 意見,分歧) = p(經(jīng)常)p(有)p(意見)p(分歧)
p(s2) = p(經(jīng)常, 有, 意, 見,分歧) = p(經(jīng)常)p(有)p(意)p(見)p(分歧)
就是比較p(s1)和p(s2)哪個(gè)大，選擇大的那個(gè)。
即使我們使用最簡單的unigram，我們也會(huì)發(fā)現(xiàn)這種做法進(jìn)行了大量的重復(fù)性工作，效率很低。那么怎么解決效率問題呢，一種途徑就是將兩步合并，用DP(動(dòng)態(tài)規(guī)劃)進(jìn)行優(yōu)化，提升效率，也就是接下來要講的維特比算法。
例子：經(jīng)常有意見分歧
詞典: ['經(jīng)常', '經(jīng)', '有', '有意見', '意見', '分歧', '見', '意', '見分歧', '分']
概率：[0.1, 0.05, 0.1, 0.1, 0.2, 0.2, 0.05, 0.05, 0.05, 0.1]
-log(概率):[2.3, 3, 2.3, 2.3, 1.6,1.6, 3, 3, 3, 2.3]
算法流程：
用圖來表示，邊權(quán)重表示這個(gè)這個(gè)字的-log概率，遍歷詞典，將各概率標(biāo)注如下圖，將未出現(xiàn)的詞用較大的數(shù)表示，這里用20表示。因?yàn)槭褂?log，這里權(quán)重和最小也就是原概率乘積最大問題。原問題為：找到一種劃分使得這種劃分的概率乘積最大，那么現(xiàn)在原問題就轉(zhuǎn)化成找到一條路徑從節(jié)點(diǎn)1到節(jié)點(diǎn)8，使權(quán)重和最小，就能用DP解決。
DP算法流程：
做如下定義：
f(8):從節(jié)點(diǎn)1到節(jié)點(diǎn)8的最短路徑
f(7):從節(jié)點(diǎn)1到節(jié)點(diǎn)7的最短路徑
......
那么
f(8) = min(f(7)+20, f(6)+1.6, f(5)+3)
f(7) = f(6)+2.3
f(6) = min(f(5)+3, f(4)+1.6, f(3)+2.3)
......
4 分詞工具
jieba分詞：https://github.com/fxsjy/jieba
SnowNLP分詞：https://github.com/isnowfy/snownlp
LTP: http://www.ltp-cloud.com/
HanNLP分詞: https://github.com/hankcs/HanLP/
reference：
[1] https://blog.csdn.net/selinda001/article/details/79345072
[2] https://www.bilibili.com/video/av86991001?p=21
未完待續(xù).....
