一只小狐貍帶你解鎖NLP/ML/DL秘籍

作者：QvQ

老板～我會寫倒排索引啦！我要把它放進(jìn)咱們自研搜索引擎啦！

我呸！你這種demo級代碼，都不夠當(dāng)單元測試的！

嚶嚶嚶，課本上就是這樣講的呀?!

來來，帶你見識一下工業(yè)級搜索引擎里的倒排索引是怎么優(yōu)化的!

前言

首先回顧一下構(gòu)建倒排索引的幾個(gè)主要步驟：
(1)?收集待建索引的文檔；
(2)?對這些文檔中的文本進(jìn)行詞條化；
(3)?對第2步產(chǎn)生的詞條進(jìn)行語言學(xué)預(yù)處理，得到詞項(xiàng)；
(4)?根據(jù)詞項(xiàng)對所有文檔建立索引。?可以看到，上訴過程中非常重要的一步就是獲得詞項(xiàng)，那么詞項(xiàng)是什么，又是怎么獲得的呢？

詞項(xiàng)集合的確定

在確定詞項(xiàng)前，我們需要明確三個(gè)概念：

詞條：一段文本中有效詞的子序列，其中每個(gè)子序列稱為一個(gè)詞條。

詞條類：相同詞條構(gòu)成的集合。

詞項(xiàng)：一個(gè)詞項(xiàng)指的是在信息檢索系統(tǒng)詞典中所包含的某個(gè)可能經(jīng)過歸一化處理的詞條類。（詞項(xiàng)集合和詞條集合可以完全不同，比如可以采用某一個(gè)分類體系中的類別標(biāo)簽作為詞項(xiàng)。當(dāng)然，在實(shí)際的信息檢索系統(tǒng)中，詞項(xiàng)往往和詞條密切相關(guān)）

三者關(guān)系如下：

下面，讓我們一起學(xué)習(xí)這幾者是如何一步步變化得來的。

1.1 詞條化

詞條化過程詞條化的主要任務(wù)就是確定哪些才是正確的詞條。比如，對于簡單的句子將字符串進(jìn)行拆分并去掉標(biāo)點(diǎn)符號即可。

然而，上面的例子僅僅代表的是一種最簡單的情況。實(shí)際上即使對于單詞之間存在空格的英文來說也存在很多難以處理的問題。比如，英文中的上撇號“’”既可以代表所有關(guān)系也可以代表縮寫，應(yīng)當(dāng)在詞條化過程中究竟應(yīng)該如何對它進(jìn)行處理?參考下面的例子:

對其中的“ O’Neill” 來說，詞條化的結(jié)果可能有如下幾種形式可以選擇，那么到底哪一種才正確？?

對于可能的各種拆分策略來說，最后的選擇結(jié)果會決定哪些布爾查詢會被匹配上、哪些不會被匹配上。給定查詢neill AND capital，上述五種拆分策略中有3種會被匹配上（即第1、4、5種情況）。而如果給定查詢o’neill AND capital，則在沒有對查詢進(jìn)行任何預(yù)處理的情況下，上述策略中只有一種能匹配上。不管是輸入布爾查詢或者自由文本查詢，人們總是希望對文檔和查詢進(jìn)行同樣的詞條化處理，這往往通過采用相同的詞條化工具來實(shí)現(xiàn)。這樣做能夠確保文本與查詢中的同一字符串序列的處理結(jié)果相一致。

在詞條化的過程中，需要注意以下幾個(gè)問題：

（1）對大多數(shù)語言特別是一些特定領(lǐng)域的語言來說，往往有一些特定的詞條需要被識別成詞項(xiàng)，如編程語言“C++”和“C#”、“B-52”之類的飛行器名字或者叫“M*A*S*H”的電視秀節(jié)目等等，這時(shí)候就不能簡單的去掉文本中的符號了，這里通常需要建立專有名詞字典來解決。

