[發明專利]一種基于海量文本數據的相似度衡量方法

有效

• 申請號: 201310335123.6
• 申請日: 2013-08-02
• 公開（公告）號: CN104346394B
• 公開（公告）日: 2018-12-21
• 發明（設計）人: 陸嘉恒
• 申請（專利權）人: 中國人民大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京中創陽光知識產權代理有限責任公司 11003
• 代理人: 尹振啟

1.一種基于海量文本數據的相似度衡量方法，其特征在于，所述方法包括：

步驟A：對于給定的字符串s₁和s₂，利用選擇擴展，選擇規則集R中規則，分別獲得其對應的擴展集合S₁′與S₂′；所述選擇擴展為全擴展和貪心擴展的結合；

所述全擴展包括：

步驟A1：對于給定的字符串s₁和s₂，分別獲得其對應的集合S₁和S₂；

步驟A2：掃描規則集R，進行全擴展：對于規則集R中任意規則r：lhs(r)→rhs(r)，若lhs(r)是S₁的子串，則將rhs(r)中包含的詞組添加到S₁；若lhs(r)是S₂的子串，則將rhs(r)中包含的詞組添加到S₂；

所述貪心擴展包括：

步驟A1：分別確定兩個字符串的可用規則集R₁和R₂；

步驟A2：分別對集合S₁和S₂進行貪心擴展：

步驟A2-1：對于S₁，執行如下擴展過程：

步驟A2-1-1：計算R₁中各個規則的增益，選出增益最大的規則；

給定兩個集合S₁和S₂，以及S₁的一條可用規則r：lhs(r)→rhs(r)，規則r的增益定義為：

步驟A2-1-2：如果步驟A2-1-1中所述增益最大的規則擴展S₁后，S₁′與S₂′的相似度增加，則將步驟A2-1-1中所述增益最大的規則從R₁中刪除，并將其添加到R₁^u中；

步驟A2-1-3：重復上述步驟，直到相似度不再增加或者R₁為空；

步驟A2-2：對于S₂，執行貪心擴展，與步驟A2-1類似，將步驟A2-1中的S₁替換為S₂并R₁替換為R₂后，執行步驟A2-1；

步驟B：衡量擴展集合S₁′與S₂′的相似度，作為原始字符串s₁和s₂的相似度；

所述選擇擴展包括：

步驟A1：分別確定兩個字符串的可用規則集R₁和R2；

步驟A2：分別選擇擴展兩個集合：

步驟A2-1：對于S₁，執行全擴展，獲得擴展后的集合S₁′,此時R₁^u＝R₁；

步驟A2-2：對于S₂，執行如下擴展過程：

步驟A2-2-1：計算規則集R₂中各個規則的增益；

步驟A2-2-2：選擇規則R₂中增益最大的規則；

步驟A2-2-3：測試使用步驟A2-2-2中所述增益最大的規則擴展S₂后，如果S₁′與S₂′的相似度增加，則將步驟A2-2-2所述增益最大的規則從R₂中刪除，并將其添加到R₂^u中；

步驟A2-2-4：重復上述步驟，直到相似度不再增加或者R₂為空；

步驟A2-3：刪去R₁^u中的無用規則；

步驟A2-3-1：計算規則集R₁^u中各個規則的增益；

步驟A2-3-2：選擇增益最小的規則，如果S₁′去掉僅由所述增益最小的規則引入的元素，可以使S₁′與S₂′的相似度增加，則去掉相應元素，從R₁^u中刪去所述增益最小的規則；

步驟A2-3-3：重復上述步驟，直到相似度不再增加或者R₁^u為空；

步驟A2-4：刪去R₂^u中的無用規則，過程類似A2-3；

步驟A2-5：返回擴展集；

步驟A3：分別對集合S₁和S₂進行擴展，步驟類似A2，在此次擴展中對S₂進行全擴展，S₁進行貪心擴展，返回擴展后的集合；

步驟A4：比較A2與A3返回的擴展集合之間的相似度，將相似度較大的選擇為最終擴展集合，較大的相似度為最終相似度。