【演算法記事本#NLP-1】最大匹配演算法分詞

本文地址https://www.cnblogs.com/oberon-zjt0806/p/12409536.html

#NLP-1 最大匹配演算法(MM)

最大匹配演算法(Maximum Matching)被用於對一個文段進行詞語劃分(Word Segmentation)。

注意

這是詞元化(Tokenization)演算法
此方法不適用於無分隔符的字母語言(e.g.:德語、使用假名替代漢字的日語、被取消分詞符的英文等)
但是對漢語這類無詞間分隔符但不依賴字母的語言效果拔群

輸入輸出

graph LR input1(文段P) input2(單詞表W) processor(MM) output(詞元表T) input1–輸入–>processor input2–輸入–>processor processor–輸出–>output

演算法內容

人話版本(自然描述)

輸入:文段$small P$,單詞表$small W$
過程:對於給定的$small P$和$small W$:

  1. 令指針$small i$從$small P$的起點開始
  2. 每當找到最長匹配於$small i$引領文段的單詞$small w$,則將$small w$加入詞元分析表$small T$(一個順序表結構)中
  3. $small i$向後移動$small w$長度個位置
  4. 回到2,直至$small i$無法向後移動為止

輸出:詞元分析表$small T$

說明

最長匹配??

這個概念用定義去描述其實很不容易理解,這裡直接上例子,比如,有一個字元串

The quick brown fox jumps over a lazy dog  

現在給出這麼幾個字元串:ThTheThe slowThe quick brown fox jumps over a lazy dog and a little duckquick brown

注意,最長匹配的前提是能匹配得上,此外還要求是端點匹配

先看Th,很明顯,儘管Th不能完美的匹配上原有字元串,但卻是原字元串的子串(Substring),也就是說它能夠完美的和原字元串的局部相匹配,而且是從起始位置相匹配,可以暫時認為是原字元串的最長匹配

再看The,和Th一樣,其整體能夠匹配上原字元串的部分,而且也是從起始位置匹配,因此也可能是最長匹配,這樣一來ThThe都能匹配上原字元串,但是

一個字元串在一個給定的字元串集合中只能找到一個最長匹配,而且是儘可能長的那個

考慮到TheTh長,因此The替掉了Th成為了目前的最長匹配

接下來看看The slow,截止到The都能匹配到原字元串上,但接下來的s無法匹配原字元串,儘管匹配部分的長度比The還長,但很遺憾,The slow只能認為是不匹配

The quick brown fox jumps over a lazy dog and a little duck也是同理,別看它甚至是原字元串的延長串(也就是原字元串是它的子串),但後面多出來的部分匹配不回去,所以也只能認為是不匹配

原字元串是大爺!!

最後再看看quick brown,當然這也是原字元串的子串,而且匹配長度為11,甚至比The的匹配性還強,但是也很遺憾,這並不是從起點匹配的,所以這個無法認為匹配

於是我們得到了結論:

在上述給出的5個字元串中,最長匹配為The

當然,這都是目前的最長匹配,如果我們繼續給出The quickThe quick brown、……這個結果還是會跟著變化的,因為:

理論上,從所有字元串構成的全集尋找某一字元串的最長匹配,其結果只能是該字元串本身

為什麼對漢語效果拔群??

這裡先說對英語吧…… 因為是做詞元化工作,所以這裡暫時無視英語中的空格分隔符

We are talking about weather.      ↓  移除所有分詞符  Wearetalkingaboutweather.  

當然,我們要對下面的內容做分詞,按說分詞工作做完後其分割結果應該和移除之前是一樣的:We|are|talking|about|weather|. 但如果採用MM演算法使用一個標準詞庫進行匹配,就會是下面這樣:

首先從W開始,從詞庫中尋找從W開始能夠最長匹配的字元串,然後非常巧,我們在詞典中找到了……Wear!! ……

於是,我們先不管後面能不能分出來,反正分完肯定是這樣子:Wear|...|...

很明顯這種分法是不行的。

這裡面的原因就在於:英語一共就26個字母,隨便找若干個字母湊成一個單詞的概率還是很大的,特別是移除分隔符後出現大量輔音字母+若干母音字母的情況。 而且,英語中辭彙的長度方差很大,短的只有一個字母,長的可以10多個,極端情況下也有40多個的甚至更多,很多短單詞會成為一些長單詞的子串(we之於wear等),而移除分隔符後兩個原本獨立的子串被拼合成一個更長的單詞也不是什麼新鮮事。 一種極端情況:

graph LR origin(“Hear the voice”) obfuscated(“Hearthevoice”) mm(“Heart|he|voice”) origin–移除分隔符–>obfuscated obfuscated–MM演算法分割–>mm

但是漢語就不一樣了,就以GB2312裡面的6700多個漢字想隨便挑出來幾個字就湊巧拼出一個詞語還是很困難的,而且詞語長度的方差很低,不考慮詩句和歇後語的話,常用的詞語和成語絕大多數為2~4個字,較長一些的8個字(比較少),這種情況下即使沒有分隔符,兩個獨立的詞語能夠被混淆成一個的幾率還是比較小的,比如:

一隻穿雲箭,千軍萬馬來相見  一隻|穿雲|箭|,|千軍萬馬|來|相見  

基本上分割的完全正確,而且即使把標點符號都去掉,也不太影響其分割的結果,斯坦福大學也給出了這樣的評價:

Doesn』t generally work in English! But works astonishingly well in Chinese!

不過其實說到底,這種演算法比較依賴於詞典(事實上很多詞元化演算法都挺依賴詞典),如果詞典編寫的不夠好,那麼即使是漢語其詞元化的品質也不盡如人意(特別是漢語需要足夠完善的辭彙庫,其工作量是相當龐大的)。