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

張 天 皓

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

0 引 言

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

1 相關(guān)工作

后綴樹(suffix tree)是一種數(shù)據(jù)結(jié)構(gòu)，是PAT樹的一種，經(jīng)常被運(yùn)用在字符串匹配等字符串相關(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個(gè)后綴的后綴樹。廣義后綴樹最常被用于生物信息學(xué)。

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

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

數(shù)據(jù)壓縮指的是將數(shù)據(jù)以另一種形式編碼，使其比原本的表示方法占用更少的比特?cái)?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為一個(gè)廣義后綴樹的實(shí)例，其中＄表示分隔符，#表示終止符。在搜索時(shí)＄會被忽略，分詞在數(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)只是文字上的巧合，并無實(shí)際意義，所以在結(jié)果中文檔2的排序在文檔1之前是更加合理的。基于這個(gè)觀察結(jié)果，現(xiàn)將任意字符串的后綴分為兩類：好后綴和壞后綴。好后綴為從字符串的開頭或者分隔符＄后一個(gè)字符開始的后綴，壞后綴為剩余所有后綴。對這兩種后綴分別建立廣義后綴樹，分別稱作好后綴樹和壞后綴樹。

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

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

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

2.2 支持域搜索

除了葉子節(jié)點(diǎn)外，中間節(jié)點(diǎn)也需要記錄文檔ID。搜索可能最終落在葉子節(jié)點(diǎn)或者中間節(jié)點(diǎn)上。對于最終落在中間節(jié)點(diǎn)的搜索串，因?yàn)橐欢ǘ及谧嫦仁窃撝虚g節(jié)點(diǎn)的所有葉子節(jié)點(diǎn)所對應(yīng)的后綴串中，所以搜索結(jié)果集合包含且僅包含這些葉子節(jié)點(diǎn)所對應(yīng)的文檔ID。為了快速得到該文檔ID集合，在中間節(jié)點(diǎn)中記錄該節(jié)點(diǎn)下的所有葉子節(jié)點(diǎn)對應(yīng)的文檔ID的集合。

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

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

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

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

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

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

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

域1 的文檔ID序列

下標(biāo)0文檔ID1

域2的文檔ID序列

域3的文檔ID序列

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

3 廣義后綴樹索引的壓縮

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

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

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

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

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

4 實(shí) 驗(yàn)

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

4.1 文檔ID序列結(jié)構(gòu)實(shí)驗(yàn)

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

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

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

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

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

4.2 索引壓縮實(shí)驗(yàn)

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

實(shí)驗(yà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序列大小。實(shí)驗(yàn)結(jié)果如圖7所示。

圖7 各壓縮算法的壓縮比

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

4.3 Lucene引擎搜索時(shí)間效率對比實(shí)驗(yàn)

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

圖8 與Lucene的搜索時(shí)間效率對比

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

5 結(jié) 語

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