一種面向中文分詞的搜索算法

張 天 皓

(復(fù)旦大學(xué)計算機(jī)科學(xué)技術(shù)學(xué)院 上海 201203)(上海視頻技術(shù)與系統(tǒng)工程研究中心 上海 201203)

0 引 言

當(dāng)今社會是個信息爆炸的時代，面對數(shù)之不盡的信息，如何快速精確定位用戶想要的信息是最迫切的需求之一。能夠完成這個任務(wù)的正是搜索引擎，搜索最常見的形式是文本搜索。現(xiàn)在除全文搜索引擎外，針對特定領(lǐng)域的垂直搜索的需求也越來越大。在特定領(lǐng)域，由于資源的種類有局限性，搜索的條件能做到十分明確，另外數(shù)據(jù)集的大小也局限在一定范圍內(nèi)。在這些前提下，可以對搜索引擎做出很多有針對性的優(yōu)化。目前漢語使用者越來越多，一些特定領(lǐng)域甚至只面向漢語用戶，針對漢語的特性定制搜索引擎以提供高效友好的服務(wù)也是搜索引擎的發(fā)展趨勢。本文提出了一個基于后綴樹的搜索算法，能夠適應(yīng)中文場景和域搜索。針對垂直搜索引擎面向的數(shù)據(jù)規(guī)模和特點優(yōu)化了其時間和空間效率。

1 相關(guān)工作

后綴樹(suffix tree)是一種數(shù)據(jù)結(jié)構(gòu)，是PAT樹的一種，經(jīng)常被運用在字符串匹配等字符串相關(guān)的問題中。其概念最早由Weiner[1]于1973年提出。后由文獻(xiàn)[2-3]對其構(gòu)造進(jìn)行大幅簡化完善。Farach[4]于1997年提出了對于任何字母表都最優(yōu)的后綴樹的構(gòu)建算法。該算法成為了此后構(gòu)建后綴樹和后綴數(shù)組的新算法的基礎(chǔ)。

廣義后綴樹是對應(yīng)一系列字符串的后綴樹。對于一組字符串集合D=S_1,S_2,…,S_d，總長度為n，該集合對應(yīng)的廣義后綴樹即為包含n個后綴的后綴樹。廣義后綴樹最常被用于生物信息學(xué)。

倒排索引(inverted index)[5]是一種索引結(jié)構(gòu)。它存儲了從內(nèi)容(單詞或者數(shù)字)到其在數(shù)據(jù)庫或文檔中的位置的一個映射。因其與正排索引恰好相對(正排索引存儲了從文檔到內(nèi)容的一個映射)，所以被稱為倒排索引。倒排索引被廣泛應(yīng)用在快速全文檢索中，是文檔檢索系統(tǒng)中最常見的索引結(jié)構(gòu)。

中文分詞[6]是中文自然語言處理中的關(guān)鍵技術(shù)之一，其概念于20世紀(jì)80年代被提出。時至今日，中文分詞技術(shù)可以大體分為如下三種類別：基于詞典的分詞方法、基于統(tǒng)計的分詞方法和基于理解的分詞方法。

數(shù)據(jù)壓縮指的是將數(shù)據(jù)以另一種形式編碼，使其比原本的表示方法占用更少的比特數(shù)的操作。使用數(shù)據(jù)壓縮技術(shù)緩解存儲原件的壓力十分必要。壓縮后的索引占用內(nèi)存也會下降，能提高CPU的緩存命中率，加快搜索速度。

在索引結(jié)構(gòu)中，整數(shù)序列是常用的數(shù)據(jù)結(jié)構(gòu)。整數(shù)的壓縮算法[7]一般分為以下幾類：variable bit壓縮、variable byte壓縮和variable word壓縮。Variable bit壓縮的主要算法有variable byte code、Unary code、Golomb code、Elias code、Rice等。Variable byte壓縮的主要算法有 PForDelta、Interpolative code、AFOR、SIMD-GVB、Group Variable Byte等。Variable word壓縮的主要算法有Simple-9、Simple-16等。

2 基于后綴樹的中文索引

