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