面向科技文獻多維語義組織的混合倒排索引構建方法

張敏 李唯 范青

關鍵詞：科技文獻；語義組織；混合倒排索引；HashMap；Treap；B+樹

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

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

1倒排索引構建方法相關研究

在傳統的倒排索引構建方法中，使用HashMap作為數據結構是常見的選擇。然而，隨著研究的深入，學者們提出了一些采用其他數據結構的倒排索引構建方法，以進一步提高查詢效率，主要有4類構建方法。

1.1基于排序數組的倒排索引構建方法

Frakes W B提出了一種基于排序數組的倒排索引構建方法。這種方法將關鍵字列表存儲在一個排序數組中，并包括與每個關鍵字相關聯的文檔數量和指向包含該關鍵字的文檔的鏈接。該方法有效地提升了查詢效率，但其主要缺點是當添加新關鍵字時，更新索引的成本較高。這種方法在查詢效率上表現優秀，但是在索引更新時的成本較高，不適用于需要頻繁更新的場景。

1.2基于B樹的倒排索引構建方法

B樹被Kraska T等用來構建倒排索引，在B樹中，每個鍵代表1個最短的單詞，并用于區分存儲在下一級別的鍵，這些鍵不需要是索引中實際術語的前綴。與排序數組相比，B樹在查詢效率上表現優秀，但會使用更多的存儲空間。這種方法適用于需要頻繁查詢而不需要頻繁更新的場景。

1.3基于樹堆的倒排索引構建方法

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

1.4基于小波樹的倒排索引構建方法

Gupta A等和Yadav A K等提出了一種基于小波樹（Wavelet Tree）的倒排索引構建方法，該方法旨在優化存儲索引所需的空間和檢索文檔所需的時間，同時保持良好的結果。作者使用100萬個Wikipedia頁面的數據庫，將這種新索引與基于B樹的索引進行了性能對比測試。實驗結果顯示，在查詢長度增加時，基于小波樹的索引相比基于B樹的索引具有更高的查詢效率。

綜上所述，不同類型的倒排索引構建方法采用了B樹、小波樹等數據結構，有效提升了查詢效率。然而，這些數據結構并不適用于所有場景，選擇數據結構必須考慮實際場景并進行評估和權衡。在本文所探討的科技文獻多維語義組織領域中，需要根據科技文獻不同語義維度的信息特征，選擇最合適的數據結構，以有效解決由單一索引結構導致的查詢效率問題。

2混合式多維語義索引構建方法

本文首先對科技文獻多維語義索引的信息特征進行分析，隨后對Treap和B+樹這兩種數據結構進行評估，并在此基礎上探索了適用于不同語義維度的倒排索引構建方法。最后，將這些方法組合形成多種適用于科技文獻多維語義組織的混合倒排索引構建方法。

2.1多維語義索引的信息特征

本文旨在通過面向科技文獻不同維度的信息特征建立混合倒排索引，信息特征主要通過存儲在不同維度的倒排索引中的信息來體現。表1概述了這4個維度的信息特征。

在文獻語篇維度，文獻倒排索引是一種存儲文檔與關鍵詞關系的索引結構，它包含文檔ID（Do-cld）和關鍵詞的詞頻信息（TF）。為了適應各種查詢需求，尤其是排序查詢需求，這個倒排索引需要具備足夠的靈活性。它會存儲詞頻信息，以便通過TF-IDF、BM25或其他術語權重計算方法計算相似度，并最終按照相似度進行排序。術語權重計算需要在查詢時完成，這可能會增加查詢處理時間。

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

在知識對象維度，知識對象倒排索引存儲的信息主要包括通過語義標注技術識別出的知識對象。為了提高科技文獻語義檢索的準確性，前期研究提出了一種基于語義信息的術語權重算法。該算法綜合考慮了知識對象在文獻中的語義信息（包括知識對象及其關系）和在文本中的頻率，并使用語義信息權重來衡量知識對象在科技文獻中的重要性。因此，知識對象倒排索引存儲的信息不僅包括文檔ID和知識對象的詞頻信息，還包括知識對象的語義信息權重（記作SIW）。

