當前位置:成語大全網 - 古籍修復 - 搜索引擎算法中,什麽是正向索引?什麽是倒排索引?

搜索引擎算法中,什麽是正向索引?什麽是倒排索引?

倒排索引表中的每壹項都包括壹個屬性值和具有該屬性值的各記錄的地址。由於不是由記錄來確定屬性值,而是由屬性值來確定記錄的位置,因而稱為倒排索引(inverted index)。帶有倒排索引的文件我們稱為倒排索引文件,簡稱倒排文件。建立全文索引中有兩項非常重要,壹個是如何對文本進行分詞,壹是建立索引的數據結構。分詞的方法基本上是二元分詞法、最大匹配法和統計方法。索引的數據結構基本上采用倒排索引的結構。

分詞的好壞關系到查詢的準確程度和生成的索引的大小。在中文分詞發展中,早期經常使用分詞方式是二元分詞法,該方法的基本原理是將包含中文的句子進行二元分割,不考慮單詞含義,只對二元單詞進行索引。因此該方法所分出的單詞數量較多,從而產生的索引數量巨大,查詢中會將無用的數據檢索出來,好處是算法簡單不會漏掉檢索的數據。之後又發展出最大匹配分詞方法,該方法又分為正向最大分詞和逆向最大分詞。其原理和查字典類似,對常用單詞生成壹個詞典,分析句子的過程中最大的匹配字典中的單詞,從而將句子拆分為有意義的單詞鏈。最大匹配法中正向分詞方法對偏正式詞語的分辨容易產生錯誤,比如“首飾和服裝”會將“和服”作為單詞分出。達夢數據庫采用的是改進的逆向最大分詞方法,該分詞方法較正向正確率有所提高。最為復雜的是通過統計方式進行分詞的方法。該方法采用隱式馬爾科夫鏈,也就是後壹個單詞出現的概率依靠於前壹個單詞出現的概率,最後統計所有單詞出現的概率的最大為分詞的依據。這個方法對新名詞和地名的識別要遠遠高於最大匹配法,準確度隨著取樣文本的數量的增大而提高。

二元分詞方法和統計方法是不依賴於詞典的,而最大匹配法分詞方法是依賴於詞典的,詞典的內容決定分詞結構的好壞。

全文檢索的索引被稱為倒排索引,之所以成為倒排索引,是因為將每壹個單詞作為索引項,根據該索引項查找包含該單詞的文本。因此,索引都是單詞和唯壹記錄文本的標示是壹對多的關系。將索引單詞排序,根據排序後的單詞定位包含該單詞的文本。

步驟1)讀取壹整條句子到變量str中,轉到步驟2

步驟2)從句子的尾端讀取1個字到變量word中,轉到步驟3

步驟3)在字典查找word中保存的單詞。如果存在則保存word,轉到步驟4,否則轉到步驟5)

步驟4)如果是字典中最大單詞或者超過最大單詞數(認定為新詞),從句尾去掉該單詞,返回步驟2

步驟5)讀取前壹個字到word中,構成新單詞,轉到步驟3)

詞庫的內存數據結構和詞庫中單詞的匹配算法

內存中單詞采用層次結構保存

假設字典中有如下的單詞:中國 中華民國 國家 人民 民主

在內存中按照如下方式按層排列,其中每壹個方塊代表壹個字,箭頭所指向為該單詞的前壹個字