張敏 李唯 范青

關(guān)鍵詞：科技文獻(xiàn)；語(yǔ)義組織；混合倒排索引；HashMap；Treap；B+樹(shù)

在科技文獻(xiàn)語(yǔ)義檢索領(lǐng)域，為滿足廣大科研人員對(duì)科技文獻(xiàn)內(nèi)部細(xì)粒度語(yǔ)義信息進(jìn)行高效查詢的迫切需求，前期研究提出了一個(gè)面向科技文獻(xiàn)的多維語(yǔ)義索引體系。該多維語(yǔ)義索引體系旨在通過(guò)科技文獻(xiàn)不同維度的細(xì)粒度語(yǔ)義信息，從不同的角度來(lái)綜合回答復(fù)雜的細(xì)粒度語(yǔ)義信息查詢，其維度代表了語(yǔ)義信息的不同細(xì)粒度層面。根據(jù)科技文獻(xiàn)內(nèi)部語(yǔ)義信息細(xì)粒度的不同，該索引體系主要包括文獻(xiàn)索引、句子索引、知識(shí)對(duì)象索引和知識(shí)關(guān)系索引這4個(gè)語(yǔ)義維度的索引。文獻(xiàn)索引指的是對(duì)文獻(xiàn)語(yǔ)篇維度的元數(shù)據(jù)信息構(gòu)建索引，句子索引則是針對(duì)文本句子所處的語(yǔ)步位置構(gòu)建索引，知識(shí)對(duì)象索引是指針對(duì)語(yǔ)義標(biāo)注的知識(shí)對(duì)象構(gòu)建索引，而知識(shí)關(guān)系索引主要涉及對(duì)知識(shí)對(duì)象之間的關(guān)系進(jìn)行索引構(gòu)建。在信息檢索領(lǐng)域，最常用的索引表示方式是倒排索引，其構(gòu)建方法對(duì)于信息檢索的查詢效率至關(guān)重要。傳統(tǒng)的倒排索引構(gòu)建方法通常使用Hash-Map來(lái)存儲(chǔ)每個(gè)單詞及其在文檔中的位置信息。這種方法簡(jiǎn)單有效，在早期基于關(guān)鍵詞的檢索任務(wù)中表現(xiàn)出色。然而，研究結(jié)果表明，當(dāng)使用Hash-Map作為數(shù)據(jù)結(jié)構(gòu)來(lái)存儲(chǔ)這4個(gè)語(yǔ)義維度的倒排索引信息時(shí)，查詢效率比較低下。

為了解決這一問(wèn)題，本文通過(guò)使用科技文獻(xiàn)不同維度的語(yǔ)義特征來(lái)建立混合倒排索引，以提高語(yǔ)義查詢的性能。本文嘗試了多種數(shù)據(jù)結(jié)構(gòu)，如Treap、B+樹(shù)等，來(lái)探索適用于不同語(yǔ)義維度的倒排索引構(gòu)建方法，并將它們組合起來(lái)形成適用于科技文獻(xiàn)多維語(yǔ)義組織的混合倒排索引構(gòu)建方法。Jantkal B A等通過(guò)混合使用B樹(shù)和HashMap優(yōu)化索引性能的方法給本文提出混合數(shù)據(jù)結(jié)構(gòu)提供了借鑒思路。此外，本文還進(jìn)行了對(duì)比實(shí)驗(yàn)，比較了不同類型的混合倒排索引構(gòu)建方法在排序查詢和布爾查詢條件下的查詢效率，以確定哪種混合倒排索引構(gòu)建方法在特定的場(chǎng)景下更為適用。本文提出的面向科技文獻(xiàn)多維語(yǔ)義組織的混合倒排索引構(gòu)建方法能有效解決單一索引結(jié)構(gòu)導(dǎo)致的查詢效率問(wèn)題，其研究成果對(duì)于提高科技文獻(xiàn)的語(yǔ)義查詢效率具有重要的實(shí)際意義。

1倒排索引構(gòu)建方法相關(guān)研究

在傳統(tǒng)的倒排索引構(gòu)建方法中，使用HashMap作為數(shù)據(jù)結(jié)構(gòu)是常見(jiàn)的選擇。然而，隨著研究的深入，學(xué)者們提出了一些采用其他數(shù)據(jù)結(jié)構(gòu)的倒排索引構(gòu)建方法，以進(jìn)一步提高查詢效率，主要有4類構(gòu)建方法。

1.1基于排序數(shù)組的倒排索引構(gòu)建方法

Frakes W B提出了一種基于排序數(shù)組的倒排索引構(gòu)建方法。這種方法將關(guān)鍵字列表存儲(chǔ)在一個(gè)排序數(shù)組中，并包括與每個(gè)關(guān)鍵字相關(guān)聯(lián)的文檔數(shù)量和指向包含該關(guān)鍵字的文檔的鏈接。該方法有效地提升了查詢效率，但其主要缺點(diǎn)是當(dāng)添加新關(guān)鍵字時(shí)，更新索引的成本較高。這種方法在查詢效率上表現(xiàn)優(yōu)秀，但是在索引更新時(shí)的成本較高，不適用于需要頻繁更新的場(chǎng)景。

