程式作品C 語言JavaC#JavaScript常用函數文字處理遊戲程式衛星定位系統程式資料結構網路程式自然語言人工智慧機率統計資訊安全等待完成訊息相關網站參考文獻最新修改簡體版English |
程式專案下載:search.zip 摘要全文檢索系統是利用關鍵字進行索引的建立、組織、存取與呈現的一個系統,目前、Google 是最常被人使用的全文檢索系統,本文將以一個程式設計者的角度,來探討全文系統的設計原理。 簡介全文檢索系統乃是搜尋引擎的核心,當網頁被抓回硬碟中儲存之後,就可以利用全文檢索的機制進行檢索,其主要的技術有兩項:
索引系統全文檢索的索引系統,其技術與資料庫的索引技術相當不同,資料庫是利用多元樹的方式建立索引結構,而全文檢索系統是利用赫序 (Hash) 函數的方式,建立硬碟中的索引結構。 資料庫的索引技術主要建立在 BTree 這種資料結構上,是利用多元樹的結構排序方式,讓系統可以在數次的存取後,取得所要找的記錄,當多元樹的分支度夠高時,就可以在2-5 次的存取當中,取得所要的記錄。 舉例而言、假如 BTree 的分支度為 100,則五次的硬碟存取共可索引高達 10 的 10 次方,也就是 100 億筆的資料,因此、BTree 廣泛被用在資料庫的索引上,成為資料庫的核心結構。 全文檢索的索引方式,則是直接將每個關鍵字出現的地點,全數編入到索引結構中,以下舉一個範例說明之。
一個中文的全文檢索系統,由於無法進行斷詞,因此、通常會以一字詞 + 二字詞的方式,將所有的詞組編入到索引當中,假設該檔案的編號為 7 號檔,則其建完索引後的一個可能狀況如下:
然而、若將所有的二字詞都建成一個單獨的檔案進行索引,則會造成檔案的數量過多,成為作業系統或資料結構上的負擔,因此、通常全文檢索系統不會直接將所有詞彙建成單獨的索引檔,而是再經過一個赫序 (Hash) 函數,將這接詞彙對應到其編碼上,假設我們的赫序函數最後採用 mod 10000 的方式,則上述範例的一個可能對映如下:
當我們採用赫序函數之後,就可以將總索引項限制在 10000 個項目以內,如此、可以減輕作業系統與資料結構的負擔,使得整體的效率提升,也降低了索引程式的複雜性。 查詢系統一但索引已經建立,則當使用者要查詢哪些文章中曾經出現過這些字元時,就可以利用同樣的方式,將輸入的關鍵字分解後,取的對應的文件列表,經合併後就可以取得對映的文件了。 以下延續上述的範例,假設使用者於介面上打入 『王小明』 三個字。 此時系統會將其拆解成:王+小+明+王小+小明 進入查詢系統,並且以較長詞優先的方式,進行查詢,也就是以『王小+小明』的組合來查詢,以下是查詢的結果:
最後、將這些組合合併之,得到:
這些文件代碼所代表的就是可能包函『王小明』一詞的所有文件,然而、由於赫序函數的碰撞可能性,與詞彙可能並非連續出現的關係 (例如:王小姐與李小明),因此、這並不保證每一個檔案都會包含『王小明』這個詞彙,因此、必須在實際讀取檔案後進行字串比對式的檢查,以確認該詞彙確實出現後,再將其顯示在查詢結果中。 一個簡單的全文檢索程式我們開發了一個簡單的全文檢索程式,該程式並非一個完整的系統,不包含使用者介面等模組,只有最核心的索引建立與檢索函數,主要目的是用來說明了全文檢索系統的製作原理,若您希望設計一個簡單的系統,歡迎直接修改我們的程式,我們並不主張程式的所有權。 程式碼中的 search.java 檔是檢索系統的核心,包含索引建立與查詢函數都在這個物件當中完成,而 STR.java 主要是用來做字串處理與檔案輸出入用的,其可供下載的完整套件(包含測試資料)位於 [[../search.zip|search.zip]] 中,歡迎自行下載使用。 該主程式展示了該程式的用法,以下列出其程式內容,該程式分為兩個步驟:
若您還沒有執行過該程式,則會先建立索引後再進行查詢,若您已經執行過該程式,則索引已經建立,因此不會再重複建立索引。 當您建立了索引之後,目標資料夾下面會出現一個子資料夾 /Idx,這是用來儲存索引的資料夾,以下是這個資料夾中一些重要檔案的描述
在測試範例中,/Idx/files.lst 建立後的內容如下所示:
其中、用來儲存全文索引的檔案,是採用 (詞彙=檔案代碼) 的方式紀錄的,以下以測試範例中的 36b.idx 的內容
在我們的程式中,以該檔案名稱在 files.lst 中的位址為檔案代碼,這樣設計的好處是一但取得索引檔(例如:36b.idx) 因此、上述範例會被程式解讀如下:
更詳細的內容,請直接閱讀程式碼。 結語全文檢索是文件管理上很常用且強大的工具,在本文中,我們除了介紹其原理之外,並且實作了一個程式,我們以儘可能簡單的方法說明與實作,希望能對您有所幫助。 |
自己動手設計搜尋引擎
page revision: 4, last edited: 19 Oct 2010 09:11
Post preview:
Close preview