:::

以PHP與PostgreSQL實作簡易中文全文檢索功能—概念說明篇

5月 17, 2010 10 Comments Edit Post

image

自從PostreSQL 8.3內建了全文檢索的功能之後,我就一直對這功能躍躍欲試。經過這兩天的研讀、嘗試之後,總算也弄出了一點成果。我在Google上並沒有搜尋到很多PHP+PostgreSQL的中文全文檢索功能解決方案,頂多看到中國大陸的文章,或是使用了nlpbampoo這個限定在Linux底下使用的套件,我覺得都不是說很理想。於是我把我所學到的資訊整理一下,在此跟大家分享。

這篇文章預設是給使用PHP發展系統,而也大概知道PostgreSQL的讀者使用,並從全文檢索的概念開始說明起,並提供我寫的簡易範例與安裝教學。由於文章有點長度,我打算分成三篇撰寫。

  1. 概念說明篇 (←現在在此)
  2. 展示安裝篇
  3. 展示說明篇

因為似乎不是一天可以寫得完,所以我就慢慢的一篇一篇地寫囉。


為什麼要需要全文檢索?

全文檢索是一個資訊檢索領域中非常重要的一個議題,知名的Google搜尋引擎就是將全文檢索技術發揮得淋漓盡致的知名成果。在正式介紹全文檢索之前,我想列出幾個您可能會遇到的問題,而這也是您可能會需要全文檢索的原因:

資訊系統就是要有「全文檢索」功能才叫做有SENSE。

這個說得像笑話又好像不是笑話,總之我的確看過有系統介紹廣告強打他們擁有「全文檢索」功能,也看過老師一看到系統就質問「這個有全文檢索嗎?」說不定這功能已經有如品牌標籤一樣,能為您的系統帶來神奇的廣告效果。

LIKE太慢了

基本的搜尋檢索功能是使用SQL的「LIKE」語法來實作。如果您寫過檢索功能,那您應該對以下SQL語法不會太陌生:

SELECT * FROM article WHERE text LIKE '%關鍵字%';

LIKE能使用萬用字元,讓您的搜尋條件變得有彈性。他的作法是採用字串比對,拿起您指定的「關鍵字」,把資料庫中的「TEXT」從頭比對到尾。如果萬用字元一多,那他還要比較個好幾次,才能確認這篇「TEXT」有沒有您指定的「關鍵字」。

當「TEXT」文章內容很短時,您並不太會覺得LIKE有何不妥。但是當您文章的長度達到上萬字,或是您的資料庫中有好幾萬筆文章時,您就會明顯地感受到LIKE的緩慢。

搜尋結果需要依照相關度排序

相關度,這是一個抽象的概念。簡單來說就是搜尋到的結果與您輸入的查詢語句之間的相關程度。相關度越高,表示該文件越符合您輸入的查詢語句;反之,相關度越低,表示該文件可能有涵蓋您指訂的查詢語句,但是並不太重要。

究竟這個「相關度」是依照什麼基準來計算呢?儘管資工領域已經有了TF-IDF之類的技術來計算相關度,但我相信應該大部分的人對於實作這些技術興趣缺缺。

我們需要一個更簡單的方式來計算搜尋結果的相關度,而這件事情PostgreSQl已經幫您作好了。

您需要更有彈性的查詢語句

如果您用過大型系統的搜尋,那麼可能會對於某些搜尋功能中可以加入「&」(表示AND,「且」)、「|」(表示OR,「或」)以及括弧「()」區分條件的查詢感到興趣。儘管這並不是一個很主要的難題,您還是可以用PHP的字串處理來實作LIKE語法,然後取得一個非常複雜、難懂的LIKE條件。

現在PostgreSQL直接支援「&」、「|」以及括弧「()」組成的查詢語法,例如:「(館藏 & 發展) | (社區 | 評估)」。您或許可以考慮那複雜的LIKE,來試著體驗看看這功能的強大。


全文檢索的倒置索引檔