1.2基于B樹(shù)的倒排索引構(gòu)建方法

B樹(shù)被Kraska T等用來(lái)構(gòu)建倒排索引，在B樹(shù)中，每個(gè)鍵代表1個(gè)最短的單詞，并用于區(qū)分存儲(chǔ)在下一級(jí)別的鍵，這些鍵不需要是索引中實(shí)際術(shù)語(yǔ)的前綴。與排序數(shù)組相比，B樹(shù)在查詢效率上表現(xiàn)優(yōu)秀，但會(huì)使用更多的存儲(chǔ)空間。這種方法適用于需要頻繁查詢而不需要頻繁更新的場(chǎng)景。

1.3基于樹(shù)堆的倒排索引構(gòu)建方法

Konow R等提出了一種基于樹(shù)堆（Treap）的倒排索引構(gòu)建方法。該方法利用相似空間，能更快速地對(duì)并集和交集進(jìn)行排序。使用Treap允許在設(shè)置頻率閾值的同時(shí)，對(duì)文檔標(biāo)識(shí)符進(jìn)行交叉／合并，而不必采用兩步經(jīng)典處理方法，從而降低成本。作者進(jìn)行的實(shí)驗(yàn)結(jié)果表明，相較于基于HashMap的倒排索引構(gòu)建方法，這種構(gòu)建方法可將所需存儲(chǔ)空間減少約20%，并將查詢執(zhí)行速度提高了3倍。該方法在存儲(chǔ)空間和查詢效率上都表現(xiàn)良好。

1.4基于小波樹(shù)的倒排索引構(gòu)建方法

Gupta A等和Yadav A K等提出了一種基于小波樹(shù)（Wavelet Tree）的倒排索引構(gòu)建方法，該方法旨在優(yōu)化存儲(chǔ)索引所需的空間和檢索文檔所需的時(shí)間，同時(shí)保持良好的結(jié)果。作者使用100萬(wàn)個(gè)Wikipedia頁(yè)面的數(shù)據(jù)庫(kù)，將這種新索引與基于B樹(shù)的索引進(jìn)行了性能對(duì)比測(cè)試。實(shí)驗(yàn)結(jié)果顯示，在查詢長(zhǎng)度增加時(shí)，基于小波樹(shù)的索引相比基于B樹(shù)的索引具有更高的查詢效率。

綜上所述，不同類型的倒排索引構(gòu)建方法采用了B樹(shù)、小波樹(shù)等數(shù)據(jù)結(jié)構(gòu)，有效提升了查詢效率。然而，這些數(shù)據(jù)結(jié)構(gòu)并不適用于所有場(chǎng)景，選擇數(shù)據(jù)結(jié)構(gòu)必須考慮實(shí)際場(chǎng)景并進(jìn)行評(píng)估和權(quán)衡。在本文所探討的科技文獻(xiàn)多維語(yǔ)義組織領(lǐng)域中，需要根據(jù)科技文獻(xiàn)不同語(yǔ)義維度的信息特征，選擇最合適的數(shù)據(jù)結(jié)構(gòu)，以有效解決由單一索引結(jié)構(gòu)導(dǎo)致的查詢效率問(wèn)題。

2混合式多維語(yǔ)義索引構(gòu)建方法

本文首先對(duì)科技文獻(xiàn)多維語(yǔ)義索引的信息特征進(jìn)行分析，隨后對(duì)Treap和B+樹(shù)這兩種數(shù)據(jù)結(jié)構(gòu)進(jìn)行評(píng)估，并在此基礎(chǔ)上探索了適用于不同語(yǔ)義維度的倒排索引構(gòu)建方法。最后，將這些方法組合形成多種適用于科技文獻(xiàn)多維語(yǔ)義組織的混合倒排索引構(gòu)建方法。

2.1多維語(yǔ)義索引的信息特征

本文旨在通過(guò)面向科技文獻(xiàn)不同維度的信息特征建立混合倒排索引，信息特征主要通過(guò)存儲(chǔ)在不同維度的倒排索引中的信息來(lái)體現(xiàn)。表1概述了這4個(gè)維度的信息特征。

在文獻(xiàn)語(yǔ)篇維度，文獻(xiàn)倒排索引是一種存儲(chǔ)文檔與關(guān)鍵詞關(guān)系的索引結(jié)構(gòu)，它包含文檔ID（Do-cld）和關(guān)鍵詞的詞頻信息（TF）。為了適應(yīng)各種查詢需求，尤其是排序查詢需求，這個(gè)倒排索引需要具備足夠的靈活性。它會(huì)存儲(chǔ)詞頻信息，以便通過(guò)TF-IDF、BM25或其他術(shù)語(yǔ)權(quán)重計(jì)算方法計(jì)算相似度，并最終按照相似度進(jìn)行排序。術(shù)語(yǔ)權(quán)重計(jì)算需要在查詢時(shí)完成，這可能會(huì)增加查詢處理時(shí)間。