（2）字符序列類型包括郵件地址（如jblack@mail.yahoo.com）、URL（如http://stuff.big.com/new/specials.html）、IP地址（如142.32.48.231）和包裹追蹤號碼（1Z9999W99845399981）等等。一種做法是不對包括貨幣量、數(shù)字、URL等在內(nèi)的詞條進(jìn)行索引，這是因?yàn)槿绻麑@些詞條進(jìn)行索引則會顯著擴(kuò)大索引的詞匯量。當(dāng)然，這樣做會對用戶的搜索產(chǎn)生一些限制。比如，人們可能會在程序缺陷（bug）庫中搜索錯(cuò)誤發(fā)生的行號，但是經(jīng)過上述處理之后的系統(tǒng)顯然不能返回正確結(jié)果。如果這類數(shù)據(jù)需要詞條化，那么利用正則是一個(gè)不錯(cuò)的辦法。

（3）即使根據(jù)空格進(jìn)行拆分有時(shí)也會將概念上本應(yīng)該看成單個(gè)詞條的對象分開，比如一些名稱（San Francisco，Los Angeles）、外來短語（au fait）或那些書寫時(shí)可分可合的復(fù)合詞（white space vs whitespace）。其他的例子還包括電話號碼[（800）234-2333]、日期（Mar11,1983）等。如果在空格處拆分這些對象可能會導(dǎo)致很差的檢索結(jié)果，比如，輸入York University（約克大學(xué)）時(shí)會返回包含New York University（紐約大學(xué)）的文檔。連字符和空格甚至?xí)ハ嘤绊憽?strong>這種情況就和中文文本中分詞類似了。

（4）對于一些主要的東亞語言（如漢語、日語、韓語和泰語等）來說，由于詞之間并不存在空格，所以問題更加嚴(yán)重。分詞的方法包括基于詞典的最大匹配法（采用啟發(fā)式規(guī)則來進(jìn)行未定義詞識別）和基于機(jī)器學(xué)習(xí)序列模型的方法（如隱馬爾可夫模型或條件隨機(jī)場模型）等，后者需要在手工切分好的語料上進(jìn)行訓(xùn)練（分詞作為NLP領(lǐng)域一個(gè)非常重要的研究內(nèi)容，我們后面會專門獨(dú)立一章來介紹分詞常用算法ヾ(?°?°?)ﾉﾞ）。由于存在多種切分可能，上述分詞方法都有可能導(dǎo)致錯(cuò)誤的切分結(jié)果，因此，永遠(yuǎn)不能保證只能得到一個(gè)完全一致的唯一切分結(jié)果。另一個(gè)解決方法則摒棄了基于詞的索引策略而采用短字符序列的方法（如字符的k-gram方法）。這種方法并不關(guān)心詞項(xiàng)是否會跨越詞的邊界。該方法之所以能夠引起人們的興趣主要有以下3個(gè)原因:第一，一個(gè)漢字更像是一個(gè)音節(jié)而不是字符，它往往具有語義信息;第二，大部分詞都很短（最常見的漢語詞長度是2個(gè)字）;第三，由于缺乏公認(rèn)的分詞標(biāo)準(zhǔn)，詞的邊界有時(shí)也很難確定。

1.2 去停用詞

某些情況下，一些常見詞在文檔和用戶需求進(jìn)行匹配時(shí)價(jià)值并不大，需要徹底從詞匯表中去除。這些詞稱為停用詞（stop word）。一個(gè)常用的生成停用詞表的方法就是將詞項(xiàng)按照文檔集頻率（collection frequency，每個(gè)詞項(xiàng)在文檔集中出現(xiàn)的頻率）從高到低排列，然后手工選擇那些語義內(nèi)容與文檔主題關(guān)系不大的高頻詞作為停用詞。停用詞表中的每個(gè)詞將在索引過程中被忽略。

?英文常用停用詞表

