计算机情报检索系统核心实现技术发展历程回顾

李洁玉

(江苏大学图书馆 镇江 212013)

·史考纵横·

计算机情报检索系统核心实现技术发展历程回顾

李洁玉

(江苏大学图书馆 镇江 212013)

计算机情报检索系统的研究起始于1950年代，到现在已经经过约60年的岁月。目前它已经成为情报学和计算机科学的一个重要分支学科。本文从情报检索的萌芽阶段，交互式搜索的兴起，文本搜索的开始，全文本搜索、英特网与搜索引擎，英特网走向昌盛五个阶段简要介绍这60年来计算机信息检索系统研究方面的历史，着重介绍检索算法和能提高检索性能的核心实现技术。并对信息检索中的中文分词和中文信息检索评价研究工作亦进行简短回顾。

情报检索 实现技术 发展阶段 排序算法

1 20世纪40年代到50年代——情报检索的萌芽阶段

直到20世纪40年代，情报检索作为一个研究学科还处于萌芽阶段，尚未形成专业化的情报检索系统[1]。1948年，在英国皇家学会的一个主题为如何应付科技信息量爆炸式增长的专题讨论会上，Holmstrom描述了一个名为Univac的机器，该机器能够搜索与所给定的科目代码相关的参考文献，代码和参考文献文本均被存储在穿孔纸带上[2]。这是首次提到计算机用于文献检索领域。其他一些计算机检索系统的介绍见文献3[3]。早期的计算机情报检索主要在两个方向上有重要进展：为文档建立索引和如何对文档进行检索。

1.1 为文档建立索引

在图书馆领域，如何将“项”(item)组织成集合是经常辩论的主题。传统的方法是使用层次型学科分类方案，如杜威十进制分类系统(the Dewey Decimal system)。然而，有很多替代方案被提出。最有名的是Taube等人提出的单元词(Uniterm)[4]，它的基本思想是用一组关键字为项建立索引。在今天看来，这个想法非常简单，但在当时这被看作是非常激进的一步。几年以后，Cleverdon对单元项系统和传统的分类方法的有效性[5]进行了详细的比较，结论是单元词至少和其他方法一样好，甚至有可能比其他方法更好。这个结论非常出人意外。但经过其他人的反复验证，Cleverdon的实验结果得到同行认可。

1.2 基于排名的检索

在早期的情报检索系统中，广泛采用布尔查询。布尔查询由一些词组合而成,据此我们可找出和查询完全匹配的所有文档。Luhn提出一种新的方法:为文档集合中的每个文档分配相应的得分以表示该文档与给定查询之间的相关性,然后将这些文档根据得分进行排序[6]。Maron、Kuhns和Ray进行了测试，结果表明它优于布尔搜索[7]。同年，基于Maron等人的工作，Luhn提出“一个词在一篇文档中出现的次数是决定这个词重要性的有效指标”[8]。该方法后来被称为词频加权。由此采用排名的检索方法在学界受到重视。接下来的几十年里，该方法被广泛使用并被不断细化和改进。

2 20世纪60年代——用户交互式搜索的兴起

2.1 商业搜索公司的兴起

在20世纪60年代，一些商业搜索公司从专为大型公司或政府机构研制专用检索系统的项目中脱壳而出。Dennis在其论文中描述了早期的一个能搜索数以万计文档的情报检索系统[9]。 另一个例子是Dialog公司，它成立于1966年，是首先专门为客户提供搜索的公司之一，该公司起源于为美国航空航天局创建的一个情报检索系统[10]。

2.2 空间向量模型

在研究领域，情报检索算法的形式化是一项有意义的工作，它是进一步提高情报检索性能的有效途径。值得注意的一种方法是由Switzer提出的空间向量模型[11]。在该模型中，文档集合中所有索引词条形成一几何空间，而文档和查询都看作是该间中的向量。文档和查询向量之间的相似性由它们之间的的余弦系数来测定[12]。

3 20世纪70年代——文本搜索的开始

3.1 逆文档频率