全文檢索並非一般的字串比對,他是藉由搜尋「索引檔」讓檢索的效率大幅提昇的技術。

索引檔是來自於文章(text,為了方便,以下皆將之稱為文章)本身,透過斷詞、計算頻率、記錄位置等程序製作而成。舉例來說,現在有一篇文章的內文如下:

a fat  cat sat on a mat - it ate a fat rats

製作而成索引檔就可能會是:

'ate':9 'cat':3 'fat':2,11 'mat':7 'rat':12 'sat':4

這份索引檔按照了「英文字母」來排序每一個文章中的詞彙,並記錄該詞彙位於文章中的「位置」,同時幫我們把英文作清理語幹(「rats」變成了「rat」)、略過停用字(stop word)「a」、「on」、「-」,讓整個索引檔變得很簡潔。

如果我們要搜尋「rat」的話,系統只需要比對4次就能找到。如果是用傳統的字串比對的話,最笨的方法則需要比對39次才能找到。即使是用人的眼睛來搜尋看看,相信您也會覺得找索引檔會比找文章本身還要容易吧?

這種索引檔正式名稱叫作「倒置索引檔」(inverted index),他將文章內容拆解成詞彙、重新組合了詞彙,讓您搜尋時是透過索引而不必去找文章本身。而這個倒置索引檔也就是整個全文檢索的核心了。以下介紹中提到的索引、倒置索引檔,指得都是同樣的東西喔!


PostgreSQL全文檢索的運作元件

PostgreSQL裡面,全文檢索的用詞叫做「Full Text Search」、「Text Search」或是簡稱「ts」。

他主要提供了以下幾種功能讓您完成全文檢索的工作:

索引:tsvector

這是PostgreSQL用來儲存倒置索引檔的資料類型。如同TEXT、INT、BOOLEAN之類,只是特別是用以作全文檢索倒置索引檔的資料類型。您可以在建立欄位時指定使用tsvector資料型態,或是利用他的函式to_tsvector()將字串轉換成索引的資料型態。

分析索引:to_tsvector()

他的基本用法如下:(詳細說明見此)

to_tsvector([ config regconfig, ] document text) returns tsvector

參數有兩個,第一個regconfig選填,用來指定PostgreSQL的分析器(Parsers);第二個則是要拿來存入索引的文章內容。

舉例來說,您可以這樣使用to_tsvector():

SELECT to_tsvector('english', 'a fat  cat sat on a mat - it ate a fat rats');

如此便會獲得以下結果:

                  to_tsvector
-----------------------------------------------------
 'ate':9 'cat':3 'fat':2,11 'mat':7 'rat':12 'sat':4

目前PostgreSQL的分析器僅有「english」,在處理英文、數字、網址、e-mail等資料上,算是十分地好用,詳細說明請見PostgreSQL的文件。但是由於english是採用半形空白「 」來作為判斷索引的依據,如果要處理像中文這種撰寫時不包含空白的資料來說,就需要搭配斷詞器來使用,稍後我會說明這個解決方案。

查詢語句:tsquery

這是PostgreSQL的查詢語句資料型態,與tsvector正好是相對應的角色。查詢語句包含了要查詢的關鍵字之外,還有「&」、「|」、以及括弧「()」。複雜查詢語句的布林邏輯組合都可以交由tsquery去處理,而不需要您自己實作喔!

分析查詢語句:to_tsquery()

就如to_tsvector一樣,to_tsquery也是將查詢字串轉換成查詢語句資料型態的函式。基本用法如下:

to_tsquery([ config regconfig, ] querytext text) returns tsquery

參數一樣有兩個,前者與to_tsvector一樣是分析器,後者則是要查詢的字串。

舉例來說,您可以這樣使用to_tsquery():

SELECT to_tsquery('english', 'The & Fat & Rats');

得到結果如下:

  to_tsquery   
---------------
 'fat' & 'rat'

分析查詢語句時,就跟分析索引一樣,會經過停用字省略、語幹清除等動作,以便用來查詢索引。然而,to_tsquery一樣會有中文斷詞的問題,這點留到稍後在一起討論。