在文本句子維度，句子倒排索引不僅需要存儲(chǔ)文檔ID和關(guān)鍵詞的詞頻信息，還需要存儲(chǔ)句子所處的語(yǔ)步位置ID（Moveld）。語(yǔ)步在語(yǔ)言學(xué)中被定義為實(shí)現(xiàn)交流功能的修辭單位。在科研論文中，語(yǔ)步包括研究背景、目的、方法、結(jié)果以及結(jié)論等要素，這些要素能夠簡(jiǎn)潔明了地反映科研論文所表達(dá)的主要意圖。例如，如果一個(gè)句子描述了科研論文的研究方法，則該句子所處的位置可以被認(rèn)為是方法。句子所處的語(yǔ)步位置是科技文獻(xiàn)內(nèi)部細(xì)粒度語(yǔ)義信息的一種重要表示形式，需要將語(yǔ)步位置信息存儲(chǔ)到句子倒排索引中。

在知識(shí)對(duì)象維度，知識(shí)對(duì)象倒排索引存儲(chǔ)的信息主要包括通過(guò)語(yǔ)義標(biāo)注技術(shù)識(shí)別出的知識(shí)對(duì)象。為了提高科技文獻(xiàn)語(yǔ)義檢索的準(zhǔn)確性，前期研究提出了一種基于語(yǔ)義信息的術(shù)語(yǔ)權(quán)重算法。該算法綜合考慮了知識(shí)對(duì)象在文獻(xiàn)中的語(yǔ)義信息（包括知識(shí)對(duì)象及其關(guān)系）和在文本中的頻率，并使用語(yǔ)義信息權(quán)重來(lái)衡量知識(shí)對(duì)象在科技文獻(xiàn)中的重要性。因此，知識(shí)對(duì)象倒排索引存儲(chǔ)的信息不僅包括文檔ID和知識(shí)對(duì)象的詞頻信息，還包括知識(shí)對(duì)象的語(yǔ)義信息權(quán)重（記作SIW）。

在知識(shí)關(guān)系維度，知識(shí)關(guān)系倒排索引存儲(chǔ)知識(shí)對(duì)象之間的關(guān)系數(shù)據(jù)，這種關(guān)系數(shù)據(jù)以SPO三元組的形式進(jìn)行表述?！爸R(shí)對(duì)象一連接詞一知識(shí)對(duì)象”構(gòu)成了知識(shí)關(guān)系三元組的基本形式。每組知識(shí)關(guān)系的倒排列表由S、P和0的3個(gè)列表組成。其中，S、P和0分別代表三元組中的主語(yǔ)、謂語(yǔ)和賓語(yǔ)。

2.2索引數(shù)據(jù)結(jié)構(gòu)分析

倒排索引構(gòu)建方法除了采用常用的數(shù)據(jù)結(jié)構(gòu)HashMap，國(guó)內(nèi)外學(xué)者還提出了基于B樹(shù)的倒排索引構(gòu)建方法、基于小波樹(shù)的倒排索引構(gòu)建方法等。本文在前人研究的基礎(chǔ)上，主要對(duì)Treap和B+樹(shù)這兩種數(shù)據(jù)結(jié)構(gòu)在構(gòu)建倒排索引方面進(jìn)行了評(píng)估分析。評(píng)估這兩種數(shù)據(jù)結(jié)構(gòu)的原因有兩個(gè)方面：一方面，研究人員Konow R等發(fā)現(xiàn)，在處理排序查詢時(shí)，相比使用HashMap構(gòu)建倒排索引，使用Treap速度更快且占用空間更少；另一方面，B+樹(shù)是常用于索引構(gòu)建的一種數(shù)據(jù)結(jié)構(gòu)，能夠高效地支持范圍查詢和排序，并被廣泛應(yīng)用于RDF數(shù)據(jù)索引的構(gòu)建。RDF表示資源描述框架，它以SPO三元組的形式組織數(shù)據(jù)。一些知名的RDF系統(tǒng)，如RDF-3X和Hexastore，利用B+樹(shù)按不同的S、P、0順序構(gòu)建RDF數(shù)據(jù)索引。科技文獻(xiàn)內(nèi)部細(xì)粒度語(yǔ)義信息中，知識(shí)關(guān)系描述的是知識(shí)對(duì)象之間的關(guān)系。例如，使用“知識(shí)對(duì)象一連接詞一知識(shí)對(duì)象”來(lái)表示這些關(guān)系。這種表示方式也采用了SPO三元組的形式組織，可以嘗試?yán)肂+樹(shù)來(lái)構(gòu)建知識(shí)關(guān)系倒排索引。

Treap是一種將二叉搜索樹(shù)和堆結(jié)合起來(lái)的數(shù)據(jù)結(jié)構(gòu)，每個(gè)節(jié)點(diǎn)都有1個(gè)鍵和1個(gè)屬性（優(yōu)先級(jí)），該屬性隨機(jī)分配給一個(gè)鍵。Treap中的鍵值按照二叉搜索樹(shù)的屬性進(jìn)行排序。每個(gè)節(jié)點(diǎn)的優(yōu)先級(jí)值大于或等于其子節(jié)點(diǎn)的優(yōu)先級(jí)值，以支持堆的順序，而堆的順序由樹(shù)的結(jié)構(gòu)決定。根節(jié)點(diǎn)的優(yōu)先級(jí)值是Treap中最大的。Treap作為一種結(jié)合了二叉搜索樹(shù)和堆的數(shù)據(jù)結(jié)構(gòu)，能夠提供較快的排序查詢處理，并且占用較少的存儲(chǔ)空間。