2.1 基于中文分詞改進(jìn)廣義后綴樹模型

分詞帶來的主要影響是搜索結(jié)果的排序。不考慮文檔熱度等額外信息，語義信息是搜索結(jié)果排序的主要決定因素，而語義信息很大程度上會體現(xiàn)在分詞結(jié)果中。

圖1為一個廣義后綴樹的實例，其中＄表示分隔符，#表示終止符。在搜索時＄會被忽略，分詞在數(shù)據(jù)結(jié)構(gòu)上沒有體現(xiàn)出效果。

假設(shè)有兩篇文檔1和文檔2，它們的分詞結(jié)果分別為“交大＄學(xué)者#”和“復(fù)旦＄大學(xué)#”，其中＄為分隔符，#為終止符。對于搜索串“大學(xué)”，文檔1和2都應(yīng)出現(xiàn)在搜索結(jié)果當(dāng)中，但是語義角度上文檔2中 “大學(xué)”的出現(xiàn)更有意義，而文檔1中“大學(xué)”的出現(xiàn)只是文字上的巧合，并無實際意義，所以在結(jié)果中文檔2的排序在文檔1之前是更加合理的。基于這個觀察結(jié)果，現(xiàn)將任意字符串的后綴分為兩類：好后綴和壞后綴。好后綴為從字符串的開頭或者分隔符＄后一個字符開始的后綴，壞后綴為剩余所有后綴。對這兩種后綴分別建立廣義后綴樹，分別稱作好后綴樹和壞后綴樹。

圖2和圖3為好后綴樹和壞后綴樹的一個實例。將兩樹拆分后自然而然達(dá)到了語義有意義和無意義的搜索結(jié)果的排序。從應(yīng)用上考慮，搜索結(jié)果總是被按批請求的，如請求某搜索串的前N個結(jié)果。大多數(shù)情況下好后綴樹給出的結(jié)果數(shù)就足夠應(yīng)對請求，這時候不必再搜索壞后綴樹。由于拆分后好后綴樹比原樹結(jié)構(gòu)簡單很多，搜索好后綴樹比原搜索樹速度更快，總體的搜索時間效率不降反升。

