全文索引結(jié)構(gòu)的研究

摘要：隨著Internet技術(shù)的普遍應(yīng)用，網(wǎng)絡(luò)信息量不斷的增大，如何在浩瀚的網(wǎng)絡(luò)數(shù)據(jù)中搜索到相關(guān)的數(shù)據(jù)信息，是目前網(wǎng)絡(luò)索引技術(shù)研究的主要問(wèn)題，本文主要介紹了全文索引結(jié)構(gòu)對(duì)網(wǎng)絡(luò)數(shù)據(jù)搜素的應(yīng)用和過(guò)程。

關(guān)鍵詞：全文索引；索引過(guò)程；搜索過(guò)程

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9599 （2012） 24-0086-02

全文索引結(jié)構(gòu)的研究主要是為了降低全文索引的空間占用、提高索引的速度，提高用戶的瀏覽檢索速率，設(shè)計(jì)空間復(fù)雜度和時(shí)間復(fù)雜度都較小的全文索引結(jié)構(gòu)是重要研究的課題。

1 全文索引結(jié)構(gòu)簡(jiǎn)介

一般我們生活中的數(shù)據(jù)分為兩類：結(jié)構(gòu)化數(shù)據(jù)和非結(jié)構(gòu)化數(shù)據(jù)。結(jié)構(gòu)化數(shù)據(jù)是指具有固定長(zhǎng)度和格式的數(shù)據(jù)；而非結(jié)構(gòu)化數(shù)據(jù)是沒有固定長(zhǎng)度和格式的數(shù)據(jù)。我們所指的全文數(shù)據(jù)就是一種非結(jié)構(gòu)化的數(shù)據(jù)，搜索的過(guò)程中可以使用對(duì)結(jié)構(gòu)化數(shù)據(jù)的搜索（如數(shù)據(jù)庫(kù)數(shù)據(jù)的搜索）和對(duì)非結(jié)構(gòu)化數(shù)據(jù)的搜索（如使用搜索引擎對(duì)網(wǎng)絡(luò)數(shù)據(jù)的搜索）。在對(duì)全文數(shù)據(jù)進(jìn)行搜索是我們主要使用兩種方法：一種是順序掃描法，就是在一個(gè)文件中從頭到尾的查看，直到找出要尋找的字符串，這種方法比較的原始，適合文件量比較小的對(duì)象，比較的直接和快捷，但是如果文檔量大則使用起來(lái)會(huì)相當(dāng)?shù)姆爆?。另一種方法是全文索引，所謂全文索引就是將全文非結(jié)構(gòu)化的數(shù)據(jù)提取出一部分，按照某種結(jié)構(gòu)重新進(jìn)行排列，這個(gè)過(guò)程叫做索引，然后再對(duì)索引進(jìn)行搜索，從而快速找到要尋找的字符串。全文檢索是指計(jì)算機(jī)索引程序通過(guò)掃描文章中的每一個(gè)詞，對(duì)每一個(gè)詞建立一個(gè)索引，指明該詞在文章中出現(xiàn)的次數(shù)和位置，當(dāng)用戶查詢時(shí)，檢索程序就根據(jù)事先建立的索引進(jìn)行查找，并將查找的結(jié)果反饋給用戶的檢索方式。這個(gè)過(guò)程類似于通過(guò)字典中的檢索字表查字的過(guò)程。全文檢索的過(guò)程包括索引創(chuàng)建和搜索索引兩個(gè)過(guò)程，索引創(chuàng)建就是將網(wǎng)絡(luò)中所有信息（包括結(jié)構(gòu)化信息和非結(jié)構(gòu)化信息）提取，創(chuàng)建索引的過(guò)程；搜索索引就是根據(jù)用戶的搜索要求，從已經(jīng)創(chuàng)建的索引中，查詢到相關(guān)結(jié)構(gòu)的過(guò)程。

下圖描述了全文索引的過(guò)程。

2 索引過(guò)程

對(duì)于非結(jié)構(gòu)數(shù)據(jù)在已有文檔中找到符合的字符串比較容易，這是文檔到字符串的映射，而索引過(guò)程中需要將符合條件的字符串歸結(jié)到相應(yīng)文檔中，就相當(dāng)于上述過(guò)程的逆過(guò)程，即字符串到文檔的映射，我們稱作反向索引。有兩種不同的反向索引形式：一條記錄的水平反向索引（或者反向檔案索引）包含每個(gè)引用單詞的文檔的列表。一個(gè)單詞的水平反向索引（或者完全反向索引）又包含每個(gè)單詞在一個(gè)文檔中的位置。后者的形式提供了更多的兼容性（比如短語(yǔ)搜索），但是需要更多的時(shí)間和空間來(lái)創(chuàng)建。反向索引的過(guò)程如下圖所示：

