【IR】【NLP】snowball & porter stemming algorithm－兔窩

來源：The original stemming algorithm paper

【IR】【NLP】snowball & porter stemming algorithm

簡介：

　　部分語言 (英文、俄文、德文等) 會利用新增詞綴來派生出相似意思的詞，例如英文複數會加 s、過去式多半會加 ed、加 tion、ing 來改變詞性等。stemming (詞幹提取)，就代表去除詞綴提取出詞幹的處理動作，如下表。

input	output
foxes	fox
jumping	jump
quickly	quick
organize	organize
organizes	organize
organizing	organize

　　stemming 演算法就是負責這個處理動作的演算法，在 NLP (Natural Language Processing，自然語言處理) 與 IR (Information Retrieval，資訊檢索) 領域中很常見用來對資料進行前處理，將意思相近的詞藉由 stemming 演算法轉變為一樣的詞來降低資料集中的詞數量。

　　這樣做有什麼好處呢？舉例來說，最常見的 stemming 實例就是搜尋引擎。如圖所示，在 google 搜尋 Going Fishing，不只會命中 going、fishing 還會命中同詞幹的 go、fish。這樣的前處理除了能搜尋到更多資料、提升搜尋召回率之外，另一方面通常也能降低系統負擔 (詞數量降低)，可謂一石二鳥的處理技巧。

lemmatization vs stemming：

　　另一個常見的前處理動作是 lemmatization (詞形還原)，lemmatization 在主目標上與 stemming 相同，都是將意思相似的派生詞轉變為相同的詞，進而大幅降低詞數量。

　　兩者的差別在於 stemming 只根據 當詞只有詞綴不同時很可能是派生詞，移除詞綴即刻獲得詞幹 的概念在運作。這代表他無法處理長的完全不同、看不出詞綴的派生詞，因為他們都不符合此概念。且 stemming 也可以接受提取出的詞幹不真實存在，只要同詞幹的詞可以被轉變成一樣的就好。

　　反之，lemmatization 則不論是否擁有詞綴都需要有能力判斷出該詞的原形，且提取出的詞必須真實存在。它並不是在提取出詞中既有的詞幹，而是 將派生詞還原成原形 (lemma)，所以才被稱作詞形還原。下表有一些詞作為範例。

input	stemming	lemmatization
better	better	good
abused	abus	abuse
abusing	abus	abuse
walking	walk	walk

　　聽起來 lemmatization 比 stemming 有用很多，但目標越難通常演算法就越複雜，大部分的 lemmatization 演算法都是藉由維護大型詞典以及對輸入詞進行形態分析來達到目標，而 stemming 演算法則由簡單的字串切割、if else 規則、小型詞典所組成。即便採用深度學習，lemmatization 訓練難度也高於 stemming。

from nltk.stem import WordNetLemmatizer
wordNet = WordNetLemmatizer()
PART_OF_SPEECH = {
    'ADJ': 'a',
    'ADJ_SAT': 's',
    'ADV': 'r',
    'NOUN': 'n',
    'VERB': 'v'
}
print(wordNet.lemmatize('better', PART_OF_SPEECH['ADJ']))     # good
print(wordNet.lemmatize('better', PART_OF_SPEECH['ADJ_SAT'])) # good
print(wordNet.lemmatize('better', PART_OF_SPEECH['ADV']))     # well
print(wordNet.lemmatize('better', PART_OF_SPEECH['NOUN']))    # better
print(wordNet.lemmatize('better', PART_OF_SPEECH['VERB']))    # better

　　我們使用 python NLP 套件 NLTK 來測試名為 WordNet 的 lemmatization 詞典型演算法，可以看到還需要額外提供詞性才能使 lemmatization 處裡正確。

　　以搜尋引擎來說，部分系統其實不在乎用戶搜尋的關鍵字以及資料庫內的資料是什麼，只在乎兩者能匹配、能被搜尋到就好，這時候採用 stemming 就是較合適的做法。視情況選擇能解決問題的演算法，而不是選擇較厲害的演算法，Keep It Simple, Stupid。

porter stemming algorithm：

　　英文專用的 stemming 演算法中，最廣為人知的就是由 Martin Porter 於 1980 發明的 porter stemming algorithm，以下簡稱 porter 演算法。要講解 porter 演算法是怎麼運作的，要先了解一些規則。

toy	母子母
syzygy	子母子母子母

　　詞當中的字母 A, E, I, O, U, 以及非母音後的 Y 被稱作母音 (元音、vowel)，其他都是子音 (輔音、consonant)。

	母音開頭	子音開頭
母音結尾	V(...)V	C(...)V
子音結尾	V(...)C	C(...)C

