基于快速排序算法的文献检索技术

姚佳

摘要：文献搜索引擎在资料查找过程中起到重要作用，帮助人们从海量数据资源中找到自己想要的信息。伴随网络技术的推广与发展，目前文献检索网站数据存储量迅速增长，造成检索过程计算量增加。采用快速排序算法，可以有效筛选出与用户需求匹配度较高的文献，方便用户使用，提高运算效率，并利用计算机模拟实现。

关键词：文献检索；快速排序；分治；字符串匹配；时间复杂度

中图分类号：TP391.9 文献标识码：A 文章编号：1009-3044（2014）02-0305-03

伴随网络技术的发展，网络信息大量增加，涵盖期刊、会议纪要、论文、学术成果、学术会议论文的大型网络数据库应运而生，如万方数据库、百度文库、维普数据库等，文献存储容量近百万篇。如何有效搜集发现信息，并对信息提取、组织、处理，就需要寻找出高效算法，降低计算复杂度，提高运算效率，以适应文献资源的迅速扩充[[1]]。

1 文献资料搜索引擎技术特点

当用户以关键词查找信息时，搜索引擎会在数据库中进行搜寻，如果找到与用户要求内容相符的信息，便采用特殊的算法，根据文献中关键词的匹配程度，如出现的次数、频率等计算出各文献的排名等级，然后根据关联度高低，按顺序将这些资源接返回给用户。

与网络搜索引擎不同，因用户需求为数据资料而非网络资源，因此文献检索主要依据为相关关键词、内容的相关度等，对域名、外链等因素考虑较少。可利用关键词匹配算法，计算出各文献特征值，以特征值作为依据，对检索文献排序删选，满足用户需求。为便于理解，该文利用词频和位置加权算法计算特征值，采用快速排序算法进行整理输出，数据库可高效检索出与用户需求匹配程度较高的文献[[2]]。

2 快速排序算法规则及性能分析

快速排序是由托尼·霍尔于1962年（Tony Hoare）所发展的一种递归排序算法，采用分治的思想。在平均状况下，排序 n 个项目需要Ο（n log n）次比较。

其算法规则可表述为：

3 算法设计与仿真

首先建立包含十五篇文献的资料库，根据用户需求，随机输入关键词，在此可将关键词视为子串，对各文献进行字符串匹配操作。文献为A串，即目标串，关键词为B串，即模式串。若A串中存在和B相等的子串（ 若干连续的字符组成的子序列） ，则匹配成功，，否则，称匹配不成功[[3]]。

匹配过程如图2所示，将模式串设置为滑动窗口。在第一次匹配过程中，第三个字符出现不相同情况，此时根据KMP算法原则，利用已经得到的部分匹配的结果，将模式串窗口向后滑动一段距离后，继续进行比较[[4]]。

参考文献：

[1] 张兴华.搜索引擎技术及研究[J].现代情报，2002（2）：142.

[2] 黄知义，周宁.几类搜索引擎的原理剖析、比较研究及发展趋势探讨[J].图书馆学研究，2005（3）：61-62.

[3] 李静.字符串的模式匹配算法[J].青岛化工学院学报，2002（2）：80.

[4] 俞文洋，张连堂，段淑敏.KM P模式匹配算法的研究[J].郑州轻工业学院报，2007（5）：65.

[5] 黄德才，戚华春.PageRank算法研究[J].计算机工程，2006（2）：145-146.

[6] 王奇才，宋国新才，邵志清.信息检索中基于链接的网页排序算法[J].华东理工大学学报，2000（5）：456.

[7] 王海源.分治算法的两种思路和形式[J].上海师范大学学报：自然科学版，2003（1）：40-41.

[8] 刘凯鹏，方滨兴.一种基于社会性标注的网页排序算法[J].计算机学报，2010（6）：1017.