不對停用詞建立索引一般情況下不會對系統(tǒng)造成太大的影響，比如搜索時(shí)采用the或by進(jìn)行查詢似乎沒有什么意義。但是，對于短語查詢來說情況并非如此，比如短語查詢President of the United States中包含兩個(gè)停用詞，但是它比查詢President AND“United States”更精確。如果忽略掉to，那么flights to London（因?yàn)檫@里的to并不是以介詞的身份出現(xiàn)）的意義將會丟失。搜索Vannevar Bush的那篇經(jīng)典文章As we may think時(shí)，如果將前3個(gè)單詞都看作停用詞，那么搜索將會很困難，因?yàn)橄到y(tǒng)只返回包含think的文章。更為嚴(yán)重的是，一些特定的查詢類型會受到更大的影響。比如一些歌名或者著名的詩歌片段可能全部由常用的停用詞組成（如To be or not to be，Let It Be，I don’t want to be等）。

1.3 詞條歸一化

將文檔和查詢轉(zhuǎn)換成一個(gè)個(gè)的詞條之后，最簡單的情況就是查詢中的詞條正好和文檔中的詞條相一致。然而在很多情況下，即使詞條之間并不完全一致，但實(shí)際上人們希望它們之間能夠進(jìn)行匹配。比如查詢USA時(shí)我們希望能夠返回包含U.S.A.的文檔。

詞條歸一化（token normalization）就是將看起來不完全一致的多個(gè)詞條歸納成一個(gè)等價(jià)類，以便在它們之間進(jìn)行匹配的過程。

最常規(guī)的做法有以下兩種：

（1）隱式地建立等價(jià)類，每類可以用其中的某個(gè)元素來命名。比如，在文檔和查詢中，都把詞條anti-discriminatory和antidiscriminatory映射成詞項(xiàng)antidiscriminatory,這樣對兩個(gè)詞中的任一個(gè)進(jìn)行搜索，都會返回包含其中任一詞的文檔。這種處理方法的優(yōu)點(diǎn)在于:一方面，等價(jià)類的建立過程是隱式的，不需要事先計(jì)算出等價(jià)類的全部元素，在映射規(guī)則下輸出相同結(jié)果的詞項(xiàng)一起構(gòu)成等價(jià)類集合;另一方面，僅僅構(gòu)建“去除字符”這種映射規(guī)則也比較容易。

（2）顯示建立等價(jià)類，維護(hù)多個(gè)非歸一化詞條之間的關(guān)聯(lián)關(guān)系。該方法可以進(jìn)一步擴(kuò)展成同義詞詞表的手工構(gòu)建，比如將car和automobile歸成同義詞。這些詞項(xiàng)之間的關(guān)系可以通過兩種方式來實(shí)現(xiàn)。第一種常用的方式是采用非歸一化的詞條進(jìn)行索引，并為某個(gè)查詢詞項(xiàng)維護(hù)一張由多個(gè)詞組成的查詢擴(kuò)展詞表。當(dāng)輸入一個(gè)查詢詞項(xiàng)時(shí)，則根據(jù)擴(kuò)展詞表進(jìn)行擴(kuò)展并將擴(kuò)展后得到的多個(gè)詞所對應(yīng)的倒排記錄表合在一塊（如下圖一）。另一種方式是在索引構(gòu)建時(shí)就對詞進(jìn)行擴(kuò)展（如下圖二）。比如，對于包含automobile的文檔，我們同時(shí)也用car來索引（同樣，包含car的文檔也用automobile來索引）。

圖一

圖二

另一方面，由于兩個(gè)關(guān)聯(lián)詞的擴(kuò)展詞表之間可以存在交集但不必完全相同，所以上述兩種方式相對于隱式建立等價(jià)類的方法來說更具靈活性。這也意味著從不同關(guān)聯(lián)詞出發(fā)可以進(jìn)行不對稱的擴(kuò)展。下圖出了一個(gè)例子。該例子中，如果用戶輸入windows，那么我們希望返回包含Windows操作系統(tǒng)的文檔。但是如果用戶輸入window，雖然此時(shí)可以和小寫的windows相匹配，但是不太可能會和Windows操作系統(tǒng)中的Windows相匹配。

