摘 要 絡(luò)的迅猛增長使得搜索引擎面臨了前所未有的挑戰(zhàn)，搜索引擎如何適應(yīng)這種規(guī)模的急劇膨脹，成為一個備受關(guān)注的問題。面向主題搜索引擎可以有選擇性的抓取與主題相關(guān)的網(wǎng)頁。選取的對象是一個或一組事先預(yù)定義的主題，其特征由樣本網(wǎng)頁標(biāo)志，而不是關(guān)鍵詞。一般性的搜索引擎總是抓取盡量多的網(wǎng)頁以滿足所有可能的查詢請求；而主題搜索被設(shè)計為只抓取與選定主題相關(guān)的網(wǎng)頁。這不僅能夠大大減少系統(tǒng)對硬件和網(wǎng)絡(luò)資源的需求，而且還有助于提高抓取的準(zhǔn)確率和搜索結(jié)果的更新速度。 本文首先對比通用搜索引擎與主題搜索引擎的區(qū)別，總結(jié)主題 搜索引擎的優(yōu)點；然后介紹目前世界上主題搜索引擎技術(shù)的發(fā)展?fàn)顩r。接著，綜述了面向主題中文搜索引擎的設(shè)計，詳細(xì)介紹涉及該領(lǐng)域的三個核心技術(shù)：文檔分類技術(shù)、中文處理技術(shù)和網(wǎng)頁搜集預(yù)測技術(shù)。對于以上三種技術(shù)，我們在簡述已知算法的基礎(chǔ)上，都闡述了具體系統(tǒng)的實現(xiàn)方案。其中中文切詞問題作為工作的重點，在文章中有比較詳盡的介紹，包括中文處理的背景知識，中文切詞軟件的基本原理和中文切詞詞典的改進。 關(guān)鍵詞： 用搜索引擎、 面向主題搜索引擎、文檔分類算法、網(wǎng)頁搜集預(yù)測算法、中文切詞 目錄 摘要 1 目錄 2 第一章 引言 3 第二章 面向主題中文搜索引擎的設(shè)計綜述 5 第三章 文檔自動分類的主要算法和具體實現(xiàn) 7 檔分類的主要算法 8 持向量機（ 法 8 單 法 8 法 9 法 9 檔分類算法的實現(xiàn) 10 檔的向量表示 10 征集的選取 11 算待分類文檔與訓(xùn)練集的相似度 12 斷待分類文檔所屬類別 12 第四章 中文信息處理問題 14 文信息處理研究背景 14 文信息的特點 14 文切詞對系統(tǒng)的重要性 14 文切詞 軟件的基本原理 15 典的格式和數(shù)據(jù)結(jié)構(gòu)表示 15 體切詞過程 18 中文切詞軟件的修改 22 第五章 網(wǎng)頁搜集預(yù)測算法設(shè)計 23 文本鏈的相關(guān)研究 23 頁搜集預(yù)測功能的設(shè)計 24 第六章 工作總結(jié)和對未來的展望 26 致謝 參考文獻(xiàn) 第一章 引言 近年來， 規(guī)模持續(xù)以令人驚嘆的速度增長著。根據(jù) 2000 年 4 月在波士頓舉行的第 5 屆搜索引擎年會的會議報告 1，當(dāng)時全球的網(wǎng)頁數(shù)量已經(jīng)超過了十億。根據(jù) 索引擎的索引庫中網(wǎng)頁數(shù)量的統(tǒng)計，全球網(wǎng)頁數(shù)量到2002 年 5 月已經(jīng)達(dá)到 20 億。 中國的發(fā)展速度也十分驚人。根據(jù)國互聯(lián)網(wǎng)絡(luò)信息中心 )2在 2002年 1月的統(tǒng)計信息表明，中國的 77100 個，能上網(wǎng)計算機 約有 1254 萬臺，比 2001 年 1 月的統(tǒng)計結(jié)果多出 350 萬臺，上網(wǎng)人數(shù)達(dá)到 3370 萬，比 2001 年多了 1100 萬。 和網(wǎng)絡(luò)規(guī)模的迅速膨脹形成鮮明的對比，盡管各個大型的通用搜索引擎都維護著龐大的索引，但是索引的規(guī)模增長遠(yuǎn)遠(yuǎn)不及網(wǎng)絡(luò)本身。相對整個網(wǎng)絡(luò)，他們僅能夠覆蓋一小部分。以 索引擎為例，在 2001 年，他們的索引庫覆蓋了大約 個網(wǎng)頁。因此，一個搜索引擎的查全率，特別是抓回的相關(guān)網(wǎng)頁和所有相關(guān)網(wǎng)頁的比例相對較低。此外，很多返回的網(wǎng)頁都已經(jīng)過期或者地址已經(jīng)轉(zhuǎn) 移。查準(zhǔn)率較低也是通用搜索引擎的一個問題。這主要是因為用戶以關(guān)鍵字的形式提出查詢請求，搜索引擎系統(tǒng)再以關(guān)鍵字匹配返回結(jié)果。同一個關(guān)鍵字可能在多種不同的上下文環(huán)境中出現(xiàn)，其中大部分都與用戶希望的請求無關(guān)。這就造成了搜索引擎返回的結(jié)果中只有一小部分是真正相關(guān)的網(wǎng)頁。 這些通用搜索引擎的缺點主要來源于它們力圖覆蓋整個網(wǎng)絡(luò)，并為所有可能的主題提供查詢服務(wù)的目標(biāo)。面向主題的搜索引擎克服了以上的缺點，擁有更好的查全率和查準(zhǔn)率，因為它們將搜索網(wǎng)頁的內(nèi)容限定在一定的領(lǐng)域里，有效所建了搜集的范圍。一個面向主題的搜索引擎用一部 分事先選定好的網(wǎng)頁作為體現(xiàn)用戶興趣的樣本。為了獲得更多相關(guān)的網(wǎng)頁，主題搜索引擎從一個給定的集合出發(fā)，遞歸的抓取集合中網(wǎng)頁指向的所有出鏈接。經(jīng)驗表明一個超鏈往往連接的是兩個相關(guān)度較大的網(wǎng)頁。更準(zhǔn)確的講，兩個鏈接在一起的網(wǎng)頁比兩個隨機選擇的網(wǎng)頁更有可能是與同主題相關(guān)的。 主題搜索引擎的一個主要問題是以什么順序訪問網(wǎng)頁里的鏈接出口才能盡量多的訪問相關(guān)主題的網(wǎng)頁，而只抓取一小部分無關(guān)頁面。這是主題搜索引擎面臨的一個重要挑戰(zhàn)，因為有高度相關(guān)性的網(wǎng)頁上也會有低相關(guān)度的鏈接出口。 自 1994 年搜索引擎問世，面向主題的搜索 引擎就已經(jīng)被提上日程。 1999 年， 作了較完備的面向主題搜索引擎的模型。系統(tǒng)使用分類層次目錄，由用戶在感興趣的領(lǐng)域作出標(biāo)記，作為搜索引擎的主題。用戶可以在瀏覽的時候標(biāo)識感興趣的網(wǎng)頁，然后按照 種經(jīng)典分類方法將該網(wǎng)頁分入對應(yīng)類別中作為樣本。該搜索引擎主要由三部分組成：搜集器，分類 器和被作者稱之為“蒸餾器”（ 進程。分類器判斷一個超文本文檔與主題的相關(guān)度；“蒸餾器”（ 在超文本鏈接分析的基礎(chǔ)上，識別出具有很多高相關(guān)度出鏈的 目錄型網(wǎng)頁（ 搜集器則根據(jù)分類器和“蒸餾器”提供的控制信息對未訪問隊列進行動態(tài)配置。通過試驗，他們指出在有限的領(lǐng)域內(nèi)挖掘網(wǎng)上資源是可行的；如果某個網(wǎng)頁與主題具有高相關(guān)度，可以認(rèn)為它在網(wǎng)絡(luò)中的鄰居（即出鏈接）也是相關(guān)的。 另一種搜索引擎由 學(xué)的 開發(fā)。他們通過先搜集“更重要”的網(wǎng)頁使搜集過程更加有效。這種“重要”性主要體現(xiàn)在與查詢請求的相似程度，網(wǎng)頁的入度（即鏈向這一頁的網(wǎng)頁數(shù)），網(wǎng)頁的出度（即這一網(wǎng)頁的鏈接出口數(shù)），網(wǎng)頁評分（ 網(wǎng)頁的位置特點等方面。一個網(wǎng) 頁的網(wǎng)頁評分（ 指向它的網(wǎng)頁的 加權(quán)和。 研究比較了這幾種衡量方法的區(qū)別。他們發(fā)現(xiàn)使用網(wǎng)頁入度計數(shù)的搜集器的表現(xiàn)近似于深度優(yōu)先搜索，傾向于優(yōu)先訪問一個“簇”（ 的網(wǎng)頁，而且不同的初始網(wǎng)頁集合的選取會對最終的結(jié)果造成比較大的影響。而使用網(wǎng)頁評分（ 法的搜集器則似乎不受這方面的影響，并且較好的結(jié)合了深度優(yōu)先和廣度優(yōu)先兩種方法的優(yōu)越性。 2001 年的研究評估了幾種不同搜集策略的優(yōu)劣。他們的試驗為100 個主題分別建立了分類 器，以衡量搜集到的網(wǎng)頁的相關(guān)度。 出一個好的面向主題搜索引擎應(yīng)該將搜索的范圍盡量保持在向量空間中與主題鄰近的區(qū)域內(nèi)。他們總共評估了三種不同的搜集策略： 集器 : 優(yōu)先隊列中的優(yōu)先級是包含該出鏈的原網(wǎng)頁與主題的相關(guān)度 集器 : 以網(wǎng)頁評分（ 高低為順序搜索，每搜集25 個網(wǎng)頁重新計算一次評分 使用神經(jīng)網(wǎng)絡(luò)算法，考慮鏈接周圍的上下文 他們的試驗發(fā)現(xiàn) 現(xiàn)出性能最優(yōu)，緊接著是 后是且他們認(rèn)為 于主題搜索任務(wù)來說，過于通用化，不能體現(xiàn)主題性。 這些工作為我們的系統(tǒng)提供了良好的參考和依據(jù)。在此基礎(chǔ)上，筆者將在下一章綜述面向主題的中文搜索引擎的設(shè)計工作。 第二章 面向主題中文搜索引擎的設(shè)計綜述 實現(xiàn)具體系統(tǒng)的簡介 我們的系統(tǒng)名稱為“面向課程的素材收集子系統(tǒng)”，將被用于“遠(yuǎn)程教育”項目的一部分，其目的是尋找一種技術(shù)，通過該技術(shù)，可以在 搜索到與給定課程相關(guān)的各類教學(xué)素材，為教師備課提供參考資料。 面向課程的素材收集子系統(tǒng)的設(shè)計 本系統(tǒng)是基于天網(wǎng)搜索引擎 系統(tǒng)的。天網(wǎng)由于采用了可伸縮的分布式結(jié)構(gòu)、查詢 引數(shù)據(jù)庫和檢索數(shù)據(jù)庫分開等先進、有效的技術(shù)，使得系統(tǒng)占用資源少、信息收集速度快、用戶查詢響應(yīng)時間快、查準(zhǔn)率和查全率較高。 原天網(wǎng)系統(tǒng)的體系結(jié)構(gòu)如圖： 圖表 1 天網(wǎng)搜索引擎系統(tǒng)的體系結(jié)構(gòu) 其中， 收集分析子系統(tǒng)： 負(fù)責(zé)從網(wǎng)上收集主控子系統(tǒng)指定的網(wǎng)頁，分析網(wǎng)頁 的內(nèi)容。從中提取關(guān)鍵詞、摘要和超文本鏈，將分析的結(jié)果回送給主控子系統(tǒng)作進一步處理； 主控子系統(tǒng)：負(fù)責(zé)按照一定的規(guī)則選取待訪問的 交給收集分析子系統(tǒng)，然后處理收集分析子系統(tǒng)返回的結(jié)果信息，將它們存入網(wǎng)頁信息數(shù)據(jù)庫； 索引子系統(tǒng)：負(fù)責(zé)處理網(wǎng)頁信息數(shù)據(jù)庫中的信息，生成查詢索引庫； 詢頁面：是天網(wǎng)系統(tǒng)和用戶之間的接口，負(fù)責(zé)向查詢子系統(tǒng)遞交用戶的查詢請求； 查詢子系統(tǒng)：負(fù)責(zé)處理用戶的查詢請求，在查詢索引庫中查找相關(guān)信息，將查詢的結(jié)果返回給用戶。 為了實現(xiàn)在現(xiàn)有天網(wǎng)系統(tǒng)的基礎(chǔ)上實現(xiàn)文檔自動分類和網(wǎng)頁搜集預(yù)測，我們設(shè)計了兩個處理進程 分類器和反饋進程 ；由原網(wǎng)頁信息數(shù)據(jù)庫中導(dǎo)出 分類結(jié)果數(shù)據(jù)庫，分類結(jié)果數(shù)據(jù)庫中的信息提交給索引子系統(tǒng)；分類器負(fù)責(zé) 實現(xiàn)對收集 的網(wǎng)頁的自動分類；反饋進程根據(jù)分類結(jié)果數(shù)據(jù)庫中的信息計算未訪問網(wǎng)頁的預(yù)測權(quán)值，將其反饋給主控子系統(tǒng)；改造現(xiàn)有天網(wǎng)系統(tǒng)的收集分析子系統(tǒng)、主控子系統(tǒng)、索引子系統(tǒng)和查詢索引庫，使它們能處理和儲存自動分類系統(tǒng)返回的分類信息，在 詢頁面上增加分類目錄，改造查詢子系統(tǒng)，向用戶提供面向分類目錄的查詢功能。 經(jīng)過改造后的收集、控制子系統(tǒng)的運行流程圖如下： 圖表 2 收集、控制子系統(tǒng)運作流程圖 第三章 文檔自動分類的主要算法和具體實現(xiàn) 文檔分類是將文檔劃分入事先確定數(shù)目的類 別中，每個文檔可能被歸入某個或多個類別中，也可以不屬于任何類別。利用機器學(xué)習(xí)（ 術(shù)，文檔自動分類的目標(biāo)是實現(xiàn)通過學(xué)習(xí)例子自動對待分類文檔指派類別。 文檔自動分類技術(shù)類似于一種經(jīng)驗學(xué)習(xí)方法，基本思路是首先搜集一組與主題高度相關(guān)的網(wǎng)頁作為樣本，這些網(wǎng)頁的集合就稱之為“訓(xùn)練集”。每個訓(xùn)練集中的樣本都由專家人工的分配了類別標(biāo)簽，因此具有高度的準(zhǔn)確性。之后，根據(jù)待分類文檔與樣本之間的相似程度來給待分類文檔指派類別標(biāo)簽。 持向量機（ 法 法 5是 1995年由 題時引入的一種經(jīng)驗學(xué)習(xí)方法。這種方法定義在向量空間中，問題的核心在于尋找一個最佳解決方案，將線性可分割空間中的點用一個決策面劃分為兩部分。 用結(jié)構(gòu)風(fēng)險最小化（ 理構(gòu)造的 超平面。 將 且將其與其它方法進行性能對比。 他的試驗結(jié)果表明 單 法 簡單 B)算法 5是 機器學(xué)習(xí)（ 常用的一種算法。法 作了兩個假設(shè)：（ 1）對于屬于這個類的文檔，特征項之間（即文檔中詞與詞之間）是獨立無關(guān)的；（ 2）對于不屬于這個類的文檔，特征項之間也是獨立無關(guān)的。 這個假設(shè)使得 法比其它 法要有效的多（其它 法具有指數(shù)級的時間復(fù)雜性）。 這種方法的基本思想是給定一個類和一篇文檔，利用 概率公 式：P(A|B)=P(B|A)*P(A)/P(B)，根據(jù)這個類對于每個特征項的條件概率計算它對于這篇文檔的條件概率。給定一個類和一篇文檔，令 ， 其 中 示文檔中出現(xiàn)的第 i 個特征項， n 為文檔中出現(xiàn)的特征項的總數(shù)。根據(jù)全概率公式，我們可以得到如下式子： P( + | = P( + ) * P( + ) / P( ； P( - | = P( - ) * P( - ) / P( ； 其中 P( = P(a1 P( + )表示待分類的文檔所處的領(lǐng)域中的文檔屬于這個類的概率， P( - )表示不屬于這個類的概率。根據(jù)兩個假設(shè)，有P()=P()*P()*P(a n|+) ，P()=P()*P()*P(a n|-) 。如果 P( + | P( - | ， 則就判定這篇文檔不屬于這個類。 簡單 法利用兩條假設(shè)極大地降低了計算的復(fù)雜度，使得算法的實現(xiàn)成為可能，但是這兩條假設(shè)缺 乏嚴(yán)格的理論推導(dǎo)作為基礎(chǔ)，無法保證它的正確性，這也在一定程度上限制了算法的性能。 法 5的縮寫，是 由一組訓(xùn)練集和類別集合自動學(xué)習(xí)生成一個多元回歸模型。訓(xùn)練的數(shù)據(jù)用輸入 /輸出的一個向量對表示，其中輸入向量是一個傳統(tǒng)向量空間模型中的文檔向量（用特征項及其權(quán)值表示），而輸出向量是該文檔對應(yīng)的類別。通過解決一個的線性最小平方法（ 題，獲得一個特征項類別的回歸系數(shù)組成的矩陣： 2m r g 矩陣 A 和 B 分別代表了訓(xùn)練數(shù)據(jù)的輸入和輸出，其中 示一個特征項 文檔 的權(quán)重， 值為 1 或 0， 1 表示文檔 于類別 0 則不然。矩陣 描述了特征項和類別之間的關(guān)系。最后，對類別的權(quán)重進行排序，形成輸入文檔的候選類列表。通過給這些類別的權(quán)重設(shè)置閾值，就得到了輸入文檔的指派類別。 NN(法 5法的縮寫，是模式識別中一種被廣 為學(xué)習(xí)和研究的統(tǒng)計學(xué)方法。 早就被用在文檔分類中，并且是幾種經(jīng)驗學(xué)習(xí)方法中性能突出的一種。這 種算法非常簡單直觀：給定一個文檔，系統(tǒng)在訓(xùn)練集中找到與其最相近的 k 個樣本，然后利用這些樣本的類別屬性來決定待分類文檔的類別。將待分類文檔和每個鄰近的文檔之間的相似度作為鄰近文檔的類別的權(quán)重。如果 k 個最近的樣本中有幾個都屬于同一類別，則將他們的相似度疊加；權(quán)重相加后的結(jié)果作為該類別對應(yīng)于待分類文檔的可能性。通過對候選類別的權(quán)重進行排序，就獲得待分類文檔的候選類列表。同 法一樣，通過設(shè)置權(quán)重的閾值，可以得到待分類文檔的最終指派類別。 法則是找 K 個最近的鄰居。因此它的分類響應(yīng)時間要長于 法，計算復(fù)雜度和訓(xùn)練集中的文檔數(shù)目成正比。不過， 法簡單有效，所以在大型應(yīng)用中獲得廣泛應(yīng)用。 檔分類算法的實現(xiàn) 本系統(tǒng)選用的文檔分類算法是 K近鄰算法。原因在于 K近鄰算法是目前分類性能最好的算法之一，實現(xiàn)非常簡單有效，不會過度影響網(wǎng)頁的收集速度。該算法涉及到如下幾個方面： 文檔的表示 特征詞的選取 計算待分類文檔與訓(xùn)練集的相似度 決定（判定）待分類文檔所屬類別 檔的向量表示 待分類的文檔和訓(xùn)練集中的文檔在分 類和訓(xùn)練時用何種形式表示是一個很實際的問題。 1969 年， 出了向量空間模型 是文檔表示的一個統(tǒng)計模型，該模型以特征項（ 為文檔表示的基本單位。 令 D 1d ， 2d ， ，示一組已分類完畢的文檔集， C 1c ， 2c ， ，類別的集合。存在一個判斷矩陣（ d 11 1 1 表示文檔為 0 表示該文檔不屬于 文檔初始集 D 被分為兩個不相交的子集，即 ： 訓(xùn)練集 1d ， ，這是一個樣本網(wǎng)頁的集合，分類器用這個集合來分析出每個類別的特征。 測試集1 ，這一集合用于檢驗分類器的有效性。測試集中的每個文檔都要送給分類器作測試，分類器根據(jù)由訓(xùn)練集分析出的每個類別的特征給測試文檔指派一個類別。分類器的效果好壞由有多少的測試文檔的類 別與前面描述的判斷矩陣中對應(yīng)的該文檔的類別一致來衡量。 征集的選取 信息挖掘研究中提出詞不僅能夠很好的描繪文檔的特征，而且它在文檔中出現(xiàn)的順序?qū)Χ鄶?shù)工作的影響很小。這就為文檔分類提供了良好的基礎(chǔ)。每個不同的詞對應(yīng)文檔的一個特征項，而該詞在文中出現(xiàn)的次數(shù)設(shè)為它的權(quán)值。為了避免不必要大的特征空間，只有出現(xiàn)過較多次數(shù)和非“停詞”（例如“和”、“或”）才會被選擇為特征項。即便是這樣，特征空間的維數(shù)仍然很容易超出 1 萬。為了解決這個問題，數(shù)據(jù)挖掘技術(shù)中提出了很多方法減少特征向量的維數(shù)： 文檔頻率法（ 信息增容法（ 相互信息法（ 2 統(tǒng)計法 （ 相對信息法（ 鑒于本項目具有以下特點：給定一門課程，其內(nèi)涵和外延一定是明確的（否則就很難稱其為一門課程），因此在講授該門課程的老師的幫助下，我們很容易在較短（一兩天）時間內(nèi)獲得該課程的特征詞。我們最終采用手工預(yù)先提取特征詞的方法。 算待分類文檔與訓(xùn)練集的相似度 通常人們選擇一種距離作為度量兩個文檔相似程度的標(biāo)準(zhǔn)。由于文檔是通過特征詞權(quán)重的一維向量來描述的，設(shè) X， Y 是兩個具有相同特 征詞的特征向量且X=（ .,21,）， Y=（ .,21 ,）。用 d(X,Y)表示文檔特征向量 X 與 Y 之間的距離。我們選用歐氏距離函數(shù)作為度量標(biāo)準(zhǔn)，則 X， Y 間的相似度為： d ( X, 21yx 斷待分類文檔所屬類別 設(shè)對應(yīng)每個類m 個樣本，則類和訓(xùn)練集中樣本的對應(yīng)情況如下： 1c 11s 12s ，令為 D 與樣本相似度。事先給定一個閾值 ，令)(m dI co 文檔 D 類 具體系統(tǒng)選擇中學(xué)數(shù)學(xué)作為課程實例， 我們首先將中學(xué)數(shù)學(xué)分為如圖表 3所示的九個類別。系統(tǒng)的分類目錄，訓(xùn)練集，特征項空間等均用數(shù)據(jù)庫中的表來描述： 表 錄課程號，課程名稱，課程中子類數(shù)和子類中的樣本數(shù) 表 ：記錄課程號，子類號，子類名稱 表 錄特征詞和特征詞 對照表 表 錄訓(xùn)練集中每個樣本的特征詞權(quán)重 表 錄網(wǎng)頁信息數(shù)據(jù)庫 的網(wǎng)頁與分類 的對應(yīng)關(guān)系，分別用 號、課程號和子類號表示 表 錄每個課程子類的所有特征項 圖表 3 分類目錄 分類目錄在數(shù)據(jù)庫中用表 描述各類的內(nèi)部結(jié)構(gòu)。具體而言，“中學(xué)數(shù)學(xué)”對應(yīng)課程名稱，課程號為 1，其中的子類有 9個，每個子類中有 20 個樣本，即分類集合 C 1c ， 2c ， ， m=9，訓(xùn)練集 1d ， ， g 180，對每個 i )1( ,20)*1( 到等于 1，其余的。 第四章 中文信息處理問題 文信息處理研究背景 在面向主題的搜索引擎的具體實現(xiàn)中，首先明確搜集和檢索的對象是中文網(wǎng)頁，因此中文信息的處理成為系統(tǒng)的一個關(guān)鍵因素。無論是在超文本文檔自動分類的過程中，還是提供檢索功能的索引數(shù)據(jù)庫，都要求首先對中文文檔做一定的預(yù)處 理，才能繼續(xù)到下一步的工作。 文信息的特點 中文信息和英文信息有一個明顯的差別：英語單詞之間用空格分隔；而在中文文本中，詞與詞之間沒有天然的分隔符，中文詞匯大多是由兩個或兩個以上的漢字組成的，并且語句是連續(xù)書寫的。這就要求在對中文文本進行自動分析前，先將整句切割成小的詞匯單元，即漢語切詞問題。用具體例子來說明，就是如何把“我的筆記本”這樣連續(xù)書寫的語句正確切分為“我”、“的”、“筆記本”的詞匯單元。 文切詞對系統(tǒng)的重要性 在檢索和文檔分類系統(tǒng)中，自動切詞系統(tǒng)的速度直接影響整個 系統(tǒng)的效率。在第五次信息檢索會議（ 增加了對中文分類系統(tǒng)的評測，而參加 中文信息的檢索主要有兩種：基于字的檢索和基于詞的檢索?；趩巫值臋z索系統(tǒng)對所有文章建立全文索引。在檢索時得到每個單字的索引，而后加以適當(dāng)?shù)倪壿嬤\算，得到檢索結(jié)果。而基于詞匯的檢索系統(tǒng)對詞匯建立索引，檢索詞匯時一次命中。本系統(tǒng)采用基于詞的索引，具有較快的速度和較高的準(zhǔn)確性，在查全率和查準(zhǔn)率之間作出一定的權(quán)衡，同時能夠減少索引信息對磁盤空間的占用。但是，這種檢索方式要求 切詞的準(zhǔn)確率較高。 對于文檔分類系統(tǒng)，構(gòu)成向量空間的特征項主要是詞，所以分詞的準(zhǔn)確率和速度與分類系統(tǒng)的準(zhǔn)確率和速度密切相關(guān)。尤其是本系統(tǒng)中，文檔的特征項多是數(shù)學(xué)專用詞匯，因此中文切詞軟件要能夠準(zhǔn)確的切出所有在特征項集中出現(xiàn)的詞匯。 文切詞軟件的基本原理 本系統(tǒng)采用北京大學(xué)計算語言所與北京大學(xué)中文系在語言信息處理領(lǐng)域內(nèi)的合作研究成果 “漢語詞語切分與詞性標(biāo)注軟件”解決中文切詞的問題。天網(wǎng)搜索引擎系統(tǒng)長期以來一直使用該軟件，在分詞準(zhǔn)確性和速度方面都取得了比較滿意的效果。 此 切詞軟件 將最穩(wěn)定、最常用的 4 萬 6 千余條現(xiàn)代漢語基本詞匯及其有關(guān)屬性組織 作 為基本詞典 。 這些詞的基本地位都是由漢語語言學(xué)家逐一檢驗認(rèn)可的， 保證了該 系統(tǒng) 的 通用性；在此詞典的基礎(chǔ)上充分利用漢語構(gòu)詞法的研究成果，可以識別出大部分的常用詞。 典的格式和數(shù)據(jù)結(jié)構(gòu)表示 切詞軟件的字典的文件表示： 1 基礎(chǔ)字典： 基礎(chǔ)字典索引文件： 用戶字典： 字列表： 標(biāo)記列表： 重疊詞文件： 有能形成 疊型的單字詞 詞表 有能形成 疊型的雙字詞詞表 有能形成 B重疊型的雙字詞詞表 有能形成 疊型的雙字詞詞表。 7 前綴詞： 綴信息表 8 后綴詞： 綴信息表 9 特殊詞： 和一些特殊后綴組合的詞語表，其中收集的特殊后綴主要包括：“家”、“師”、“生”、“長”等。 基礎(chǔ)字典、基礎(chǔ)字典索引文件、字列表、標(biāo)記列表的關(guān)系： 各個文件的格式： 基礎(chǔ)字典： 詞匯 標(biāo)記 索引文件：如圖 4 所示 字列表： 字 標(biāo)記列表： 標(biāo)記 圖表 4 基礎(chǔ)詞典、索引文件 、標(biāo)記列表和字列表關(guān)系圖 注：灰色字體表示行號，在文件中不存在 圖表 4 以基礎(chǔ)字典中“斑”字打頭的所有詞為例，說明前文所提四者之間的對應(yīng)關(guān)系。稱一個字和以它打頭的所有詞為一個“結(jié)構(gòu)單元”。結(jié)構(gòu)單元中的數(shù)據(jù)的意義依次為： 93 代表“斑”字在字列表（字典）中的位置。 1、 6、 1、 1 分別表示詞典中“斑”字打頭的由 1、 2、 3、 4 個字組成的詞的數(shù)量。 5 是“斑”字的標(biāo)記號，查看標(biāo)記列表可知是名詞。 黑色字體的 數(shù)據(jù)是兩個字組成的詞的列表，依次是“斑點”、“斑痕”、“斑馬”、“斑禿”、“斑紋”、“斑鳩”，其中“點”對應(yīng)字列表中位置 532，“斑點”對應(yīng)標(biāo)記 5，已知是名詞。其它的依此類推。 藍(lán)色字體的數(shù)據(jù)是三個字組成的詞的列表，其表示方法同兩個字。 綠色字體的是四個字組成的詞的列表，其表示方法同兩個字。 基礎(chǔ)字典的數(shù)據(jù)結(jié)構(gòu) 首字列表： /存放兩個字組成的詞的結(jié)構(gòu)，包括第二個字在字列表中的位置，/和詞的標(biāo)記 ; ; /存放首字在字列表中的位置 /指向兩個字的詞的列表 /指向三個字的詞的列表 /指向四個字的詞的列表 /結(jié)構(gòu)單元的列表 /列表中數(shù)據(jù)項的總數(shù) ; /存放以首字打頭的 2、 3、 4 個字組成的詞的個數(shù) 標(biāo)記列表 * /標(biāo)記列表 /標(biāo)記列表中的標(biāo)記總數(shù) 字列表 * /字列表（字典） /字列表中的漢字總數(shù) 切詞軟件初始化基礎(chǔ) 詞典時，調(diào)入內(nèi)存的有 別是基礎(chǔ)字典索引文件、字列表和標(biāo)記列表，而 不真正調(diào)入內(nèi)存中。在查找時，三個文件在內(nèi)存中的信息進行對照，獲得每個結(jié)構(gòu) 單元的實際信息。 用戶字典的數(shù)據(jù)結(jié)構(gòu) /存放用戶字典中詞匯和標(biāo)記的結(jié)構(gòu) ; ; * /用戶字典 *=0;*/ /用戶字典中詞的總數(shù) /存放用戶字典中首字信息的結(jié)構(gòu) ; /首字 /以首字打頭的詞第一次出現(xiàn)的位置 /以首字打頭的詞的總數(shù) /以首字打頭的詞的最大長度 /* * /用戶字典首字列表 /用戶字典中首字的總數(shù) 注意：用戶字典的格式同基礎(chǔ)詞典相同，但是數(shù)據(jù)結(jié)構(gòu)表示卻有較大的不同。 體切詞過程 本 系統(tǒng)的處理過程包括自動切分和初始詞性標(biāo)記、切分歧義字段識別、組詞和標(biāo)注預(yù)處理、詞性標(biāo)記排歧、切分和詞性標(biāo)注后處理等過程 。 下圖為切詞過程 程序流程圖： 圖表 5 切詞過程 先初始化變量，在 程進行真正的切詞工作，是最重要的函數(shù)。它主要是通過查字典得到詞匯的標(biāo)記，根據(jù)標(biāo)記的智能組合，切分出結(jié)果。切詞結(jié)果記錄在 組中，分別是詞匯和標(biāo)記。切分后要進行一系列的處理工作。 程主要處理前綴詞，后綴詞和疊詞。如果 的某個標(biāo)記含有歧義（例如：愛好 是名詞 又是動詞），要對 詞性標(biāo)記排歧 。 并所有連續(xù) 的 詞性語素）和 容詞性語素）。在新版本中， 加了合并一些特殊詞匯的功能。例如：“一九九八年”在字典中不會出現(xiàn)，但是本函數(shù)會將起合并。最后，從 獲取切詞結(jié)果信息，存入 。調(diào)用 過程讀取 為切詞結(jié)果。 圖表 6 進行真正的切詞工作，循環(huán)調(diào)用 到整句 切分完畢。 查找用戶和基礎(chǔ)字典，獲得詞匯的標(biāo)記，有可能獲得多種切分可能性 果查找詞匯在字典中只出現(xiàn)過一次則直接切分原句。具體切分的函數(shù)是 其中移動 針，指示 下次切分的起始點。如果查找詞匯有多種切分可能性（ ），則調(diào)用數(shù)在 確定實際切分位置，并調(diào)用 圖表 7 過查找字典確定切分的諸多可能性，但是并不真正進行切分工作。它主要由兩步組成，一是查找用戶字典，二是查找基礎(chǔ)字典。找用戶字典是否有待查找詞匯的第一個字。如果有，就返回以該字打頭的詞的最長串的長度；否則返回 0。以 指的字為起始點，按照 1， 2， 3 到 回的最長串長度的順序，依次查找對應(yīng)長度的詞在用戶字典中是否出現(xiàn)。如果出現(xiàn)則在 且使切分可能性 1。查找基礎(chǔ)詞典是同一個過程。 以上是對計算語言所“漢語詞語切分與詞性標(biāo)注軟件”切詞過程的一個粗略描述。其中，只涉及數(shù)據(jù)結(jié)構(gòu)，程序流程等內(nèi)容，不涉及歧義性的排除。 中文切詞軟件的修改 有兩種方法可以加入新詞。一種是修改天網(wǎng)和切詞軟件的接口，允許用戶字典的加入。將所有的特征詞加入用戶字典，由系統(tǒng)在初始化的時候?qū)⑵漭d入內(nèi)存。這樣，切詞軟件首先在用戶字典中查找詞，然后再查基礎(chǔ)字典。另一種則直接修改基礎(chǔ)字典。系統(tǒng)初始化時將用戶字典的索引文件載入內(nèi)存。修改基礎(chǔ)字典，就要重新生成了一個索 引文件作為新詞典，其中加入所有特征詞，然后對原程序作出少量修改，使其能夠順利讀取新詞典。 我們選擇了第二種方法，主要是考慮到將來擴充系統(tǒng)后，用戶字典的增長可能會導(dǎo)致切詞速度下降。另外，鑒于本系統(tǒng)的特殊性，很多詞匯幾乎不會在與中學(xué)數(shù)學(xué)相關(guān)的網(wǎng)頁或者用戶的查詢請求中出現(xiàn)，可以去掉。這樣，我們可以靈活方便地對字典文件進行增加、刪除和修改。 第五章 網(wǎng)絡(luò)搜集預(yù)測算法設(shè)計 文本鏈的相關(guān)研究 在搜集階段，如何決定下一個要訪問的網(wǎng)頁是衡量主題搜索引擎性能的關(guān)鍵步驟。 網(wǎng)頁與普通文檔有一個標(biāo)志性差別超 文本鏈，通過分析超文本鏈上的信息，可以獲得整個網(wǎng)絡(luò)的一個資源分布圖。將每個網(wǎng)頁都視為節(jié)點，其上的超鏈都看成一條由該節(jié)點到指向目標(biāo)節(jié)點的有向邊，就能獲得整個 用它能大大提高搜集的目的性。 下面介紹兩種典型地通過分析超文本鏈接信息對候選網(wǎng)頁進行排序的方法： 法 法 7最早在網(wǎng)絡(luò)搜索中對超文本鏈結(jié)構(gòu)進行了分析利用，由此構(gòu)成的 索引擎在商業(yè)上取得了巨大的成功。其具體算法是：給定一個 i，用 PR(i)來表示它的權(quán)值。 PR(i)用以下方程遞歸定義： PR(i) = dD(i) + (1 d) PR(j)/N(j, 其中， D 是所有網(wǎng)頁上的一個概率分布； PR(j)/N(i 頁的網(wǎng)頁 j 上求和， N(j)是從 j 頁上指出的鏈接總數(shù)； d 是 0 和 1 之間的一個常數(shù)。 法 區(qū)別于 網(wǎng)頁價值的問題上 提出了更精確的主張。他認(rèn)為網(wǎng)頁的價值應(yīng)該依賴于搜索的具體查詢請求，每個網(wǎng)頁都應(yīng)該有獨立的“ （ 基于指向該網(wǎng)頁的鏈接）和“ （基于由該網(wǎng)頁指出的鏈接）。 集合”，集合中包括和給定查詢請求相關(guān)的一小部分網(wǎng)頁。接著，用指向該集合中元素的網(wǎng)頁和集合中元素所指向的網(wǎng)頁擴充集合，成為一個“基本集合”。如果 ，其中 1表示從頁 則 0。 a = (. . . , 示所有 h = (. . . , 表示 所有 始時， a和 u= (1, 1, . . . , 1)。 反復(fù)執(zhí)行操作 I (“ ) 和 O (“ )。操作 I將 a = AT h， 操作 O將 h = A a。 每執(zhí)行一次都要進行一步標(biāo)準(zhǔn)化，使向量 a和 證了在足夠多的重復(fù)操作后，向量 a和 別收斂到矩陣 主特征向量 。上文提到的標(biāo)準(zhǔn)化步驟有很多種不同方法。無論采用哪種，像 ai/特征向量 ，即該特征向量對應(yīng)過渡矩陣的最大特征值。 頁搜集預(yù)測功能的設(shè)計 原來的天網(wǎng)搜集系統(tǒng)具有一定的網(wǎng)頁預(yù)測能力，它主要通過配置導(dǎo)向詞來引導(dǎo)系統(tǒng)優(yōu)先訪問從與導(dǎo)向詞相關(guān)度較大的網(wǎng)頁鏈接出的 導(dǎo)向詞就是一組關(guān)鍵詞，它們會引導(dǎo)搜索器按照一定順序 搜索整個網(wǎng)絡(luò)，使得搜索引擎可以在最短的時間里面得到最全面的與某一個主題相關(guān)的信息。通過設(shè)置導(dǎo)向詞以及它們對應(yīng)的不同權(quán)值，所有標(biāo)題、作者、正文或超連接文本中含有某一導(dǎo)向詞的網(wǎng)頁都會被賦予較高的權(quán)值，在搜索的時候會優(yōu)先考慮。搜索器在向主控程序獲得時候也是按照權(quán)值由高到低的順序。反之，搜索器在向主控程序提交新的 它的權(quán)值的時候，主控程序會按照權(quán)值預(yù)先排序，以便下一次有序的發(fā)給搜索器。 權(quán)值的設(shè)置有兩種方法，第一種是根據(jù)管理員的經(jīng)驗手工設(shè)置，第二種是給定一個跟主題有關(guān)的網(wǎng)頁集合，由程序自動提取這些網(wǎng) 頁里面共同的特征，在這些網(wǎng)頁里面都出現(xiàn)的很多的關(guān)鍵詞，它就被選作導(dǎo)向詞，即“特征提取”。原系統(tǒng)綜合兩種方法的優(yōu)缺點，采用了兩種方法的結(jié)合策略： 1 手工設(shè)置好一組導(dǎo)向詞和它們對應(yīng)的權(quán)值； 2 用這組導(dǎo)向詞到原搜索引擎中查找出對應(yīng)的網(wǎng)頁； 3 按照權(quán)值的比例選取一