圖2 {“動物＄世界#”,“世界＄物語#”}的好后綴樹結(jié)構(gòu)

圖3 {“動物＄世界#”,“世界＄物語#”}的壞后綴樹結(jié)構(gòu)

2.2 支持域搜索

除了葉子節(jié)點外，中間節(jié)點也需要記錄文檔ID。搜索可能最終落在葉子節(jié)點或者中間節(jié)點上。對于最終落在中間節(jié)點的搜索串，因為一定都包含在祖先是該中間節(jié)點的所有葉子節(jié)點所對應(yīng)的后綴串中，所以搜索結(jié)果集合包含且僅包含這些葉子節(jié)點所對應(yīng)的文檔ID。為了快速得到該文檔ID集合，在中間節(jié)點中記錄該節(jié)點下的所有葉子節(jié)點對應(yīng)的文檔ID的集合。

上述結(jié)構(gòu)有相當(dāng)多冗余數(shù)據(jù)，圖4是該結(jié)構(gòu)的一個實例。從葉子節(jié)點到根節(jié)點的路徑上都需要記錄該葉子節(jié)點對應(yīng)的文檔ID。當(dāng)文檔集合增大時，節(jié)點的文檔ID集合也相應(yīng)增大，這個現(xiàn)象對于上層節(jié)點尤為突出。為了解決該問題，引入如圖4所示的結(jié)構(gòu)。

圖4 中間節(jié)點記錄文檔ID的廣義后綴樹結(jié)構(gòu)

文檔ID序列包含所有文檔ID，初始為空。葉子節(jié)點先記錄其對應(yīng)后綴所在的文檔ID。后序遍歷整棵廣義后綴樹，對于葉子節(jié)點，將其對應(yīng)的文檔ID加入文檔ID序列當(dāng)中。對于其他任何節(jié)點，在訪問其子節(jié)點前記下文檔ID序列當(dāng)前長度S，在訪問子節(jié)點后也記下文檔ID序列當(dāng)前長度E,則任何節(jié)點的文檔ID集合就是文檔ID序列中下標(biāo)區(qū)間為[S,E)的所有文檔ID。

圖5是該結(jié)構(gòu)的一個實例。除葉子節(jié)點外的所有節(jié)點不必記錄其對應(yīng)的所有文檔ID集合，只需要記錄其對應(yīng)的所有文檔ID集合在文檔ID序列中的起止位置，大大降低了索引結(jié)構(gòu)的空間占用。另外，由于文檔ID由原來的散落在樹狀結(jié)構(gòu)的各個位置變成了集中在一個序列當(dāng)中，可以更有效地對其進(jìn)行壓縮。

圖5 {a#, a＄b#, ab#}的文檔ID序列結(jié)構(gòu)

域搜索指的是單詞本身帶有域信息(如屬于標(biāo)題、作者等)，在搜索過程中可以指定一個或多個域作為篩選條件，只在符合篩選條件的域中給出搜索結(jié)果。在這種情況下，文檔中的內(nèi)容會被劃分成多個域，各個域的內(nèi)容是獨立的，在構(gòu)建索引的過程中，不是將整個文檔作為單詞加入單詞集合，而是將各個域的內(nèi)容作為單詞加入單詞集合。為了支持域搜索，在文檔ID序列結(jié)構(gòu)的基礎(chǔ)上進(jìn)行改動。

假設(shè)總共有n個域，將文檔ID序列拆分成n份，每份存儲各自域的文檔ID，節(jié)點存儲各個域的起止下標(biāo)。假設(shè)文檔1有三個域{1, 2, 3}，內(nèi)容分別為a#、a＄b#、ab#，那么僅此文檔構(gòu)建出的上述結(jié)構(gòu)如圖6所示。該方案在搜索時只需要將符合域搜索條件的文檔ID集合合并，可以直接得到結(jié)果文檔ID序列。

域1 的文檔ID序列

下標(biāo)0文檔ID1

域2的文檔ID序列

域3的文檔ID序列

圖6 支持域搜索的文檔ID序列結(jié)構(gòu)

3 廣義后綴樹索引的壓縮

文檔ID序列是一個整數(shù)序列，壓縮使用基于Simple-9和Simple-16的壓縮算法。

文獻(xiàn)[8]提出了適用于64位的Simple算法(稱為SimpleX64)。解決了Simple-9算法適用范圍少和浪費存儲空間的問題。SimpleX64以長度為64比特的字作為編碼解碼的最小單位。表1是SimpleX64-16的一種可能的編碼方式。

表1 SimpleX64算法的一種實現(xiàn)的各個模式編碼方式

表1中一些復(fù)雜表達(dá)式，如模式1的20×1+20×2的意義為：20個1比特的整數(shù)和20個2比特的整數(shù)。以整數(shù)序列{128, 128, 128, 128, 128, 0, 0, 0}為例，由于128占8字節(jié)，所以模式0～7都不適用；由于第5個128也占8個字節(jié)，所以模式8也不適用；前7個整數(shù)都占8個字節(jié)以內(nèi)，所以模式9適用。將前7個數(shù)字編碼成一個64比特的字，最后1個0只能適用于模式15，也編碼成一個64比特的字，最終該序列被編碼成2個64比特的字。

文檔ID序列是一個標(biāo)準(zhǔn)的從0開始的整數(shù)序列，適合用Simple算法進(jìn)行壓縮。起止位置信息也是一個整數(shù)序列，可以進(jìn)行類似的壓縮。另外，將終止位置改成跨越的長度，即 (終止位置-起始位置)。每個整數(shù)所占的平均比特數(shù)會下降，進(jìn)一步提升壓縮性能。

4 實 驗

本實驗的實驗數(shù)據(jù)集共包含200 000條節(jié)目信息。每條節(jié)目信息包含標(biāo)題、導(dǎo)演、演員、關(guān)鍵字和標(biāo)簽共5個可搜索域。

4.1 文檔ID序列結(jié)構(gòu)實驗

本實驗旨在測試2.2節(jié)中提及的文檔ID序列結(jié)構(gòu)對搜索效率的影響。對于原解決方案(所有節(jié)點中都存儲文檔ID集合)和文檔ID序列解決方案在數(shù)據(jù)集大小分別為10 000、20 000、50 000和100 000的首字母索引中做以下實驗：隨機(jī)生成長度為2～4不等的搜索串。每一種長度的搜索串25個，總共75種搜索串。對于每一種搜索串，不考慮域篩選的影響，都為如下域篩選條件：{標(biāo)題，導(dǎo)演，演員，關(guān)鍵字，標(biāo)簽}，共75種搜索條件。對于每種搜索條件都進(jìn)行100 000次串行搜索，在搜索結(jié)果正確的前提下，檢查它們的時間消耗。實驗結(jié)果如表2所示。

表2 原解決方案和文檔ID序列搜索時間效率對比

文檔ID序列解決方案和原解決方案在時間效率上幾乎不存在差別。表3展示了文檔ID序列解決方案和原解決方案在各個數(shù)據(jù)集上存儲文檔ID所需空間的對比。

表3 原解決方案和文檔ID序列空間效率對比

可以看到文檔ID序列方案在處理數(shù)據(jù)冗余方面有著很好的性能，整數(shù)序列形式益于壓縮管理，同時不降低搜索時間效率。

4.2 索引壓縮實驗

本實驗旨在對第3節(jié)中描述的整數(shù)序列壓縮算法在本索引結(jié)構(gòu)的文檔ID序列結(jié)構(gòu)上的性能進(jìn)行驗證。

實驗過程為：在大小分別為10 000、20 000、50 000和100 000的數(shù)據(jù)集上建立索引和其對應(yīng)的文檔ID序列。對文檔ID序列分別以Elias Gamma Code, Elias Delta Code和SimpleX64-16算法進(jìn)行壓縮，對比壓縮前和壓縮后的文檔ID序列大小。實驗結(jié)果如圖7所示。

圖7 各壓縮算法的壓縮比

無論是何種數(shù)據(jù)集，Simple算法的壓縮性能都是最優(yōu)的，加之文檔ID序列本身的優(yōu)化，文檔ID總共可以減少82%以上的空間。

4.3 Lucene引擎搜索時間效率對比實驗

本實驗旨在對比第2節(jié)中提出的后綴樹索引和基于倒排表的Lucene引擎[9]的搜索時間效率。實驗方式為：在大小為10 000、20 000、50 000、100 000和200 000的數(shù)據(jù)集上用兩種方式分別建立首字母索引。隨機(jī)生成長度為2～4不等的搜索串。每一種長度的搜索串25個，總共75種搜索串。對于每一種搜索串，不考慮域篩選的影響，都為如下域篩選條件：{標(biāo)題，導(dǎo)演，演員，關(guān)鍵字，標(biāo)簽}，共75種搜索條件。對于每種搜索條件都進(jìn)行100 000次串行搜索，在搜索結(jié)果正確的前提下，檢查它們的時間消耗。實驗結(jié)果如圖8所示。

圖8 與Lucene的搜索時間效率對比

第2節(jié)中描述的后綴樹索引在任何數(shù)據(jù)集上都有著比Lucene更好的搜索時間效率，該結(jié)果在小數(shù)據(jù)集上更加明顯。在數(shù)據(jù)集小于50 000的情況下，本文索引結(jié)構(gòu)的搜索效率可以達(dá)到Lucene的7～10倍。

5 結(jié) 語

本文提出了一個高效快速的面向中文分詞的解決全文檢索問題的后綴樹索引。在傳統(tǒng)的后綴樹索引上進(jìn)行了改良，加快了其搜索時間效率的同時盡量減少其空間占用。經(jīng)過實驗對比，本文的索引結(jié)構(gòu)比Lucene有著更高的搜索時間效率。另外實驗分析得出了對文檔ID序列壓縮效率最高的壓縮算法，進(jìn)一步減少了索引的空間占用。