李潔玉

(江蘇大學圖書館 鎮(zhèn)江 212013)

·史考縱橫·

計算機情報檢索系統(tǒng)核心實現(xiàn)技術發(fā)展歷程回顧

李潔玉

(江蘇大學圖書館 鎮(zhèn)江 212013)

計算機情報檢索系統(tǒng)的研究起始于1950年代，到現(xiàn)在已經(jīng)經(jīng)過約60年的歲月。目前它已經(jīng)成為情報學和計算機科學的一個重要分支學科。本文從情報檢索的萌芽階段，交互式搜索的興起，文本搜索的開始，全文本搜索、英特網(wǎng)與搜索引擎，英特網(wǎng)走向昌盛五個階段簡要介紹這60年來計算機信息檢索系統(tǒng)研究方面的歷史，著重介紹檢索算法和能提高檢索性能的核心實現(xiàn)技術。并對信息檢索中的中文分詞和中文信息檢索評價研究工作亦進行簡短回顧。

情報檢索 實現(xiàn)技術 發(fā)展階段 排序算法

1 20世紀40年代到50年代——情報檢索的萌芽階段

直到20世紀40年代，情報檢索作為一個研究學科還處于萌芽階段，尚未形成專業(yè)化的情報檢索系統(tǒng)[1]。1948年，在英國皇家學會的一個主題為如何應付科技信息量爆炸式增長的專題討論會上，Holmstrom描述了一個名為Univac的機器，該機器能夠搜索與所給定的科目代碼相關的參考文獻，代碼和參考文獻文本均被存儲在穿孔紙帶上[2]。這是首次提到計算機用于文獻檢索領域。其他一些計算機檢索系統(tǒng)的介紹見文獻3[3]。早期的計算機情報檢索主要在兩個方向上有重要進展：為文檔建立索引和如何對文檔進行檢索。

1.1 為文檔建立索引

在圖書館領域，如何將“項”(item)組織成集合是經(jīng)常辯論的主題。傳統(tǒng)的方法是使用層次型學科分類方案，如杜威十進制分類系統(tǒng)(the Dewey Decimal system)。然而，有很多替代方案被提出。最有名的是Taube等人提出的單元詞(Uniterm)[4]，它的基本思想是用一組關鍵字為項建立索引。在今天看來，這個想法非常簡單，但在當時這被看作是非常激進的一步。幾年以后，Cleverdon對單元項系統(tǒng)和傳統(tǒng)的分類方法的有效性[5]進行了詳細的比較，結(jié)論是單元詞至少和其他方法一樣好，甚至有可能比其他方法更好。這個結(jié)論非常出人意外。但經(jīng)過其他人的反復驗證，Cleverdon的實驗結(jié)果得到同行認可。

1.2 基于排名的檢索

在早期的情報檢索系統(tǒng)中，廣泛采用布爾查詢。布爾查詢由一些詞組合而成,據(jù)此我們可找出和查詢完全匹配的所有文檔。Luhn提出一種新的方法:為文檔集合中的每個文檔分配相應的得分以表示該文檔與給定查詢之間的相關性,然后將這些文檔根據(jù)得分進行排序[6]。Maron、Kuhns和Ray進行了測試，結(jié)果表明它優(yōu)于布爾搜索[7]。同年，基于Maron等人的工作，Luhn提出“一個詞在一篇文檔中出現(xiàn)的次數(shù)是決定這個詞重要性的有效指標”[8]。該方法后來被稱為詞頻加權。由此采用排名的檢索方法在學界受到重視。接下來的幾十年里，該方法被廣泛使用并被不斷細化和改進。

2 20世紀60年代——用戶交互式搜索的興起

2.1 商業(yè)搜索公司的興起

在20世紀60年代，一些商業(yè)搜索公司從專為大型公司或政府機構(gòu)研制專用檢索系統(tǒng)的項目中脫殼而出。Dennis在其論文中描述了早期的一個能搜索數(shù)以萬計文檔的情報檢索系統(tǒng)[9]。 另一個例子是Dialog公司，它成立于1966年，是首先專門為客戶提供搜索的公司之一，該公司起源于為美國航空航天局創(chuàng)建的一個情報檢索系統(tǒng)[10]。

2.2 空間向量模型

在研究領域，情報檢索算法的形式化是一項有意義的工作，它是進一步提高情報檢索性能的有效途徑。值得注意的一種方法是由Switzer提出的空間向量模型[11]。在該模型中，文檔集合中所有索引詞條形成一幾何空間，而文檔和查詢都看作是該間中的向量。文檔和查詢向量之間的相似性由它們之間的的余弦系數(shù)來測定[12]。

