全文檢索系統的原理摘要全文檢索系統是利用關鍵字進行索引的建立、組織、存取與呈現的一個系統，目前、Google 是最常 被人使用的全文檢索系統，本文將以一個程式設計者的角度，來探討全文系統的設計原理。簡介全文檢索系統乃是搜尋引擎的核心，當網頁被抓回硬碟中儲存之後，就可以利用全文檢索的機制 進行檢索，其主要的技術有兩項：
索引系統全文檢索的索引系統，其技術與資料庫的索引技術相當不同，資料庫是利用多元樹的方式 建立索引結構，而全文檢索系統是利用赫序 (Hash) 函數的方式，建立硬碟中的索引結構。資料庫的索引技術主要建立在 BTree 這種資料結構上，是利用多元樹的結構排序方式， 讓系統可以在數次的存取後，取得所要找的記錄，當多元樹的分支度夠高時，就可以在 2-5 次的存取當中，取得所要的記錄。 舉例而言、假如 BTree 的分支度為 100，則五次的硬碟存取共可索引高達 1010 ，也就是 100 億筆的資料，因此、BTree 廣泛被用在資料庫的索引上，成為資料庫的核心結構。 全文檢索的索引方式，則是直接將每個關鍵字出現的地點，全數編入到索引結構中，以下舉一個 範例說明之。 檔案：王小明上學記.txt 一個中文的全文檢索系統，由於無法進行斷詞，因此、通常會以一字詞 + 二字詞的方式，將 所有的詞組編入到索引當中，假設該檔案的編號為 7 號檔，則其建完索引後的一個可能狀況 如下： 王：3, 5, 7, 8, ... 小：2, 4, 7, 9, ... 明：7, 11, ... 今：3, 4, 7, ... ... 撿：5, 7, ... 到：7, 8, ... 了：7, 10, ... ... 王小：6, 7, ... 小明：1, 2, 7, ... 明今：1, 6, 7, ... ... 撿到：2, 7, ... 到了：3, 7, ... 然而、若將所有的二字詞都建成一個單獨的檔案進行索引，則會造成檔案的數量過多， 成為作業系統或資料結構上的負擔，因此、通常全文檢索系統不會直接將所有詞彙建成單獨的索引檔， 而是再經過一個赫序 (Hash) 函數，將這接詞彙對應到其編碼上，假設我們的赫序函數 最後採用 mod 10000 的方式，則上述範例的一個可能對映如下： 0394：3, 5, 7, 8, ... H(王)=0394 H(到了)=0394 9382：2, 4, 7, 9, ... H(小)=9382 0395：7, 11, ... H(明)=0395 9384：3, 4, 7, ... H(今)=9384 ... 0939：5, 7, ... H(撿)=0939 0294：7, 8, ... H(到)=0294 2334：7, 10, ... H(了)=2334 ... 9487：3, 6, 7, 10, 11, 13 ... H(王小)=9487 6734：1, 3, 7, 12, 13, 15, ... H(小明)=6734 9123：1, 6, 7, ... H(明今)=9123 ... 9876：2, 7, ... H(撿到)=9876 當我們採用赫序函數之後，就可以將總索引項限制在 10000 個項目以內，如此、可以減輕 作業系統與資料結構的負擔，使得整體的效率提升，也降低了索引程式的複雜性。 查詢系統一但索引已經建立，則當使用者要查詢哪些文章中曾經出現過這些字元時，就可以利用同樣的 方式，將輸入的關鍵字分解後，取的對應的文件列表，經合併後就可以取得對映的文件了。以下延續上述的範例，假設使用者於介面上打入 『王小明』 三個字。 此時系統會將其拆解成：王+小+明+王小+小明 進入查詢系統，並且以較長詞優先的方式，進行 查詢，也就是以『王小+小明』的組合來查詢，以下是查詢的結果： 9487：3, 6, 7, 10, 11, 13 ... H(王小) 6734：1, 3, 7, 12, 13, 15, ... H(小明) 最後、將這些組合合併之，得到： 3, 7, 13, ... 這些文件代碼所代表的就是可能包函『王小明』一詞的所有文件，然而、由於赫序函數的碰撞可能性， 與詞彙可能並非連續出現的關係 (例如：王小姐與李小明)，因此、這並不保證每一個檔案都會包含 『王小明』這個詞彙，因此、必須在實際讀取檔案後進行字串比對式的檢查，以確認該詞彙確實出現後， 再將其顯示在查詢結果中。 一個簡單的全文檢索程式我們開發了一個簡單的全文檢索程式，該程式並非一個完整的系統，不包含使用者介面等模組， 只有最核心的索引建立與檢索函數，主要目的是用來說明了全文檢索系統的製作原理，若您希望 設計一個簡單的系統，歡迎直接修改我們的程式，我們並不主張程式的所有權。程式碼中的 search.java 檔是檢索系統的核心，包含索引建立與查詢函數都在這個物件當中完成， 而 STR.java 主要是用來做字串處理與檔案輸出入用的，其可供下載的完整套件(包含測試資料) 位於 search.zip 中，歡迎自行下載使用。 該主程式展示了該程式的用法，以下列出其程式內容，該程式分為兩個步驟：
public static void main(String[] args) throws Exception {
// 建立 data 資料夾中的全文索引，放在 data/idx/ 目錄中。
Search indexer = new Search("data/");
indexer.indexDir();
indexer.flush();
// 本段落將搜尋 『閩南』一詞所出現過的檔案
String[] files = indexer.search("閩南");
System.out.println(Arrays.asList(files));
indexer.close();
}
若您還沒有執行過該程式，則會先建立索引後再進行查詢，其結果如下所示： 
若您已經執行過該程式，則索引已經建立，因此不會再重複建立索引，其結果如下所示： 
當您建立了索引之後，目標資料夾下面會出現一個子資料夾 /Idx，這是用來儲存索引的資料夾， 以下是這個資料夾中一些重要檔案的描述
/Idx/files.lst 儲存已經建立過索引的檔案列表
/Idx/files.hash 儲存這些檔案的 hash 與在 files.lst 中的位址 (offset)
用途是在檢查一個檔案是否曾經建立過索引，以免重複建立。
/Idx/*.idx 儲存全文索引的檔案
在測試範例中，/Idx/files.lst 建立後的內容如下所示： 台北人與金門人.htm 台北人與金門人.wiki 如何在金門地區購買房地產.htm 如何在金門地區購買房地產.wiki 我在資訊管理上的失敗經驗.htm 我在資訊管理上的失敗經驗.wiki 我該學哪種程式語言呢.htm 我該學哪種程式語言呢.wiki 金門與台北的閩南語.htm 金門與台北的閩南語.wiki 其中、用來儲存全文索引的檔案，是採用 (詞彙=檔案代碼) 的方式紀錄的，以下以測試範例中的 36b.idx 舉例說明：
檔案：36b.idx
內容：兩大=0 供大=0 兩大=14 供大=14 ，無=29 閩南=29 證=29 ，無=47 閩南=47 證=47
得大=66 序大=66 得大=84 序大=84 閩南=d8 南=d8 證=d8 閩南=f0 南=f0 證=f0
在我們的程式中，以該檔案名稱在 files.lst 中的位址為檔案代碼，這樣設計的好處是一但取得索引檔(例如：36b.idx) 的內容後，立刻可以直接讀出檔案名稱，而不需要經過另一次的轉換程序。 因此、上述範例會被程式解讀如下： 兩大=0 代表『兩大』這個詞在代碼為 0 的檔案中出現過，也就是 『台北人與金門人.htm』 ... 閩南=29 代表『閩南』這個詞在代碼為 29 的檔案中出現過，也就是 『如何在金門地區購買房地產.htm』 ... 更詳細的內容，請直接閱讀程式碼。 結語全文檢索是文件管理上很常用且強大的工具，在本文中，我們除了介紹其原理之外，並且實作了一個程式， 我們以儘可能簡單的方法說明與實作，希望能對您有所幫助。 |
|||||
|
作者：陳鍾誠 E-mail:ccc@kmit.edu.tw。  本著作係採用創用 CC 「姓名標示─相同方式分享 2.5 台灣版」授權條款釋出。 大學課程網 | 手機入口網 |