自己動手設計搜尋引擎

程式作品 C 語言 Java C＃ JavaScript 常用函數 文字處理 遊戲程式 衛星定位 系統程式 資料結構 網路程式 自然語言 人工智慧 機率統計 資訊安全 等待完成 訊息 相關網站 參考文獻 最新修改 簡體版 English

文章 程式專案下載：search.zip 摘要 全文檢索系統是利用關鍵字進行索引的建立、組織、存取與呈現的一個系統，目前、Google 是最常被人使用的全文檢索系統，本文將以一個程式設計者的角度，來探討全文系統的設計原理。 簡介 全文檢索系統乃是搜尋引擎的核心，當網頁被抓回硬碟中儲存之後，就可以利用全文檢索的機制進行檢索，其主要的技術有兩項： 索引系統：建立檢索時使用的索引，使系統能在一兩次的硬碟存取後就查到資料。 查詢系統：利用索引系統查詢資料後，將查到的資料呈現在顯示介面 (例如：網頁) 上。 索引系統 全文檢索的索引系統，其技術與資料庫的索引技術相當不同，資料庫是利用多元樹的方式建立索引結構，而全文檢索系統是利用赫序 (Hash) 函數的方式，建立硬碟中的索引結構。 資料庫的索引技術主要建立在 BTree 這種資料結構上，是利用多元樹的結構排序方式，讓系統可以在數次的存取後，取得所要找的記錄，當多元樹的分支度夠高時，就可以在2-5 次的存取當中，取得所要的記錄。 舉例而言、假如 BTree 的分支度為 100，則五次的硬碟存取共可索引高達 10 的 10 次方，也就是 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|search.zip]] 中，歡迎自行下載使用。 該主程式展示了該程式的用法，以下列出其程式內容，該程式分為兩個步驟： 第一個步驟是在建立了 data 資料夾中所有檔案的索引後 第二個步驟是查詢了『閩南』一詞的出現檔案列表。 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』 ... 更詳細的內容，請直接閱讀程式碼。 結語 全文檢索是文件管理上很常用且強大的工具，在本文中，我們除了介紹其原理之外，並且實作了一個程式，我們以儘可能簡單的方法說明與實作，希望能對您有所幫助。 Facebook 留言 Facebook Wikidot Post preview: Close preview or Sign in as Wikidot user (will not be published) - + Help: wiki text quick reference 授權 本網頁的作者、授權與引用方式 作者 陳鍾誠，於金門大學資訊工程系，電子郵件：wt.ude.uqn|ccc#wt.ude.uqn|ccc，網站：http://ccckmit.wikidot.com。 授權 本文採用創作共用 (Creative Common) 3.0 版的 姓名標示─非商業性─相同方式分享 授權條款，歡迎轉載或修改使用，但若做為商業使用時必須取得授權，引用本文時請參考下列格式。 中文版 (APA格式) 陳鍾誠 (28 Sep 2009 03:31)，(網頁標題) 自己動手設計搜尋引擎，(網站標題) 陳鍾誠的網站，取自 http://ccckmit.wikidot.com/code:searcher ，網頁修改第 4 版。 英文版 (APA格式) Chung-Chen Chen (28 Sep 2009 03:31), Retrieved from http://ccckmit.wikidot.com/code:searcher , Page Revision 4.