B+樹(shù)是B樹(shù)的一種變體，在數(shù)據(jù)庫(kù)和文件系統(tǒng)中得到廣泛應(yīng)用。它通過(guò)自底向上的插入方式和葉子節(jié)點(diǎn)的鏈表鏈接，提供了快速的排序查詢能力。B+樹(shù)的非葉子節(jié)點(diǎn)僅存儲(chǔ)鍵值，而數(shù)據(jù)存儲(chǔ)在葉子節(jié)點(diǎn)中。葉子節(jié)點(diǎn)按照關(guān)鍵字的升序排列，并以鏈表的方式鏈接在一起。在查詢時(shí)，B+樹(shù)會(huì)沿著最左匹配原則繼續(xù)向下查找，直到找到包含查詢關(guān)鍵字的葉子節(jié)點(diǎn)。B+樹(shù)在構(gòu)建較大文本的索引方面的支持有限，但在處理具有層次結(jié)構(gòu)的文本數(shù)據(jù)和路徑導(dǎo)航方面表現(xiàn)出色。它能夠提供快速的路徑導(dǎo)航和查詢能力，特別適用于具有層次結(jié)構(gòu)的數(shù)據(jù)。

基于以上分析，本文將采用HashMap、Treap和B+樹(shù)這3種數(shù)據(jù)結(jié)構(gòu)作為倒排索引構(gòu)建方法。這樣可以充分利用HashMap的快速查找特性，以及Treap的優(yōu)化空間利用以及B+樹(shù)的適應(yīng)路徑索引的能力。通過(guò)結(jié)合這些不同的數(shù)據(jù)結(jié)構(gòu)，就可以構(gòu)建出高效、靈活并且滿足不同查詢需求的倒排索引。

2.3混合倒排索引構(gòu)建

本文旨在結(jié)合多維語(yǔ)義索引的信息特征和索引數(shù)據(jù)結(jié)構(gòu)進(jìn)行應(yīng)用分析，探索混合倒排索引構(gòu)建的實(shí)際應(yīng)用。具體而言，本文將分析如何有效地采用HashMap、Treap和B+樹(shù)這3種數(shù)據(jù)結(jié)構(gòu)作為適用于4個(gè)維度的倒排索引構(gòu)建方法。

2.3.1采用HashMap作為倒排索引的構(gòu)建方法

采用HashMap作為4個(gè)倒排索引的構(gòu)建方法具有相似性。在該方法中，HashMap的鍵和值分別對(duì)應(yīng)著倒排索引的詞匯表?xiàng)l目和相關(guān)的倒排列表。以采用HashMap構(gòu)建知識(shí)對(duì)象倒排索引為例，每個(gè)知識(shí)對(duì)象被用作HashMap的鍵，對(duì)應(yīng)的倒排列表被視為該鍵所對(duì)應(yīng)的值。倒排列表是指包含了知識(shí)對(duì)象的所有文檔的列表，倒排項(xiàng)是指倒排列表中的每個(gè)條目，它代表了一個(gè)知識(shí)對(duì)象在某個(gè)文檔中的出現(xiàn)情況。每個(gè)倒排項(xiàng)通常包含了文檔ID和其他相關(guān)的信息，如權(quán)重（如TF、TF-IDF）或其他語(yǔ)義信息。

2.3.2采用Treap作為倒排索引的構(gòu)建方法

Treap是一種近期被廣泛應(yīng)用于存儲(chǔ)倒排索引信息的數(shù)據(jù)結(jié)構(gòu)。相較于其他數(shù)據(jù)結(jié)構(gòu)，Treap在減少查詢處理時(shí)間和內(nèi)存使用方面表現(xiàn)出顯著優(yōu)勢(shì)。采用Treap作為倒排索引的構(gòu)建方法將倒排列表表示為1個(gè)Treap，其中每個(gè)倒排項(xiàng)被視為T(mén)reap的1個(gè)節(jié)點(diǎn)。該節(jié)點(diǎn)能夠同時(shí)存儲(chǔ)文檔ID和權(quán)重信息（如TF、TF-IDF等）。這種構(gòu)建方法提供了高效支持排序查詢的能力。

如表1所示，文獻(xiàn)倒排索引的存儲(chǔ)信息主要包括文檔ID信息（Docld）和詞頻信息（TF）。該方法將Docld作為節(jié)點(diǎn)的鍵值，TF作為節(jié)點(diǎn)的優(yōu)先級(jí)值。倒排列表中的倒排項(xiàng)按照Docld的大小進(jìn)行遞增排序，并保持對(duì)TF的堆排序。