　　當母音連續出現 1 次或多次時，標示為 V；當子音連續出現 1 次或多次時，標示為 C。由於任何英文字都由母音與子音組合，所以根據其開頭與結尾可以寫成以上四種狀況，並進一步標示為下方式子。

[C](VC)^m[V]

[X] 代表 X 出現 0 次或 1 次。
(X)^m 代表 X 出現 m 次，m 為不小於 0 的整數。

　　而 porter 演算法就是由這些 C、V、m 以及常見的詞綴所組合成的一連串 if else 判斷條件。

(condition) S1 -> S2

condition 代號	代表意思
*S	詞幹由 S 結尾 (S 可替換為任意字)
v	詞幹包含母音
*d	詞幹由兩個子音結尾
*o	詞幹結尾最後三字為母子母音順序且結尾母音不是 W、X、Y

　　以上為判斷條件的表示規則，代表意思為，如果詞由 S1 結尾，且移除 S1 後得到的詞幹滿足條件 condition，就將 S1 結尾替換為 S2 (condition、S1、S2 皆可為空)。

　　了解這些規則後我們可以來看一些判斷條件的範例。

判斷條件	範例
SSES -> SS	caresses -> caress
S ->	cats -> cat
(m > 0) EED -> EE	agreed -> agree feed -> fee
(m > 0) FUL ->	hopeful -> hope
(m = 1 and *o) -> E	fil -> file fail -> fail
(v) Y -> I	happy -> happi sky -> sky
(m > 1 and d and L) -> single letter	controll -> control roll -> roll

　　值得一提的是它引入 m 這個屬性來避免 saw、sun 等短詞被轉換成 s，最終被視為相同詞的事情發生 (overstemming)。

來源：The original stemming algorithm paper

　　porter 演算法會將一共幾十個判斷條件分為八步驟，分別為 step 1a、step 1b、step 1c、step 2、step 3、step 4、step 5a、step 5b，除了 step 1b 有嵌套判斷條件導致可能處理兩次外，每一步驟都只會執行該步驟的其中一條判斷條件，所以一個詞最多可能會被處理九次。

Step 1a

SSES -> SS

IES -> I

SS -> SS

S ->

　　當步驟像 step 1a 一樣有複數命中時，以最長匹配的 S1 為主，所以 caresses 會匹配 SSES 這個 S1 的規則，而不是 S。這也是為什麼會出現 SS -> SS 這種不變的規則，目的在於避免 SS 結尾的詞被 S 這個 S1 匹配到。

來源：The original stemming algorithm paper

　　porter 演算法的運作原理就是將輸入詞經過八步驟處理後，最後 step 5b 輸出的就是詞幹。

　　可以看到 porter 演算法的這些判斷條件比起程式技術大多與語言學跟形態學較相關，所以我就不附上完整的 porter 演算法了，有興趣看完整版的朋友請參考 The Porter stemming algorithm - Snowball，以上的介紹應該足以讓你看懂全部的八步驟。

snowball：

　　提到 porter 演算法就不得不說 snowball。snowball 是一種用來設計的 stemming 演算法的字串處理語言，起初由 porter 演算法作者 Martin Porter 於兩千年初設計，並於2014 年結束維護工作，現在 snowball 與多數開源項目一樣由社群在維護。

來源：The Porter stemming algorithm - Snowball

　　snowball 能實作出一樣以判斷條件為主體的 stemming 演算法，上圖即為官方將 porter 演算法 step1a 轉換成 snowball 程式碼的範例。snowball 程式碼的複雜度不高，在這邊附上官方手冊。

