全文信息檢索介紹及算法分析

一、摘要
　　本文主要介紹了全文信息檢索的概念、應(yīng)用領(lǐng)域、算法分類、技術(shù)難點和算法比較。及一款實現(xiàn)全文檢索的數(shù)據(jù)結(jié)構(gòu)和算法。

二、什么是全文數(shù)據(jù)庫和全文信息檢索
　　保存在數(shù)據(jù)庫中的記錄數(shù)據(jù)，從類型上可以分為兩種。其一是結(jié)構(gòu)化數(shù)據(jù)，象字符、日期、數(shù)值、貨幣等，這些數(shù)據(jù)都是具有有限長度或固定格式的數(shù)據(jù)；其二是非結(jié)構(gòu)化數(shù)據(jù)，也叫全文數(shù)據(jù)，象簡歷、簡介、論文等，這些數(shù)據(jù)都是以不定長、非固定格式保存的字符型數(shù)據(jù)。
　　現(xiàn)有的數(shù)據(jù)庫系統(tǒng)，都是以結(jié)構(gòu)化數(shù)據(jù)為檢索的主要目標(biāo)，因為實現(xiàn)相對簡單。比如數(shù)值檢索，可以建立一張排序好的索引表，以二分法實現(xiàn)查找，速度很快。但對于非結(jié)構(gòu)化數(shù)據(jù)，即全文數(shù)據(jù)，要想實現(xiàn)檢索，相對難度要大的很多了。
　　當(dāng)然，你也許會說：“這個多簡單呀，把全文數(shù)據(jù)讀到內(nèi)存，然后進行比較查找不就可以了？”。不錯，的確是一個很樸素想法。不過最嚴(yán)重的問題是，如果數(shù)據(jù)庫中有1萬條，10萬條，100萬條記錄的話，可以想象一下檢索所消耗的時間了吧？！如果一個全文數(shù)據(jù)庫系統(tǒng)，對一條檢索命令的響應(yīng)時間超過了半分鐘，那么沒有用戶是能夠容忍的了。
　　因此，全文檢索的主要目的，就是實現(xiàn)對大容量的非結(jié)構(gòu)化數(shù)據(jù)的快速查找。

三、應(yīng)用領(lǐng)域
　　現(xiàn)在，隨著計算機使用的越來越普及，數(shù)據(jù)的積累越來越多，全文檢索的要求也就越來越迫切了。目前，主要的應(yīng)用領(lǐng)域是：圖書館數(shù)據(jù)庫、情報數(shù)據(jù)庫、專利數(shù)據(jù)庫、醫(yī)藥數(shù)據(jù)庫、辦公自動化、歷史資料庫、電子出版系統(tǒng)、等等。

四、算法和算法比較
　　目前，實現(xiàn)全文信息檢索的算法有兩大基本方案，詞索引和字索引。
　　詞索引，以單詞為索引單位的檢索算法。這個技術(shù)是全文檢索技術(shù)的鼻祖（60年代，就已經(jīng)有產(chǎn)品問世）。道理很簡單，計算機是適合于英語語言環(huán)境的，而英語又是以單詞為語言要素。說的更通俗一些，就是每個英文單詞之間都有一個空格。因此，在對全文數(shù)據(jù)庫建立索引的時候，按照單詞劃分建立索引，是即簡單又自然的。我們國家最開始引入全文檢索技術(shù)的時候，是漢化英文的數(shù)據(jù)庫系統(tǒng)，因此也就自然使用了詞索引技術(shù)。但由于中英文環(huán)境中語素的不同特點，使得中文必須要解決分詞的問題。比如對一句話“我是中國人”，那么必須要切分出“我 是 中國 人”這樣的單詞形式。如果是人的大腦來進行分詞判斷，那真是太簡單了，只要有小學(xué)二年級的中文水平，就足夠了。但是，如果想讓計算機能夠進行分詞，卻非常困難。計算機分詞的大致算法是：由文章切分出段落，由段落切分出句子，由句子切分出短語，然后查找詞庫，根據(jù)動詞、連詞、形容詞再進行切分得到所有的單詞。在某些情況下，計算機是根本無法正確進行分詞的。下面是計算機自動分詞所鬧的笑話：

　　(1)我們要積極地主動作好計劃生育工作
計算機愚蠢的分詞結(jié)果：我們 要 積極 地主 動作 好 計劃 生育 工作
評論：我胡漢三又回來啦
后果：檢索“地主”的時候，產(chǎn)生誤查結(jié)果

　　(2)吉林省長春市的人民
計算機愚蠢的分詞結(jié)果：吉林 省長 春市 的 人民
評論：我知道了，吉林有個省長叫“春市”
后果：檢索“吉林省”的時候，產(chǎn)生漏查結(jié)果