在知識關系維度，知識關系倒排索引存儲知識對象之間的關系數據，這種關系數據以SPO三元組的形式進行表述。“知識對象一連接詞一知識對象”構成了知識關系三元組的基本形式。每組知識關系的倒排列表由S、P和0的3個列表組成。其中，S、P和0分別代表三元組中的主語、謂語和賓語。

2.2索引數據結構分析

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

Treap是一種將二叉搜索樹和堆結合起來的數據結構，每個節點都有1個鍵和1個屬性（優先級），該屬性隨機分配給一個鍵。Treap中的鍵值按照二叉搜索樹的屬性進行排序。每個節點的優先級值大于或等于其子節點的優先級值，以支持堆的順序，而堆的順序由樹的結構決定。根節點的優先級值是Treap中最大的。Treap作為一種結合了二叉搜索樹和堆的數據結構，能夠提供較快的排序查詢處理，并且占用較少的存儲空間。

B+樹是B樹的一種變體，在數據庫和文件系統中得到廣泛應用。它通過自底向上的插入方式和葉子節點的鏈表鏈接，提供了快速的排序查詢能力。B+樹的非葉子節點僅存儲鍵值，而數據存儲在葉子節點中。葉子節點按照關鍵字的升序排列，并以鏈表的方式鏈接在一起。在查詢時，B+樹會沿著最左匹配原則繼續向下查找，直到找到包含查詢關鍵字的葉子節點。B+樹在構建較大文本的索引方面的支持有限，但在處理具有層次結構的文本數據和路徑導航方面表現出色。它能夠提供快速的路徑導航和查詢能力，特別適用于具有層次結構的數據。

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

2.3混合倒排索引構建

本文旨在結合多維語義索引的信息特征和索引數據結構進行應用分析，探索混合倒排索引構建的實際應用。具體而言，本文將分析如何有效地采用HashMap、Treap和B+樹這3種數據結構作為適用于4個維度的倒排索引構建方法。

2.3.1采用HashMap作為倒排索引的構建方法

采用HashMap作為4個倒排索引的構建方法具有相似性。在該方法中，HashMap的鍵和值分別對應著倒排索引的詞匯表條目和相關的倒排列表。以采用HashMap構建知識對象倒排索引為例，每個知識對象被用作HashMap的鍵，對應的倒排列表被視為該鍵所對應的值。倒排列表是指包含了知識對象的所有文檔的列表，倒排項是指倒排列表中的每個條目，它代表了一個知識對象在某個文檔中的出現情況。每個倒排項通常包含了文檔ID和其他相關的信息，如權重（如TF、TF-IDF）或其他語義信息。

2.3.2采用Treap作為倒排索引的構建方法

Treap是一種近期被廣泛應用于存儲倒排索引信息的數據結構。相較于其他數據結構，Treap在減少查詢處理時間和內存使用方面表現出顯著優勢。采用Treap作為倒排索引的構建方法將倒排列表表示為1個Treap，其中每個倒排項被視為Treap的1個節點。該節點能夠同時存儲文檔ID和權重信息（如TF、TF-IDF等）。這種構建方法提供了高效支持排序查詢的能力。

如表1所示，文獻倒排索引的存儲信息主要包括文檔ID信息（Docld）和詞頻信息（TF）。該方法將Docld作為節點的鍵值，TF作為節點的優先級值。倒排列表中的倒排項按照Docld的大小進行遞增排序，并保持對TF的堆排序。

句子倒排索引的存儲信息主要由Docld、TF和Moveld組成，由于Treap的每個節點只能包含1個鍵值對，即鍵和優先級值，需要對其進行修改以存儲額外的信息。為此，本文將TF和Moveld的值結合起來生成Treap節點的優先級值。組合方法需要快速編碼和解碼，因為編碼和解碼時間會影響查詢處理時間。優先級值是通過將TF的值與1個“0”字符連接，并乘以Moveld的值來建立的。例如，如果TF為10，Moveld為1，則它們的組合將是1001000。要解碼該序列，本文從序列的右側開始，一直找到1—9之間的數字，這個數字提供Moveld的值，左邊的數字則是TF的值。