分析純文字查詢語句:plainto_tsquery()

plainto_tsquery()提供了更簡單的分析方法。他的基本用法與例子都跟to_tsquery()差不多,但是分析器會把半形空白「 」作為&的條件。舉例來說,您可以這樣使用plainto_tsquery():

SELECT plainto_tsquery('english', 'The Fat & Rats:C');

這樣會取得以下結果:

   plainto_tsquery   
---------------------
 'fat' & 'rat' & 'c'

您可以注意到,結果除了像to_tsquery一樣地省略停用字、語幹清除之外,還將空白、標點符號轉換成「&」(AND)條件輸入查詢,因此比起to_tsquery來說更為方便使用。

查詢比對

結合tsvector、to_tsvector()、tsquery、plainto_tsquery()之後,基本的全文檢索引擎就成形了。他們之間可以使用「@@」符號來進行比對,作法如下:

SELECT to_tsvector('fat cats ate fat rats') @@ plainto_tsquery('fat rat');

取得結果將會是「t」,表示有找到。

查詢比對的相關度:ts_rank()跟ts_rank_cd()

這兩個函式可以用來計算索引與查詢語句的相關程度。根據PostgreSQL的說明,他們計算查詢語句在索引中出現的次數、查詢字之間的接近程度以及出現位置。

基本用法如下:

ts_rank([ weights float4[], ] vector tsvector, query tsquery [, normalization integer ]) returns float4
ts_rank_cd([ weights float4[], ] vector tsvector, query tsquery [, normalization integer ]) returns float4

兩個函式的參數都差不多。第一個是權重,可以省略,權重是由4個參數組成,但我到現在還不太會用,詳細還是請去翻翻文件吧。第二、三個是索引與查詢語句,也就是主要計算相關度的來源。最後一個是計算方式的控制,依據輸入的整數不同而會有不同的結果,您也可以同時輸入多個整數,例如「2|4」。計算方法有以下幾種:(4)

  • 0:(預設) 忽略文章長度
  • 1:將相關度除與1+log(文章長度)
  • 2:將相關度除與文章長度
  • 8:將相關度除與文章中字詞出現種類的個數。(例如「fat cats ate fat rats」共有4個種類的字出現)
  • 16:將相關度除與1+log(字詞種類)
  • 32:將相關度除與1+(相關度)

其中,ts_rank_cd()是標準的計算方法,他參考了Clarke、Cormack與Thdhops等人1999年發表的論文「Relevance Ranking for One to Three Term Queries」有興趣的人可以看一看這篇的全文喔!

有了相關度,就能利用他來排序查詢結果了。作法舉例如下:

SELECT title, ts_rank_cd(textsearch, query) AS rank
FROM apod, to_tsquery('neutrino|(dark & matter)') query
WHERE query @@ textsearch
ORDER BY rank DESC LIMIT 10;

結果如下:

                     title                     |   rank
-----------------------------------------------+----------
 Neutrinos in the Sun                          |      3.1
 The Sudbury Neutrino Detector                 |      2.4
 A MACHO View of Galactic Dark Matter          |  2.01317
 Hot Gas and Dark Matter                       |  1.91171
 The Virgo Cluster: Hot Plasma and Dark Matter |  1.90953
 Rafting for Solar Neutrinos                   |      1.9
 NGC 4650A: Strange Galaxy and Dark Matter     |  1.85774
 Hot Gas and Dark Matter                       |   1.6123
 Ice Fishing for Cosmic Neutrinos              |      1.6
 Weak Lensing Distorts the Universe            | 0.818218

PostgreSQL運作架構

小結上述的各種元件,PostgreSQL基本的全文檢索運作圖如下:

image

  1. 將文件轉換成索引。
  2. 將儲存在資料表中。往後文件有更新時,也一併轉換成索引、更新索引檔。
  3. 使用者利用查詢功能輸入關鍵字,系統將之轉換成查詢語句。
  4. 將查詢語句與資料庫中的索引進行比對。
  5. 取得找到的結果。
  6. 計算相關度,並依照相關度排序結果。