句子倒排索引的存儲(chǔ)信息主要由Docld、TF和Moveld組成，由于Treap的每個(gè)節(jié)點(diǎn)只能包含1個(gè)鍵值對(duì)，即鍵和優(yōu)先級(jí)值，需要對(duì)其進(jìn)行修改以存儲(chǔ)額外的信息。為此，本文將TF和Moveld的值結(jié)合起來(lái)生成Treap節(jié)點(diǎn)的優(yōu)先級(jí)值。組合方法需要快速編碼和解碼，因?yàn)榫幋a和解碼時(shí)間會(huì)影響查詢處理時(shí)間。優(yōu)先級(jí)值是通過(guò)將TF的值與1個(gè)“0”字符連接，并乘以Moveld的值來(lái)建立的。例如，如果TF為10，Moveld為1，則它們的組合將是1001000。要解碼該序列，本文從序列的右側(cè)開(kāi)始，一直找到1—9之間的數(shù)字，這個(gè)數(shù)字提供Moveld的值，左邊的數(shù)字則是TF的值。

知識(shí)對(duì)象倒排索引的存儲(chǔ)信息由Docld、TF和語(yǔ)義信息權(quán)重SIW組成，由于Treap的每個(gè)節(jié)點(diǎn)只能包含1個(gè)鍵值對(duì)，即鍵和優(yōu)先級(jí)值，需要進(jìn)行一些修改以存儲(chǔ)額外的信息。本文將TF和SIW的值按照上述相同的組合方法結(jié)合起來(lái)，為T(mén)reap中的節(jié)點(diǎn)生成優(yōu)先級(jí)值。

知識(shí)關(guān)系倒排索引的存儲(chǔ)信息由S、P和0 3個(gè)獨(dú)立的列表組成，由于Treap只能表示1個(gè)鍵值對(duì)列表，而無(wú)法同時(shí)表示多個(gè)列表。此外，對(duì)于知識(shí)關(guān)系倒排索引中的信息，維護(hù)堆排序沒(méi)有任何意義。因此，Treap不適用于作為知識(shí)關(guān)系倒排索引的構(gòu)建方法。

2.3.3采用B+樹(shù)作為倒排索引的構(gòu)建方法

B+樹(shù)并不適合用于構(gòu)建較大文本的倒排索引，因?yàn)樗乃饕荡鎯?chǔ)會(huì)占用較大的空間，從而導(dǎo)致B+樹(shù)的深度增加，進(jìn)而影響查詢效率。文獻(xiàn)倒排索引和句子倒排索引通常都是針對(duì)較大文本構(gòu)建倒排索引。另外，從索引更新操作這層因素考慮，文獻(xiàn)倒排索引和句子倒排索引會(huì)隨著文獻(xiàn)的不斷增加而頻繁更新，而B(niǎo)+樹(shù)因?yàn)樾枰３制胶庑远鴮?dǎo)致插入和刪除操作相對(duì)較慢，從而可能會(huì)影響倒排索引構(gòu)建效率。B+樹(shù)并不適合作為文獻(xiàn)倒排索引和句子倒排索引的構(gòu)建方法。此外，B+樹(shù)的非葉子節(jié)點(diǎn)不存儲(chǔ)數(shù)據(jù)，只在葉子節(jié)點(diǎn)存儲(chǔ)關(guān)鍵詞。而知識(shí)對(duì)象倒排索引需要額外存儲(chǔ)語(yǔ)步位置ID（Moveld）的信息，這個(gè)附加信息無(wú)法通過(guò)B+樹(shù)來(lái)存儲(chǔ)。因此．B+樹(shù)也不適合作為知識(shí)對(duì)象倒排索引的構(gòu)建方法。

知識(shí)關(guān)系倒排索引的存儲(chǔ)信息是知識(shí)對(duì)象與知識(shí)對(duì)象之間的關(guān)系，以SPO三元組的形式表達(dá)，可以采用B+樹(shù)構(gòu)建知識(shí)關(guān)系倒排索引。由于知識(shí)關(guān)系三元組數(shù)據(jù)中包含大量文字信息，需要足夠的磁盤(pán)空間來(lái)存儲(chǔ)這些數(shù)據(jù)以建立倒排索引。為此，可以首先對(duì)知識(shí)關(guān)系三元組進(jìn)行整數(shù)序列化，即按照一定的編碼規(guī)則對(duì)S、P和0進(jìn)行編碼。然后，利用這些編碼之間的關(guān)系來(lái)構(gòu)建B+樹(shù)的邏輯層次結(jié)構(gòu)。這樣可以通過(guò)B+樹(shù)提供的高效索引結(jié)構(gòu)，快速定位到相關(guān)的知識(shí)關(guān)系倒排列表，從而實(shí)現(xiàn)高效的語(yǔ)義查詢。

2.3.4混合倒排索引構(gòu)建方法

經(jīng)過(guò)以上分析，可以得出適用于構(gòu)建知識(shí)關(guān)系倒排索引的方法有B+樹(shù)和HashMap，而用于構(gòu)建知識(shí)對(duì)象倒排索引的方法可以采用HashMap和Treap。對(duì)于文獻(xiàn)倒排索引和句子倒排索引，由于它們都是針對(duì)大文本，它們的構(gòu)建方法應(yīng)該保持一致，即采用HashMap和Treap。因此，本文提出的混合倒排索引構(gòu)建方法共有8種可能的組合方式。為了方便記錄，本文使用相應(yīng)數(shù)據(jù)結(jié)構(gòu)名稱的首字母來(lái)表示，例如，H代表HashMap，B代表B+樹(shù)，T代表Treap。具體的混合倒排索引構(gòu)建方法如表2所示。在表2中，TTHB表示采用Treap作為文獻(xiàn)倒排索引和句子倒排索引的構(gòu)建方法，采用HashMap作為知識(shí)對(duì)象倒排索引的構(gòu)建方法，以及采用B+樹(shù)作為知識(shí)關(guān)系倒排索引的構(gòu)建方法，簡(jiǎn)記為C8。