　　實作完後 snowball 編譯器可以將 snowball 程式碼編譯成各種常見程式語言 (C#、Go、Java、Javascript、Python 等)，讓任何人都有能力輕易設計、修改 stemming 演算法。

來源：Download - Snowball

　　除了編譯器本體之外，snowball 早已將多種語言常用的 stemming 演算法實作完成，並提供已編譯的 library 讓大家下載。有一些設計文件會直接用 snowball stemmer 來代表他們使用這些預設包含的 stemming 演算法。

　　Martin Porter 在推出 snowball 時也更新了 porter stemming algorithm，稱作 english (Porter2) stemming algorithm (以下簡稱 porter2 演算法)，當然也有附上相對應的 snowball 程式碼供大家使用。詳細的更新規則與 porter 演算法一樣是語言學跟形態學的判斷條件，有興趣看完整版的朋友可以參考官網。

　　簡單來說，porter 演算法與 porter2 演算法都是 stemming 演算法。snowball 則是由同作者發明的程式語言，是用來實現 stemming 演算法的工具。

　　我自己認為這樣方便的工具不太常見，或許各研究者的實驗室內都有類似的工具，但會公開出來給社群維護的不多。今天不論是 stemming 演算法能成熟的在各領域落地還是 porter、porter2 演算法能成為英文 stemming 演算法的首選，相信 snowball 都是重要功臣的之一。

other algorithm：

　　現在來看看其他常見的英文 stemming 演算法，我也從 IR 與 NLP 領域中各取一個常見工具，分別是 Elasticsearch 以及前面出現過的 NLTK，並整理出下表，表示他們是否內建這些常見的英文 stemming 演算法。

	Elasticsearch	NLTK
porter & snowball	O	O
Lovins	O	X
Krovetz stemmer (kstem)	O	X
lancaster stemming	X	O
wordnet	X	O

　　Lovins 演算法是第一個被公開發表的 stemming 演算法 (1968)，雖然在多數情況下它不會是最有效的演算法，但是可能因為其地位而被包含在工具中。

　　kstem 演算法是半詞典的 stemming 演算法，除了判斷條件外它還使用詞典來輔助確認 stemming 後的精確度。也因為這樣，多數情況下比 porter 演算法的積極性更低，換句話說就是他的規則在切割詞綴時較保守。

　　lancaster 演算法則相反，多數情況下比 porter 演算法的積極性更高、規則更激進，使更多的詞被視為同詞幹，這會產生以下效果。

召回率提高：同詞幹的派生詞大多被正確視為同詞幹。
精確度降低：不是同詞幹的派生詞，因為被提取過頭的所以被視為同詞幹。

　　寫個範例來實際看一下多積極，我們採用 snowball 內用來測試 porter 演算法的測試集，其數量為 30428 個詞。

from nltk.stem.snowball import PorterStemmer, EnglishStemmer
from nltk.stem.lancaster import LancasterStemmer
porter = PorterStemmer()
porterStems = set()
porter2 = EnglishStemmer()
porter2Stems = set()
lancaster = LancasterStemmer()
lancasterStems = set()
filename = 'voc.txt'
with open(filename) as file:
    for line in file:
        inputWord = line.rstrip()
        Stems = porter.stem(inputWord)
        porterStems.add(Stems)
        Stems = porter2.stem(inputWord)
        porter2Stems.add(Stems)
        Stems = lancaster.stem(inputWord)
        lancasterStems.add(Stems)
print('test data size: 30428')
print('porter output stem size: ', len(porterStems)) # 18915
print('porter2 output stem size: ', len(porter2Stems)) # 18512
print('lancaster output stem size: ', len(lancasterStems)) # 15065

　　程式中使用 NLTK 來測試該資料集被 porter、porter2、lancaster 演算法所處理過後會剩下多少詞 (詞幹)，可以看見 porter 系列的效果差不多，而 lancaster 演算法整整少了 3000 多個詞，確實更積極的在提取詞幹。

　　最後的 wordnet 則是純查詞典的 lemmatization 演算法，就像前面出現的範例一樣，它需要一點詞性輔助才能做好 lemmatization。

　　不過以上提到的這些都是英文專用的，英文外的語言大概就只能找看看 snowball 是否支援，或尋找該語言使用國家的研究資料。

注意事項：

　　簡介中雖然說到 stemming 對於搜尋引擎來說有好處，但是就如同軟體開發沒有銀彈一樣，演算法絕大部分也都不是萬用的。這部分在 Snowball 官網也有提到 Lovins 演算法的規則與發明者研究領域的詞彙有相關性在。

　　那什麼情況下用常見的 stemming 演算法會效果不佳甚至不 stemming 資料集反而效果更好呢？根據我自己的經驗有兩種常見的情況。

　　一、我正在處理 NLP 語意分析、詞性標註相關的作業，且我使用的演算法依賴詞綴來分析詞性、主詞位置等。這時候 stemming 不只會移除掉有用訊息，更有可能產生出不存在的詞來妨礙我。

　　二、我正在處理的資料集主語言並不是英文 (或其他有綴詞特性的語言)，除了量少導致 stemming 益處不大外，非主語言的英文通常會附加下面兩種特性：

英文在資料集中多為特殊專有名詞，如：品牌、藥物名稱。特殊專有名詞對用戶來說有唯一性，幾乎不存在 stemming 空間。如：adidas 轉變為 adida 顯然不是用戶會期望的。
資料集處於一個容易生出自創詞、portmanteau 的環境中，如：社群網站、遊戲論壇。自創詞除了也算一種特殊專有名詞外，它可能不具備正常語言的規則與結構，使得通用型的 stemming 演算法成效大幅下降。

　　遇到特殊專有名詞、自創詞狀況導致常見 stemming 演算法效能不佳時，可以再仔細想想需求。