Jones首次提出逆文档频率(IDF)的概念[13]。逆文档频率(IDF)是指在一个文档集合中，一个单词出现的频率和其检索意义上的重要性成反比：不太常见的词倾向于反映更具体的概念，它在检索中更重要。结合TF和IDF两种权值的想法被提出后很快就被广泛采纳了。另一方面，Salton带领他的研究组继续从事向量空间模型的工作[14]。他们的研究成果支撑了许多研究型检索系统，激励后来者在随后20年中做了更进一步的研究。

3.2 概率模型

情报检索系统的另一种建模方法是利用概率论扩充Maron、Kuhns和Ray的想法。Robertson定义了概率排名原理[15]，对于特定的评价指标，它确定如何得到基于概率的最佳排名。一些变种在Robertson和Jones发表的另一篇论文[16]和Rijsbergen的书[17]中给出。这些成果刺激了大量的对概率论模型的进一步研究。

1971年,第一届ACM情报检索会议在纽约举行。1997年召开了第二次会议,此后该会议每年举行一次。

4 1980年代至1990年代中期——全文本搜索、英特网与搜索引擎

4.1 排名函数BM25

20世纪70年代，人们对TF-IDF加权方案提出了一些变种。Salton和 Buckley[18]对此方法用于向量空间模型做了广泛的讨论与回顾。在概率模型方面，最初的概率模型没有包括TF权重，一些研究人员有效地将其纳入其中。这项工作最终导致了排名函数BM25。BM25虽然在形式化方面有所不足，但有效性较之前的概率模型有较大的提高。

4.2 潜在语义索引

和向量空间模型有关，潜在语义索引(Latent Semantic Indexing)通过奇异值分解[19]将任何文档集合所对应的向量空间的维数减少。这样文档和查询被映射到较低维的空间。Deerwester和他的同事声称降维导致查询能够匹配到更多的相关文件。

4.3 计算语言学方法的应用

不同于潜在语义索引这样的纯数值方法，其他一些探测性的计算语言学方法考虑英语的很多方面如词的语法与语义、词的重复和模糊性、命名实体等。在这方面虽然进行了大量的研究工作，但对于检索系统的有效性鲜少有什么帮助。唯一被发现有用的是词干提取算法(stemming)。词干提取算法是指将文档和查询中的英文单词均去掉词尾，保留词头和词干。词干提取算法可以追溯到1960年代。波特在1970年代末开发出一套小巧的适用于英语的提取规则，他的波特词干提取算法[20]至今仍有很大影响。

4.4 文本检索会议——TREC

1980年代末到1990年代初学术界关注的一个问题是，相较于当时一些商业搜索引擎公司采用的文档集合，当时学术界用于测试的文档集合普遍规模很小。从1992年起，Donna Harman和她的同事创办TREC(Text REtrieval Conference，文本检索)会议，每年举办一次。由众多的国际研究团体合作构造出一些测试集合，比以前使用的文档集合要大几个数量级[21]。采用这些新的数据集后可使实验结果更具实际意义。

4.5 学习排名

到这一时期，在搜索引擎中使用的排序函数是由人工设计，并在实验中手动调整一些参数。Fuhr[22]描述了如何通过确定一组查询和其相关的文档作为训练数据而学到检索函数。文献23[23]和文献24[24]提出了更多的方法。由于缺乏足够的训练数据,这些方法在当时效果不佳。到了2000年代，Web查询日志大量出现，可用作为训练数据。这些方法使用了Web查询日志后，效果变好。

5 1990年代中期至今——英特网走向昌盛的年代

5.1 英特网搜索与相应的技术

Berners-Lee在1990年底创建了万维网，在最初几年网站和网页的数量还相对较少,采用传统的手工编目方法就可以。但后来网站和网页的数量成倍地增长，手工方法日渐不敷。Web搜索引擎在1993年下半年开始出现，以满足日益增长的需要。

为了有效支持Web上的应用，出现了两处重要的研究进展，它们是链接分析和锚文本的搜索。锚文本不仅搜索网页本身的内容，并且搜索链接指向的文本。锚文本一般是页面的一个简短的总结，在较早时候就被认识到可作为有价值的信息源(如McBryan在1994年的工作[25])。一些人为网页写作了锚文本，主要目的是使操纵该文本更难实现。使用锚文本是谷歌搜索引擎的一个主要特点[26]。链接分析法PageRank由谷歌的创始人提出，而HITS是在差不多同时由Kleinberg 提出[27]。