　　因此，詞索引的技術(shù)難點是分詞算法。Oracle 和 Notes 等漢化的數(shù)據(jù)庫系統(tǒng)，雖然也都提供了部分全文檢索功能，但都出現(xiàn)了這樣或那樣的問題。分詞算法的提升空間還是有的，需要加入人工智能分析、上下文判斷等技術(shù)。但還有一個致命的弱點，那就是對地名，人名的判斷。

　　字索引，以漢語單字為索引單位的檢索算法。這個也是我推薦的算法，較詞索引更適合于中文環(huán)境。這也就是為什么英文漢化版的全文檢索軟件沒有占領(lǐng)中國市場的主要原因。（目前，本土民族化的軟件，比如手寫板，漢字掃描識別，中文全文信息檢索......還是比國外的同類產(chǎn)品領(lǐng)先很多的。）但字索引也不是沒有缺點，最主要的問題是：

　　(1)、檢索“華人”，會誤查出“中華人民共和國”
　　(2)、檢索中藥“大黃”，會誤查出“大黃緘”，“大黃麻”等完全不同概念的藥品。而這些單詞在英文中是不會出現(xiàn)錯誤的，因為根本就是不同的拼寫。

　　字索引的多查錯誤，也是可以更正的。比如檢索“大黃”的同時，也檢索“大黃緘”，然后排除“大黃緘”的檢索命中點，但這需要付出檢索時間的代價。下表，是字、詞索引方案各項性能的比較：

五、一款中文全文信息檢索算法的實現(xiàn)
　　這個算法是1993年設(shè)計并實現(xiàn)的。十年過去了，新版本中使用了更高級的技術(shù)，因此該算法已經(jīng)廢棄，并得以公開給大家。計算機界有一個著名的命題：程序 = 數(shù)據(jù)結(jié)構(gòu) + 算法。而公開的這個設(shè)計，正是數(shù)據(jù)結(jié)構(gòu)和算法的完美體現(xiàn)。呵呵，不吹牛了，看看如何實現(xiàn)的吧。

I 基本原理

　　圖(一) 展示了在數(shù)據(jù)結(jié)構(gòu)中，最標(biāo)準(zhǔn)的一個單向鏈表的結(jié)構(gòu)示意圖。
　　圖(二) 在標(biāo)準(zhǔn)的單向鏈表中，如果結(jié)點內(nèi)容A、B......N 完全相同的時候，那么我們可以進行變換了，用圖（二）表示，為敘述方便，稱為“單一結(jié)點內(nèi)容鏈表”。即，只需要在頭結(jié)點中表示出內(nèi)容，鏈表中后續(xù)的結(jié)點只有 NEXT 指針域，而省略掉內(nèi)容域。
　　圖(三) 在圖二的“單一結(jié)點內(nèi)容鏈表”中有一個缺點：如果我們得到了任意的一個非頭結(jié)點指針的話，由于是單向鏈表，因此無法回溯得到該結(jié)點所表示的內(nèi)容。因此再次變換，改進為圖（三）的方式，稱為“接續(xù)單向鏈表”。這樣結(jié)構(gòu)的鏈表有如下的特征：
  (1)從頭結(jié)點出發(fā)，可以得到后續(xù)所有結(jié)點的地址；
  (2)從任意一個結(jié)點出發(fā)，當(dāng)沿著指針跳轉(zhuǎn)到“接續(xù)”結(jié)點的時候，就可以得到該結(jié)點所表示的內(nèi)容；
  (3)“接續(xù)鏈表”的存儲空間，比標(biāo)準(zhǔn)的單向鏈表的存儲空間要小很多。

II 構(gòu)造頭結(jié)點
　　設(shè)計一個數(shù)組，用來存儲所有漢字鏈表的頭結(jié)點。GB2312包容了漢字共7673個，用2個字節(jié)來表示一個漢字的內(nèi)碼，第一個字節(jié)的范圍是A0~F7，第二個字節(jié)的范圍是A0~FE。恰好的是，7673個漢字，加上一些常用符號，制表符號，再刨除一些未定義的空區(qū)，正好完全可以用16K字節(jié)的存儲空間來全部表示出來。

　　和帶有接點內(nèi)容的鏈表有所不同的是，在這個頭結(jié)點中，只有指針而沒有結(jié)點內(nèi)容。結(jié)點內(nèi)容（漢字）其實是用數(shù)組的偏移地址來間接表示的。如上圖所示，數(shù)組中偏移為 0000 的指針?biāo)硎镜臐h字是 A0A0 （即，全角空格）。

III 鏈表結(jié)構(gòu)
　　由于每個指針只用2個字節(jié)表示，因此，鏈表指針的范圍是 0000 - FFFF，64K大小。為了使鏈表能超越 64K 的范圍，那么現(xiàn)在正好可以用“接續(xù)鏈表”構(gòu)造出來了。下圖表現(xiàn)了整個數(shù)據(jù)庫的結(jié)構(gòu)。