3實(shí)驗(yàn)設(shè)計(jì)及結(jié)果分析

3.1實(shí)驗(yàn)設(shè)計(jì)介紹

本實(shí)驗(yàn)選取了來(lái)自arXiv平臺(tái)的10萬(wàn)篇物理領(lǐng)域科研論文作為初始數(shù)據(jù)集，并進(jìn)行語(yǔ)義標(biāo)注，抽取文獻(xiàn)元數(shù)據(jù)信息、句子語(yǔ)義信息、知識(shí)對(duì)象信息以及知識(shí)關(guān)系信息。詳細(xì)的數(shù)據(jù)集信息如表3所示。

本文旨在解決基于HashMap的倒排索引構(gòu)建方法所導(dǎo)致的查詢效率低下的問(wèn)題。為了進(jìn)行改進(jìn)前后的對(duì)比分析，本實(shí)驗(yàn)將以基于HashMap的倒排索引構(gòu)建方法作為基準(zhǔn)實(shí)驗(yàn)組（即表2中的C1組HHHH）。通過(guò)與基準(zhǔn)實(shí)驗(yàn)組進(jìn)行比較，可以評(píng)估不同類型的混合倒排索引構(gòu)建方法的查詢效率。

在信息檢索領(lǐng)域，查詢類型主要分為排序查詢（Top-k）和布爾查詢（Boolean）兩種。排序查詢是根據(jù)與信息查詢需求相關(guān)的證據(jù)對(duì)文檔進(jìn)行評(píng)分并按照排名返回結(jié)果。在排序查詢中，使用了不同的評(píng)分函數(shù)，通常包括文檔中的術(shù)語(yǔ)頻率和逆文檔頻率等類似信息。布爾查詢目標(biāo)是根據(jù)查詢條件來(lái)識(shí)別滿足條件的文檔子集。布爾查詢由一系列關(guān)鍵詞組成，其中穿插著布爾運(yùn)算符。為了全面評(píng)估，本文將通過(guò)對(duì)比實(shí)驗(yàn)，在排序查詢和布爾查詢條件下分析驗(yàn)證不同類型倒排索引構(gòu)建方法的查詢效率。

為了衡量查詢效率，本文主要使用響應(yīng)時(shí)間和索引存儲(chǔ)空間作為評(píng)價(jià)指標(biāo)。響應(yīng)時(shí)間是指從查詢提交到獲取結(jié)果所經(jīng)歷的時(shí)間，它直接反映了查詢處理的速度。索引需要占用額外的存儲(chǔ)空間，如果索引過(guò)大，可能會(huì)消耗更多的磁盤(pán)I/O資源，從而影響查詢效率，在衡量查詢效率上還需要分析索引存儲(chǔ)空間的消耗。

此外，考慮到查詢長(zhǎng)度是影響查詢處理時(shí)間的重要因素之一，本文進(jìn)行了3次不同查詢長(zhǎng)度的查詢，其長(zhǎng)度由輸入查詢術(shù)語(yǔ)的數(shù)量決定。具體每次的查詢?cè)~設(shè)置如表4所示，其中Q1包含1個(gè)術(shù)語(yǔ)，Q2包含兩個(gè)術(shù)語(yǔ)，Q3包含3個(gè)術(shù)語(yǔ)。

3.2實(shí)驗(yàn)結(jié)果及分析

3.2.1排序查詢響應(yīng)時(shí)間對(duì)比分析

針對(duì)排序查詢（Top-k），本文首先選取k值為10，并對(duì)8種混合倒排索引構(gòu)建方法進(jìn)行了3次排序查詢，其查詢響應(yīng)時(shí)間結(jié)果如表5所示。此外，為了分析驗(yàn)證查詢長(zhǎng)度對(duì)排序查詢響應(yīng)時(shí)間的影響，本文比較了不同查詢長(zhǎng)度下的排序查詢響應(yīng)時(shí)間增長(zhǎng)率，其結(jié)果如圖1所示。

根據(jù)圖1的結(jié)果顯示，首先，隨著查詢長(zhǎng)度的增加，所有混合倒排索引構(gòu)建方法的查詢響應(yīng)時(shí)間都呈現(xiàn)增加的趨勢(shì)。這是由于隨著查詢長(zhǎng)度的增加，需要匹配的倒排列表數(shù)量也隨之增加，從而導(dǎo)致查詢處理時(shí)間的增加。

其次，在每次查詢中，C3（HHHB）展現(xiàn)出最短的處理時(shí)間，這表明HHHB構(gòu)建方法在處理查詢時(shí)表現(xiàn)出最高的效率。這可能是因?yàn)镠HHB中的哈希表能夠?qū)⑾嗨频脑~項(xiàng)映射到相同的桶中，從而減少倒排列表的長(zhǎng)度，提高查詢效率。

