詞幹提取

詞法學信息檢索里,詞幹提取是去除詞綴得到詞根的過程─—得到單詞最一般的寫法。對於一個詞的形態詞根,詞幹並不需要完全相同;相關的詞映射到同一個詞幹一般能得到滿意的結果,即使該詞幹不是詞的有效根。從1968年開始在計算機科學領域出現了詞幹提取的相應算法。很多搜尋引擎在處理詞彙時,對同義詞採用相同的詞幹作為查詢拓展,該過程叫做歸併。

詞幹提取項目一般涉及到詞幹提取算法或詞幹提取器。

例子

一個面向英語的詞幹提取器,例如,要識別字符串「cats」、「catlike」和「catty」是基於詞根「cat」;「stemmer」、「stemming」和「stemmed」是基於詞根「stem」。一根詞幹提取算法可以簡化詞 「fishing」、「fished」、「fish」和「fisher」 為同一個詞根「fish」。

歷史背景

第一篇關於詞幹提取器的文章是Julie Beth Lovins英語Julie Beth Lovins在1968年[1]寫的。該文章由於其超前性所以特別出眾,對後人對該領域的研究有深遠的影響。

一個篇較晚一些的文章來自於馬丁·波特英語Martin Porter[2],出版在1980年7月的《程序》雜誌上[3]。該算法被廣泛應用,成為英文詞幹提取中一個事實上的評判標準,被稱為「波特詞幹算法德語Porter-Stemmer-Algorithmus」。Porter 博士因為其在詞幹提取和信息檢索中的成就獲得了2000年的托尼·肯特思獎

很多實現基於Porter詞幹提取的算法而寫出來,並免費分發。然而,大部分這些實現都包含著一些敏感的缺陷。所以,這些詞幹提取器沒有很好地適應算法的潛能。為了消除誤差的來源,Martin Porter在2000年發布了一個基於該算法的官方版本的免費應用軟體[4]。他在自己的工作上進行延伸,建立了一個Snowball算法英語Snowball_programming_language,是編寫詞幹提取算法的框架,並實現了一個改良的英文詞幹提取器可以同時提取一些其他語言。

相應算法

存在著幾種的詞幹提取的算法,它們在性能和準確率還有對詞幹提取中遇到的問題的解決上有所不同。

查找算法

一個簡單的詞幹提取器從查找表中查找詞尾變化。這種方法的優勢是簡單、速度快並容易控制異常情況。但它的缺點是所有的詞尾變化的形式必須明確地包含在查詢表中:一個新的或者是陌生的詞是沒辦法控制的,即使是具有完整的規則(如iPads ~ iPad),並且表會變得非常大。對於具有簡單形態的語言,像英文,表的大小比較適中,但對於變化較大語言,如土耳其語,對於每個詞根都可能有幾百個潛在的變化形式。 一個查找算法初步詞性標註來避免過度詞幹化.[5]

產品技術

查詢表在一個詞幹提取器中的使用通常會產生半自動。例如,如果單詞是「run」,那麼算法會自動生成形式如「running」,「runs」,「runned」和「runly」。最後兩種形式是不正確的,它們也不大可能會在正常的英語文本中出現。

後綴去除算法

後綴去除算法不依賴於包含詞形變換和詞根的查詢表。取而代之的是一個包含規則的具有代表性的小列表提供了相應的方法,通過給定的單詞的形式去查找它的詞根形式。如,其中的一些規則包括:

  • 如果詞的結尾是「ed」,則去掉「ed」
  • 如果詞的結尾是「ing」,則去掉「ing」
  • 如果詞的結尾是「ly」,則去掉「ly」

後綴去除算法相對於一般的蠻力算法能夠得到更為簡單的維護,假設維護人員充分掌握語言學跟形態學方面的知識並且編寫後綴去除規則。在解決一些特殊的關係(如「ran」和「run」)上,後綴去除算法被認為是粗糙的並且性能很差。後綴去除算法的解決方案在那些具有大眾化詞綴但有包含異常的詞性上受到了限制。然而,這是一個問題,因為並非所有的詞類都有這樣一個好制定的規則集。Lemmatisation試圖解決這個問題。

lemmatization算法

一種更加複雜的確定一個詞彙停頓詞的方法是lemmatization。這種處理方式包括首先確定詞彙的發音部分,接著,根據發音的部分確定詞彙的根。 。停頓詞規則隨著單詞的發聲部分的改變而改變。

這種處理方式與其獲得的正確的詞彙目錄有非常高的聯繫。由於在規範化方法上有一些重疊,確定錯誤的目錄或者不能夠找到正確的目錄限制了這方法對suffix stipping 算法的附加好處。基本思想是,如果我們更夠從詞彙的停頓詞中獲取更多的信息,那麼,我們更夠更加準確的使用規範化方法。

隨機算法

隨機算法使用概率方法確定一個詞的詞根。隨機算法在一張詞根表上訓練有影響的詞根形式從而開發出詞根可能性模型。這種模型是典型的複雜語言規則,自然相似性等的表達形式。停頓詞表現為輸入有影響的已經經過訓練的詞根,根據規則,使用模型產生詞根形式。