3 20世紀70年代——文本搜索的開始

3.1 逆文檔頻率

Jones首次提出逆文檔頻率(IDF)的概念[13]。逆文檔頻率(IDF)是指在一個文檔集合中，一個單詞出現(xiàn)的頻率和其檢索意義上的重要性成反比：不太常見的詞傾向于反映更具體的概念，它在檢索中更重要。結(jié)合TF和IDF兩種權值的想法被提出后很快就被廣泛采納了。另一方面，Salton帶領他的研究組繼續(xù)從事向量空間模型的工作[14]。他們的研究成果支撐了許多研究型檢索系統(tǒng)，激勵后來者在隨后20年中做了更進一步的研究。

3.2 概率模型

情報檢索系統(tǒng)的另一種建模方法是利用概率論擴充Maron、Kuhns和Ray的想法。Robertson定義了概率排名原理[15]，對于特定的評價指標，它確定如何得到基于概率的最佳排名。一些變種在Robertson和Jones發(fā)表的另一篇論文[16]和Rijsbergen的書[17]中給出。這些成果刺激了大量的對概率論模型的進一步研究。

1971年,第一屆ACM情報檢索會議在紐約舉行。1997年召開了第二次會議,此后該會議每年舉行一次。

4 1980年代至1990年代中期——全文本搜索、英特網(wǎng)與搜索引擎

4.1 排名函數(shù)BM25

20世紀70年代，人們對TF-IDF加權方案提出了一些變種。Salton和 Buckley[18]對此方法用于向量空間模型做了廣泛的討論與回顧。在概率模型方面，最初的概率模型沒有包括TF權重，一些研究人員有效地將其納入其中。這項工作最終導致了排名函數(shù)BM25。BM25雖然在形式化方面有所不足，但有效性較之前的概率模型有較大的提高。

4.2 潛在語義索引

和向量空間模型有關，潛在語義索引(Latent Semantic Indexing)通過奇異值分解[19]將任何文檔集合所對應的向量空間的維數(shù)減少。這樣文檔和查詢被映射到較低維的空間。Deerwester和他的同事聲稱降維導致查詢能夠匹配到更多的相關文件。

4.3 計算語言學方法的應用

不同于潛在語義索引這樣的純數(shù)值方法，其他一些探測性的計算語言學方法考慮英語的很多方面如詞的語法與語義、詞的重復和模糊性、命名實體等。在這方面雖然進行了大量的研究工作，但對于檢索系統(tǒng)的有效性鮮少有什么幫助。唯一被發(fā)現(xiàn)有用的是詞干提取算法(stemming)。詞干提取算法是指將文檔和查詢中的英文單詞均去掉詞尾，保留詞頭和詞干。詞干提取算法可以追溯到1960年代。波特在1970年代末開發(fā)出一套小巧的適用于英語的提取規(guī)則，他的波特詞干提取算法[20]至今仍有很大影響。

4.4 文本檢索會議——TREC

1980年代末到1990年代初學術界關注的一個問題是，相較于當時一些商業(yè)搜索引擎公司采用的文檔集合，當時學術界用于測試的文檔集合普遍規(guī)模很小。從1992年起，Donna Harman和她的同事創(chuàng)辦TREC(Text REtrieval Conference，文本檢索)會議，每年舉辦一次。由眾多的國際研究團體合作構(gòu)造出一些測試集合，比以前使用的文檔集合要大幾個數(shù)量級[21]。采用這些新的數(shù)據(jù)集后可使實驗結(jié)果更具實際意義。

4.5 學習排名

到這一時期，在搜索引擎中使用的排序函數(shù)是由人工設計，并在實驗中手動調(diào)整一些參數(shù)。Fuhr[22]描述了如何通過確定一組查詢和其相關的文檔作為訓練數(shù)據(jù)而學到檢索函數(shù)。文獻23[23]和文獻24[24]提出了更多的方法。由于缺乏足夠的訓練數(shù)據(jù),這些方法在當時效果不佳。到了2000年代，Web查詢?nèi)罩敬罅砍霈F(xiàn)，可用作為訓練數(shù)據(jù)。這些方法使用了Web查詢?nèi)罩竞?，效果變好?/p>

5 1990年代中期至今——英特網(wǎng)走向昌盛的年代

5.1 英特網(wǎng)搜索與相應的技術

Berners-Lee在1990年底創(chuàng)建了萬維網(wǎng)，在最初幾年網(wǎng)站和網(wǎng)頁的數(shù)量還相對較少,采用傳統(tǒng)的手工編目方法就可以。但后來網(wǎng)站和網(wǎng)頁的數(shù)量成倍地增長，手工方法日漸不敷。Web搜索引擎在1993年下半年開始出現(xiàn)，以滿足日益增長的需要。

為了有效支持Web上的應用，出現(xiàn)了兩處重要的研究進展，它們是鏈接分析和錨文本的搜索。錨文本不僅搜索網(wǎng)頁本身的內(nèi)容，并且搜索鏈接指向的文本。錨文本一般是頁面的一個簡短的總結(jié)，在較早時候就被認識到可作為有價值的信息源(如McBryan在1994年的工作[25])。一些人為網(wǎng)頁寫作了錨文本，主要目的是使操縱該文本更難實現(xiàn)。使用錨文本是谷歌搜索引擎的一個主要特點[26]。鏈接分析法PageRank由谷歌的創(chuàng)始人提出，而HITS是在差不多同時由Kleinberg 提出[27]。

在現(xiàn)有的文檔排序功能上添加鏈接分析和文檔的多重文本表示，意味著我們會使情報檢索系統(tǒng)的內(nèi)部算法變得更加復雜。為不同的特征正確地設置參數(shù)是一個挑戰(zhàn)，這使得人們重新探討由Fuhr啟動的學習排序方法。Fuhr當時苦于缺乏足夠的訓練數(shù)據(jù)，但是，當搜索引擎廣泛流行，人們認識到，用戶交互的日志可作此用。

5.2 從查詢?nèi)罩局刑崛⌒畔?/p>

從搜索引擎的日志中自動提取信息也引起人們的注意。雖然存儲并檢查日志的實踐已有多年，但大多數(shù)情況是作為對手動調(diào)節(jié)檢索系統(tǒng)提供有用的信息。當大眾普遍開始使用Web搜索引擎時，人們逐步認識到可從這些日志中提取有價值的信息的真正潛力。檢查用戶的查詢、選擇結(jié)果列表中文檔的用戶模式和用戶查詢的再形成，使研究人員能準確理解用戶的“意圖”， 以制定更有效的查詢處理技術，如自動拼寫校正[28]、自動查詢擴展[29]和更準確的詞干保留技術(stemming)[30]。

5.3 信息需求的多樣性

人們早就認識到，即使是使用同一個查詢，不同的用戶可能有不同的信息需求，情報檢索系統(tǒng)應該能夠滿足這些不同的需求。這就需要在對文檔進行排名時，搜索引擎要同時考慮文檔的相關性和多樣性。自1990年代末以來，已經(jīng)有很多科學家共同努力試圖解決這個問題。Carbonell和Goldstein關于他們的多樣性系統(tǒng)MMR的描述[31]是該問題的一篇核心論文。

5.4 檢索模型的新進展

在此期間，作為情報檢索系統(tǒng)中的核心排名功能的基礎，檢索模型繼續(xù)有新的進展。特別值得注意的是使用語言模型的概率方法，最早由Ponte、Croft[32]和Hiemstra[33]提出。通過對文檔和查詢之間的匹配過程采取新的觀點，語言模型方法為一些情報檢索過程，如相關性反饋、形成文檔的集群(cluster)、項之間的依賴等提供了新的認識。

隨著計算環(huán)境的變化，搜索和情報檢索仍然繼續(xù)發(fā)展。近來這種類型的變化最明顯的例子就是移動設備和社交媒體的快速增長。情報檢索學界對此的反應是開展對社會化搜索的研究，其中涉及到用戶社區(qū)和非正式的信息交換。新的研究在各種主題諸如用戶標記、談話檢索、過濾和推薦、協(xié)作搜索等開展，并開始提供用于管理個人和社會信息有效的新工具。

5.5 短查詢與長查詢