隱式建立等價(jià)類或查詢擴(kuò)展的使用幅度仍然是個(gè)開放的問題。適度使用絕對沒錯(cuò)，但是過度使用很容易會在無意間造成非預(yù)期的擴(kuò)展結(jié)果。例如，通過刪除U.S.A.中的句點(diǎn)可以把它轉(zhuǎn)化成USA，由于在首字母省略用法中存在這種轉(zhuǎn)換模式，所以上面的做法乍看上去非常合理。但是，如果輸入查詢C.A.T.，返回的很多包含cat的文檔卻肯定不是我們想要的結(jié)果。

接下來我們將給出一些在實(shí)際當(dāng)中會遇到的詞條歸一化問題及其對策：

（1）重音及變音符號問題

英語中變音符號的使用越來越少見，盡管如此，人們很可能希望cliche和cliché或者naive和na?ve能匹配。這可以通過在詞條歸一化時(shí)去掉變音符號來實(shí)現(xiàn)。而在許多其他語言中，變音符號屬于文字系統(tǒng)的常規(guī)部分，不同的變音符號表示不同的發(fā)音。有時(shí)候，不同單詞之間的區(qū)別只是重音不同。比如，西班牙語中，pe?a的意思是“懸崖”，而pena的意思卻是“悲哀”。然而，關(guān)鍵并不是規(guī)范或者語言學(xué)問題，而是用戶如何構(gòu)造查詢來查找包含這些詞的文檔。

（2）大小寫轉(zhuǎn)換問題

大小寫轉(zhuǎn)換（case-folding）問題的一個(gè)一般處理策略是將所有的字母都轉(zhuǎn)換成小寫。這種做法通常的效果不錯(cuò)，比如這樣可以允許句首的Automobile和查詢automobile匹配。對于Web搜索引擎來說，這種做法也很有好處，因?yàn)榇蠖鄶?shù)用戶輸入ferrari時(shí)實(shí)際想找的是Ferrari（法拉利）車。

（3）英語中的其他問題

英語中還存在一些獨(dú)特的歸一化做法。比如，用戶希望將ne’er和never、英式英語的拼寫方式colour和美式英語的拼寫方式color等同起來。日期、時(shí)間和其他類似的對象往往以多種形式出現(xiàn)，這給歸一化造成了額外的負(fù)擔(dān)。人們可能希望將3/12/91和Mar.12，1991統(tǒng)一起來。但是，要正確處理這個(gè)例子將會十分復(fù)雜，因?yàn)樵诿绹?#xff0c;3/12/91指的1991年3月12日（Mar.12,1991），而在歐洲，卻指的是1991年12月3日（3Dec.1991）

1.4 詞干還原和詞性歸并

出于語法上的要求，文檔中常常會使用詞的不同形態(tài)，比如organize、organizes和organizing。另外，語言中也存在大量意義相近的同源詞，比如democracy、democratic和democratization。在很多情況下，如果輸入其中一個(gè)詞能返回包含其同源詞的文檔，那么這樣的搜索似乎非常有用。

詞干還原和詞形歸并的目的都是為了減少屈折變化的形式，并且有時(shí)會將派生詞轉(zhuǎn)化為基本形式。

詞干還原：通常指的是一個(gè)很粗略的去除單詞兩端詞綴的啟發(fā)式過程，并且希望大部分時(shí)間它都能達(dá)到這個(gè)正確目的，這個(gè)過程也常常包括去除派生詞綴。

詞形歸并：通常指利用詞匯表和詞形分析來去除屈折詞綴，從而返回詞的原形或詞典中的詞的過程，返回的結(jié)果稱為詞元。

這兩個(gè)過程的區(qū)別還在于:詞干還原在一般情況下會將多個(gè)派生相關(guān)詞合并在一起，而詞形歸并通常只將同一詞元的不同屈折形式進(jìn)行合并。詞干還原或詞形歸并往往通過在索引過程中增加插件程序的方式來實(shí)現(xiàn)，這類插件程序有很多，其中既有商業(yè)軟件也有開源軟件。

?

基于跳表的快速合并算法