有些lemmatisatin算法是統計算法。給予一個詞彙,也許屬於多個詞彙的發音部分,對每個部分賦予一個概率值,這需要考慮詞彙環境,也就是上下文,沒有上下文關係的語法不需要考慮附加信息。在有些例子裡,在賦予各個發聲部分一個概率後,概率最大的部分被選中,最合適的規範化方法也被選中用於處理輸入的詞彙,以產生規範化的詞根。

匹配算法

這種算法使用停頓詞資料庫(比如,一個包含停頓詞的文檔)。這些停頓詞,如先前所述,是不需要合法的詞彙的。為了停頓一個詞彙,算法試圖將這些停頓詞與資料庫中的停頓詞匹配,使用各種各樣的約束,如與候選停頓詞的相關性長度(如,be的縮寫,是以下這些詞如be,been,being的詞幹,將不會被考慮為beside的詞幹)。

n元語法分析

一些詞幹提取技術利用一個詞的語境來提取正確的詞幹。

混合法

混合方法同時使用上述的方法中的兩種或更多種。一個簡單的例子是一個後綴樹算法首先會強制諮詢查找表。然而,查找 表不是試圖存儲給定的語言中詞與詞之間所有的的關係,而是保持小規模,僅用於存儲微量的「頻繁使用的例外詞彙」, 如「ran=>run」。如果這個詞不在例外列表中,應用後綴去除算法或lemmatisation算法的輸出結果。

詞綴提取法

在語言學,詞綴一詞是指前綴或後綴。除了處理後綴,有幾種方法也嘗試移除前綴。例如,給一個詞 indefinitely, 首先確定開頭的「in」是前綴是可以被移除的。很多前面的提到的方法都可以適用,但是都屬於詞綴提取。歐洲語言的幾種詞綴提取算法可以在這裡找到。

語言挑戰

由於之前的學術工作都是集中於英語語言,許多其他的語言還沒有被深入研究。 希伯來語和阿拉伯語仍然被認為在詞根上很難研究的語言。語言停頓詞是相當瑣碎的(除了一些偶爾的例子,如dries是動詞dry的第三人稱單數現在時,axes是axe的複數形式),但停頓詞在語態,正詞法,單詞編碼上變得越來越難。希伯來語甚至變更更加複雜。

多語言停頓詞

在接受查詢時,多語言停頓詞應用在兩個或者多個語言相似度語態規則上而不是在單一的語言上。在商業系統中存在這多語言停頓詞

誤差度量

有兩種測量誤差所產生的算法,overstemming和understemming。 。 overstemming 是兩個不同的且有影響的詞在相同的詞根上停止,但不應當有假陽性的錯誤。understemming是兩個不同且有影響的詞在相同的詞根上停止,但不應當有假陰性。詞幹算法試圖以減少每種類型的錯誤,雖然減少一類,可以導致增加。

應用

停頓詞是一種把具有相同意義的詞彙組的詞彙分組的估計方法。例如,一個文檔提及"daffodils"很有可能與一個文檔提及"daffodil"相關(沒有加s).但是在有些例子裡,具有相同詞根形態也會有截然不同的意義,也就是說,這兩個意義很不相同。當用戶查詢marketing,他會對包含markets的文檔非常不滿意。

信息檢索

停頓詞在檢索中是一個非常普遍的元素,如在網頁搜尋引擎中。但在英語搜索中,很快發現,停頓詞的有效性是有限的。然而,這使得早期的信息檢索研究者認為大體上停頓詞是沒有關聯的。一種替代的方式是,基於n-grams方法而不是基於停頓詞的方法。當然,最佳的研究表明,停頓詞在其他語言的搜索中收到的效果比在英語中要好

域分析

停頓詞在領域分析中確定領域詞彙有應用。

商業產品

從上世紀80年代開始,很多商業公司已經開始使用停頓詞了,現在已經在很多預言中開發了算法和詞彙停頓詞 雪球般的停頓詞已經開始和各種各樣的 的商業詞彙停頓詞作比較了。 google search在2003年採用停頓詞。在這之前,搜索fish將不會出現fishing。另外的搜索算法也使用各種各樣的的停頓詞。用簡單的子串搜索也能在搜索fishing時候搜到fish,但不能搜到fishes

參考文獻

  1. ^ Julie Beth Lovins (1968). Development of a stemming algorithm. Mechanical Translation and Computational Linguistics 11:22–31.
  2. ^ 秦續業. 波特词干算法. 2011-05-21 [2015-01-29]. (原始內容存檔於2015-01-29) (中文(簡體)). 
  3. ^ Porter, Martin F. An algorithm for suffix stripping. Program. 1980-07, 14 (3): 130–137 (英語). 
  4. ^ Porter, Martin F. Official website of Porter Stemmer Algorithm. [2012-05-12]. (原始內容存檔於2012-05-14) (英語). 
  5. ^ Yatsko, V.A. Y-stemmer. [2012-05-12]. (原始內容存檔於2012-03-23).