中文斷詞

前文中提及PostgreSQL使用的english分析器主要是依據半形空格來切割字句,但是對於中文這種並沒有明顯分割字句的資料,就無能為力了。

沒有中文斷詞的索引

以下是一個失敗的例子:

SELECT to_tsvector('english', '布丁布丁吃布丁的Blog一直都很無聊');

結果如下:

'布丁布丁吃布丁的Blog一直都很無聊':1

對於這種索引檔,就算您查詢語句輸入「布丁」、「Blog」、「無聊」(具體來說就是「SELECT to_tsvector('布丁布丁吃布丁的Blog一直都很無聊') @@ plainto_tsquery('布丁 無聊');」),都將找不到這份文件

有中文斷詞的索引

為了解決這個困擾,您需要先將中文經過斷詞的程序。將「布丁布丁吃布丁的Blog一直都很無聊」切割成「布丁 布丁 吃 布丁 的 Blog 一直 都 很 無聊」的結果,在丟進PostgreSQL的分割器,才能正確地建立起索引檔。

例如:

SELECT to_tsvector('english', '布丁 布丁 吃 布丁 的 Blog 一直 都 很 無聊');

將會取得以下結果:

'吃':3 '很':9 '的':5 '都':8 'blog':6 '一直':7 '布丁':1,2,4 '無聊':10

這樣的索引檔就可以使用SELECT to_tsvector('布丁 布丁 吃 布丁 的 Blog 一直 都 很 無聊') @@ plainto_tsquery('布丁 無聊');查詢,並正確地找出來了。

中文斷詞器

上述過程中,將「布丁布丁吃布丁的Blog一直都很無聊」轉換成「布丁 布丁 吃 布丁 的 Blog 一直 都 很 無聊」的程序,就叫作「中文斷詞」,中國大陸用語則是「中文分詞」。大致上作法是比對「辭典」、常用字、停用字來判斷哪些字是一個詞,因此「辭典」越豐富的斷詞器,其斷詞的成果就會越好。

我國最知名的斷詞器是中研院發展的CKIP。將上述例子丟進線上展示斷詞之後,得到的結果是「布丁(Na) 布丁(Na) 吃(VC) 布丁(Na) 的(DE) Blog(FW) 一直(D) 都(D) 很(Dfa) 無聊(VH)」。後面的括號是詞性,這是CKIP的特色之一。

我們DLLL實驗室也發展了一套斷詞系統ECScanner,他會定期地蒐集網路新聞文章,以擴大他的辭典。斷詞結果是「布丁/布丁/吃/布丁/的/一直/都/很/無聊」,雖然不知為何少掉了「Blog」一詞,總之還是在此廣告一下。

SCWS簡體中文分詞系統

其他還有各種中文斷詞器,用人用C實作、有人用Java實作,也有人利用PHP來實作,那就是SCWS簡體中文分詞系統。由於我論文的系統是採用PHP+PostgreSQL作為架構,所以看到可以以PHP進行的斷詞器,自然是優先考量。作者hightman不僅讓此系統用於簡體中文,也可以讓臺灣主要的正體中文使用。上述例子中斷詞結果是「布丁 布丁 吃 布丁 的 Blog 一直 都 很 無聊」,還算令人滿意的結果。

但是SCWS的省略標點符號的功能我不是很滿意,所以這是我在展示時有稍微處理的部份。

SCWS除了需要安裝PHP的延伸套件以讓PHP能使用斷詞器之外,還需要附帶XDB辭典與設定檔(包含停用字等設定)。稍後在展示安裝篇時,我會再詳細介紹他的安裝方法。

SCWS原本也有用PHP寫成的PSCWS4,但是我嘗試用於正體中文UTF8碼時,卻每每變成亂碼。推測可能是PHP的中文在UTF8中會被視為3字元的原因。儘管PSCWS4的處理速度比起SCWS慢很多,但是安裝上卻比SCWS更為簡單、跨平台。PSCWS4在2008年底停止開發,著實讓人感到遺憾。