上一章我們講解了倒排記錄表的基本合并算法:同時(shí)在兩個(gè)表中遍歷，并且最后算法的時(shí)間復(fù)雜度為記錄表大小的線性函數(shù)。假定兩個(gè)表的大小分別是m和n，那么合并過程有O（m+n）次操作。很自然的一個(gè)問題就是我們能否做得更好？也就是說，能否在亞線性時(shí)間內(nèi)完成合并過程？下面我們將看到，如果索引變化不太頻繁的話那么答案是肯定的。

如果待合并的兩個(gè)倒排表數(shù)據(jù)量很大, 但是交集很少時(shí), 會是什么情況呢?

[1, 2, 3, 4, 5, ... 10001, 10005] [1, 10001, 10008]

如果對這兩個(gè)做合并操作, 最后的交集結(jié)果只有 ?[1, 10001] 2個(gè)元素, 但是卻要做10001次移動和比較操作, 所以肯定有什么辦法來優(yōu)化這一點(diǎn). 可能你已經(jīng)想到了, 我們做了這么多無用比較, 是因?yàn)槲覀兠看沃羔樝蚯耙苿拥牟阶犹×它c(diǎn), 如果我們在每次比較后向前多移動一點(diǎn), 可以忽略很多無用的操作. 這就是跳表的思想.

跳表（skip list）—— 在構(gòu)建索引的同時(shí)在倒排記錄表上建立跳表（如下圖所示）。跳表指針能夠提供捷徑來跳過那些不可能出現(xiàn)在檢索結(jié)果中的記錄項(xiàng)。構(gòu)建跳表的兩個(gè)主要問題是:在什么位置設(shè)置跳表指針?如何利用跳表指針進(jìn)行倒排記錄表的快速合并?

我們以上圖為例來先考慮快速合并的問題。假定我們在兩個(gè)表中遍歷一直到發(fā)現(xiàn)共同的記錄8為止，將8放入結(jié)果表中之后我們繼續(xù)移動兩個(gè)表的指針。假定第一個(gè)表的指針移到16處，而第二個(gè)表的指針移到41處，兩者中較小項(xiàng)為16。這時(shí)候我們并不繼續(xù)移動上面的表指針，而是檢查跳表指針的目標(biāo)項(xiàng)，此時(shí)為28，仍然比41要小，因此此時(shí)可以直接把上表的表指針移到28處，這樣就跳過了19和23兩項(xiàng)。基于跳表的倒排記錄表合并算法有很多變形，它們的主要不同可能在于跳表檢查的時(shí)機(jī)不一樣。

我們再考察另一個(gè)問題，即在什么位置上放置跳表指針?這里存在一個(gè)指針個(gè)數(shù)和比較次數(shù)之間的折中問題。跳表指針越多意味著跳躍的步長越短，那么在合并過程中跳躍的可能性也更大，但同時(shí)這也意味著需要更多的指針比較次數(shù)和更多的存儲空間。跳表指針越少意味著更少的指針比較次數(shù)，但同時(shí)也意味著更長的跳躍步長，也就是說意味著更少的跳躍機(jī)會。放置跳表指針位置的一個(gè)簡單的啟發(fā)式策略是，在每個(gè)㏒?P處均勻放置跳表指針，其中P是倒排記錄表的長度。這個(gè)策略在實(shí)際中效果不錯(cuò)，但是仍然有提高的余地，因?yàn)樗]有考慮查詢詞項(xiàng)的任何分布細(xì)節(jié)。

# 基于跳表的倒排記錄表快速合并算法 a = range(10008) b = [1, 10001, 10008]i = j = 0 result = [] step = 100 count = 0 while i < len(a) and j < len(b):if a[i] == b[j]:result.append(a[i])i = i + 1j = j + 1count = count + 1elif a[i] < b[j]:while (i + step < len(a)) and a[i + step] <= b[j]:i = i + stepcount = count + 1else:i = i + 1count = count + 1else:while (j + step < len(b)) and b[j + step] <= a[i]:j = j + stepcount = count + 1else:j = j + 1count = count + 1 print(result) # [1, 10001] print(count) # 207

