自己動手設計搜尋引擎

程式作品

C 語言

Java

C#

JavaScript

常用函數

文字處理

遊戲程式

衛星定位

系統程式

資料結構

網路程式

自然語言

人工智慧

機率統計

資訊安全

等待完成

訊息

相關網站

參考文獻

最新修改

簡體版

English

程式專案下載:search.zip

摘要

全文檢索系統是利用關鍵字進行索引的建立、組織、存取與呈現的一個系統,目前、Google 是最常被人使用的全文檢索系統,本文將以一個程式設計者的角度,來探討全文系統的設計原理。

簡介

全文檢索系統乃是搜尋引擎的核心,當網頁被抓回硬碟中儲存之後,就可以利用全文檢索的機制進行檢索,其主要的技術有兩項:

  1. 索引系統:建立檢索時使用的索引,使系統能在一兩次的硬碟存取後就查到資料。
  2. 查詢系統:利用索引系統查詢資料後,將查到的資料呈現在顯示介面 (例如:網頁) 上。

索引系統

全文檢索的索引系統,其技術與資料庫的索引技術相當不同,資料庫是利用多元樹的方式建立索引結構,而全文檢索系統是利用赫序 (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]] 中,歡迎自行下載使用。

該主程式展示了該程式的用法,以下列出其程式內容,該程式分為兩個步驟:

  1. 第一個步驟是在建立了 data 資料夾中所有檔案的索引後
  2. 第二個步驟是查詢了『閩南』一詞的出現檔案列表。
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

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License