在现有的文档排序功能上添加链接分析和文档的多重文本表示，意味着我们会使情报检索系统的内部算法变得更加复杂。为不同的特征正确地设置参数是一个挑战，这使得人们重新探讨由Fuhr启动的学习排序方法。Fuhr当时苦于缺乏足够的训练数据，但是，当搜索引擎广泛流行，人们认识到，用户交互的日志可作此用。

5.2 从查询日志中提取信息

从搜索引擎的日志中自动提取信息也引起人们的注意。虽然存储并检查日志的实践已有多年，但大多数情况是作为对手动调节检索系统提供有用的信息。当大众普遍开始使用Web搜索引擎时，人们逐步认识到可从这些日志中提取有价值的信息的真正潜力。检查用户的查询、选择结果列表中文档的用户模式和用户查询的再形成，使研究人员能准确理解用户的“意图”， 以制定更有效的查询处理技术，如自动拼写校正[28]、自动查询扩展[29]和更准确的词干保留技术(stemming)[30]。

5.3 信息需求的多样性

人们早就认识到，即使是使用同一个查询，不同的用户可能有不同的信息需求，情报检索系统应该能够满足这些不同的需求。这就需要在对文档进行排名时，搜索引擎要同时考虑文档的相关性和多样性。自1990年代末以来，已经有很多科学家共同努力试图解决这个问题。Carbonell和Goldstein关于他们的多样性系统MMR的描述[31]是该问题的一篇核心论文。

5.4 检索模型的新进展

在此期间，作为情报检索系统中的核心排名功能的基础，检索模型继续有新的进展。特别值得注意的是使用语言模型的概率方法，最早由Ponte、Croft[32]和Hiemstra[33]提出。通过对文档和查询之间的匹配过程采取新的观点，语言模型方法为一些情报检索过程，如相关性反馈、形成文档的集群(cluster)、项之间的依赖等提供了新的认识。

随着计算环境的变化，搜索和情报检索仍然继续发展。近来这种类型的变化最明显的例子就是移动设备和社交媒体的快速增长。情报检索学界对此的反应是开展对社会化搜索的研究，其中涉及到用户社区和非正式的信息交换。新的研究在各种主题诸如用户标记、谈话检索、过滤和推荐、协作搜索等开展，并开始提供用于管理个人和社会信息有效的新工具。

5.5 短查询与长查询

根据统计大部分提交到Web搜索引擎的查询都很短(1～3词)，所以很多基于Web的情报检索研究都把注意力集中于短查询。短查询一般没有什么语言结构，有些时候只由一个名词或名词短语组成。另一项进展是支持用户提出的长查询。这项研究工作的开始与TREC的问题回答任务[34]有关。该任务试图对某些类型的问题(像“WH”问题如“谁”和“什么时候”)找出简短的答案。该任务很适合大型社区答疑档案这样的应用。研究人员还一直在对更详细的问题开发、提供更有针对性的答案的技术。一些应用程序如苹果的情报检索Siri、IBM的Watson和雅虎问答的成功，很大程度上是由于该项研究的开展。

6 中文信息检索

中文信息检索是中文情报处理的一部分。中国中文信息学会成立于1981年6月，钱伟长、甄健民、安其春等为主要发起人。中文信息处理学科是在语言文字学、计算机应用技术、人工智能、认知心理学和数学等相关学科的基础上形成的一门交叉学科。中文信息检索系统的实现多采用国际上已有的基于英文的信息检索技术。但在下述两个方面有差别。

6.1 中文分词

中英文信息(情报)检索的主要区别在于检索的基本单位不同。英文词之间一般可根据空格自动区分，而中文检索更为复杂。如为所有的单字建立索引，则检索效果不理想。所以一般为一个或多个字组成的词建立索引，则需要好的分词算法。现有的分词算法可分为三类：基于辞典、词库匹配的分词方法，基于词频统计的分词方法和基于知识理解的分词方法。对于每一类，都已提出了很多种方法。

6.2 中文信息检索评价

2003 年，国家863 计划软硬件主题设立了“中文信息处理和智能人机接口技术评测”专项课题，对包括机器翻译、语音识别、信息检索在内的中文信息处理关键技术进行评测。该课题由中国科学院计算技术研究所承办，从2003 年到2005年连续举办三届[35]。