以中文斷詞改善全文搜尋架構

image

這次我們把中文斷詞加進整個架構當中,流程如下:

  1. 將文件經過中文斷詞,轉換成索引
  2. 將索引儲存在資料表中。往後文件有更新時,也一併經過中文斷詞、轉換成索引、更新索引檔。
  3. 使用者利用查詢功能輸入關鍵字,系統將之先經過中文斷詞處理,再轉換成查詢語句。
  4. 將查詢語句與資料庫中的索引進行比對。
  5. 取得找到的結果。
  6. 計算相關度,並依照相關度排序結果。

這就是簡單的中文全文檢索引擎的原理囉!


以下是我用來meeting時報告的投影片,就是上述內容的簡單概要版。(SkyDrive下載)


image

其實光是原理的介紹,距離實作可用還有一點點的距離。所以我寫了一個簡單的系統來展示如何利用PHP與PostgreSQL來實作中文全文檢索引擎。不過……就讓我稍微延後一下,接著我還是先回到UML的作業上吧XD

總共10 則留言, (我要發問)

  1. 真是太棒了! 正好最近會用到!!! 真想趕快看到SCWS的安裝方法!!!

    回覆刪除
  2. 有一點觀念方面我一直搞不太清楚, 希望大大可以幫我解答. 就是"中文分詞系統"指的應該是"中文parser"吧? 那中文字典(Dictionary)呢? 做中文全文檢索, 會需要中文字典嗎? 又中文字典如何獲得呢??

    回覆刪除
  3. 因為我可能還要一段時間才會回來繼續補完這篇(遮臉)
    SCWS的安裝方法可以先看這個網頁XD
    http://www.ftphp.com/scws/docs.php#instscws

    中文全文檢索會使用到中文字典,其實分詞或斷詞的原理,主要還是依賴字典的豐富程度。字典越完整,斷詞也就越準確。

    字典檔通常是要錢的,或是各家的機密!
    不過SCWS倒是供人直接下載就是

    請看XDB 词典文件
    http://www.ftphp.com/scws/download.php

    回覆刪除
  4. 感謝您快速的回答~
    其實我比較感興趣的是如何把中文parser跟Dictionary整合到postgres裡面,因為您在文章中一開始就介紹postgres。 請問有方法讓to_tsvector像您文章中提到的可以解析中文嘛?


    SCWS的安裝方法好像純粹是就是把它裝入Linux系統,然後可以讓PHP在網頁調用,好像沒有提到如何加入postgres裡面....???

    回覆刪除
  5. 呵,這就要靠PHP來處理了。
    這個部分的細節正是我接下來要講的……

    不過近期可能比較沒時間寫,七月中之後吧QQ

    回覆刪除
  6. 布丁大, 我不太懂你的意思? 您的意思是要讓 "to_tsvector" 吃中文, 需要靠PHP嗎??

    回覆刪除
  7. 您這篇寫的非常好

    對我還滿大的幫助

    我也有個想法

    適用於

    在標題 或是 網站標題

    我愛吃布丁 Hi love

    用PHP 去分割字串
    英文部分 不分割

    我愛 愛吃 吃布 布丁 Hi love

    這種方法也可以用於

    其他語言 不限定繁體

    撋使嗽SCWS 只能用繁體和簡體

    回覆刪除
  8. 您好,

    一般的斷詞器都會判斷半型空格來分割字串,包括SCWS。
    正常撰寫英文時,就已經有半型空格在內,斷詞器也就會把他依照空格來斷詞囉。
    所以您的方法是正確的,而一般斷詞器也都考慮到這點了!
    而PostgreSQL的全文檢索功能還會把英文做詞幹分析,更為強大。

    請期待下一篇的介紹!……等我論文系統寫到一個段落之後吧orz

    回覆刪除

留言工具: