[發明專利]一種基于啟發式方法的信息搜索方法

有效

• 申請號: 201310566963.3
• 申請日: 2013-11-14
• 公開（公告）號: CN103646035B
• 公開（公告）日: 2017-07-07
• 發明（設計）人: 趙杰;趙吉燕;常育新
• 申請（專利權）人: 北京銳安科技有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京君尚知識產權代理事務所(普通合伙)11200
• 代理人: 余功勛

技術領域

本發明屬于網絡技術、信息搜索技術領域，涉及一種基于啟發式方法的信息搜索方法。

背景技術

目前信息搜索、檢索技術已取得了很大發展。一些信息比如新聞等具有時效性、地域性、政治性等特點，對于如何搜索最有價值的信息是一個典型的NP難題。對于重要信息的定義，不同的國家，不同的地域、不同的媒體都是千差萬別的，如何在眾多的信息中，自動搜索出最有價值的，必須選擇一種有效的策略。

此類NP問題一般具有求解條件不完備、不確定性等特點。用常規的搜索算法很難搜索到最優的結果。現有的一些方法，存在搜索效率低、計算時間與空間耗費過多的問題。現在計算重要信息主要是通過關鍵詞搜索和聚類兩種思路，但是這兩種思路都有相應的缺陷，比如：關鍵詞搜索主要通過關鍵詞命中次數來定義信息的重要性，雖然效率很高，但是準確度很差；聚類方法雖然精確度很高，但是存在計算時間過長，時效性不夠的缺點。

啟發式搜索算法是解決NP難題時常用到的一種算法。啟發式算法的運用綜合了關鍵詞搜索和聚類的優點，在保證時間及時性的同時，提高重要信息搜索的準確度。下面對啟發式算法做一些簡要介紹。

啟發式搜索的基本思路是：預先確定好一個函數，它能反映該結點與目標結點的接近程度，這個函數叫啟發函數（heuristic function)。啟發式搜索就是在問題狀態空間中對每一個搜索的位置進行評估，由此得到最好的位置，再從這個位置進行搜索直到解決問題。應用此算法可以節省無謂的搜索路徑，提高搜索的效率。

在啟發式搜索中，對位置的估價是十分重要的，不同的估價可能有不同的效果。啟發算法中啟發函數的具體構造如下：

f(n)=g(n)+h(n)

其中f(n)表示對節點n的總估價，g(n)表示從起始狀態到節點n的已知估價，h(n)表示節點n本身的預測估價，即啟發信息。

例如博弈樹的搜索過程是一個典型的啟發式搜索，如圖1所示。采用啟發函數表示該圖中的節點信息，在f(n)=g(n)+h(n)中，g(n)表示節點所在的深度，h(n)表示節點的啟發信息。如何選擇啟發信息是此種算法的關鍵。在這里啟發信息是黑下完一手白方填滿相應的空白格后所能連成線的數目。白方連線越少，表明黑方下的越成功。在上述節點各子節點的估價由左到右為f(1)=g(1)+h(1)=1+2=3，f(2)=2,f(3)=2,f(4)=2,f(5)=2。由上述函數可以得出，第一個節點代價較高，就不再考慮了。

發明內容

現有的信息搜索方法，尤其是對于如何搜索最有價值的新聞、論壇等信息，現有方法還無法很好的解決，存在搜索效率低、計算時間與空間耗費過多的問題。本發明提供一種基于啟發式方法的信息搜索方法，可以節省計算時間與空間，提高信息搜索效率。

為實現上述目的，本發明采用的技術方案如下：

一種基于啟發式方法的信息搜索方法，其步驟包括：

1）根據信息的特征確定與信息重要性相關的參數類型，每一種參數類型包含至少一個關鍵字，將同類型參數內的關鍵字分成不同級別，并對各級別設置不同的初始權值，將不同類型參數的最大的關鍵字權值相加作為權值上限；

2）采用散列方式存儲各參數類型、各參數類型對應的關鍵字及其權值，并建立索引；

3）對于每一條待定信息，獲取其關鍵字向量，并在所述索引中找出對應鍵字及相應的權值，通過對不同類型參數內的關鍵詞的權值進行合并得到該信息的權值，然后以所述權值上限減去該信息的權值，得到該信息的啟發信息；

4）根據所述啟發信息，運用啟發算法得到每一條待定信息的總估價，進而確定最有價值的信息，并輸出信息搜索結果。

進一步地，步驟3）通過分詞處理獲取所述關鍵字向量。

進一步地，步驟4）所述啟發算法采用的啟發公式為：

f(n)=g(n)+h(n)，

其中，f(n)為總估價，g(n)為信息的本身價值，h(n)為啟發信息。

進一步地，所述啟發公式為多啟發函數：

f(n)=g(n)+h1(n)+h2(n)，

其中，f(n)為總估價，g(n)為信息的本身價值，h1(n)為轉載率決定的啟發信息，h2(n)為關鍵字決定的啟發信息。

進一步地，g(n)由信息在網站頁面的位置決定，越重要的位置權值越小。

進一步地，步驟4）還根據不同信息的價值對信息進行排序。