根據(jù)統(tǒng)計大部分提交到Web搜索引擎的查詢都很短(1～3詞)，所以很多基于Web的情報檢索研究都把注意力集中于短查詢。短查詢一般沒有什么語言結(jié)構(gòu)，有些時候只由一個名詞或名詞短語組成。另一項進展是支持用戶提出的長查詢。這項研究工作的開始與TREC的問題回答任務[34]有關。該任務試圖對某些類型的問題(像“WH”問題如“誰”和“什么時候”)找出簡短的答案。該任務很適合大型社區(qū)答疑檔案這樣的應用。研究人員還一直在對更詳細的問題開發(fā)、提供更有針對性的答案的技術。一些應用程序如蘋果的情報檢索Siri、IBM的Watson和雅虎問答的成功，很大程度上是由于該項研究的開展。

6 中文信息檢索

中文信息檢索是中文情報處理的一部分。中國中文信息學會成立于1981年6月，錢偉長、甄健民、安其春等為主要發(fā)起人。中文信息處理學科是在語言文字學、計算機應用技術、人工智能、認知心理學和數(shù)學等相關學科的基礎上形成的一門交叉學科。中文信息檢索系統(tǒng)的實現(xiàn)多采用國際上已有的基于英文的信息檢索技術。但在下述兩個方面有差別。

6.1 中文分詞

中英文信息(情報)檢索的主要區(qū)別在于檢索的基本單位不同。英文詞之間一般可根據(jù)空格自動區(qū)分，而中文檢索更為復雜。如為所有的單字建立索引，則檢索效果不理想。所以一般為一個或多個字組成的詞建立索引，則需要好的分詞算法?，F(xiàn)有的分詞算法可分為三類：基于辭典、詞庫匹配的分詞方法，基于詞頻統(tǒng)計的分詞方法和基于知識理解的分詞方法。對于每一類，都已提出了很多種方法。

6.2 中文信息檢索評價

2003 年，國家863 計劃軟硬件主題設立了“中文信息處理和智能人機接口技術評測”專項課題，對包括機器翻譯、語音識別、信息檢索在內(nèi)的中文信息處理關鍵技術進行評測。該課題由中國科學院計算技術研究所承辦，從2003 年到2005年連續(xù)舉辦三屆[35]。

SEWM是另一項主要的中文信息檢索評測活動，這項活動由北京大學從2004年起至2011年共舉辦8次[36]。該活動側(cè)重于Web信息檢索，在某些年份，也有其他一些不同的主題如垃圾郵件過濾、非網(wǎng)頁數(shù)字資源分類等。關于構(gòu)建測試集的一些考慮因素的討論見文獻37[37]。

7 結(jié)論和未來方向

在20世紀初，人們常常利用圖書館，通過使用卡片目錄，希望找到有關的書籍或文檔資料，以滿足查找信息的需求。這種方式既不方便又慢，效率較低，還受到圖書館收藏的局限，通常僅能找到有限的信息，用它解決極少量的問題。到了21世紀，基于Web的搜索幾乎是無處不在的，人們通過互聯(lián)網(wǎng)，采用搜索引擎在瞬間訪問到數(shù)百萬兆字節(jié)的網(wǎng)頁、視頻剪輯、新聞、圖片、社會媒體掃描的書籍、學術論文、音樂、電視節(jié)目和電影。在過去幾年中，甚至發(fā)展到利用移動電話來進行類似的搜索。與100年前的情報檢索方式唯一的共同點是，這兩種服務一般都可以免費使用。

如今的情報檢索系統(tǒng)已經(jīng)很容易使用，然而情報檢索系統(tǒng)背后的技術卻凝聚了眾多科學家和研究人員的心血，是他們60多年來的不斷創(chuàng)新和努力的結(jié)果。

展望未來，短期而言，各種垂直型的搜索引擎(如旅游、餐飲、購物、體育、學術等)、社會網(wǎng)絡分析與事件和輿情的識別、移動訪問、與位置和時間有關的情報檢索、個性化服務、多媒體情報檢索等還會有進一步的發(fā)展。從長期的和用戶的角度而言，更加完善的情報檢索系統(tǒng)包括能夠提供無可挑剔的語音識別、自然對話的管理、對于搜索者的信息需求的高水平的語義理解，以及能夠?qū)Υ罅康奈臋n和聯(lián)邦數(shù)據(jù)庫的無限制訪問。

[1] 丁 蔚，倪 波，成 穎. 情報檢索的發(fā)展——情報學世紀回眸之一[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] 北京大學網(wǎng)絡實驗室. 中文Web信息檢索論壇(CWIRF)[EB/OL]. [2014-04-20]. http://www.cwirf.org/.

[37] 李靜靜，閆宏飛. 中文網(wǎng)頁信息檢索測試集的構(gòu)建、分析及應用[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年生，碩士，工程師。