SEWM是另一项主要的中文信息检索评测活动，这项活动由北京大学从2004年起至2011年共举办8次[36]。该活动侧重于Web信息检索，在某些年份，也有其他一些不同的主题如垃圾邮件过滤、非网页数字资源分类等。关于构建测试集的一些考虑因素的讨论见文献37[37]。

7 结论和未来方向

在20世纪初，人们常常利用图书馆，通过使用卡片目录，希望找到有关的书籍或文档资料，以满足查找信息的需求。这种方式既不方便又慢，效率较低，还受到图书馆收藏的局限，通常仅能找到有限的信息，用它解决极少量的问题。到了21世纪，基于Web的搜索几乎是无处不在的，人们通过互联网，采用搜索引擎在瞬间访问到数百万兆字节的网页、视频剪辑、新闻、图片、社会媒体扫描的书籍、学术论文、音乐、电视节目和电影。在过去几年中，甚至发展到利用移动电话来进行类似的搜索。与100年前的情报检索方式唯一的共同点是，这两种服务一般都可以免费使用。

如今的情报检索系统已经很容易使用，然而情报检索系统背后的技术却凝聚了众多科学家和研究人员的心血，是他们60多年来的不断创新和努力的结果。

展望未来，短期而言，各种垂直型的搜索引擎(如旅游、餐饮、购物、体育、学术等)、社会网络分析与事件和舆情的识别、移动访问、与位置和时间有关的情报检索、个性化服务、多媒体情报检索等还会有进一步的发展。从长期的和用户的角度而言，更加完善的情报检索系统包括能够提供无可挑剔的语音识别、自然对话的管理、对于搜索者的信息需求的高水平的语义理解，以及能够对大量的文档和联邦数据库的无限制访问。

[1] 丁 蔚，倪 波，成 颖. 情报检索的发展——情报学世纪回眸之一[J]. 情报科学，2001,19(1)：81-86.

[2] Holmstrom J E. Section III. Opening plenary session [C]// The Royal Society Scientific Information Conference, 21 June-2 July 1948 : report and papers submitted. London: Royal Society, 1948.

[3] Nanus B. The use of electronic computers for information retrieval[J]. Bulletin of the Medical Library Association, 1960, 48(3): 278.

[4] Taube M, Gull C D, Wachtel I S. Unit terms in coordinate indexing[J]. American documentation, 1952, 3(4): 213-218.

[5] Belkin N J, Croft W B. Information filtering and information retrieval: two sides of the same coin?[J]. Communications of the ACM, 1992, 35(12): 29-38.

[6] Luhn H P. A statistical approach to mechanized encoding and searching of literary information[J]. IBM Journal of research and development, 1957, 1(4): 309-317.

[7] Maron M E, Kuhns J L, Ray L C. Probabilistic indexing. a statistical technique for document identification and retrieval[R]. Los Angeles：Thompson Ramo Wooldridge Inc , 1959.

[8] Luhn H P. The automatic creation of literature abstracts[J]. IBM Journal of research and development, 1958, 2(2): 159-165.

[9] Dennis B K, Brady J J, Dovel Jr J A. Index manipulation and abstract retrieval by computer[J]. Journal of Chemical Documentation, 1962, 2(4): 234-242.

[10] Bjorner S, Ardito S C. Online before the Internet: Early pioneers tell their stories, Part 2: Growth of the online industry[J]. Searcher, 2003, 11(7): 52-61.

[11] Switzer P. Vector images in document retrieval[J]. Statistical association methods for mechanized documentation, 1965: 163-171.

[12] Rocchio J J. Relevance feedback in information retrieval[R]. Cambridge：Harvard University, 1965.

[13] Jones K S. A statistical interpretation of term specificity and its application in retrieval[J]. Journal of documentation, 1972, 28(1): 11-21.

[14] Salton G, Wong A, Yang C S. A vector space model for automatic indexing[J]. Communications of the ACM, 1975, 18(11): 613-620.

[15] Robertson S E. The probability ranking principle in IR[J]. Journal of documentation, 1977, 33(4): 294-304.

