全文信息檢索介紹及算法分析
一、摘要
本文主要介紹了全文信息檢索的概念、應用領(lǐng)域、算法分類(lèi)、技術(shù)難點(diǎn)和算法比較。及一款實(shí)現全文檢索的數據結構和算法。
二
、什么是全文數據庫和全文信息檢索 保存在數據庫中的記錄數據，從類(lèi)型上可以分為兩種。其一是結構化數據，象字符、日期、數值、貨幣等，這些數據都是具有有限長(cháng)度或固定格式的數據；其二是非結構化數據，也叫全文數據，象簡(jiǎn)歷、簡(jiǎn)介、論文等，這些數據都是以不定長(cháng)、非固定格式保存的字符型數據。
現有的數據庫系統，都是以結構化數據為檢索的主要目標，因為實(shí)現相對簡(jiǎn)單。比如數值檢索，可以建立一張排序好的索引表，以二分法實(shí)現查找，速度很快。但對于非結構化數據，即全文數據，要想實(shí)現檢索，相對難度要大的很多了。
當然，你也許會(huì )說(shuō)：“這個(gè)多簡(jiǎn)單呀，把全文數據讀到內存，然后進(jìn)行比較查找不就可以了？”。不錯，的確是一個(gè)很樸素想法。不過(guò)最嚴重的問(wèn)題是，如果數據庫中有1萬(wàn)條，10萬(wàn)條，100萬(wàn)條記錄的話(huà)，可以想象一下檢索所消耗的時(shí)間了吧？！如果一個(gè)全文數據庫系統，對一條檢索命令的響應時(shí)間超過(guò)了半分鐘，那么沒(méi)有用戶(hù)是能夠容忍的了。
因此，全文檢索的主要目的，就是實(shí)現對大容量的非結構化數據的快速查找。
三、應用領(lǐng)域 現在，隨著(zhù)計算機使用的越來(lái)越普及，數據的積累越來(lái)越多，全文檢索的要求也就越來(lái)越迫切了。目前，主要的應用領(lǐng)域是：圖書(shū)館數據庫、情報數據庫、專(zhuān)利數據庫、醫藥數據庫、辦公自動(dòng)化、歷史資料庫、電子出版系統、等等。
四、算法和算法比較
目前，實(shí)現全文信息檢索的算法有兩大基本方案，
詞索引和
字索引。
詞索引，以單詞為索引單位的檢索算法。這個(gè)技術(shù)是全文檢索技術(shù)的鼻祖（60年代，就已經(jīng)有產(chǎn)品問(wèn)世）。道理很簡(jiǎn)單，計算機是適合于英語(yǔ)語(yǔ)言環(huán)境的，而英語(yǔ)又是以單詞為語(yǔ)言要素。說(shuō)的更通俗一些，就是每個(gè)英文單詞之間都有一個(gè)空格。因此，在對全文數據庫建立索引的時(shí)候，按照單詞劃分建立索引，是即簡(jiǎn)單又自然的。我們國家最開(kāi)始引入全文檢索技術(shù)的時(shí)候，是漢化英文的數據庫系統，因此也就自然使用了
詞索引技術(shù)。但由于中英文環(huán)境中語(yǔ)素的不同特點(diǎn)，使得中文必須要解決
分詞的問(wèn)題。比如對一句話(huà)“我是中國人”，那么必須要切分出“我 是 中國 人”這樣的單詞形式。如果是人的大腦來(lái)進(jìn)行分詞判斷，那真是太簡(jiǎn)單了，只要有小學(xué)二年級的中文水平，就足夠了。但是，如果想讓計算機能夠進(jìn)行分詞，卻非常困難。計算機分詞的大致算法是：由文章切分出段落，由段落切分出句子，由句子切分出短語(yǔ)，然后查找詞庫，根據動(dòng)詞、連詞、形容詞再進(jìn)行切分得到所有的單詞。在某些情況下，計算機是根本無(wú)法正確進(jìn)行分詞的。下面是計算機自動(dòng)分詞所鬧的笑話(huà)：
(1)我們要積極地主動(dòng)作好計劃生育工作
計算機愚蠢的分詞結果：我們 要 積極 地主 動(dòng)作 好 計劃 生育 工作
評論：我胡漢三又回來(lái)啦
后果：檢索“地主”的時(shí)候，產(chǎn)生誤查結果
(2)吉林省長(cháng)春市的人民
計算機愚蠢的分詞結果：吉林 省長(cháng) 春市 的 人民
評論：我知道了，吉林有個(gè)省長(cháng)叫“春市”
后果：檢索“吉林省”的時(shí)候，產(chǎn)生漏查結果
因此，
詞索引的技術(shù)難點(diǎn)是
分詞算法。Oracle 和 Notes 等漢化的數據庫系統，雖然也都提供了部分全文檢索功能，但都出現了這樣或那樣的問(wèn)題。分詞算法的提升空間還是有的，需要加入人工智能分析、上下文判斷等技術(shù)。但還有一個(gè)致命的弱點(diǎn)，那就是對地名，人名的判斷。
字索引，以漢語(yǔ)單字為索引單位的檢索算法。這個(gè)也是我推薦的算法，較詞索引更適合于中文環(huán)境。這也就是為什么英文漢化版的全文檢索軟件沒(méi)有占領(lǐng)中國市場(chǎng)的主要原因。（目前，本土民族化的軟件，比如手寫(xiě)板，漢字掃描識別，中文全文信息檢索......還是比國外的同類(lèi)產(chǎn)品領(lǐng)先很多的。）但字索引也不是沒(méi)有缺點(diǎn)，最主要的問(wèn)題是：
(1)、檢索“華人”，會(huì )誤查出“中華人民共和國”
(2)、檢索中藥“大黃”，會(huì )誤查出“大黃緘”，“大黃麻”等完全不同概念的藥品。而這些單詞在英文中是不會(huì )出現錯誤的，因為根本就是不同的拼寫(xiě)。
字索引的多查錯誤，也是可以更正的。比如檢索“大黃”的同時(shí)，也檢索“大黃緘”，然后排除“大黃緘”的檢索命中點(diǎn)，但這需要付出檢索時(shí)間的代價(jià)。下表，是字、詞索引方案各項性能的比較：
索引方式 | 索引比 | 索引速度 | 檢索速度 | 誤查 | 漏查 |
詞索引 | 0.8 ~ 2.0 | 慢 | 快 | 有 | 有 |
字索引 | 0.3 ~ 2.0 | 稍快 | 稍慢 | 有 | 無(wú) |
五、一款中文全文信息檢索算法的實(shí)現
這個(gè)算法是1993年設計并實(shí)現的。十年過(guò)去了，新版本中使用了更高級的技術(shù)，因此該算法已經(jīng)廢棄，并得以公開(kāi)給大家。計算機界有一個(gè)著(zhù)名的命題：程序 = 數據結構 + 算法。而公開(kāi)的這個(gè)設計，正是數據結構和算法的完美體現。呵呵，不吹牛了，看看如何實(shí)現的吧。
I 基本原理 圖(一) 展示了在數據結構中，最標準的一個(gè)單向鏈表的結構示意圖。
圖(二) 在標準的單向鏈表中，如果結點(diǎn)內容A、B......N 完全相同的時(shí)候，那么我們可以進(jìn)行變換了，用圖（二）表示，為敘述方便，稱(chēng)為“單一結點(diǎn)內容鏈表”。即，只需要在頭結點(diǎn)中表示出內容，鏈表中后續的結點(diǎn)只有 NEXT 指針域，而省略掉內容域。
圖(三) 在圖二的“單一結點(diǎn)內容鏈表”中有一個(gè)缺點(diǎn)：如果我們得到了任意的一個(gè)非頭結點(diǎn)指針的話(huà)，由于是單向鏈表，因此無(wú)法回溯得到該結點(diǎn)所表示的內容。因此再次變換，改進(jìn)為圖（三）的方式，稱(chēng)為“接續單向鏈表”。這樣結構的鏈表有如下的特征：
(1)從頭結點(diǎn)出發(fā)，可以得到后續所有結點(diǎn)的地址；
(2)從任意一個(gè)結點(diǎn)出發(fā)，當沿著(zhù)指針跳轉到“接續”結點(diǎn)的時(shí)候，就可以得到該結點(diǎn)所表示的內容；
(3)“接續鏈表”的存儲空間，比標準的單向鏈表的存儲空間要小很多。
II 構造頭結點(diǎn)
設計一個(gè)數組，用來(lái)存儲所有漢字鏈表的頭結點(diǎn)。GB2312包容了漢字共7673個(gè)，用2個(gè)字節來(lái)表示一個(gè)漢字的內碼，第一個(gè)字節的范圍是A0~F7，第二個(gè)字節的范圍是A0~FE。恰好的是，7673個(gè)漢字，加上一些常用符號，制表符號，再刨除一些未定義的空區，正好完全可以用16K字節的存儲空間來(lái)全部表示出來(lái)。
和帶有接點(diǎn)內容的鏈表有所不同的是，在這個(gè)頭結點(diǎn)中，只有指針而沒(méi)有結點(diǎn)內容。結點(diǎn)內容（漢字）其實(shí)是用數組的偏移地址來(lái)間接表示的。如上圖所示，數組中偏移為 0000 的指針所表示的漢字是 A0A0 （即，全角空格）。
III 鏈表結構
由于每個(gè)指針只用2個(gè)字節表示，因此，鏈表指針的范圍是 0000 - FFFF，64K大小。為了使鏈表能超越 64K 的范圍，那么現在正好可以用“接續鏈表”構造出來(lái)了。下圖表現了整個(gè)數據庫的結構。
IV 實(shí)現檢索
在下圖的一個(gè)數據庫結構中，我們實(shí)現單字“中”的檢索和單詞“中國”的檢索。三種顏色，分別表示數據庫中的三條記錄的內容區域。
檢索“中”。根據“中”的內碼 D6D0 可以在頭指針區域中定位到起點(diǎn)指針，然后按照鏈表分別在數據庫第一條記錄找到2個(gè)命中點(diǎn)，在第二條記錄中找到1個(gè)命中點(diǎn)，而第三條記錄沒(méi)有命中。這時(shí)，指針到達“接續的頭指針”區域，然后就可以繼續檢索下一個(gè)數據區了......直到結束。
檢索“中國”。根據“中”和“國”的內碼，定位頭指針。這一對指針連續在鏈表中跳轉，如果兩個(gè)指針在跳轉的時(shí)候恰好在數據區的地址偏移中相鄰，則表示命中這個(gè)單詞了（第一條記錄中，畫(huà)紅圈部分）。然后，這對指針繼續向后跳轉，直到結束。
V 提取記錄內容
由于記錄內容中的漢字，已經(jīng)用鏈表的指針表示了，那么如何提取還原出原始的漢字文章那？從數據區記錄的開(kāi)始，按照鏈表向后跳轉，肯定會(huì )跳轉到“接續頭指針”的區域中，那么這時(shí)候根據指針所在地址，計算出相對偏移，就得到它表示的漢字了。重復操作，就能把原始的漢字文章全部還原出來(lái)。
VI 記錄的入庫
不用多說(shuō)了吧？把指向“接續頭指針”的鏈表斷開(kāi)，連接上新的地址，而該地址的存儲的指針指向“接續頭指針”。
VII 算法特點(diǎn)
(1)算法呈現出字索引方式。能夠滿(mǎn)足“查全”的功能。
(2)原始文本數據追加入庫時(shí)，由于入庫就是構造指針的過(guò)程，并同時(shí)建立了索引。入庫數據量和處理時(shí)間呈線(xiàn)性關(guān)系。速度很快。
(3)文字信息在數據庫中全部以指針存儲，本身具有加密的功能。
(4)如果有某個(gè)指針在存取過(guò)程中發(fā)生錯誤，則該指針的后續必將產(chǎn)生連續錯誤且無(wú)法糾正，這是該算法的主要缺陷。
(5)數據區48K，頭指針（接續）區16K，索引比為33%。這是全世界現有全文算法中，索引比最小的。
(6)該算法只適合于GB2312字符集。由于GBK，UNICODE，BIG5包含更多的漢字，會(huì )導致頭指針（接續）區域的擴大，而數據區被壓縮，因此失去了算法意義。
(7)檢索時(shí)，需要按照64K為單位讀取數據庫文件（這正好適用于16位操作系統），檢索效率會(huì )隨著(zhù)數據庫的增大而減小。因此該算法適合于小型數據庫的全文檢索系統(10萬(wàn)條記錄以?xún)?，總容?00M以下)。
六、結束語(yǔ)
學(xué)習計算機軟件設計，最重要的一門(mén)課程就是《數據結構》。這套全文檢索算法，正是依靠精妙的數據結構構建出來(lái)的，其實(shí)說(shuō)起來(lái)也很簡(jiǎn)單，就是鏈表數組。1993年的時(shí)候，PC機大多運行著(zhù) DOS + WINDOWS 3.1 + 中文環(huán)境（GB2312），這套算法正是適應當時(shí)的環(huán)境而設計的?，F在十年過(guò)去了，隨著(zhù)計算機軟硬環(huán)境的提升和全文數據量的增長(cháng)，該算法雖然已經(jīng)廢棄，但通過(guò)該算法，大家一定能體會(huì )出“數據結構”的重要性。1998年，我又設計了新的全文檢索算法，使用的是“數據結構”中的“散列表”。不過(guò)現在保密，也許10年后再公布吧，嘿嘿。
