[發(fā)明專利]一種基于語言模型的排序算法

無效

• 申請?zhí)枺?/td>: 200910068047.0
• 申請日: 2009-03-06
• 公開（公告）號: CN101826075A
• 公開（公告）日: 2010-09-08
• 發(fā)明（設(shè)計）人: 劉金莉
• 申請（專利權(quán)）人: 劉金莉
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種基于語言模型的排序算法，其特征在于包括下列步驟：

預(yù)處理單元，對用戶輸入的查詢詞和候選文檔進(jìn)行分詞和過濾停用詞處理；

建立倒排索引單元，對候選文檔建立倒排索引，以方便快速定位；

靜態(tài)權(quán)重確定單元，既中心性迭代計算單元，利用初始候選文檔建圖，迭代得到靜態(tài)權(quán)重；

動態(tài)權(quán)重確定單元，用戶將查詢與候選文檔之間利用語言模型得到的權(quán)重就是動態(tài)權(quán)重；

總權(quán)重確定單元，用于確定查詢在候選文檔中的總權(quán)重；

排序單元，用于按照總權(quán)重對所述各待排序的網(wǎng)絡(luò)資源進(jìn)行排序。

2.如權(quán)利要求1所述的方法，其特征在于在建立倒排索引之前還包括對候選文檔進(jìn)行預(yù)處理部分。首先要過濾停用詞，使得類似“的”、“了”、“呢”、“之”之類無效詞過濾掉，這樣可以減少檢索代價；其次要進(jìn)行中文分詞，常用的方法有正向最大匹配算法，反正最大匹配算法，雙向最大匹配算法等，我們采用了正向最大匹配算法。

3.如權(quán)利要求1所述的方法，其特征在于，在用戶輸入查詢之前還包括對候選文檔建立倒排索引的過程，以詞為單位的詞典文件，包含該詞頻率的頻率文件，該詞在文檔中所處位置的位置文件。其中詞典文件不僅保存有每個關(guān)鍵詞，還保留了指向頻率文件和位置文件的指針，通過指針可以找到該關(guān)鍵字的頻率信息和位置信息，以實(shí)現(xiàn)快速定位。

4.如權(quán)利要求1所述的方法，其特征在于，確定候選文檔集合包括以下步驟：

以對查詢進(jìn)行分詞處理所得的分詞分別在倒排索引中進(jìn)行查找，找到每個分詞所屬的文檔集合取各所述集合的交集，作為候選文檔集合。

5.如權(quán)利要求1所描述的方法，排序算法由兩部分組成，靜態(tài)權(quán)重和動態(tài)權(quán)重。如權(quán)利要求1所述的方法，其特征在于，將用戶的輸入查詢進(jìn)行預(yù)處理得到關(guān)鍵詞之后，可以利用權(quán)利要求3中建立的倒排索引，快速定位包含查詢關(guān)鍵詞的文檔當(dāng)作初始候選結(jié)果集，這里可以利用語言模型得到查詢與候選文檔之間權(quán)重，這個權(quán)重就是動態(tài)權(quán)重，記為p_d(q)。

6.如權(quán)利1要求所描述的方法，其特征在于，將動態(tài)權(quán)重得到的初始候選結(jié)果集利用語言模型建圖。語言模型建圖的過程就是構(gòu)建非真實(shí)鏈接關(guān)系的PageRank，并且迭代得到每個文檔的最終值作為排序算法中的靜態(tài)權(quán)重，也稱為中心性，記作Cen(d，G)，則中心性的計算方法為：

Cen(d;G)=defΣo∈Dinitwt(o→d)]]>

其中wt(o→d)＝p_d(o)。

7.如權(quán)利要求1所描述的方法，其特征在于排序算法可以表示為

Cen(d，G)*p_d(G)