我們指定文檔庫(kù)中有1到100篇文檔，找到相關(guān)的字符串保存在詞典中，并且保存詞典到文檔的鏈接，我們也把此表稱作倒排表。由此可見，順序查找每一次都需要掃描，浪費(fèi)大量的時(shí)間，而全文索引只需要建立一次索引，就可以一勞永逸，在已有的索引結(jié)構(gòu)中進(jìn)行查找了。索引的具體過(guò)程如下：

有一系列被索引文件

被索引文件經(jīng)過(guò)語(yǔ)法分析和語(yǔ)言處理形成一系列詞。

經(jīng)過(guò)索引創(chuàng)建形成詞典和反向索引表。

通過(guò)索引存儲(chǔ)將索引寫入硬盤。

3 搜索過(guò)程

搜索就是在已經(jīng)建立索引的文檔庫(kù)中找到相關(guān)文檔，但是當(dāng)相關(guān)文檔數(shù)目過(guò)大時(shí)也要經(jīng)過(guò)如下步驟：

3.1 用戶輸入查詢語(yǔ)句。查詢語(yǔ)句也有一定的語(yǔ)法，語(yǔ)法規(guī)則和我們普通語(yǔ)言類似。

3.2 對(duì)查詢語(yǔ)句經(jīng)過(guò)語(yǔ)法分析和語(yǔ)言分析得到一系列詞。

（1）詞法分析主要用來(lái)識(shí)別單詞和關(guān)鍵字。

（2）語(yǔ)法分析主要根據(jù)查詢語(yǔ)句的語(yǔ)法規(guī)則來(lái)形成一顆語(yǔ)法樹。

（3）語(yǔ)言處理和索引過(guò)程中的語(yǔ)言處理幾乎相同。

3.3 通過(guò)語(yǔ)法分析得到一個(gè)查詢樹。

（1）在反向索引表中找到相關(guān)字符串的鏈表

（2）對(duì)相關(guān)字符串的鏈表進(jìn)行合并

（3）通過(guò)相關(guān)運(yùn)算排除，找到鏈表為相關(guān)字符串鏈表

3.4 利用查詢樹搜索索引，從而得到每一個(gè)詞的文檔鏈表，對(duì)文檔鏈表精心交、差、并得到結(jié)構(gòu)文檔。

3.5 將索引得到的結(jié)果文檔對(duì)查詢的相關(guān)性進(jìn)行排序。

判斷詞之間的關(guān)系從而得到文檔相關(guān)性的過(guò)程應(yīng)用一種叫做向量空間模型的算法，包括以下兩個(gè)過(guò)程：計(jì)算權(quán)重的過(guò)程和判斷詞之間的關(guān)系從而得到文檔相關(guān)性的過(guò)程。

3.6 返回查詢結(jié)果給用戶。

下圖總結(jié)了全文索引結(jié)構(gòu)的全過(guò)程（紅色箭頭代表了索引的過(guò)程，藍(lán)色箭頭代表了搜索的過(guò)程）。

結(jié)束語(yǔ)：總之，全文索引結(jié)構(gòu)是一種有效的網(wǎng)絡(luò)數(shù)據(jù)檢索方式，通過(guò)索引的建立和搜索兩個(gè)過(guò)程可以方便有效的實(shí)現(xiàn)對(duì)網(wǎng)絡(luò)數(shù)據(jù)的查找。它具有查詢速度快，準(zhǔn)確，響應(yīng)時(shí)間短的優(yōu)點(diǎn)，然而如何發(fā)揮它的強(qiáng)大功能，并逐步完善它的功能，是需要我們進(jìn)一步深入探討的問(wèn)題。

參考文獻(xiàn)：

[1]劉曉珠，彭志勇.全文索引技術(shù)時(shí)空效率分析[J].軟件學(xué)報(bào)，2009，7.

[2]曹元大，賀海軍，涂哲明，等.全文檢索字索引技術(shù)的研究與實(shí)現(xiàn)[J].計(jì)算機(jī)工程，2002，6.

[3]徐小剛，王俊杰，于玉.全文索引的研究[J].計(jì)算機(jī)工程，2002，2.