[發明專利]評估兩種排序算法相似度的方法

無效

• 申請號: 200910040329.X
• 申請日: 2009-06-17
• 公開（公告）號: CN101604316A
• 公開（公告）日: 2009-12-16
• 發明（設計）人: 王頊
• 申請（專利權）人: 騰訊科技（深圳）有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 廣州華進聯合專利商標代理有限公司
• 代理人: 何 平;曾旻輝

技術領域

本發明涉及數據處理技術領域，更具體地說，涉及一種評估兩種排序算法相似度的方法。

背景技術

機器學習(Machine?Learning)是研究計算機怎樣模擬或實現人類的學習行為，其以獲取新的知識或技能，重新組織已有的知識結構使之不斷改善自身的性能。機器排序(Learning?to?Rank)是機器學習中的一個領域，其目的是綜合考慮各種復雜的條件，對一組數據進行排序。

在機器排序的過程中，往往會人工的設定一個排好序的目標序列，用機器學習的方法，去將一組數據進行排序，使得排序結果盡可能與目標序列相同。不同的排序算法所得到的結果是不同的，例如，不同的搜索引擎由于使用的相關性算法不同，對于相同的查詢返回的結果不同。這樣，不同的排序算法針對同一組數據會得到不同的排序序列，對這些序列與目標序列之間的差異需進行量化的對比，同時，需得到這些序列和目標序列的公共部分及差異部分，以便于評估和改進排序算法，使得根據該排序算法獲得的排序結果滿足人們的需求。

發明內容

基于此，有必要提供一種能得到兩種排序算法結果的公共部分的評估兩種排序算法相似度的方法。

所述評估兩種排序算法相似度的方法包括：遍歷其中一種排序算法得到的第一排序序列中的元素，根據另一排序算法得到的第二排序序列對第一排序序列中的元素進行標識；根據第一排序序列中的元素標識獲取兩個排序序列的最長公共序列；根據最長公共序列計算得到所述兩種排序算法的相似度。

該對第一排序序列中的元素進行標識的步驟可包括：查找在所述第一排序序列和第二排序序列中都位于當前元素之前的元素，并將所述位于當前元素之前的元素中標識最大的元素記錄為當前元素的前溯元素，根據所述前溯元素的標識對當前元素進行標識。

根據前溯元素的標識對當前元素進行標識的步驟具體可以是：設置當前元素的標識為所述當前元素的前溯元素的標識加1。

對第一排序序列中的元素進行標識的步驟還可包括：設置所述第一排序序列中的第一個元素的標識。

另外，對第一排序序列中的元素進行標識的步驟可包括：查找在所述第一排序序列和第二排序序列中都位于當前元素之后的元素，并查找都位于當前元素之后的元素中標識比當前元素的標識與預設值的和小的元素，以及根據當前元素的標識更新標識比當前元素的標識與預設值的和小的元素的標識。

而根據當前元素的標識更新標識比當前元素的標識與預設值的和小的元素的標識的步驟具體可以是：將標識比當前元素的標識與預設值的和小的元素的標識更新為當前元素的標識加1。

該對第一排序序列中的元素進行標識的步驟還可包括：對第一排序序列中的元素設置初始標識。

對第一排序序列中的元素進行標識的步驟還可包括：將標識比當前元素的標識與預設值的和小的元素的前溯元素更新為當前元素。

另外，根據第一排序序列中的元素標識獲取兩個排序序列的最長公共序列的步驟具體可以是：查找所述第一排序序列中標識最大的元素，并遞歸地查找各前溯元素，將標識最大的元素及各前溯元素按標識順序組成兩個排序序列的最長公共序列。

而根據最長公共序列計算得到兩種排序算法的相似度的步驟具體可以是：獲取最長公共序列的長度，計算兩種排序算法的相似度為最長公共序列的長度與排序序列的長度的比值。

上述評估兩種排序算法相似度的方法，通過對其中一種排序算法得到的排序序列中的元素進行標識，并根據元素的標識獲取兩個排序序列的最長公共序列，以及根據最長公共序列計算得到兩種排序算法的相似度。因此，該方法除了能得到兩種排序算法的相似度，還能得到這兩種排序算法結果的公共部分，從而有利于排序算法的分析，以進一步評估和改進排序算法，使得根據該排序算法獲得的排序結果滿足人們的需求。

附圖說明

圖1是一個實施例中評估兩種排序算法相似度的方法流程圖；

圖2是一個實施例中對第一排序序列中的元素進行標識的方法流程圖；

圖3是另一個實施例中對第一排序序列中的元素進行標識的方法流程圖；

圖4是一個實施例中獲取最長公共序列的方法流程圖。

具體實施方式

圖1示出了一個實施例中評估兩種排序算法相似度的方法流程，具體過程如下：

在步驟S101中，遍歷其中一種排序算法得到的第一排序序列中的元素，根據另一排序算法得到的第二排序序列對第一排序序列中的元素進行標識。

在步驟S102中，根據第一排序序列中的元素標識獲取兩個排序序列的最長公共序列。

在步驟S103中，根據最長公共序列計算得到兩種排序算法的相似度。