第三，隨著查詢長(zhǎng)度增加，C2（TTTH）的查詢處理時(shí)間增長(zhǎng)率高于其他組合。這表明Treap對(duì)查詢長(zhǎng)度最為敏感。這可能是因?yàn)門(mén)reap在處理長(zhǎng)查詢時(shí)需要更多的旋轉(zhuǎn)操作來(lái)保持平衡，從而導(dǎo)致查詢處理時(shí)間的增加。

最后，C2（TTTH）的查詢處理時(shí)間增長(zhǎng)率高于C4（TTTB），這表明相比于B+樹(shù)，HashMap對(duì)查詢長(zhǎng)度更為敏感。這可能是因?yàn)镠ashMap的哈希函數(shù)在處理長(zhǎng)鍵時(shí)可能會(huì)出現(xiàn)哈希沖突，進(jìn)而導(dǎo)致查詢處理時(shí)間的增加。

為了評(píng)估k值增加對(duì)查詢效率的影響，本文將k值設(shè)置為20，并再次進(jìn)行了3次排序查詢，其查詢響應(yīng)時(shí)間結(jié)果如表6所示。本文還比較了它們?cè)谂判虿樵冎械捻憫?yīng)時(shí)間增長(zhǎng)率，其結(jié)果如表7所示。

根據(jù)表6的結(jié)果顯示，在k=20時(shí)，C3（HH-HB）具有最短的每次查詢處理時(shí)間，與k=10的時(shí)候表現(xiàn)一致，這表明隨著k值的增加，HHHB在處理查詢時(shí)仍然具有最高的查詢效率。而根據(jù)表7的結(jié)果顯示，隨著k值的增加，所有組的查詢響應(yīng)時(shí)間也隨之增加。在這些結(jié)果中，C3（HHHB）的查詢處理時(shí)間增長(zhǎng)率相比其他幾組最小。這意味著對(duì)于HHHB，增加k值對(duì)查詢響應(yīng)時(shí)間的影響較小，說(shuō)明HHHB在處理排序查詢時(shí)具有較好的穩(wěn)定性和可靠性。然而，C2（TTTH）的查詢響應(yīng)時(shí)間在k值增加時(shí)顯著增加，說(shuō)明TTTH在處理排序查詢時(shí)的效率不如其他方法。

綜上所述，在這8種倒排索引構(gòu)建方法中，HHHB是處理排序查詢上最高效的混合倒排索引構(gòu)建方法。具體而言，這種混合倒排索引構(gòu)建方法HHHB表示采用HashMap作為文獻(xiàn)倒排索引和句子倒排索引的構(gòu)建方法，采用HashMap作為知識(shí)對(duì)象倒排索引的構(gòu)建方法，以及采用B+樹(shù)作為知識(shí)關(guān)系倒排索引的構(gòu)建方法。此外，Treap對(duì)查詢長(zhǎng)度最為敏感，其次是HashMap，而B(niǎo)+樹(shù)對(duì)查詢長(zhǎng)度的敏感性最低，這說(shuō)明在處理長(zhǎng)查詢時(shí)，選擇合適的倒排索引構(gòu)建方法對(duì)于查詢處理時(shí)間的影響非常重要。

3.2.2布爾查詢響應(yīng)時(shí)間對(duì)比分析

本文對(duì)8種混合倒排索引構(gòu)建方法進(jìn)行了3次布爾查詢，其查詢響應(yīng)時(shí)間結(jié)果如表8所示。此外，為了分析驗(yàn)證查詢長(zhǎng)度對(duì)布爾查詢響應(yīng)時(shí)間的影響，本文比較了不同查詢長(zhǎng)度下的布爾查詢響應(yīng)時(shí)間增長(zhǎng)率，其結(jié)果如圖2所示。

根據(jù)表8的結(jié)果顯示，在8種混合倒排索引構(gòu)建方法中，C4（TTTB）每次查詢處理時(shí)間最短。同時(shí)，隨著查詢長(zhǎng)度的增加，所有構(gòu)建方法的查詢響應(yīng)時(shí)間都會(huì)增加，這表明查詢長(zhǎng)度是影響查詢響應(yīng)時(shí)間的一個(gè)重要因素。圖2的結(jié)果表明C3（HHHB）是對(duì)查詢長(zhǎng)度最不敏感的構(gòu)建方法，而C2（TTTH）則是對(duì)查詢長(zhǎng)度最敏感的構(gòu)建方法。這可能是由于HHHB主要使用哈希表來(lái)存儲(chǔ)倒排列表，而TTTH主要使用Treap來(lái)存儲(chǔ)倒排列表導(dǎo)致的。在處理布爾查詢方面．TTTB被證明是最高效的混合倒排索引構(gòu)建方法。這可能是由于TTTB使用了更緊湊的編碼方式來(lái)存儲(chǔ)倒排列表，從而減少了訪問(wèn)磁盤(pán)的次數(shù)。通過(guò)評(píng)估查詢響應(yīng)時(shí)間和查詢長(zhǎng)度之間的關(guān)系，同樣可以發(fā)現(xiàn)Treap對(duì)查詢長(zhǎng)度最敏感，其次是HashMap，最后是B+樹(shù)。