上面代碼中故意構(gòu)造了一個(gè)很大的集合 [0 ... 10007], 然后用變量count作為計(jì)數(shù)器來分析兩個(gè)算法分別執(zhí)行的操作次數(shù), 可以看到采用跳表算法時(shí)(我們模擬了step=100)的計(jì)算次數(shù)是207, 而用之前的方式計(jì)算次數(shù)是10008, 可見性能提升了很多倍.

這里有幾點(diǎn)說明下:

1. 這里為了簡單說明跳表的思路, 全部用了數(shù)組表示倒排表, 其實(shí)真實(shí)的數(shù)據(jù)結(jié)構(gòu)應(yīng)該是鏈表結(jié)構(gòu)(linked list). 這才符合磁盤存儲結(jié)構(gòu).?

2. 跳表的原始結(jié)構(gòu)算法比這個(gè)復(fù)雜, 而且根據(jù)場景的不同, 跳表有不同的實(shí)現(xiàn). 這里因?yàn)椴皇抢锰淼目焖俨樵児δ? 所以沒有多級指針?biāo)饕拍? 詳細(xì)跳表實(shí)現(xiàn)查考:?Skip Lists: A Probabilistic Alternative to Balanced Trees

含位置信息的倒排記錄表

先來看一個(gè)問題，當(dāng)用戶將“Stanford University”這個(gè)查詢中的兩個(gè)詞看成一個(gè)整體的時(shí)候，用戶是為了查詢和Stanford University這所高校相關(guān)的信息。但是如果是基于布爾查詢（詳見第一章）的話，將會被拆解成Stanford AND University進(jìn)行查詢，從而一篇含有句子The inventor Stanford Ovshinsky never went to university的文檔會推送給用戶，這并不是我們想要的。那么如何解決這個(gè)問題呢？這里引入二元詞索引。

3.1 二元詞索引

處理短語查詢的一個(gè)辦法就是將文檔中每個(gè)接續(xù)詞對看成一個(gè)短語。例如，文本 Friends,Romans, Countrymen 會產(chǎn)生如下的二元接續(xù)詞對

friends?romans romans countrymen

這種方法將每個(gè)接續(xù)詞對看成詞項(xiàng)，這樣馬上就能處理兩個(gè)詞構(gòu)成的短語查詢，更長的查詢可以分成多個(gè)短查詢來處理。比如，按照上面的方法可以將查詢 stanford university palo alto

分成如下的布爾查詢：

“stanford university” AND “university palo” AND “palo alto”

可以期望該查詢在實(shí)際中效果會不錯(cuò)，但是偶爾也會有錯(cuò)誤的返回例子。對于該布爾查詢返回的文檔，我們并不知道其是否真正包含最原始的四詞短語。在所有可能的查詢中，用名詞和名詞短語來表述用戶所查詢的概念具有相當(dāng)特殊的地位。但是相關(guān)的名詞往往被各種虛詞分開，比如短語the abolition of slavery或者renegotiation of the constitution。這種情況下，可以采用如下方法來建立二元詞索引:首先對文本進(jìn)行詞條化然后進(jìn)行詞性標(biāo)注，這樣就可以把每個(gè)詞項(xiàng)歸成名詞（N，也包括專有名詞）、虛詞（X，冠詞和介詞）和其他詞。然后將形式為NX*N非詞項(xiàng)序列看成一個(gè)擴(kuò)展的二元詞。利用上述算法，可以將查詢cost overruns on a power plant分析成“cost overruns” AND “overruns power” AND “power plant”，實(shí)際上忽略中間的那個(gè)二元詞所形成的查詢的效果會更好。如果使用更精確的詞性模式來定義擴(kuò)展二元詞可能會取得更好的結(jié)果。