知識對象倒排索引的存儲信息由Docld、TF和語義信息權重SIW組成，由于Treap的每個節點只能包含1個鍵值對，即鍵和優先級值，需要進行一些修改以存儲額外的信息。本文將TF和SIW的值按照上述相同的組合方法結合起來，為Treap中的節點生成優先級值。

知識關系倒排索引的存儲信息由S、P和0 3個獨立的列表組成，由于Treap只能表示1個鍵值對列表，而無法同時表示多個列表。此外，對于知識關系倒排索引中的信息，維護堆排序沒有任何意義。因此，Treap不適用于作為知識關系倒排索引的構建方法。

2.3.3采用B+樹作為倒排索引的構建方法

B+樹并不適合用于構建較大文本的倒排索引，因為它的索引值存儲會占用較大的空間，從而導致B+樹的深度增加，進而影響查詢效率。文獻倒排索引和句子倒排索引通常都是針對較大文本構建倒排索引。另外，從索引更新操作這層因素考慮，文獻倒排索引和句子倒排索引會隨著文獻的不斷增加而頻繁更新，而B+樹因為需要保持平衡性而導致插入和刪除操作相對較慢，從而可能會影響倒排索引構建效率。B+樹并不適合作為文獻倒排索引和句子倒排索引的構建方法。此外，B+樹的非葉子節點不存儲數據，只在葉子節點存儲關鍵詞。而知識對象倒排索引需要額外存儲語步位置ID（Moveld）的信息，這個附加信息無法通過B+樹來存儲。因此．B+樹也不適合作為知識對象倒排索引的構建方法。

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

2.3.4混合倒排索引構建方法

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

3實驗設計及結果分析

3.1實驗設計介紹

本實驗選取了來自arXiv平臺的10萬篇物理領域科研論文作為初始數據集，并進行語義標注，抽取文獻元數據信息、句子語義信息、知識對象信息以及知識關系信息。詳細的數據集信息如表3所示。

本文旨在解決基于HashMap的倒排索引構建方法所導致的查詢效率低下的問題。為了進行改進前后的對比分析，本實驗將以基于HashMap的倒排索引構建方法作為基準實驗組（即表2中的C1組HHHH）。通過與基準實驗組進行比較，可以評估不同類型的混合倒排索引構建方法的查詢效率。

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

為了衡量查詢效率，本文主要使用響應時間和索引存儲空間作為評價指標。響應時間是指從查詢提交到獲取結果所經歷的時間，它直接反映了查詢處理的速度。索引需要占用額外的存儲空間，如果索引過大，可能會消耗更多的磁盤I/O資源，從而影響查詢效率，在衡量查詢效率上還需要分析索引存儲空間的消耗。

此外，考慮到查詢長度是影響查詢處理時間的重要因素之一，本文進行了3次不同查詢長度的查詢，其長度由輸入查詢術語的數量決定。具體每次的查詢詞設置如表4所示，其中Q1包含1個術語，Q2包含兩個術語，Q3包含3個術語。

3.2實驗結果及分析

3.2.1排序查詢響應時間對比分析

針對排序查詢（Top-k），本文首先選取k值為10，并對8種混合倒排索引構建方法進行了3次排序查詢，其查詢響應時間結果如表5所示。此外，為了分析驗證查詢長度對排序查詢響應時間的影響，本文比較了不同查詢長度下的排序查詢響應時間增長率，其結果如圖1所示。

根據圖1的結果顯示，首先，隨著查詢長度的增加，所有混合倒排索引構建方法的查詢響應時間都呈現增加的趨勢。這是由于隨著查詢長度的增加，需要匹配的倒排列表數量也隨之增加，從而導致查詢處理時間的增加。

其次，在每次查詢中，C3（HHHB）展現出最短的處理時間，這表明HHHB構建方法在處理查詢時表現出最高的效率。這可能是因為HHHB中的哈希表能夠將相似的詞項映射到相同的桶中，從而減少倒排列表的長度，提高查詢效率。

第三，隨著查詢長度增加，C2（TTTH）的查詢處理時間增長率高于其他組合。這表明Treap對查詢長度最為敏感。這可能是因為Treap在處理長查詢時需要更多的旋轉操作來保持平衡，從而導致查詢處理時間的增加。