[16] Robertson S E, Jones K S. Relevance weighting of search terms[J]. Journal of the American Society for Information science, 1976, 27(3): 129-146.

[17] Van Rijsbergen C J. Information Retrieval[M]. Oxford: Butterworth-Heinemann Ltd, 1979:224.

[18] Salton G, Buckley C. Term-weighting approaches in automatic text retrieval[J]. Information Processing & Management, 1988, 24(5): 513-523.

[19] Deerwester S C, Dumais S T, Landauer T K, et al. Indexing by latent semantic analysis[J]. JASIS, 1990, 41(6): 391-407.

[20] Porter M F. An algorithm for suffix stripping[J]. Program: electronic library and information systems, 1980, 14(3): 130-137.

[21] Voorhees E M，Harman D K. TREC: Experiment and evaluation in information retrieval[M]. Cambridge: MIT press, 2005:123-152.

[22] Fuhr N. Optimum polynomial retrieval functions based on the probability ranking principle[J]. ACM Transactions on Information Systems (TOIS), 1989, 7(3): 183-204.

[23] Fuhr N, Buckley C. A probabilistic learning approach for document indexing[J]. ACM Transactions on Information Systems (TOIS), 1991, 9(3): 223-248.

[24] Cooper W S, Gey F C, Dabney D P. Probabilistic retrieval based on staged logistic regression[C]// Proceedings of the 15th annual international ACM SIGIR conference on Research and development in information retrieval. ACM, 1992: 198-210.

[25] McBryan O A. GENVL and WWWW: Tools for taming the web[C]// Proceedings of the first international world wide web conference. 1994:341.

[26] Brin S, Page L. The anatomy of a large-scale hypertextual Web search engine[J]. Computer networks and ISDN systems, 1998, 30(1): 107-117.

[27] Kleinberg J M. Authoritative sources in a hyperlinked environment[J]. Journal of the ACM, 1999, 46(5): 604-632.

[28] Cucerzan S, Brill E. Spelling Correction as an Iterative Process that Exploits the Collective Knowledge of Web Users[C]// EMNLP. 2004, 4: 293-300.

[29] Agichtein E, Brill E, Dumais S. Improving web search ranking by incorporating user behavior information[C]// Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval. ACM, 2006: 19-26.

[30] Peng F, Ahmed N, Li X, et al. Context sensitive stemming for web search[C]// Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval. ACM, 2007: 639-646.

[31] Carbonell J, Goldstein J. The use of MMR, diversity-based reranking for reordering documents and producing summaries[C]// Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval. ACM, 1998: 335-336.

[32] Ponte J M, Croft W B. A language modeling approach to information retrieval[C]// Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval. ACM, 1998: 275-281.

[33] Hiemstra D. A linguistically motivated probabilistic model of information retrieval[M]// Research and advanced technology for digital libraries. Berlin: Springer Berlin Heidelberg, 1998: 569-584.

[34] Voorhees E M. The TREC question answering track[J]. Natural Language Engineering, 2001, 7(4): 361-378.

[35] 中国科学院计算技术研究所. 信息检索评测技术概述[EB/OL]. [2014-04-20]. http://www.ict.ac.cn/kxcb/kxr/201009/t20100907_2945830.html.

[36] 北京大学网络实验室. 中文Web信息检索论坛(CWIRF)[EB/OL]. [2014-04-20]. http://www.cwirf.org/.

[37] 李静静，闫宏飞. 中文网页信息检索测试集的构建、分析及应用[J]. 中文信息学报，2008,22(1):30-36.

(责任编校 田丽丽)

ABriefIntroductiontotheHistoryoftheKeyImplementationTechnologyofComputerInformationRetrieval

Li Jieyu

Jiangsu University Library, Zhenjiang 212013, China

It has been over 60 years since researchers began to investigate computerized information retrieval systems in the 1950s. Up to now it has become an important branch in information science and computer science as well. We break the whole 60 years down to 5 stages, namely appearance of information retrieval, interactional search, text search, whole text search and Internet search engine, Internet tending towards prosperity, and discuss each of them with a focus on the key implementation technology. We also give a brief account of the evaluation of Chinese segmentation and Chinese information retrieval.

information retrieval; implementation technology; stage of development; ranking algorithm

G354

李洁玉，女，1963年生，硕士，工程师。