原出處: http://ccl.pku.edu.cn/doubtfire/Course/Chinese%20Information%20Processing/contents/Chapter_07_1.ppt 調研報告 題 目 搜尋結果排序算法的研究 學生姓名 張天 指導教師 徐德智 學 院 資訊科學與工程學院 專業班級 教信011班 報告完成日期 2005-4-10 一、研究背景 1 、Internet與WWW發展現狀[5] (1)Internet 的發展曆程 Internet的前身是美國國防部進階研究計劃署的研究試驗性網絡ARPANET。1983年TCP/IP成為ARPANET上唯一的正式協定。此後，ARPANET上連接配接的網絡、機器和使用者快速增長。1988年NSFNET和ARPANET互聯，它的規模以指數增長，很多地區網絡開始加入，并且開始與加拿大、歐洲和太平洋地區的網絡連接配接。後來形成Internet。90年代初到現在，是Internet增長最迅速的時期。1993年，Internet的增長速度是341%。截止到1996年7月，Internet已連接配接了134336個網絡，入網主機1228萬台，以及數以億計的使用者。到1998年7月，Internet已擁有427萬個網址，4300萬個域名，3673.9萬台主機和3.2億個網頁，其規模大概每年翻一番。 (2)World Wide Web(WWW) World Wide Web(WWW)是全球性的網絡資訊系統。一九八九年，位于瑞士的European Laboratory for Particle Physics(CERN)首先開始了WWW的研究工作。随後，許多其他的研究機構、大學和公司也加入WWW研究者的行列，并相繼開發出各自的WWW軟體。這些WWW軟體的運作平台覆寫了目前主流的計算機硬體和作業系統。在此過程中，WWW也不斷完善和發展。同時，為了保證不同WWW軟體之間的互操作性，一系列WWW協定和标準也正在使用和完善之中。 在最近幾年裡，WWW得到了長足的發展，不僅成為企業必不可少的組成部分，并且開始走進千家萬戶。根據NEC研究院在《自然》上釋出的資料，截止到1999年2月，Internet上共有網站1600萬個，其中公開提供WWW服務的網站280萬個；共有WWW網頁大約8億頁，這些網頁包含了15T位元組的資料。按照2000年4月在波士頓舉行的第5屆搜尋引擎年會的會議報告，我們可以知道現今的網頁數目已經超過了10億。 WWW在中國的發展速度也十分驚人。根據CNNIC(中國網際網路絡資訊中心)2001年1月17日在京釋出的《中國網際網路絡發展狀況統計報告》，截止到2000年12月31日止，我國上網計算機數有約892萬台。我國上網使用者人數約2250萬人，除計算機外同時使用其它裝置（移動終端、資訊家電等）上網的使用者人數為92萬。CN下注冊的域名總數為122099個，WWW站點數（包括.CN、.COM、.NET、.ORG下的網站）約265405個，我國國際線路的總容量為2799M。關于網頁的數目沒有具體的統計資料，但根據《科學》雜志上提供的集合估計法，通過中國幾個主要搜尋引擎獲得的搜尋資料（天網、Chinaren、新浪、搜狐、網易），我們可以估計到目前中國擁有的網頁數已經超過3000萬。 (3)Internet 的資訊分布 Internet上的資訊資源随着Internet的發展而呈現出以下特點： l 資訊量大而且分散 l 自治性強 l 資訊資源多種多樣 l 不一緻和不完整性 這些特點對網絡軟體的性能提出了很高的要求。網絡的快速發展給資訊挖掘帶來了挑戰。WWW上資訊呈現爆炸性的指數增長，同時伴随着上網經驗不足、不太了解如何查找資訊的新使用者的加入。使用者很可能最大程度的運用超鍊來在網上沖浪，他們通常從以下兩類網站開始： 第一類是目錄系統，其典型代表是Yahoo!的分類目錄（http://www.yahoo.com），Yahoo的分類目錄通過有專業知識的網頁編輯人員對網上的網頁進行精選，建立一個索引目錄，來給使用者提供服務。這類通過手工維護得很好的系統的優點是提供的網頁準确率高，可以有效的覆寫所有熱門的主題，但它們的缺點是過于主觀，而且需要高昂的代價來建立和維護，更新改進的慢，同時不能很好的覆寫所有深奧的主題。 第二類是搜尋引擎系統，比如天網中英文搜尋引擎（http://e.pku.edu.cn），它通過程式自動地從網上搜集和分析網頁，建立索引，為使用者服務。這類通過關鍵詞比對實作查找的自動更新的搜尋引擎優點是涵蓋的網頁數量巨大，但通常傳回太多的低品質相關性不大的結果。 二、 國内外研究現狀 1、搜尋引擎發展簡史 面對浩瀚的網絡資源，搜尋引擎為所有網上沖浪的使用者提供了一個入口，毫不誇張的說，所有的使用者都可以從搜尋出發到達自己想去的網上任何一個地方。是以它也成為除了電子郵件以外最多人使用的網上服務。 搜尋引擎技術伴随着WWW的發展是引人注目的。搜尋引擎大約經曆了三代的更新發展： 第一代搜尋引擎出現于1994年。這類搜尋引擎一般都索引少于1，000，000個網頁，極少重新搜集網頁并去重新整理索引。而且其檢索速度非常慢，一般都要等待10秒甚至更長的時間。在實作技術上也基本沿用較為成熟的IR（Information Retrieval）、網絡、資料庫等技術，相當于利用一些已有技術實作的一個WWW上的應用。在1994年3月到4月，網絡爬蟲World Wide Web Worm(WWWW)平均每天承受大約1500次查詢。 大約在1996年出現的第二代搜尋引擎系統大多采用分布式方案（多個微型計算機協同工作）來提高資料規模、響應速度和使用者數量，它們一般都保持一個大約50,000,000網頁的索引資料庫，每天能夠響應10,000,000次使用者檢索請求。1997年11月，當時最先進的幾個搜尋引擎号稱能建立從2,000,000到100,000,000的網頁索引。Altavista搜尋引擎聲稱他們每天大概要承受20,000,000次查詢。 自1998年到現在，出現了一個搜尋引擎空前繁榮的時期，我們統稱這一時期的搜尋引擎為第三代搜尋引擎。第三代搜尋引擎的發展有如下幾個特點： (1)索引資料庫的規模繼續增大，一般的商業搜尋引擎都保持在幾千萬甚至 上億個網頁。 (2)除了一般意義上的搜尋以外，開始出現主題搜尋和地域搜尋。很多小型的垂直門戶站點開始使用該技術。 (3)由于搜尋傳回資料量過大，檢索結果相關度評價成為研究的焦點。相關的研究又可以分為兩類：一類是對超文本鍊的分析，在這方面Stanford大學的Google系統和IBM的Clever系統作出了很大的貢獻；另一類是使用者資訊的回報，Direct Hit系統采用的就是這種方法。 (4)開始使用自動分類技術。Northern Light和Inktomi的Directory,Engine都在一定程度上使用了該技術。 2000年搜尋引擎2000年大會上，按照Google公司總裁Larry Page的演講，Google正在用3,000台運作Linux系統的個人電腦在搜集Web上的網頁，而且以每天30台的速度向這個微機叢集裡添加電腦，以保持與網絡的發展相同步。每台微機運作多個爬蟲程式搜集網頁的峰值速度是每秒100個網頁，平均速度是每秒48.5個網頁，一天可以搜集超過4,000,000網頁。 現在有許多網站推出号稱第四代的搜尋引擎，但是因為沒有明顯的标志，“第四代”的說法還僅僅是一個說法，并沒有成為一個明顯的趨勢。随着時間的推移，相信會有一個比較統一的标準形成。 2、幾個著名的搜尋引擎 (1)AltaVista AltaVista建立于1995年12月，其網絡域名是http:/www.altavista.conm。在不考慮網絡傳輸速度的情況下，AltaVista每秒可以檢索200Gb的資料量，作為一種搜尋的量化名額，這個速度遠遠快于你在硬碟上找一個檔案。[2] (2)Yahoo Yahoo最開始是比較常用的查詢工具，後來發展成綜合性的網站，涵蓋搜尋、新聞、郵件等。其域名是http://www.yahoo.com。Yahoo的真正實力來自Yahoo的分類層次，Yahoo的定位非常準确，他們的主要服務對象是查詢者而不是其它網站的網管。作為一個其它網站網址的收錄者，它正确地處理了查詢者、網絡管理者之間的互相關系。對于提供網絡目錄服務站點來說，資料庫中儲存的網址資訊越豐富、越準确，越能為查詢者提供高品質的服務，而高品質的服務是維持高通路率的關鍵。使用人工進行站點分類是一項極大的工程。一般站點隻有兩層到三層目錄來歸納與日俱增的上百萬個資訊點，而Yahoo通常都有十幾層，它所提供的詳細分類索引能幫助使用者迅速找到相關站點。[2] (3)Google Google建立于1998年，網絡域名是http://www.google.com。6年來，Google公司已經由一個純粹的搜尋引擎網站發展為一家非凡的門戶網站——擁有廣告網絡、對比購物服務、電子郵件和Web出版産品，是全球影響力最大的搜尋引擎之一。Google支援100多種語言，界面簡潔友好。它以其複雜而全自動的搜尋方法排除了任何人為因素對搜尋結果的影響。雖然Google也在搜尋結果旁刊登相關廣告，但沒人能花錢買到更高的網頁級别，進而保證了網頁排名的客觀公正。Google可以友善、誠實、客觀地在網上找到有價值的資料。Google目錄中收錄了10億多個網址，這在同類搜尋引擎中是首屈一指的。這些網站的内容涉獵廣泛，無所不有。 (4)CiteSeer CiteSeer引文搜尋引擎由NEC公司在美國普林斯頓的NEC研究所(NEC Research Institute，Inc)研制開發，網絡域名為http://citeseer.ist.psu.edu。1997年起利用自主的研究成果“自動引文标引系統”在網上建立樣品數字圖書館，并起名為“CiteSeer-Scientific literature digital library”，公開在網際網路上提供服務。 CiteSeer采用機器自動識别技術搜集網際網路上Postscript和PDF檔案格式的各種類型的學術論文，然後依照引文索引方法标引和連接配接每一篇文獻。至今CiteSeer标引的網頁數超過1000萬，存儲的文獻全文達60萬篇；内容主要涉及計算機科學領域，主題包括智能代理、人工智能、硬體、軟體工程、資料壓縮、人機互動、作業系統、資料庫、資訊檢索、網絡技術、機器學習等。 讀者通路CiteSeer既可像使用搜尋引擎那樣檢索浏覽相關學術文獻，也可利用其特有的引文檢索功能檢視文獻的引用與被引用資訊，同時還能獲得相關學科最新文獻與出版物引用排行。系統實作全天24小時實時更新，包括下載下傳PS或PDF格式的全文。 除以上所介紹的搜尋引擎外，還有如MSN、sohu、infoseek、northern、light、Lycos、Excite等著名的搜尋引擎，這裡就不一一介紹。 3、搜尋引擎的分類 (1)通用搜尋引擎 對所有網頁和檔案進行收錄整理并提供搜尋服務，又可以分為兩類，一類以Google為代表，幾乎完全是由程式自動控制整個流程，人為的幹預很少，效率比較高，比較公平，但缺點是由于程式的資訊處理能力的局限性，對于網頁内容的分類不夠準确，有可能給使用者提供實際并不需要的頁面連結；另一種以Yahoo為代表，依靠人工建立龐大細緻的分類體系，友善使用者找到自己最需要的頁面，這樣可以最大限度保證分類的準确性，但是網際網路上的資訊量正以前所未有的速度增長，人工分類的效率相比之下就過于低下了，不能滿足“查全”的要求。 (2)專業搜尋引擎 針對某一特定領域或特定檔案類型進行收錄整理并提供搜尋服務。例如CiteSeer，就是典型的專業搜尋引擎。其他的如北大天網FTP搜尋引擎，專門針對FTP目錄下的檔案進行搜尋；最近随着部落格（網絡日志）興起而興起的部落格搜尋引擎，由于部落格的分類機制比較穩定，而且部落格的世界裡常常關心的是最新的最有意思的一些新聞，是以未來很可能有大的發展；音樂搜尋引擎、電影搜尋引擎，針對特定的音頻、視訊檔案格式提供搜尋；等等。 (3)元搜尋引擎 元搜尋引擎是基于通用Web搜尋引擎GSE架構建立的一種搜尋機制。GSE架構結構主要由使用者、Web伺服器、Web資訊擷取與處理接口、任務排程器、連接配接管理器Web及搜尋引擎組成。使用者隻需遞交一次檢索請求，由元搜尋引擎負責轉換處理後送出給多個預先標明的獨立搜尋引擎，并将所有查詢結果集中起來以整體統一的格式呈現到使用者面前。通用Web搜尋引擎架構将網際網路上衆多的現有的Web搜尋引擎看成一個整體，為使用者提供一個透明的分布式異構Web搜尋引擎環境，該種方式的引擎可以看作元搜尋引擎，它為使用者提供一個統一的、內建的查詢請求，元搜尋引擎根據知識庫中的資訊轉換為各個Web搜尋引擎所能識别的格式，然後發給各個搜尋引擎，由這些搜尋引擎完成實際的資訊檢索。元檢索引擎在搜尋到各個Web搜尋引擎系統傳回的結果後，經過比較分析，然後以一定的格式傳回使用者。 4、搜尋引擎目前主要存在的問題[4] 現在的搜尋引擎可謂“百花齊放”，Google、Yahoo、百度、天網等搜尋引擎激烈競争，連之前很少涉及搜尋引擎領域的微軟也按捺不住，推出了MSN搜尋引擎。但是仍然有許多問題： (1)網絡資訊量太大，而且處于不斷的更新當中，難以進行全面的收錄，而且收錄得越多，全面的更新越困難。 (2)對于搜尋引擎使用者的真正需求，程式并不能準确判斷。同樣的關鍵詞，不同的人可能需要查找的内容不一樣。要在傳回查找結果的過程中，将所有結果按重要程度從高到低的順序組織起來呈現給使用者，排序算法是十分關鍵的。目前許多搜尋引擎都使用基于關鍵字查詢的傳統的資訊檢索算法和技術，傳回的頁面數量仍然是成千上萬。然而“據估計近85%的使用者隻浏覽搜尋引擎傳回的第一頁結果”是以，如何将使用者最感興趣、最重要的頁面放在搜尋結果的前面就成為影響搜尋品質的一個重要因素。 (3)現在越來越多的人為了能夠在搜尋引擎傳回的結果中排位靠前，特别針對搜尋引擎的算法進行一定的優化，如在網頁中大量添加熱門搜尋詞彙等，影響搜尋引擎的正确判斷，使得使用者得到許多毫無用處的結果。 (4)分詞技術不完善，對中文的檢索結果很多不能與使用者期望的很好比對。 5 、天網搜尋引擎系統結構及各部分功能 簡介 天網系統主要由WWW資訊存取和分析子系統(主要程式)、WWW資訊收集控制子系統(搜尋器)、資源索引資料庫、資訊檢索子系統、管理和監控子系統等幾個部分組成。各個部分的功能如圖所示： 圖1 WebGather系統總體結構示意圖 (1)WWW資訊存取和分析子系統（主要程式） 根據WWW資訊收集控制子系統提供的URL和相關資訊，使用HTTP協定，在Internet上擷取相關資源，并能就對方主機傳回的不同狀态碼作出相應處理。對取回的Web頁面(主要是HTML格式)進行分析，自動對中文編碼進行識别和轉化，對中文資訊進行分詞、提取頁面的标題、關鍵詞、摘要以及其中的超鍊（HyperLink）。将分析的結果通過擴充SOIF接口送出給資訊收集控制子系統。 (2)WWW 資訊收集控制子系統（搜尋器） 根據配置檔案運用自然語言了解和知識擷取技術、引導資訊收集系統優先通路特定知識領域和特定地域範圍内的資訊，向HTML存取分析程序發送需通路的URL及相關資訊，接收其發回的通路和分析結果。将相應的資料存入資訊資料庫中。并對資訊收集的頻度和流量加以控制。 (3) 資源索引資料庫 存儲收集到的WWW資訊，以及分析的結果。并對其重新進行基于詞的分級優化索引，以加快查詢速度． (4) 資訊檢索子系統 提供基于WWW方式的資訊檢索服務。使用者通過任何标準的WWW浏覽器直接通路。檢索系統可以支援在一次檢索中使用多個檢索詞(中、英文)，并支援檢索詞之間的邏輯關系（與、或）。還可以指定查詢的範圍和方式（精确、模糊）。檢索結果以HTML形式傳回給使用者。各項結果的标題與它所對應的URL用超鍊連接配接起來。使用者隻需在浏覽器中點中檢索結果項的标題，就能馬上取得相應頁面的實際内容。命中的URL頁面按它與使用者檢索關鍵詞的關聯程度排序，使使用者的檢索更有效率。系統還支援在上一次傳回的結果中進行查詢。 (5) 管理和監控子系統 提供系統配置，啟動、停止、監控、統計等管理功能。 資訊收集控制子系統與WWW存取分析程序之間的資訊互動是通過TCP Socket連接配接來實作的，是以各子系統可以分布運作于網絡中不同的主機上。 圖2 管理系統結構圖 6、幾種排序算法簡介 (1)HITS算法 它是由康奈爾大學(Cornell University)的Jon Kleinberg博士于1998年首先提出的，HITS的英文全稱為Hypertext-Induced Topic Search。目前，它為IBM公司阿爾馬登研究中心(IBM Almaden Research Center)的名為“CLEVER”的研究項目中的一部分。Kleinberg認為搜尋開始于使用者的檢索提問，每個頁面的重要性也依賴于使用者的檢索提問，他将使用者檢索提問分為三種:特指主題檢索提問(specific queries，也稱窄主題檢索提問)、泛指主題檢索提問(Broad-topic queries，也稱寬主題檢索提問)及相似網頁檢索提問(Similar-page queries)。而HITS算法則專注于改善泛指主題檢索的結果。Kleinberg将網頁(或網站)分為兩類，即hubs和authorities。應該注意的是，每個頁面也有兩個級别(ranking)，即hubs(中心級别)和authorities(權威級别)，authorities為具有較高價值的網頁，依賴于指向它的頁面，而hubs為指向較多authorities的網頁，依賴于它所指向的頁面。HITS算法的目标就是通過一定的計算(疊代計算)方法以得到針對某個檢索提問的最具價值的網頁，即排名最高的authority。 (2)PageRank算法 雖然Web頁面的重要性取決于人的興趣、知識、意見等主觀判斷，但仍有一些與頁面重要性相關的客觀準則可供利用。PageRank算法的基本思想是:如果一個頁面被許多其他頁面引用，則這個頁面很可能是重要頁面；一個頁面盡管沒有被多次引用，但被一個重要頁面引用，那麼這個頁面很可能也是重要頁面；一個頁面的重要性被均分并傳遞到它所引用的頁面。頁面的重要性用PageRank度量。最後搜尋引擎按照頁面的PageRank值對搜尋結果進行排序，将PageRank值高的重要頁面放在前面。 7、中文分詞、相似度判别 (1)中文分詞 衆所周知，英文是以詞為機關的，詞和詞之間是靠空格隔開，而中文是以字為機關，句子中所有的字連起來才能描述一個意思。例如，英文句子I am a student，用中文則為：“我是一個學生”。計算機可以很簡單通過空格知道student是一個單詞，但是不能很容易明白「學」、「生」兩個字合起來才表示一個詞。把中文的漢字序列切分成有意義的詞，就是中文分詞，有些人也稱為切詞。我是一個學生，分詞的結果是：我/是/一個/學生。中文分詞的準确與否，常常直接影響到對搜尋結果的相關度排序。 中文分詞技術屬于自然語言處理技術範疇，對于一句話，人可以通過自己的知識來明白哪些是詞，哪些不是詞，但如何讓計算機也能了解？其處理過程就是分詞算法。 現有的分詞算法可分為三大類：基于字元串比對的分詞方法、基于了解的分詞方法和基于統計的分詞方法。 基于字元串比對的分詞方法又叫做機械分詞方法，它是按照一定的政策将待分析的漢字串與一個「充分大的」機器詞典中的詞條進行配，若在詞典中找到某個字元串，則比對成功（識别出一個詞）。按照掃描方向的不同，串比對分詞方法可以分為正向比對和逆向比對；按照不同長度優先比對的情況，可以分為最大（最長）比對和最小（最短）比對；按照是否與詞性标注過程相結合，又可以分為單純分詞方法和分詞與标注相結合的一體化方法。常用的幾種機械分詞方法有正向最大比對法（由左到右的方向）、逆向最大比對法（由右到左的方向）、最少切分（使每一句中切出的詞數最小）。還可以将上述各種方法互相組合，例如，可以将正向最大比對方法和逆向最大比對方法結合起來構成雙向比對法。由于漢語單字成詞的特點，正向最小比對和逆向最小比對一般很少使用。一般說來，逆向比對的切分精度略高于正向比對，遇到的歧義現象也較少。統計結果表明，單純使用正向最大比對的錯誤率為1/169，單純使用逆向最大比對的錯誤率為1/245。但這種精度還遠遠不能滿足實際的需要。實際使用的分詞系統，都是把機械分詞作為一種初分手段，還需通過利用各種其它的語言資訊來進一步提高切分的準确率。 一種方法是改進掃描方式，稱為特征掃描或标志切分，優先在待分析字元串中識别和切分出一些帶有明顯特征的詞，以這些詞作為斷點，可将原字元串分為較小的串再來進機械分詞，進而減少比對的錯誤率。另一種方法是将分詞和詞類标注結合起來，利用豐富的詞類資訊對分詞決策提供幫助，并且在标注過程中又反過來對分詞結果進行檢驗、調整，進而極大地提高切分的準确率。 對于機械分詞方法，可以建立一個一般的模型。 基于了解的分詞方法通過讓計算機模拟人對句子的了解，達到識别詞的效果。其基本思想就是在分詞的同時進行句法、語義分析，利用句法資訊和語義資訊來處理歧義現象。它通常包括三個部分：分詞子系統、句法語義子系統、總控部分。在總控部分的協調下，分詞子系統可以獲得有關詞、句子等的句法和語義資訊來對分詞歧義進行判斷，即它模拟了人對句子的了解過程。這種分詞方法需要使用大量的語言知識和資訊。由于漢語語言知識的籠統、複雜性，難以将各種語言資訊組織成機器可直接讀取的形式，是以目前基于了解的分詞系統還處在試驗階段。 基于統計的分詞方法認為從形式上看，詞是穩定的字的組合，是以在上下文中，相鄰的字同時出現的次數越多，就越有可能構成一個詞。是以字與字相鄰共現的頻率或機率能夠較好的反映成詞的可信度。可以對語料中相鄰共現的各個字的組合的頻度進行統計，計算它們的互現資訊。定義兩個字的互現資訊，計算兩個漢字X、Y的相鄰共現機率。互現資訊展現了漢字之間結合關系的緊密程度。當緊密程度高于某一個門檻值時，便可認為此字組可能構成了一個詞。這種方法隻需對語料中的字組頻度進行統計，不需要切分詞典，因而又叫做無詞典分詞法或統計取詞方法。但這種方法也有一定的局限性，會經常抽出一些共現頻度高、但并不是詞的常用字組，例如「這一」、「之一」、「有的」、「我的」、「許多的」等，并且對常用詞的識别精度差，時空開銷大。實際應用的統計分詞系統都要使用一部基本的分詞詞典（常用詞詞典）進行串比對分詞，同時使用統計方法識别一些新的詞，即将串頻統計和串比對結合起來，既發揮比對分詞切分速度快、效率高的特點，又利用了無詞典分詞結合上下文識别生詞、自動消除歧義的優點。
到底哪種分詞算法的準确度更高，目前并無定論。對于任何一個成熟的分詞系統來說，不可能單獨依靠某一種算法來實作，都需要綜合不同的算法。筆者了解，海量科技的分詞算法就采用「複方分詞法」，所謂複方，相當于用中藥中的複方概念，即用不同的藥才綜合起來去醫治疾病，同樣，對于中文詞的識别，需要多種算法來處理不同的問題。 分詞中的難題。 有了成熟的分詞算法，是否就能容易的解決中文分詞的問題呢？事實遠非如此。中文是一種十分複雜的語言，讓計算機了解中文語言更是困難。在中文分詞過程中，有兩大難題一直沒有完全突破。 歧義識别。 歧義是指同樣的一句話，可能有兩種或者更多的切分方法。例如：表面的，因為「表面」和「面的」都是詞，那麼這個短語就可以分成「表面的」和「表面的」。這種稱為交叉歧義。像這種交叉歧義十分常見，前面舉的「和服」的例子，其實就是因為交叉歧義引起的錯誤。「化妝和服裝」可以分成「化妝和服裝」或者「化妝和服裝」。由于沒有人的知識去了解，計算機很難知道到底哪個方案正确。 交叉歧義相對組合歧義來說是還算比較容易處理，組合歧義就必需根據整個句子來判斷了。例如，在句子「這個門把手壞了」中，「把手」是個詞，但在句子「請把手拿開」中，「把手」就不是一個詞；在句子「将軍任命了一名中将」中，「中将」是個詞，但在句子「産量三年中将增長兩倍」中，「中将」就不再是詞。這些詞計算機又如何去識别? 如果交叉歧義群組合歧義計算機都能解決的話，在歧義中還有一個難題，是真歧義。真歧義意思是給出一句話，由人去判斷也不知道哪個應該是詞，哪個應該不是詞。例如：「乒乓球拍賣完了」，可以切分成「乒乓球拍賣完了」、也可切分成「乒乓球拍賣完了」，如果沒有上下文其他的句子，恐怕誰也不知道「拍賣」在這裡算不算一個詞。 新詞識别 新詞，專業術語稱為未登入詞。也就是那些在字典中都沒有收錄過，但又确實能稱為詞的那些詞。最典型的是人名，人可以很容易了解句子「王軍虎去廣州了」中，「王軍虎」是個詞，因為是一個人的名字，但要是讓計算機去識别就困難了。如果把「王軍虎」做為一個詞收錄到字典中去，全世界有那麼多名字，而且每時每刻都有新增的人名，收錄這些人名本身就是一項巨大的工程。即使這項工作可以完成，還是會存在問題，例如：在句子「王軍虎頭虎腦的」中，「王軍虎」還能不能算詞？ 新詞中除了人名以外，還有機構名、地名、産品名、商标名、簡稱、省略語等都是很難處理的問題，而且這些又正好是人們經常使用的詞，是以對于搜尋引擎來說，分詞系統中的新詞識别十分重要。目前新詞識别準确率已經成為評價一個分詞系統好壞的重要标志之一。 (2)相似度判斷 目前比較成功的搜尋引擎系統大多是基于關鍵詞比對來完成使用者的檢索請求的。典型的系統包括Stanford大學研制的Google系統以及北大的“天網”系統。通常這類系統在對已抓取回來的網頁進行分析時，要提取網頁中出現的關鍵詞和摘要資訊，并以關鍵詞作為網頁的特征項。 如果我們令 來表示網頁的集合， 表示特征項集，它由網頁集中的所有或部分特征項組成，網頁 用特征項空間中的向量 表示，其中： 表示特征項 在網頁 中的權值， 表示特征項 在網頁 中出現的頻率，稱為項頻， 則表示網頁集P中出現了特征項 的網頁數目的倒數，稱為反向網頁頻率。 在很多的文檔自動分類系統中，任意兩個網頁 和 的相似度通常用其對應向量 和 的夾角餘弦值來定義（如公式2所示），向量夾角越小（即夾角餘弦值越大）表明其相似度越高。 三、研究重點 1、題目要求 (1)組織搜尋引擎結果集展現形式，友善使用者快速的找到需要的資訊 (2)改進頁面排序算法，可以盡量使“重要”的頁面出現在傳回結果的前面 (3)根據經驗或一定的計算模型，事先确定出靜态的類别層次，然後通過網頁内容的語義分析确定其所屬類别 2、重點難點分析 重點難點如下： (1)改進對收集到的網頁剔除幹擾内容的算法，提高速度和識别準确率； (2)對PageRank算法計算過程的改進，減少備援計算，提高速度； (3)利用中文分詞算法，對網頁進行分詞，然後用相似度算法對網頁内容自動進行歸類。可改進對相似度的學習算法； (4)在PageRank算法中加入類别的權重，得到更符合需要的排序； (5)如果可能，進行個性化搜尋的試驗。 四、具體實作思路 1、所用技術及工具介紹 SQL Server2000對資料庫的各種應用特性都有很好的支援，并且極容易從C#.NET程式通路它的資料庫。C#是基于微軟下一代操作平台.NET，面向對象的全新的開發語言，集VC的靈活性和VB的易用性于一身，同時還具有與JAVA相同的跨平台特性。ASP技術的出現使伺服器端程式開發變得簡單易行，ASP.NET則進一步拉近了桌面應用開發和Web開發的距離。 利用C#.NET編寫蜘蛛、網頁處理和監控程式，将經過處理的網頁資訊存放在SQL Server資料庫中，再以ASP.NET開發使用者互動界面，實作經過優化的排頁面序整理，提供搜尋服務。 2、開發思路 蜘蛛程式、分詞算法和使用者界面可能參考或直接使用已有源代碼，因為這不是研究的重點；重點對頁面排序算法進行優化，加入語義分析和自動分類。自動分類考慮改進學習方法，提高分類精确度，進而提高傳回結果的品質。 五、小結 通過檢索和查閱文獻資料，收集和了解搜尋引擎的發展及現有系統機制中存在的問題，并提出解決這些問題的初步設想。接下來就是在下一步工作進行系統的詳細設計時，同時對構思中錯誤或不足之處進行修正和改進。 六、參考文獻 [1]Sepandar Kamvar, Taher Haveliwala, Gene Golub, Adaptive methods for the computation of PageRank, Linear Algebra and its Applications 386 (2004) 51–65. [2]彭緒富，鄒友寬，鄧榮華，INTERNET搜尋引擎探解，高等函授學報(自然科學版)， 2001年2月. [4]何曉陽，吳 強，吳治蓉，HITS算法與PageRank算法比較分析，情報雜志，2004年第2期. [48]關于搜尋引擎目前存在的主要問題及其發展趨勢的探讨，淩美秀，高校圖書館工作，2001年第5期 [54]羅昶，第四代搜尋引擎——主題搜尋引擎的設計與實作，http://www.cs.ucla.edu/~lc/paper/4th%20generation%20search%20engine.doc [65]中文搜尋引擎技術揭密：中文分詞，http://www.googleblue.com/html/Search-Engine/22.html. [76]解讀C#中的正規表達式 http://www.knowsky.com/4202.html [87]第七章 詞彙分析（一）—— 找出字元串中的“詞”，詹衛東
![241 Different Ways to Add Parentheses（C代碼版）[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)