基于快速排序算法的文獻(xiàn)檢索技術(shù)

姚佳

摘要：文獻(xiàn)搜索引擎在資料查找過(guò)程中起到重要作用，幫助人們從海量數(shù)據(jù)資源中找到自己想要的信息。伴隨網(wǎng)絡(luò)技術(shù)的推廣與發(fā)展，目前文獻(xiàn)檢索網(wǎng)站數(shù)據(jù)存儲(chǔ)量迅速增長(zhǎng)，造成檢索過(guò)程計(jì)算量增加。采用快速排序算法，可以有效篩選出與用戶(hù)需求匹配度較高的文獻(xiàn)，方便用戶(hù)使用，提高運(yùn)算效率，并利用計(jì)算機(jī)模擬實(shí)現(xiàn)。

關(guān)鍵詞：文獻(xiàn)檢索；快速排序；分治；字符串匹配；時(shí)間復(fù)雜度

中圖分類(lèi)號(hào)：TP391.9 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2014）02-0305-03

伴隨網(wǎng)絡(luò)技術(shù)的發(fā)展，網(wǎng)絡(luò)信息大量增加，涵蓋期刊、會(huì)議紀(jì)要、論文、學(xué)術(shù)成果、學(xué)術(shù)會(huì)議論文的大型網(wǎng)絡(luò)數(shù)據(jù)庫(kù)應(yīng)運(yùn)而生，如萬(wàn)方數(shù)據(jù)庫(kù)、百度文庫(kù)、維普數(shù)據(jù)庫(kù)等，文獻(xiàn)存儲(chǔ)容量近百萬(wàn)篇。如何有效搜集發(fā)現(xiàn)信息，并對(duì)信息提取、組織、處理，就需要尋找出高效算法，降低計(jì)算復(fù)雜度，提高運(yùn)算效率，以適應(yīng)文獻(xiàn)資源的迅速擴(kuò)充[[1]]。

1 文獻(xiàn)資料搜索引擎技術(shù)特點(diǎn)

當(dāng)用戶(hù)以關(guān)鍵詞查找信息時(shí)，搜索引擎會(huì)在數(shù)據(jù)庫(kù)中進(jìn)行搜尋，如果找到與用戶(hù)要求內(nèi)容相符的信息，便采用特殊的算法，根據(jù)文獻(xiàn)中關(guān)鍵詞的匹配程度，如出現(xiàn)的次數(shù)、頻率等計(jì)算出各文獻(xiàn)的排名等級(jí)，然后根據(jù)關(guān)聯(lián)度高低，按順序?qū)⑦@些資源接返回給用戶(hù)。

與網(wǎng)絡(luò)搜索引擎不同，因用戶(hù)需求為數(shù)據(jù)資料而非網(wǎng)絡(luò)資源，因此文獻(xiàn)檢索主要依據(jù)為相關(guān)關(guān)鍵詞、內(nèi)容的相關(guān)度等，對(duì)域名、外鏈等因素考慮較少?？衫藐P(guān)鍵詞匹配算法，計(jì)算出各文獻(xiàn)特征值，以特征值作為依據(jù)，對(duì)檢索文獻(xiàn)排序刪選，滿(mǎn)足用戶(hù)需求。為便于理解，該文利用詞頻和位置加權(quán)算法計(jì)算特征值，采用快速排序算法進(jìn)行整理輸出，數(shù)據(jù)庫(kù)可高效檢索出與用戶(hù)需求匹配程度較高的文獻(xiàn)[[2]]。

2 快速排序算法規(guī)則及性能分析

快速排序是由托尼·霍爾于1962年（Tony Hoare）所發(fā)展的一種遞歸排序算法，采用分治的思想。在平均狀況下，排序 n 個(gè)項(xiàng)目需要Ο（n log n）次比較。

其算法規(guī)則可表述為：

3 算法設(shè)計(jì)與仿真

首先建立包含十五篇文獻(xiàn)的資料庫(kù)，根據(jù)用戶(hù)需求，隨機(jī)輸入關(guān)鍵詞，在此可將關(guān)鍵詞視為子串，對(duì)各文獻(xiàn)進(jìn)行字符串匹配操作。文獻(xiàn)為A串，即目標(biāo)串，關(guān)鍵詞為B串，即模式串。若A串中存在和B相等的子串（ 若干連續(xù)的字符組成的子序列） ，則匹配成功，，否則，稱(chēng)匹配不成功[[3]]。

匹配過(guò)程如圖2所示，將模式串設(shè)置為滑動(dòng)窗口。在第一次匹配過(guò)程中，第三個(gè)字符出現(xiàn)不相同情況，此時(shí)根據(jù)KMP算法原則，利用已經(jīng)得到的部分匹配的結(jié)果，將模式串窗口向后滑動(dòng)一段距離后，繼續(xù)進(jìn)行比較[[4]]。

參考文獻(xiàn)：

[1] 張興華.搜索引擎技術(shù)及研究[J].現(xiàn)代情報(bào)，2002（2）：142.

[2] 黃知義，周寧.幾類(lèi)搜索引擎的原理剖析、比較研究及發(fā)展趨勢(shì)探討[J].圖書(shū)館學(xué)研究，2005（3）：61-62.

[3] 李靜.字符串的模式匹配算法[J].青島化工學(xué)院學(xué)報(bào)，2002（2）：80.

[4] 俞文洋，張連堂，段淑敏.KM P模式匹配算法的研究[J].鄭州輕工業(yè)學(xué)院報(bào)，2007（5）：65.

[5] 黃德才，戚華春.PageRank算法研究[J].計(jì)算機(jī)工程，2006（2）：145-146.

[6] 王奇才，宋國(guó)新才，邵志清.信息檢索中基于鏈接的網(wǎng)頁(yè)排序算法[J].華東理工大學(xué)學(xué)報(bào)，2000（5）：456.

[7] 王海源.分治算法的兩種思路和形式[J].上海師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2003（1）：40-41.

[8] 劉凱鵬，方濱興.一種基于社會(huì)性標(biāo)注的網(wǎng)頁(yè)排序算法[J].計(jì)算機(jī)學(xué)報(bào)，2010（6）：1017.