IV 實現(xiàn)檢索
　　在下圖的一個數(shù)據(jù)庫結(jié)構(gòu)中，我們實現(xiàn)單字“中”的檢索和單詞“中國”的檢索。三種顏色，分別表示數(shù)據(jù)庫中的三條記錄的內(nèi)容區(qū)域。

　　檢索“中”。根據(jù)“中”的內(nèi)碼 D6D0 可以在頭指針區(qū)域中定位到起點指針，然后按照鏈表分別在數(shù)據(jù)庫第一條記錄找到2個命中點，在第二條記錄中找到1個命中點，而第三條記錄沒有命中。這時，指針到達“接續(xù)的頭指針”區(qū)域，然后就可以繼續(xù)檢索下一個數(shù)據(jù)區(qū)了......直到結(jié)束。
　　檢索“中國”。根據(jù)“中”和“國”的內(nèi)碼，定位頭指針。這一對指針連續(xù)在鏈表中跳轉(zhuǎn)，如果兩個指針在跳轉(zhuǎn)的時候恰好在數(shù)據(jù)區(qū)的地址偏移中相鄰，則表示命中這個單詞了（第一條記錄中，畫紅圈部分）。然后，這對指針繼續(xù)向后跳轉(zhuǎn)，直到結(jié)束。

V 提取記錄內(nèi)容
　　由于記錄內(nèi)容中的漢字，已經(jīng)用鏈表的指針表示了，那么如何提取還原出原始的漢字文章那？從數(shù)據(jù)區(qū)記錄的開始，按照鏈表向后跳轉(zhuǎn)，肯定會跳轉(zhuǎn)到“接續(xù)頭指針”的區(qū)域中，那么這時候根據(jù)指針?biāo)诘刂?，計算出相對偏移，就得到它表示的漢字了。重復(fù)操作，就能把原始的漢字文章全部還原出來。

VI 記錄的入庫
　　不用多說了吧？把指向“接續(xù)頭指針”的鏈表斷開，連接上新的地址，而該地址的存儲的指針指向“接續(xù)頭指針”。

VII 算法特點
　　(1)算法呈現(xiàn)出字索引方式。能夠滿足“查全”的功能。
　　(2)原始文本數(shù)據(jù)追加入庫時，由于入庫就是構(gòu)造指針的過程，并同時建立了索引。入庫數(shù)據(jù)量和處理時間呈線性關(guān)系。速度很快。
　　(3)文字信息在數(shù)據(jù)庫中全部以指針存儲，本身具有加密的功能。
　　(4)如果有某個指針在存取過程中發(fā)生錯誤，則該指針的后續(xù)必將產(chǎn)生連續(xù)錯誤且無法糾正，這是該算法的主要缺陷。
　　(5)數(shù)據(jù)區(qū)48K，頭指針（接續(xù)）區(qū)16K，索引比為33%。這是全世界現(xiàn)有全文算法中，索引比最小的。
　　(6)該算法只適合于GB2312字符集。由于GBK，UNICODE，BIG5包含更多的漢字，會導(dǎo)致頭指針（接續(xù)）區(qū)域的擴大，而數(shù)據(jù)區(qū)被壓縮，因此失去了算法意義。
　　(7)檢索時，需要按照64K為單位讀取數(shù)據(jù)庫文件（這正好適用于16位操作系統(tǒng)），檢索效率會隨著數(shù)據(jù)庫的增大而減小。因此該算法適合于小型數(shù)據(jù)庫的全文檢索系統(tǒng)(10萬條記錄以內(nèi)，總?cè)萘?00M以下)。

六、結(jié)束語
　　學(xué)習(xí)計算機軟件設(shè)計，最重要的一門課程就是《數(shù)據(jù)結(jié)構(gòu)》。這套全文檢索算法，正是依靠精妙的數(shù)據(jù)結(jié)構(gòu)構(gòu)建出來的，其實說起來也很簡單，就是鏈表數(shù)組。1993年的時候，PC機大多運行著 DOS + WINDOWS 3.1 + 中文環(huán)境（GB2312），這套算法正是適應(yīng)當(dāng)時的環(huán)境而設(shè)計的。現(xiàn)在十年過去了，隨著計算機軟硬環(huán)境的提升和全文數(shù)據(jù)量的增長，該算法雖然已經(jīng)廢棄，但通過該算法，大家一定能體會出“數(shù)據(jù)結(jié)構(gòu)”的重要性。1998年，我又設(shè)計了新的全文檢索算法，使用的是“數(shù)據(jù)結(jié)構(gòu)”中的“散列表”。不過現(xiàn)在保密，也許10年后再公布吧，嘿嘿。