以PHP與PostgreSQL實作簡易中文全文檢索功能—概念說明篇
以PHP與PostgreSQL實作簡易中文全文檢索功能—概念說明篇
自從PostreSQL 8.3內建了全文檢索的功能之後，我就一直對這功能躍躍欲試。經過這兩天的研讀、嘗試之後，總算也弄出了一點成果。我在Google上並沒有搜尋到很多PHP+PostgreSQL的中文全文檢索功能解決方案，頂多看到中國大陸的文章，或是使用了nlpbampoo這個限定在Linux底下使用的套件，我覺得都不是說很理想。於是我把我所學到的資訊整理一下，在此跟大家分享。
這篇文章預設是給使用PHP發展系統，而也大概知道PostgreSQL的讀者使用，並從全文檢索的概念開始說明起，並提供我寫的簡易範例與安裝教學。由於文章有點長度，我打算分成三篇撰寫。
- 概念說明篇 (←現在在此)
- 展示安裝篇
- 展示說明篇
因為似乎不是一天可以寫得完，所以我就慢慢的一篇一篇地寫囉。
為什麼要需要全文檢索？
全文檢索是一個資訊檢索領域中非常重要的一個議題，知名的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基本的全文檢索運作圖如下：
- 將文件轉換成索引。
- 將儲存在資料表中。往後文件有更新時，也一併轉換成索引、更新索引檔。
- 使用者利用查詢功能輸入關鍵字，系統將之轉換成查詢語句。
- 將查詢語句與資料庫中的索引進行比對。
- 取得找到的結果。
- 計算相關度，並依照相關度排序結果。
中文斷詞
前文中提及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年底停止開發，著實讓人感到遺憾。
以中文斷詞改善全文搜尋架構
這次我們把中文斷詞加進整個架構當中，流程如下：
- 將文件經過中文斷詞，轉換成索引
- 將索引儲存在資料表中。往後文件有更新時，也一併經過中文斷詞、轉換成索引、更新索引檔。
- 使用者利用查詢功能輸入關鍵字，系統將之先經過中文斷詞處理，再轉換成查詢語句。
- 將查詢語句與資料庫中的索引進行比對。
- 取得找到的結果。
- 計算相關度，並依照相關度排序結果。
這就是簡單的中文全文檢索引擎的原理囉！
以下是我用來meeting時報告的投影片，就是上述內容的簡單概要版。(SkyDrive下載)
其實光是原理的介紹，距離實作可用還有一點點的距離。所以我寫了一個簡單的系統來展示如何利用PHP與PostgreSQL來實作中文全文檢索引擎。不過……就讓我稍微延後一下，接著我還是先回到UML的作業上吧XD
(more...)
Comments