二元詞索引的概念可以擴(kuò)展到更長的詞序列（三元、四元...），如果索引中包含變長的詞序列，通常就稱為短語索引（phrase index）。實(shí)際上，利用二元詞索引來處理單個(gè)詞的查詢不太方便（必須要掃描整個(gè)詞匯表來發(fā)現(xiàn)包含該查詢詞的二元詞），因此同時(shí)還需要有基于單個(gè)詞的索引。盡管總有可能得到錯(cuò)誤的匹配結(jié)果，但是在長度為3或者更長的索引短語上發(fā)生匹配錯(cuò)誤的可能性實(shí)際上卻很小。然而在另一方面，存儲更長的短語很可能會大大增加詞匯表的大小。窮盡所有長度超過2的短語并維護(hù)其索引絕對是一件令人生畏的事情，即使只窮盡所有的二元詞也會大大增加詞匯表的大小。

3.2 位置信息索引

很顯然，基于上面談到的原因，二元詞索引并非標(biāo)準(zhǔn)的解決方案。實(shí)際中更常用的一種方式是采用所謂的位置信息索引（positional index，簡稱位置索引）。在這種索引中，對每個(gè)詞項(xiàng)，以如下方式存儲倒排記錄

單詞be的文檔頻率是178239，在文檔1中出現(xiàn)2次，位置分別是17、25。

為處理短語查詢，仍然需要訪問各個(gè)詞項(xiàng)的倒排記錄表。像以往一樣，這里可以采用最小文檔頻率優(yōu)先的策略，從而可以限制后續(xù)合并的候選詞項(xiàng)的數(shù)目。在合并操作中，同樣可以采用前面提到的各種技術(shù)來實(shí)現(xiàn)，但是這里不只是簡單地判斷兩個(gè)詞項(xiàng)是否出現(xiàn)在同一文檔中，而且還需要檢查它們出現(xiàn)的位置關(guān)系和查詢短語的一致性。這就需要計(jì)算出詞之間的偏移距離。

舉個(gè)栗子，假如用戶輸入"boy friend"進(jìn)行搜索, 如果只要出現(xiàn)了"boy" 或者 "friend"的文檔都搜索出來, 那么下面三篇文檔都滿足要求:

the boy and the girl are good friends

you are my boy friend

the boy has many friends.

現(xiàn)在用戶應(yīng)該只想搜出文檔 2 出來. 基于"位置信息索引"方式, 我們可以做到這一點(diǎn).

這種搜索方法類似于k詞近鄰搜索 —— a /k b

這里，/k 意味著“ 從左邊或右邊相距在 k 個(gè)詞之內(nèi)，若k=1，則意味著a、b相鄰” 。很顯然，位置索引能夠用于鄰近搜索，而二元詞索引則不能。

有了這個(gè)索引存儲結(jié)構(gòu), 要找出不同的短語就比較容易了, 比如用戶想搜索"boy friend", 就可以轉(zhuǎn)化成 boy /1 friend 即可以完成要求。只要找出在文檔中, boy出現(xiàn)的位置剛好在friend前一個(gè)位置的所有文檔. 所以文檔2滿足我們的要求被搜索出來. 下面用python簡單實(shí)現(xiàn)下這個(gè)算法:

# p1, p2是兩個(gè)上述結(jié)構(gòu)的倒排記錄表, k是兩個(gè)詞項(xiàng)的位置在k以內(nèi) def positional_interset(p1, p2, k):result = [] # 最終的搜索結(jié)果, 以(文檔id, 詞項(xiàng)1的位置, 詞項(xiàng)2的位置)形式存儲while p1 is not None and p2 is not None: # 當(dāng)p1, 和 p2 都沒有達(dá)到最尾部時(shí)if p1.docId == p2.docId: # 如果兩個(gè)詞項(xiàng)出現(xiàn)在同一個(gè)文檔中l(wèi) = [] # 臨時(shí)變量, 用來存儲計(jì)算過程中滿足位置距離的位置對信息pp1 = p1.positionpp2 = p2.positionwhile pp1 is not None: # 先固定pp1的位置, 循環(huán)移動pp2的位置進(jìn)行檢查while pp2 is not None:if abs(pp1.pos - pp2.pos) <= k: # 如果pp1和pp2的距離小于k, 則滿足要求l.append(pp2.pos) # 添加到臨時(shí)變量pp2 = pp2.next # pp2向后移一個(gè)位置elif pp2.pos > pp1.pos: # 如果pp2當(dāng)前的位置相對pp1已經(jīng)超過給定的范圍(構(gòu)不成短語要求), 則停止移動pp2, 后續(xù)后把pp1再往前移動一個(gè)位置breakwhile not l and abs(l[0] - pp1.pos) > k: # 當(dāng)每次移動一次pp1時(shí), l里面會存儲上一次計(jì)算所得的pp2的一些位置, 這里要過濾那些相對于當(dāng)前pp1最新位置, 那些不再滿足要求的pp2的位置del l[0]for p in l:result.append[(p1.docId, pp1.pos, p)] # 把最終的結(jié)果加入到結(jié)果集中pp1 = pp1.next # pp1向前移動一個(gè)位置, 重復(fù)上次邏輯計(jì)算p1 = p1.nextp2 = p2.nextelif p1.docId < p2.docId:p1 = p1.nextelse:p2 = p2.next

