[發明專利]一種基于倒排索引的評估類文檔不定長詞句的查詢方法

有效

• 申請號: 201811153438.8
• 申請日: 2018-09-30
• 公開（公告）號: CN109284352B
• 公開（公告）日: 2022-02-08
• 發明（設計）人: 沈毅;趙虹博;楊朔;王宏志;張淼
• 申請（專利權）人: 哈爾濱工業大學
• 主分類號: G06F16/31
• 分類號: G06F16/31;G06F40/289;G06F40/242
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種基于倒排索引的評估類文檔不定長詞句的查詢方法，其特征在于它包括以下步驟：

步驟一：將待查詢文檔進行數據預處理，統一轉換為純文本格式存儲，并添加自定義詞典和停用詞表，利用jieba分詞方法，采用Tire樹結構存儲單詞，生成DAG圖并基于DP算法計算最優切分方案，并通過中文詞匯BMES狀態表記法來進行分詞處理，得到單詞詞典與詞頻信息；

步驟二：基于完全重建策略的倒排索引原理，通過調整存儲結構、強化單詞位置信息、壓縮存儲空間，建立自適應倒排表和倒排生成文件，實現快速提取單詞位置、頻率信息；

步驟三：結合所需要查找不定長詞句的信息，通過倒排表索引詞句中各個分詞位置信息，基于字符串匹配方法識別不定長詞句位置信息并索引其所在段落，來完成評估類文檔不定長詞句的查詢功能。

2.根據權利要求1所述的基于倒排索引的評估類文檔不定長詞句的查詢方法，其特征在于所述的步驟一具體包括：

將待查詢文檔數據預處理為純文本格式，存儲在同一目錄下，記為數據集D；在進行jieba分詞前，須添加自定義詞典和停用詞表，設jieba分詞詞典為S₀，自定義詞典包含專業領域術語記為U；則自定義單詞詞典集合S′可表示為：

S′＝S₀∪U；

其中S₀為jieba分詞詞典中所有單詞構成的集合，U代表評估類文檔中專業領域術語所構成的集合；

停用詞表包含常用詞庫，記為C₁；數字，記為C₂；字母，記為C₃，停用詞表C可表示為：

C＝C₁∪C₂∪C₃；

其中C₁為包含日常用語常用詞匯的單詞所構成的集合；C₂為數字0至9所構成的集合；C₃為英文字母所構成的集合；

在得到自定義詞典S′和停用詞表C后，最終單詞詞典S_D可以表示為：

S_D＝(S′-C)∪C′；

C′＝{c′₁,c′₂,...,c′_n}；

其中C′表示具有特殊含義的字母與數字組合而成的集合，在自定義詞典S′與停用詞表C做差集后，與C′做并集運算得到單詞詞典S_D；

在精確模式下對待處理文檔數據進行改進的jieba分詞，得到分詞結果以及詞頻統計信息并保存，改進的jieba分詞具體步驟如下：

1)依據單詞詞典S_D對數據集D中的所有句子進行切分，將所有可以切分成詞的單詞存儲到Trie樹中，同時將每個詞的出現次數轉換為頻率，通過快速詞圖掃描，將所有可能的分詞情況生成DAG圖(Directed Acyclic Graph，有向無環圖)；

2)在得到了多種情況下的切分方案后，采用DP算法(Dynamic Programming，動態規劃算法)來查找最大概率路徑Rmax，對于DAG中的每個節點，其權重為對應詞語的詞頻，記為w_i，計算方法如下：

由DAG圖構成切分路徑Route集合，包含k個切分方案：

Route＝{R₁,R₂,...,R_k}；

其中任意一個切分方案R_i是由m個具有順序結構關系的單詞構成的序列：

R_i＝[word₁,word₂,...,word_m]i∈[1,k]；

對于DAG中k個切分方案所包含的全部n個節點單詞，其出現的概率為對應單詞詞頻在所有單詞詞頻之和中的占比，可表示為：

為了選取最大概率路徑Rmax，須使其路徑上的單詞權重概率之和W最大：

對于整個句子的最優路徑Rmax和一個末端節點w_x，對于其可能存在的多個前驅節點w_i，w_j，w_k，…，w_z，設達到w_i，w_j，w_k，w_z的最大路徑分別為Rmaxi，Rmaxj，Rmaxk，Rmaxz有：

Rmax＝max(Rmaxi,Rmaxj,Rmaxk,...,Rmaxz)+Weight(w_x)Rmax∈Route；

于是問題轉化為求Rmaxi，Rmaxj，Rmaxk，…，Rmaxz組成的最優路徑，其中的最優解是全局的最優解的一部分，因此狀態轉移方程為：

Rmax＝max{max(Rmaxi,Rmaxj,Rmaxk,...,Rmaxz)+Weight(w_x)}Rmax∈Route；

3)對于單詞詞典S_D中未登錄的詞，通過建立HMM，即Hidden Markov Model，隱馬爾科夫模型，用于描述一個含有隱含未知參數的馬爾可夫過程，采用Viterbi路徑方法來尋找分詞結果，其方法描述如下：

給定HMM模型狀態空間，共有k個狀態，初始狀態i的概率為π_i，從狀態i到狀態j的轉移概率為a_i,j；設觀察到的輸出為y₁,...,y_T；產生觀察結果的最有可能的狀態序列x₁,...,x_T由遞推關系給出：

其中V_t,k是前t個最終狀態為k的觀測結果最有可能對應的狀態序列的概率，通過保存向后指針記錄在上式中用到的狀態x可以獲得Viterbi路徑，聲明一個函數Ptr(k,t)，若它返回t＞1時計算V_t,k用到的x值，或若t＝1時的k，則有：

通過對中文詞匯按照BMES四個狀態來進行標記，B是begin開始位置，M是middle中間位置，E是end結束位置，S是single單獨成詞的位置；通過構建的HMM模型對大量語料進行訓練后，依靠Viterbi路徑方法就可以得到一個概率最大的BMES序列，基于這個序列對句子結構進行重新組合，即可得到分詞結果。