信息快速插入與搜索算法研究

沈春元，張曉峰，李華君

(1.海軍駐南京地區(qū)雷達系統(tǒng)軍事代表室，南京 210003;2.中國船舶重工集團公司第七二四研究所，南京 210003)

0 引言

隨著計算機的不斷升級，關(guān)于信息的插入大多數(shù)采用的是遍歷方式，在通常情況下很符合條件，其原理為:

(1）在信息庫中查找是否有相同標識的信息，如果有轉(zhuǎn)到(3），否則轉(zhuǎn)到(2）;

(2）查找是否有空閑的位置，如果有轉(zhuǎn)到(3），否則轉(zhuǎn)到(4）;

(3）更新數(shù)據(jù)信息;

(4）滿信息后，采用處理方式。

此算法的時間復雜度為O(2n）。在實際處理過程中，信息量越來越大，在一些強實時情況下，采用上述的算法很難達到要求。

本文提出的快速插入與搜索算法(Quick Insert and Search Algorithm，簡寫QISA）QISA算法主要包括快速插入算法(QIA）和快速搜索算法(QSA）。

1 快速插入算法

本文提出的快速插入算法(見圖1），主要是基于雙索引之上實時變化索引關(guān)系，快速達到空閑位置，其時間復雜度為O(1）。

圖1中，索引表A 存放索引表B的位置信息，索引表B 存放索引表A 對應的位置信息，指針p為讀指針指向當時可以寫的位置，指針q為寫指針指向索引表A中所要修改的位置。

圖1 快速插入算法

圖2 算法關(guān)系圖

算法流程如下:

(1）初始化p和q 指向索引表A中的A1的位置，索引表A與索引表B 一一對應，如圖1(b）所示;

(2）有信息輸入時，直接索引到p所指定的位置，對應的索引表B中的信息為B［p］;

(3）第3個信息需要刪除時(圖2(a）），交換A［q］與A［Bi］中的位置信息，更新索引表A的值，其結(jié)果如圖2(b）所示。

2 快速搜索算法

搜索算法實際上是根據(jù)初始條件和擴展規(guī)則構(gòu)造一顆“解答樹”并尋找符合目標狀態(tài)的節(jié)點的過程。

圖3 樹形關(guān)系圖

由圖3所知，形成的一棵樹為搜索樹。初始狀態(tài)對應著根節(jié)點，目標狀態(tài)對應著目標節(jié)點，圖中的實線則為我們需要尋找的路徑。

本文采用的快速搜索算法(QSA）同樣是基于樹的關(guān)系之上，實時計算樹信息，為之后搜索的信息提供必要條件。

信息不同構(gòu)建搜索樹的方式也會不同，本文處理的信息主要是關(guān)于點跡、航跡的信息。根據(jù)此特征選取一個標識，確定此標識為關(guān)鍵字，最后通過此標識來檢索相關(guān)信息。其時間復雜度為O(L），其中L為標識的復雜度，例如用4 位的標識來確定關(guān)鍵字，那么L=4。

圖4 標識分解樹

由圖4 可知，標識為“知419”，在樹中表示為用實線箭頭表示的成功路徑。

算法流程如下:

(1）初始化樹的根節(jié)點、標識有效信息;

(2）分解標識信息;

(3）查找搜索樹，如果尋找到目標節(jié)點轉(zhuǎn)到到(4），否則轉(zhuǎn)到到(5）;

(4）更新目標節(jié)點信息;

(5）添加目標節(jié)點信息。

3 結(jié)果與分析

仿真環(huán)境配置:

CPU:Core i5系列、內(nèi)存:4G、操作系統(tǒng):Windows XP。

本文的仿真測試主要對20000 批內(nèi)的批數(shù)進行抽樣測試，測試結(jié)果如圖5所示。

圖5 測試結(jié)果圖

由圖5(a）所知，如果信息的批數(shù)在1000 批以內(nèi)時，通用的算法優(yōu)于本文的QISA，時間主要消耗在搜索樹的構(gòu)建上，其時間差也是控制在0.5 ms 以內(nèi)。由圖5(b）所知，當批數(shù)大于1000 批時，通用的算法時間會直線上升，QISA的耗時仍然是穩(wěn)步上升;如果把批數(shù)提高到20000 批時，通用算法需要消耗約為477 ms，而QISA 則只需消耗約為20 ms的時間，如圖5(c）所示。詳細的數(shù)據(jù)對比結(jié)果如表1所示。

表1 QISA與通用結(jié)果對比

4 結(jié)束語

QISA 主要是采用了雙索引技術(shù)，并構(gòu)建搜索樹的方式，實時為目標信息分配索引位置，減少了重復遍歷搜索消耗的時間，提高了搜索速度。QISA的時間耗費主要在于對搜索樹的建立、更新、刪除等的操作，關(guān)系到系統(tǒng)內(nèi)存的分配、更新、刪除的操作，對QISA的更深入的研究可以擴展到內(nèi)存優(yōu)化的研究中。

［1］張水平.數(shù)據(jù)結(jié)構(gòu)及算法分析［M］.西安:西北工業(yè)大學出版社，2003.

［2］夏定純，徐濤，等.人工智能技術(shù)與方法［M］.武漢:華中科技大學出版社，2004.

［3］Thomas H.Cormen，Charles E.Leiserson，Ronald L.Rivest，Clifford Stein.Introduction to Algorithms［M］.3rd Edition.The MIT Press，2009.