?毋庸置疑，采用位置索引會加深倒排記錄表合并操作的漸進(jìn)復(fù)雜性，這是因?yàn)樾枰獧z查的項(xiàng)的個(gè)數(shù)不再受限于文檔數(shù)目而是文檔集中出現(xiàn)的所有的詞條的個(gè)數(shù) T。也就是說，布爾查詢的復(fù)雜度為Θ (T)而不是Θ (N)。然而，由于用戶往往期望能夠進(jìn)行短語搜索和鄰近搜索，所以實(shí)際中的大部分應(yīng)用并沒有其他選擇而不得不采用這種做法。

3.3 混合索引機(jī)制

二元詞索引和位置索引這兩種策略可以進(jìn)行有效的合并。假如用戶通常只查詢特定的短語，如Michael Jackson，那么基于位置索引的倒排記錄表合并方式效率很低。一個(gè)混合策略是:對某些查詢使用短語索引或只使用二元詞索引，而對其他短語查詢則采用位置索引。短語索引所收錄的那些較好的查詢可以根據(jù)用戶最近的訪問行為日志統(tǒng)計(jì)得到，也就是說，它們往往是那些高頻常見的查詢。當(dāng)然，這并不是唯一的準(zhǔn)則。處理開銷最大的短語查詢往往是這樣一些短語，它們中的每個(gè)詞都非常常見，但是組合起來卻相對很少見。

Williams等人(2004)評估了一個(gè)更復(fù)雜的混合索引機(jī)制，其中除了包含上面兩種形式的索引外，還在它們之間引入了一個(gè)部分后續(xù)詞索引（next word index），即對每個(gè)詞項(xiàng)，有個(gè)后續(xù)詞索引記錄了它在文檔中的下一個(gè)詞項(xiàng)。論文的結(jié)論是，雖然比僅僅使用位置索引增加了26%的空間，但是面對典型的Web短語混合查詢，其完成時(shí)間大概是只使用位置索引的1/4。

本章節(jié)主要對詞項(xiàng)的形成和倒排索引的兩個(gè)升級版算法做了一個(gè)粗略的介紹。雖然這是搜索引擎中最基礎(chǔ)的東西，但值得細(xì)細(xì)挖掘的地方還有很多，畢竟每一個(gè)小點(diǎn)的改善都可以極大的提高用戶體驗(yàn)，搜索引擎學(xué)習(xí)之路道阻且長呀~加油(｀?ω?′)

可

能

喜

歡

• 跨平臺NLP/ML文章索引
  

• 倒排索引初體驗(yàn)

• 讓搜索推薦更聰明的篇章標(biāo)簽自動化生產(chǎn)

• 神經(jīng)網(wǎng)絡(luò)調(diào)參指南

• DFS、BFS與A*搜索算法

求關(guān)注 求投喂 拉你進(jìn)高端群哦~

參考文獻(xiàn)

《信息檢索導(dǎo)論 修訂版》

倒排索引優(yōu)化 - 跳表 ?—— ?博客園 海鳥

總結(jié)

以上是生活随笔為你收集整理的搜索引擎核心技术与算法 —— 词项词典与倒排索引优化的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。