姚佳

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

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

中圖分類號：TP391.9 文獻標識碼：A 文章編號：1009-3044（2014）02-0305-03

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

1 文獻資料搜索引擎技術(shù)特點

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

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

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

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

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

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

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

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

參考文獻：

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

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

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

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

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

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

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

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