綜上所述，在這8種倒排索引構(gòu)建方法中，TTTB是處理布爾查詢上最高效的混合倒排索引構(gòu)建方法。具體而言，這種混合倒排索引構(gòu)建方法TTTB表示采用Treap作為文獻(xiàn)倒排索引和句子倒排索引的構(gòu)建方法，采用Treap作為知識(shí)對(duì)象倒排索引的構(gòu)建方法，以及采用B+樹(shù)作為知識(shí)關(guān)系倒排索引的構(gòu)建方法。此外，在處理長(zhǎng)查詢時(shí)，Treap對(duì)查詢長(zhǎng)度最敏感，其次是HashMap，而B(niǎo)+樹(shù)則最不受查詢長(zhǎng)度影響。

通過(guò)以上在排序查詢和布爾查詢條件下的對(duì)比實(shí)驗(yàn)可以得知，混合倒排索引構(gòu)建方法的選擇對(duì)查詢處理時(shí)間具有重要的影響。此外，不同構(gòu)建方法對(duì)查詢長(zhǎng)度的敏感程度也存在差異。除此之外，還有一些其他因素（如數(shù)據(jù)規(guī)模、數(shù)據(jù)分布等）可能會(huì)影響查詢響應(yīng)時(shí)間。因此，在實(shí)際應(yīng)用中，應(yīng)該根據(jù)具體的場(chǎng)景權(quán)衡各種因素，以選擇最合適的混合倒排索引構(gòu)建方法。

3.2.3索引存儲(chǔ)空間對(duì)比分析

本實(shí)驗(yàn)從數(shù)據(jù)集合中隨機(jī)選取了不同規(guī)模的論文數(shù)量，包括1000篇（記作D1）、5000篇（記作D2）、10000篇（記作D3）、20000篇（記作D4）、50000篇（記作D5）和100000篇（記作D6）作為每組實(shí)驗(yàn)數(shù)據(jù)集。針對(duì)索引存儲(chǔ)空間這一評(píng)價(jià)指標(biāo)展開(kāi)了測(cè)試，其實(shí)驗(yàn)結(jié)果如表9所示。

根據(jù)表9的結(jié)果顯示，C3（HHHB）的存儲(chǔ)空間在8種混合倒排索引構(gòu)建方法中居于最高位置，而C2（TTTH）的存儲(chǔ)空間則最為緊湊。這可能是由于HHHB主要利用哈希表來(lái)存儲(chǔ)倒排列表，而TTTH主要使用Treap來(lái)存儲(chǔ)倒排列表所致。

綜上所述，Treap所需的存儲(chǔ)空間最為緊湊，其次是HashMap，而B(niǎo)+樹(shù)的存儲(chǔ)空間需求最高。這一結(jié)論也驗(yàn)證了先前對(duì)索引數(shù)據(jù)結(jié)構(gòu)的分析結(jié)果，即Treap能夠以較小的存儲(chǔ)空間實(shí)現(xiàn)優(yōu)化，因?yàn)門(mén)reap采用隨機(jī)化結(jié)構(gòu)來(lái)確保平衡性，避免了維護(hù)有序性所需的額外存儲(chǔ)空間。相比之下，B+樹(shù)通常需要更多的存儲(chǔ)空間，因?yàn)槠鋬?nèi)部節(jié)點(diǎn)需要存儲(chǔ)鍵的范圍信息以維護(hù)有序性，并且需要存儲(chǔ)子樹(shù)的指針，從而導(dǎo)致相對(duì)較大的存儲(chǔ)空間開(kāi)銷。不同的混合倒排索引構(gòu)建方法對(duì)存儲(chǔ)空間的需求存在差異，在實(shí)際應(yīng)用中，應(yīng)該根據(jù)具體的場(chǎng)景選擇最合適的混合倒排索引構(gòu)建方法，以取得最佳的存儲(chǔ)空間利用和查詢處理時(shí)間的平衡。

4結(jié)論

本文旨在通過(guò)采用Treap、B+樹(shù)等多種數(shù)據(jù)結(jié)構(gòu)，探索適用于科技文獻(xiàn)不同語(yǔ)義維度的倒排索引構(gòu)建方法，并將其組合成適用于科技文獻(xiàn)多維語(yǔ)義組織的混合倒排索引構(gòu)建方法，以此改進(jìn)科技文獻(xiàn)語(yǔ)義查詢性能。實(shí)驗(yàn)結(jié)果表明，在8種混合倒排索引構(gòu)建方法中，表2所示的C3（HHHB）在排序查詢條件下具有最高的效率，而C4（TTTB）則在布爾查詢條件下表現(xiàn)最佳。未來(lái)的工作將進(jìn)一步分析不同索引模型對(duì)不同語(yǔ)義粒度索引構(gòu)建效率的影響原因。同時(shí)，將進(jìn)一步優(yōu)化混合倒排索引的構(gòu)建方法，探索更多高效的數(shù)據(jù)結(jié)構(gòu)，以滿足不斷增長(zhǎng)和豐富的語(yǔ)義信息存儲(chǔ)需求，并進(jìn)一步提升查詢效率。