最后，C2（TTTH）的查詢處理時間增長率高于C4（TTTB），這表明相比于B+樹，HashMap對查詢長度更為敏感。這可能是因為HashMap的哈希函數在處理長鍵時可能會出現哈希沖突，進而導致查詢處理時間的增加。

為了評估k值增加對查詢效率的影響，本文將k值設置為20，并再次進行了3次排序查詢，其查詢響應時間結果如表6所示。本文還比較了它們在排序查詢中的響應時間增長率，其結果如表7所示。

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

綜上所述，在這8種倒排索引構建方法中，HHHB是處理排序查詢上最高效的混合倒排索引構建方法。具體而言，這種混合倒排索引構建方法HHHB表示采用HashMap作為文獻倒排索引和句子倒排索引的構建方法，采用HashMap作為知識對象倒排索引的構建方法，以及采用B+樹作為知識關系倒排索引的構建方法。此外，Treap對查詢長度最為敏感，其次是HashMap，而B+樹對查詢長度的敏感性最低，這說明在處理長查詢時，選擇合適的倒排索引構建方法對于查詢處理時間的影響非常重要。

3.2.2布爾查詢響應時間對比分析

本文對8種混合倒排索引構建方法進行了3次布爾查詢，其查詢響應時間結果如表8所示。此外，為了分析驗證查詢長度對布爾查詢響應時間的影響，本文比較了不同查詢長度下的布爾查詢響應時間增長率，其結果如圖2所示。

根據表8的結果顯示，在8種混合倒排索引構建方法中，C4（TTTB）每次查詢處理時間最短。同時，隨著查詢長度的增加，所有構建方法的查詢響應時間都會增加，這表明查詢長度是影響查詢響應時間的一個重要因素。圖2的結果表明C3（HHHB）是對查詢長度最不敏感的構建方法，而C2（TTTH）則是對查詢長度最敏感的構建方法。這可能是由于HHHB主要使用哈希表來存儲倒排列表，而TTTH主要使用Treap來存儲倒排列表導致的。在處理布爾查詢方面．TTTB被證明是最高效的混合倒排索引構建方法。這可能是由于TTTB使用了更緊湊的編碼方式來存儲倒排列表，從而減少了訪問磁盤的次數。通過評估查詢響應時間和查詢長度之間的關系，同樣可以發現Treap對查詢長度最敏感，其次是HashMap，最后是B+樹。

綜上所述，在這8種倒排索引構建方法中，TTTB是處理布爾查詢上最高效的混合倒排索引構建方法。具體而言，這種混合倒排索引構建方法TTTB表示采用Treap作為文獻倒排索引和句子倒排索引的構建方法，采用Treap作為知識對象倒排索引的構建方法，以及采用B+樹作為知識關系倒排索引的構建方法。此外，在處理長查詢時，Treap對查詢長度最敏感，其次是HashMap，而B+樹則最不受查詢長度影響。

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

3.2.3索引存儲空間對比分析

本實驗從數據集合中隨機選取了不同規模的論文數量，包括1000篇（記作D1）、5000篇（記作D2）、10000篇（記作D3）、20000篇（記作D4）、50000篇（記作D5）和100000篇（記作D6）作為每組實驗數據集。針對索引存儲空間這一評價指標展開了測試，其實驗結果如表9所示。

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

綜上所述，Treap所需的存儲空間最為緊湊，其次是HashMap，而B+樹的存儲空間需求最高。這一結論也驗證了先前對索引數據結構的分析結果，即Treap能夠以較小的存儲空間實現優化，因為Treap采用隨機化結構來確保平衡性，避免了維護有序性所需的額外存儲空間。相比之下，B+樹通常需要更多的存儲空間，因為其內部節點需要存儲鍵的范圍信息以維護有序性，并且需要存儲子樹的指針，從而導致相對較大的存儲空間開銷。不同的混合倒排索引構建方法對存儲空間的需求存在差異，在實際應用中，應該根據具體的場景選擇最合適的混合倒排索引構建方法，以取得最佳的存儲空間利用和查詢處理時間的平衡。

4結論

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