【畢業(yè)學(xué)位論文】(Word原稿)中英文發(fā)現(xiàn)系統(tǒng)的轉(zhuǎn)接層子系統(tǒng)、索引子系統(tǒng)的設(shè)計與實現(xiàn)-計算機(jī)系網(wǎng)絡(luò)與分布式系統(tǒng)_第1頁
【畢業(yè)學(xué)位論文】(Word原稿)中英文發(fā)現(xiàn)系統(tǒng)的轉(zhuǎn)接層子系統(tǒng)、索引子系統(tǒng)的設(shè)計與實現(xiàn)-計算機(jī)系網(wǎng)絡(luò)與分布式系統(tǒng)_第2頁
【畢業(yè)學(xué)位論文】(Word原稿)中英文發(fā)現(xiàn)系統(tǒng)的轉(zhuǎn)接層子系統(tǒng)、索引子系統(tǒng)的設(shè)計與實現(xiàn)-計算機(jī)系網(wǎng)絡(luò)與分布式系統(tǒng)_第3頁
【畢業(yè)學(xué)位論文】(Word原稿)中英文發(fā)現(xiàn)系統(tǒng)的轉(zhuǎn)接層子系統(tǒng)、索引子系統(tǒng)的設(shè)計與實現(xiàn)-計算機(jī)系網(wǎng)絡(luò)與分布式系統(tǒng)_第4頁
【畢業(yè)學(xué)位論文】(Word原稿)中英文發(fā)現(xiàn)系統(tǒng)的轉(zhuǎn)接層子系統(tǒng)、索引子系統(tǒng)的設(shè)計與實現(xiàn)-計算機(jī)系網(wǎng)絡(luò)與分布式系統(tǒng)_第5頁
已閱讀5頁,還剩28頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)

文檔簡介

北京大學(xué)學(xué)士學(xué)位論文 中英文發(fā)現(xiàn)系統(tǒng)的轉(zhuǎn)接層子系統(tǒng)、索引子系統(tǒng)的設(shè)計與實現(xiàn) 第 1 頁 論文 摘要 中國于 1994 年進(jìn)入 后 中國得到了迅速的發(fā)展,中文的 息也迅速增加。這使得在搜索中文信息時也需要一定的搜索工具。由于世界上現(xiàn)有的搜索引擎大部分都是針對英文設(shè)計的,它們或支持中文的能力很差,或根本不支持中文。個別支持中文搜索的搜索引擎,它們的數(shù)據(jù)庫中所包含的中文信息的數(shù)量十分小,搜索的結(jié)果非常不理想。對于日益增長的中國 說,實現(xiàn)一個具有大量中文信息數(shù)據(jù)庫,能夠良好支持中文檢索的搜索引擎已是一種迫切的需求。 本論文所描述的系統(tǒng)即是作 者參與設(shè)計和實現(xiàn)的一個支持中文的搜索引擎。它即支持對中文,英文的簡單檢索,又支持邏輯運算,模糊匹配等高級檢索。它通過對中文的分詞,實現(xiàn)了對在中文詞匯一級檢索的支持;通過對中文,英文的編碼,實現(xiàn)了對中文,英文系統(tǒng)核心實現(xiàn)的一致化;通過兩級索引機(jī)制和索引項的特殊設(shè)計,實現(xiàn)了檢索的快速命中。 論文首先介紹了系統(tǒng)設(shè)計和實現(xiàn)的一些背景資料,介紹了 發(fā)展于現(xiàn)狀,世界主要搜索引擎及其比較,中文的特點與搜索引擎對中文的支持。之后,描述了系統(tǒng)的整體設(shè)計,詳細(xì)介紹了轉(zhuǎn)接層子系統(tǒng)和索引數(shù)據(jù)庫子系統(tǒng)的設(shè)計。 關(guān)鍵詞 : 搜索引擎 中文分詞 索引數(shù)據(jù)庫 編碼方案 北京大學(xué)學(xué)士學(xué)位論文 中英文發(fā)現(xiàn)系統(tǒng)的轉(zhuǎn)接層子系統(tǒng)、索引子系統(tǒng)的設(shè)計與實現(xiàn) 第 2 頁 目錄 第一章 背景介紹 . 發(fā)展與現(xiàn)狀 . 界主要得搜索引擎及其比較 . 文的特點和搜索引擎對中文的支持 .二章 系統(tǒng)概述 . 統(tǒng)設(shè)計目標(biāo) . 統(tǒng)總體結(jié)構(gòu) .三章 轉(zhuǎn)結(jié)層子系統(tǒng)的設(shè)計 . 結(jié)層子系統(tǒng)的設(shè)計思想 . 文編碼互換 . 英文編碼方案 . 文分詞 . 英文詞匯的自動學(xué)習(xí) .四章 索引數(shù)據(jù)庫子系統(tǒng)的設(shè)計 . 引數(shù)據(jù)庫系統(tǒng)的設(shè)計思想 . 引數(shù)據(jù)庫的設(shè)計 . 引數(shù)據(jù)庫的更新和維護(hù) . 引數(shù)據(jù)庫的檢索 .五章 總結(jié)展望 . 統(tǒng)測試和評估 . 景展望 .謝 .考文獻(xiàn) .京大學(xué)學(xué)士學(xué)位論文 中英文發(fā)現(xiàn)系統(tǒng)的轉(zhuǎn)接層子系統(tǒng)、索引子系統(tǒng)的設(shè)計與實現(xiàn) 第 3 頁 第一章 背景介紹 發(fā)展與現(xiàn)狀 前身是美國國防部高級研究計劃管理局( 1969 年建立的 ,初期只有 4 臺,其設(shè)計目標(biāo)是:當(dāng)網(wǎng)絡(luò)中的一部分因為戰(zhàn)爭等特殊原因而遭到破壞時,其他部分仍能正常運行。 80 年代初期, 美國國防部通訊局研制成功了用于異構(gòu)網(wǎng)絡(luò)的 后美國加州大學(xué)伯克萊分校把該協(xié)議作為其 一部分,使得該協(xié)議得以流行。 1986 年,美國國家科學(xué)基金( 5 個科研教育服務(wù)的超級計算機(jī)中心為基礎(chǔ)建立 絡(luò),以便在全國實現(xiàn)資源共享。 90 年代初到到現(xiàn)在,是 長最迅速的時期,每天都有許多的主機(jī)加入到 ,以下是這一時期 接主機(jī)數(shù)的統(tǒng)計資料: 圖 90 年代 接主機(jī)數(shù)目統(tǒng)計表 (自 隨著 迅速發(fā)展, 使用性質(zhì)已從建網(wǎng)初期的 科研教育為主,變?yōu)楝F(xiàn)在的商業(yè)化,普及化的一種信息資源交流工具。 北京大學(xué)學(xué)士學(xué)位論文 中英文發(fā)現(xiàn)系統(tǒng)的轉(zhuǎn)接層子系統(tǒng)、索引子系統(tǒng)的設(shè)計與實現(xiàn) 第 4 頁 源于歐洲核子研究中心( 它最初的目的是用于研究中心內(nèi)部文檔的連接。在 1990 年 9月,第一個基于文本的原形開始運作并在 1991 年國際超文本會議上作了公眾演示。在 1993 年一月,第一個基于圖形界面的 覽器 生了。 使得網(wǎng)絡(luò)脫離了原來單調(diào)的字符界面,以及不友好的交互方式,獲 得了普通用戶的喜愛,從而也推動了 身的發(fā)展。隨著 新的 覽器的面世,使得 覽器的功能不斷加強,息越來越豐富,這使得 有了更強的吸引力,使得 的發(fā)展勢不可擋。 發(fā)展速度是驚人的,它的發(fā)展速度遠(yuǎn)遠(yuǎn)高于 發(fā)展速度,但這種發(fā)展速度也在隨著時間的推移而逐漸下降。在 1993 年下半年, 不到三個月的時間里翻了一翻。即使到了現(xiàn)在, 在以每六個月翻一翻的速度飛速增長。 在 還支持許多其他服務(wù),如 。在生之前,這些服務(wù)占用了 所有流量。 生后,便迅速增長并相繼超過了所有的服務(wù),到 1995 年四月達(dá)到了 量的第一位,直到現(xiàn)在還是穩(wěn)定的處于第一位。 中國進(jìn)入 較晚。高能所是中國第一個進(jìn)入 單位,在 1994年 5 月。隨后,中國教育科研網(wǎng)( 6月也進(jìn)入了 后, 中國也得到了 十分迅速的發(fā)展。到 1997年 1 月,在短短的不到三年的時間里,在 下的主機(jī)數(shù)已達(dá)到 19739 臺,這足以證明 中國發(fā)展的迅速。 界主要得搜索引擎及其比較 由于 迅速發(fā)展, 的信息量急劇增長。在 1996 年早些時候,司通過每日的例行記錄,得出的結(jié)論是網(wǎng)上大約有 1900 萬網(wǎng)頁。根據(jù)上面所提及的 長速度,現(xiàn)在網(wǎng)上大概擁有 1 億個以上的網(wǎng)頁。 在如此眾多的網(wǎng)頁中篩選用戶需要的信息,沒有十分有效的,自動化的搜索工具是難以想象的。這就象在一個巨大的圖書館 中,但這個圖書館沒有目錄。當(dāng)用戶希望找到一本自己需要的書時,他只能一個一個的書架,一本一本書的查找。這顯然對于用戶來說是不可忍受的。搜索引擎就象一個自動化的目錄一北京大學(xué)學(xué)士學(xué)位論文 中英文發(fā)現(xiàn)系統(tǒng)的轉(zhuǎn)接層子系統(tǒng)、索引子系統(tǒng)的設(shè)計與實現(xiàn) 第 5 頁 樣,它可以幫助用戶發(fā)現(xiàn)用戶所需要的信息來源,并幫助用戶去獲取它。 搜索引擎的工作機(jī)制大致如下: 首先,搜索引擎用一個綽號為“蜘蛛”的自動代理軟件在網(wǎng)址中爬行,訪問網(wǎng)絡(luò)中公開區(qū)域的每個站點并記錄其網(wǎng)址,從而創(chuàng)建一個詳盡的網(wǎng)絡(luò)目錄。 而后,搜索引擎根據(jù)自己的需要,訪問數(shù)據(jù)庫中記錄的部分站點或所有站點。系統(tǒng)把“機(jī)器人”軟件發(fā)往要訪問的站點,記錄每 一頁的所有文本內(nèi)容或者從這些信息中提取自己所需的摘要和其他信息。得到的這些信息被存放于一個數(shù)據(jù)庫中,這個數(shù)據(jù)庫必須經(jīng)常更新,重建,以保持與信息世界的同步發(fā)展。 最后,數(shù)據(jù)庫中的信息最終是為檢索用戶服務(wù)的。搜索引擎啟動一個 符合用戶請求的信息從數(shù)據(jù)庫中提取出來,并按其相關(guān)程度排序后輸出給用戶。 隨著 迅速發(fā)展,專門作為搜索引擎的站點也正以驚人的速度發(fā)展。現(xiàn)在網(wǎng)上常用的搜索引擎有 第。這些搜索引擎給 戶帶來了極大的方便。網(wǎng)上的搜索引擎大部分都是對整個 行搜索的。由于搜索的范圍相同,各種搜索引擎就有了一種比較的關(guān)系。在大量的使用中,各種搜索引擎表現(xiàn)出了許多共同之處,同時頁體現(xiàn)出了許多各自的特點。 相同之處: 1。搜索速度十分快,用戶響應(yīng)時間非常短。搜索時間一般都在 12 秒之間。這得益于競爭的結(jié)果,因為各搜索引擎的設(shè)計者都知道速度是用戶的最基本需求,在速度上不能滿足用戶需求將使得他所設(shè)計的搜索引擎毫無競爭力。 2。搜索結(jié)果的準(zhǔn)確性依賴于被搜索的內(nèi)容。對于每一種搜 索引擎,除非讓它進(jìn)行以容易描述的主題為基礎(chǔ)的簡單檢索,否則它就會給出相當(dāng)高比例的無關(guān)信息。 3。不能很好的支持自然語言。用戶的簡單的搜索輸入,準(zhǔn)確的搜索輸出的要求在一定的時間內(nèi)是無法滿足的。用戶希望得到一個精確的搜索結(jié)果時,用戶只能通過復(fù)雜的布爾表達(dá)式來實現(xiàn)其目的。 4。在進(jìn)行相同的搜索時,各個搜索引擎給出的結(jié)果有很大不同,雖然結(jié)果中也有相當(dāng)數(shù)量的重疊信息。對一個搜索引擎進(jìn)行相同的搜索時,其返回結(jié)果總是相同的。 不同之處: 現(xiàn)有的搜索引擎主要的特色體現(xiàn)在它的查全率和查準(zhǔn)率。查全率主要依賴于搜索引擎的 數(shù)據(jù)庫的大小,在這一方面, 有數(shù)千萬的網(wǎng)頁容量,故而有很高的查全率。其他數(shù)據(jù)庫相對較小的搜索引擎在查全率上無法和它們匹敵。查準(zhǔn)率主要依賴于數(shù)據(jù)庫索引的建立方式,查詢時的算法和對用北京大學(xué)學(xué)士學(xué)位論文 中英文發(fā)現(xiàn)系統(tǒng)的轉(zhuǎn)接層子系統(tǒng)、索引子系統(tǒng)的設(shè)計與實現(xiàn) 第 6 頁 戶搜索要求的理解。在這一方面, 口碑很好。 然不能給出最全面的信息,但是其搜索結(jié)果的相關(guān)性非常的好。 以下是各種搜索引擎的對比表: 型與容量 全文本 2100 萬頁 全文 本 150 萬頁 全文本 100 萬頁 摘要 1900 萬頁 全文本 150 萬頁 數(shù)據(jù)庫 點 無 無 無 有 有 點 無 無 無 有 有 新聞組 有 有 有 無 無 精細(xì)化搜索結(jié)果 無 無 有 無 有 事件敏感性 有 無 有 無 無 搜索 高級增強搜索 有 無 無 有 有 布爾運算 有 無 無 有 有 搜索結(jié)果描述 有 有 有 有 有 圖 網(wǎng)絡(luò)搜索引擎對比表 文的特點和搜索引擎對中文的支持 中文是一種象形文字,它與字母文字有 著十分巨大的區(qū)別。字母文字的字母數(shù)量一般都十分有限,例如英文有 26 個字母,德語有 28 個字母,俄語有 33 個字母。由于字母少這個特點, 使得字母文字在計算機(jī)上的應(yīng)用十分簡單,無論從文字的輸入輸出,還是文字的傳輸處理。中文的字的數(shù)量卻十分的龐大,有數(shù)萬個字。這些字中的使用頻率有相差懸殊,有些常用詞幾乎每個句子中都有:如的,是等詞。有些詞十分罕見,只存在于某些特殊用法或姓氏中,在很多字典中都沒有收錄。對于這些中文的特點,古代印刷術(shù)的解釋中就有說明,“遇到罕見的字,在現(xiàn)有的字模中沒有,當(dāng)即用泥土刻造該字作為字模使用?!?。這也充分說明了很難將漢字搜集完整。中文由于字?jǐn)?shù)多,表示復(fù)雜,使得在計算機(jī)上使用中文有一定的困難。為了將計算機(jī)對中文支持的標(biāo)準(zhǔn)化,國家標(biāo)準(zhǔn)局頒布了國家漢字編碼標(biāo)準(zhǔn)( 碼)。 碼使用的是擴(kuò)展符集,其使用范圍是 0碼共收錄一級,二級常用字共6768 個,每個漢字或漢字符號用兩個的字節(jié)實現(xiàn)。第一個字節(jié)表示該漢字的區(qū)號,第二個字節(jié)表示該漢字在該區(qū)內(nèi)的編號。由于國家制定了 準(zhǔn),使得漢字在計算機(jī)上的處理有了一定的標(biāo)準(zhǔn)。但是,在其他方面,如漢字輸入,還沒有相應(yīng)的國家標(biāo) 準(zhǔn),使得在這個領(lǐng)域相對混亂。 北京大學(xué)學(xué)士學(xué)位論文 中英文發(fā)現(xiàn)系統(tǒng)的轉(zhuǎn)接層子系統(tǒng)、索引子系統(tǒng)的設(shè)計與實現(xiàn) 第 7 頁 中文的另一個特點是語言的書寫方式。在英文的書寫中,詞語之間以空格作為天然的分隔符,使得每個單詞都一目了然。中文則僅僅以標(biāo)點符號分隔句子,詞語之間沒有任何分隔符,這使得對中文詞匯的劃分成為一件困難的事情。 例如,句子 在古代,人們寫信用毛筆。 有兩種機(jī)械的分法: 1。在 古代 , 人們 寫信 用 毛筆 。 2。在 古代 , 人們 寫 信用 毛筆 。 當(dāng)然,我們一眼就能看出第一種分法是合理的。因為我們能夠根據(jù)漢語的語法,句子的邏輯關(guān)系,以及句子所要表達(dá)的意思 來確定哪一種分詞方法是合理的。顯然,第一種分詞方法符合漢語的語法,而且按照這種分詞方法能夠正確的理解句子的意思。而在第二種分詞方法中,句子則顯得無法讓人理解,而且在語法上也不合理,毛筆這個詞在句子中的成分顯得不明確。 在上面的例子中,只要用語法,基本語義等一些規(guī)則,就可以判斷一個句子的分詞方法是否合理。但是,在一些句子中,單單靠這些還是不夠的。 例如,句子 這樣的人才能出眾。 有三種分詞方法: 1。這樣 的 人才 能 出眾。 2。這樣 的 人 才能 出眾。 3。這樣 的 人 才 能 出 眾。 在這三種分詞方法(三種理解方法)中,可以發(fā)現(xiàn)無論從語法,語義還是邏輯結(jié)構(gòu)上,它們都沒有任何不合理的地方。那么到底應(yīng)該如何對這個句子進(jìn)行分詞?難道一句話的三種分詞方法都正確嗎? 是的,三種分詞方法都正確。這個例子就是中文中常常講起的中文理解的歧義問題。到底應(yīng)當(dāng)選用哪一種分詞方法就要依據(jù)句子所在的上下文環(huán)境了。在具體的上下文環(huán)境中,我們可以得到其中的一種分詞方法。但是,由于中文表達(dá)信息的豐富性和不確定性,使得有時即使在確定的上下文環(huán)境中,正確的分詞方法也不止一種。 北京大學(xué)學(xué)士學(xué)位論文 中英文發(fā)現(xiàn)系統(tǒng)的轉(zhuǎn)接層子系統(tǒng)、索引子系統(tǒng)的設(shè)計與實現(xiàn) 第 8 頁 在人工智能領(lǐng)域中,現(xiàn)在自然語 言理解,機(jī)器翻譯方向十分活躍。在它們所需要解決的一些關(guān)鍵問題中,上面所提及的分詞問題就是其中之一。對于第一個例子,只要依賴一個詞庫,一個語法規(guī)則庫,加之以簡單的語義分析即可解決。但對于第二個例子,實現(xiàn)起來就會十分的困難,至今還沒有十分準(zhǔn)確,有效的實現(xiàn)方法。 由于在中文分詞中存在上述的困難,許多系統(tǒng)在實現(xiàn)中文處理系統(tǒng)時干脆就不考慮中文分詞,而是把中文信息作為一個一個漢字的排列,即對中文信息實現(xiàn)基于漢字的處理。但是筆者認(rèn)為,在許多的應(yīng)用環(huán)境中,使用基于詞的中文信息處理還是十分必要的。 漢語象其他許多語言 一樣,其語義的表達(dá)是基于詞匯的。當(dāng)我們看到這樣的一句話“我現(xiàn)在在計算機(jī)系學(xué)習(xí)”時,我們會很自然的把“現(xiàn)在”,“計算機(jī)系”,“學(xué)習(xí)”抽象出來,作為一個有意義的整體來考慮,而不會去顧及到該詞中每個單字的詳細(xì)意義(對于“我”,“在”等這類單字,可以作為由單個字組成的詞語來處理)。這正如在生物學(xué)中,雖然細(xì)胞是由分子,原子等基本單位構(gòu)成的,但我們在研究有機(jī)體的結(jié)構(gòu),功能時,總是以細(xì)胞作為基本單位一樣。既然漢語的表達(dá)是建立在詞匯的基礎(chǔ)之上的,那么在計算機(jī)系統(tǒng)對中文進(jìn)行處理時,就應(yīng)當(dāng)考慮到詞匯的關(guān)鍵作用。 由于對單個 漢字的處理簡單,系統(tǒng)實現(xiàn)相對容易,目前大部分中文處理系統(tǒng)都是基于單個漢字的?;谠~匯的中文處理系統(tǒng)在實現(xiàn)上相對復(fù)雜,但由于它有良好處理性能,目前發(fā)展也十分迅速。以中文檢索系統(tǒng)為例,基于單個字的系統(tǒng)對所有文章建立全文索引。在檢索時得到每個單字的索引,而后加以適當(dāng)?shù)倪壿嬤\算,得到檢索結(jié)果。而基于詞匯的檢索系統(tǒng)對詞匯建立索引。檢索詞匯時一次命中,沒有煩瑣的邏輯運算,速度十分的快。在檢索結(jié)果的全面性上基于單字的檢索要優(yōu)于基于詞匯的檢索,但在結(jié)果的相關(guān)性上基于單字的檢索要差于基于詞匯的檢索,另外在檢索速度上要基于單字 的檢索要慢一些。 例如在對關(guān)鍵詞“機(jī)能”的檢索中,有一篇關(guān)于通信的文章中含有“ A 機(jī)能向 B 機(jī)發(fā)出確認(rèn)”的句子。那么在基于單字的檢索中,結(jié)果中將會包含這篇文章,因為句子中機(jī),能兩個字都存在而且相鄰,系統(tǒng)就認(rèn)為它符合檢索的要求。在基于詞匯的檢索中,將不會給出這篇文章,因為機(jī),能雖然同時存在而且相鄰,但它們在句子中并不構(gòu)成詞匯,所以基于詞匯的檢索將不能命中它。由此例可見基于單字檢索系統(tǒng)的一個致命弱點,即它不能“理解”句子的意思,因而不能給出最切合檢索者檢索意圖的結(jié)果?;谠~匯的檢索系統(tǒng)能在一定程 度上“理解”句子的意思,因而在檢索結(jié)果的相關(guān)性上要更好一些。 北京大學(xué)學(xué)士學(xué)位論文 中英文發(fā)現(xiàn)系統(tǒng)的轉(zhuǎn)接層子系統(tǒng)、索引子系統(tǒng)的設(shè)計與實現(xiàn) 第 9 頁 基于單字和基于詞匯的檢索在實現(xiàn)機(jī)制上的不同,它們在很多方面都有很大的區(qū)別,對于它們的比較如下: 基因字的檢索 基于詞的檢索 實現(xiàn)難度 一般 較難 中文預(yù)處理的實現(xiàn) 容易 很難 檢索核心的實現(xiàn) 一般 容易 索引的類型 全文索引 基于詞的索引 索引的大小 很大(文章的 4) 較?。?文 文 文 英文譯碼 北京大學(xué)學(xué)士學(xué)位論文 中英文發(fā)現(xiàn)系統(tǒng)的轉(zhuǎn)接層子系統(tǒng)、索引子系統(tǒng)的設(shè)計與實現(xiàn) 第 13 頁 圖 轉(zhuǎn)結(jié)層體系結(jié)構(gòu)圖 在具體的實現(xiàn)中,轉(zhuǎn)結(jié)層包含了四個部分: 1。 中文編碼互換 實現(xiàn)中文的 碼之間的互相轉(zhuǎn)換。 2。 中文分詞 實現(xiàn)中文的自動分詞。 3。 中英文編碼方案 實現(xiàn)對中文,英文詞匯的編碼和譯碼。 4。 中英文詞匯的自動學(xué)習(xí) 實現(xiàn)從用戶的輸入中自動學(xué)習(xí)新的中文,英文詞匯的功能。 文編碼互換 由于中文漢字?jǐn)?shù)量多,相對英文而言編碼規(guī)則比較復(fù)雜。編碼規(guī)則的復(fù)雜就會導(dǎo)致編碼種類的多樣化,每種編碼都有其特長,同時也有一定的使用范圍。 現(xiàn)有的中文漢字編碼有很多種,其中使用量最大的有三種: 這個系統(tǒng)中也主要支持這三種編碼。其中 國家標(biāo)準(zhǔn)編碼,對應(yīng)于國家簡體漢字字庫的一二級常用字,主要使用地區(qū)是大陸。 臺灣所制定的標(biāo)準(zhǔn)編碼,它同時支持漢字的簡體和繁體形式,主要在臺灣以及其他需要使用繁體漢字的場合。 一種為方便網(wǎng)絡(luò)傳輸所制定的編碼方案,它支持漢字在網(wǎng)上以文本的 形式傳輸。 三種漢字編碼都是使用兩個字節(jié)來表示一個漢字,但是每個字節(jié)所使用的數(shù)字范圍,以及每個字節(jié)所代表的意義不同。 碼中兩個字節(jié)都是使用的擴(kuò)展符集,范圍是 0碼中第一個字節(jié)使用的是擴(kuò)展的符集,范圍是 0二個字節(jié)使用的是 符集和擴(kuò)展符集,范圍是 0碼使用的兩個字節(jié)都是 符集,范圍是 0 在系統(tǒng)實現(xiàn)時,采用 碼作為系統(tǒng)內(nèi)部編碼。當(dāng)用戶使用的是 者 碼時,調(diào)用轉(zhuǎn)換程序?qū)⑵滢D(zhuǎn)換 碼后遞交給系統(tǒng)處理,是 碼北京大學(xué)學(xué)士學(xué)位論文 中英文發(fā)現(xiàn)系統(tǒng)的轉(zhuǎn)接層子系統(tǒng)、索引子系統(tǒng)的設(shè)計與實現(xiàn) 第 14 頁 時,直接交給系統(tǒng)處理。這樣,中文編碼互換主要由兩個部分組成: 互換。 ( A) 互換 碼之間沒有相關(guān)性,在互換時采用編碼轉(zhuǎn)換表的方式進(jìn)行。即對于一個 碼的漢字,檢索 編碼轉(zhuǎn)換表,得到該漢字的碼。對于 碼的轉(zhuǎn)換也一樣。 ( B) 互換 碼之間的聯(lián)系很緊密,它們之間的轉(zhuǎn)換相對容易。對于一個 漢字,只要把每個字節(jié)的第 8 位更改為 0,即得到該漢字的 碼; B 編碼轉(zhuǎn)換時只要把第 8 位更改為 1 即可。 英文編碼方案 在本搜索引擎的設(shè)計中,檢索是基于詞匯的。因此,對中英文詞匯的處理就成為了系統(tǒng)設(shè)計的一個核心部分。如何識別一個中英文詞,如何找到該詞在數(shù)據(jù)庫中所對應(yīng)的文章就成為了系統(tǒng)檢索效率高低的關(guān)鍵。 由于中英文詞匯都是人們在自然生活中形成,發(fā)展而來的,因而內(nèi)容豐富,數(shù)量巨大,而且各個詞的長度也相差懸殊。如果把這些自然的詞匯直接交給系統(tǒng)核心處理,那么將會提高系統(tǒng)核心處理的 復(fù)雜度,降低系統(tǒng)核心的效率。 解決的一種方法就是利用編碼。就象現(xiàn)在已經(jīng)成為標(biāo)準(zhǔn)的英文 及中文 碼方案一樣,這些標(biāo)準(zhǔn)通過將自然形成的字符進(jìn)行編碼而使得它們易于計算機(jī)的處理。在本系統(tǒng)的設(shè)計中同樣可以利用這種思想,將比字符更高一級的語言單位 得它易于系統(tǒng)核心的處理。 詞匯在編碼的處理上與字符的有很大的不同。字符編碼的每個標(biāo)準(zhǔn)中字符集都是固定,每個字符的編碼也都是固定的。而在詞匯的編碼中,我們不能確定詞匯的集合。對于字符來說,字母文字的字符集是完全固定的;相形文字的字符集也是 相對穩(wěn)定的。但對于詞匯來說,無論是字母還是相形文字,它們的詞匯都是在不斷發(fā)展的,而且這種發(fā)展的速度還相當(dāng)?shù)目臁R虼?,詞匯的編碼方案只能是一個動態(tài)增長的,而不是靜態(tài)的方案。這種動態(tài)的特點給編碼譯碼的設(shè)計帶來了一定的難度。 編碼譯碼機(jī)理描述圖: 北京大學(xué)學(xué)士學(xué)位論文 中英文發(fā)現(xiàn)系統(tǒng)的轉(zhuǎn)接層子系統(tǒng)、索引子系統(tǒng)的設(shè)計與實現(xiàn) 第 15 頁 圖 編碼譯碼機(jī)理描述圖 在這一部分的設(shè)計中,對中英文的設(shè)計是基本相同的。在這里,我們以中文為例子來介紹編碼和譯碼部分的詳細(xì)設(shè)計。 在編碼 譯碼部分由三個子部分組成:編碼,碼到詞的翻譯,詞到碼的翻譯。 ( A)編碼: 編碼采用的是從小到大依次分配的方法。即每向編碼庫加入一個新詞時,該詞便獲得現(xiàn)在編碼庫中最大編碼加一的編碼。這樣的編碼設(shè)計方案中,編碼和詞匯之間沒有必然的聯(lián)系。但是,這樣最大程度的利用了編碼空間,使得在編碼空間內(nèi)沒有空缺(在編碼空間中每個編碼都對應(yīng)一個詞匯)。 在實現(xiàn)編碼時,要首先有一個原始的詞庫。原始詞庫共有詞匯 N 個,從該詞庫的第一個詞開始,到最后一個詞,編碼依次為 1詞庫需要擴(kuò)充時,例如需要向詞庫添加 M 個詞匯時 ,那么這 M 個詞匯的編碼為 碼庫以文件的方式存在。 ( B)碼到詞的翻譯: 將編碼庫的詞匯,按照編碼的大小排序,在內(nèi)存中建立一個大小為 N 的 組。在碼到詞的翻譯中,將編碼作為數(shù)組的下標(biāo),一次就可以譯出對于的詞匯。 碼到詞翻譯的原理圖: 對詞匯 進(jìn)行 編碼 原始 詞庫 編碼 詞庫 中英文詞匯 詞碼互譯 編碼 北京大學(xué)學(xué)士學(xué)位論文 中英文發(fā)現(xiàn)系統(tǒng)的轉(zhuǎn)接層子系統(tǒng)、索引子系統(tǒng)的設(shè)計與實現(xiàn) 第 16 頁 圖 碼到詞的翻譯原理圖 ( C)詞到碼的翻譯: 在這個翻譯過程中,詞 庫在內(nèi)存中的組織采用有序的散列表結(jié)構(gòu)。 ( a)散列表的生成: 從編碼庫中獲得一個詞后,按照下面的散列函數(shù)得到該詞所對應(yīng)的地址: h ( = f ( 在上個表達(dá)式中, f 函數(shù)作用是一個將中文漢字轉(zhuǎn)化為一個 0 到 6767 之間的整數(shù)。這是根據(jù) 碼規(guī)則設(shè)計的,其實現(xiàn)簡單迅速。對所有的詞匯進(jìn)行散列后,碰撞的詞匯就是以同一個中文漢字開頭的詞匯。對于碰撞的詞匯,用快速排序的方法按照字符串的大小進(jìn)行排序,保存于碰撞區(qū)里。 ( b) 譯碼的實現(xiàn): 對于一個中文詞匯,取該詞匯的第一個漢字作為關(guān)鍵碼,命中該詞匯在散列表中的地址。然后,用二分法在該地址的碰撞區(qū)內(nèi)對該詞匯進(jìn)行匹配。如果匹配成功,則返回該詞匯的編碼,否則,返回 詞到碼翻譯的原理圖如下: 詞匯數(shù)組 詞匯編碼 0 1 阿拉伯 愛情 66 。 66 計算機(jī) 。 N 網(wǎng)絡(luò) 北京大學(xué)學(xué)士學(xué)位論文 中英文發(fā)現(xiàn)系統(tǒng)的轉(zhuǎn)接層子系統(tǒng)、索引子系統(tǒng)的設(shè)計與實現(xiàn) 第 17 頁 圖 詞到碼翻譯的原理圖 在這種譯碼的設(shè)計中 ,譯碼的效率還是相當(dāng)高的。對譯碼的時間復(fù)雜度估計如下: 譯碼時間復(fù)雜度 =散列表命中時間復(fù)雜度 +碰撞區(qū)命中時間復(fù)雜度 對于散列表命中時間復(fù)雜度來說,其大小總是 1,因為它是按照散列地址一次命中的。對于碰撞區(qū)命中時間復(fù)雜度來說,可以做如下估計。 現(xiàn)在中文漢字詞庫共有詞匯 62377 個,根據(jù)國家 有漢字 6767個,這樣平均每個漢字的碰撞區(qū)內(nèi)保存有 10 個詞匯。由于使用二分法檢索,其檢索時間復(fù)雜度為 1 = 4; 綜以上所述,譯碼的平均時間復(fù) 雜度為 1 + 4 = 5; 文分詞 中 國 人 民 0 愛1 把。6 6 中。N 字 0 稱。 。 。 1 3 2 2 華1 3 2 3 國。 。 。1 3 2 6 國 人 民。 。 。1 3 3 0 指 北京大學(xué)學(xué)士學(xué)位論文 中英文發(fā)現(xiàn)系統(tǒng)的轉(zhuǎn)接層子系統(tǒng)、索引子系統(tǒng)的設(shè)計與實現(xiàn) 第 18 頁 中文分詞在背景資料中提及很多。在這里主要描述一下中文分詞所采用的算法。北京大學(xué)學(xué)士學(xué)位論文 中英文發(fā)現(xiàn)系統(tǒng)的轉(zhuǎn)接層子系統(tǒng)、索引子系統(tǒng)的設(shè)計與實現(xiàn) 第 19 頁 圖 中文分詞的算法描述圖 N N 將短語的第一個字譯為整數(shù),并將該字記入 。 從字索引數(shù)組中得到以該字開頭的詞表。 比較當(dāng)前項號對應(yīng)詞是否與短語中同長度的詞相等。 當(dāng)前項號為 相等? 將該詞記入 當(dāng)前項號加 1。 比較當(dāng)前項號對應(yīng)詞的第二個字是否與短語第二個字相同。 二分法在詞表中查找與短語第二個字相同的表序號最小的項。若找到,記錄該表序號為當(dāng)前項號。否則,記錄當(dāng)前項號為 相同? 返回 Y Y N Y 北京大學(xué)學(xué)士學(xué)位論文 中英文發(fā)現(xiàn)系統(tǒng)的轉(zhuǎn)接層子系統(tǒng)、索引子系統(tǒng)的設(shè)計與實現(xiàn) 第 20 頁 本系統(tǒng)中中文分詞的設(shè)計是在常用的最大匹配算法之上加以加以改進(jìn)。在詞庫的組織上仍采用中英文編碼方案中的有序散列表結(jié)構(gòu)。其工作機(jī)理大體可以這樣描述: 第一步:根據(jù)輸入串的第一個漢字命中散列表的一個地址。 第二步:在散列表該地址所對應(yīng)的碰撞區(qū)中,用二分法檢索與 輸入串中第二個漢字匹配的所有詞中的第一個。 第三步:從上一步所得的詞開始,向下依次匹配,找到前兩個漢字相同的最大匹配的詞返回。 在這里,我們來估計分出一個中文詞的時間復(fù)雜度。在工作機(jī)理的大體描述中,整個分詞過程被分為了三步,總的時間復(fù)雜度相當(dāng)于每一部分時間復(fù)雜度的總和。第一步是一次命中的其時間復(fù)雜度為 1;第二步相當(dāng)與在譯碼中檢索一個兩個漢字組成的詞,其時間復(fù)雜度同譯碼部分的估計,為 4。第三步,就要看何時匹配成功或者失敗。這也就相當(dāng)與求得中文詞匯中前平均兩個漢字相同的詞的個數(shù)。根據(jù)現(xiàn)有的詞庫統(tǒng)計,這個數(shù) 據(jù)大概為 庫中共有詞匯 6 萬余條,其中 4 萬余條為兩字詞)??紤]成功和失敗的綜合因素,這一部分的時間復(fù)雜度為 2。由以上三個部分,可以得到分出一個中文詞匯的時間復(fù)雜度為: 1 + 4 + 2 = 7; 英文詞匯的自動學(xué)習(xí) 時代的發(fā)展,信息的擴(kuò)大,同時帶來了詞匯量的擴(kuò)大。大量具有時代特色的新詞不斷的產(chǎn)生出來,如“超媒體”,“ 詞匯。如果詞庫采用靜態(tài)的,那么它將不能適應(yīng)時代的發(fā)展。許多新涌現(xiàn)出來的,熱點的詞匯在詞庫中無法找到,這將大大降低系統(tǒng)的實用價值,使得用戶對系統(tǒng)產(chǎn)生懷疑和不信賴 。如果由管理員來負(fù)責(zé)人工的向詞庫中加入新詞匯,一方面給管理員帶來了極大的負(fù)擔(dān);另一方面,管理員也不可能樣樣精通,他所能了解到的新詞將會十分的有限,雖然他可以定期給詞庫補充一定量的新詞,但是更多的新詞將會被疏漏掉。 本系統(tǒng)所采用的方法是用一個“學(xué)習(xí)機(jī)”來自動的學(xué)習(xí)。它從 頁中和用戶的檢索輸入中來學(xué)習(xí)最新的詞匯,再由管理員進(jìn)行增刪后加入到詞庫中。這一部分的工作原理圖如下: 北京大學(xué)學(xué)士學(xué)位論文 中英文發(fā)現(xiàn)系統(tǒng)的轉(zhuǎn)接層子系統(tǒng)、索引子系統(tǒng)的設(shè)計與實現(xiàn) 第 21 頁 圖 詞匯自動學(xué)習(xí)的工作原理圖 對英文的學(xué)習(xí)主要來源于對 頁的分析。網(wǎng)頁搜索程序從 上獲得大量的 頁,并且對它們進(jìn)行分析關(guān)鍵詞,提取摘要等處理。英文就是從關(guān)鍵詞部分學(xué)習(xí)到的。當(dāng)“學(xué)習(xí)機(jī)”發(fā)現(xiàn)它不認(rèn)識某個關(guān)鍵詞時,它就會在預(yù)備添加詞庫中記錄下這個詞匯,準(zhǔn)備以后向詞庫中加入。 對中文的學(xué)習(xí)主要來源于檢索的用戶。當(dāng)他們檢索某個中文詞匯時,如果詞庫中沒有這個詞匯,分詞程序?qū)阉?割成幾個字和詞。這時,“學(xué)習(xí)機(jī)”也能發(fā)現(xiàn)這個事實,它將會把這個詞匯記錄再預(yù)備添加詞庫中備用。 預(yù)備添加詞庫中的“詞匯”并不一定合理,這就是為什么需要管理員來進(jìn)行人工增刪管理。例如用戶輸入詞匯“超媒體”,“學(xué)習(xí)機(jī)”學(xué)習(xí)到它,將它加入到預(yù)備添加詞庫中,管理員認(rèn)為這個詞匯是一個新產(chǎn)生的詞匯,它就會把它加入到正式的詞庫中。這樣,在以后的處理中,“超媒體”將會被按照一個詞匯處理。如果用戶隨便輸入一個詞匯,如“大大小小”,“學(xué)習(xí)機(jī)”也會學(xué)習(xí)到它,這就需要管理員來判斷它是不是一個新詞了。 “學(xué)習(xí)機(jī)” 管理員 正式 詞庫 預(yù)備添 加詞庫 用 戶查詢信息 “學(xué)習(xí)機(jī)” 北京大學(xué)學(xué)士學(xué)位論文 中英文發(fā)現(xiàn)系統(tǒng)的轉(zhuǎn)接層子系統(tǒng)、索引子系統(tǒng)的設(shè)計與實現(xiàn) 第 22 頁 第四章 索引數(shù)據(jù)庫子系統(tǒng)的 設(shè)計 引數(shù)據(jù)庫子系統(tǒng)的設(shè)計思想 索引數(shù)據(jù)庫子系統(tǒng)的設(shè)計與實現(xiàn)是在整個系統(tǒng)的設(shè)計與實現(xiàn)中占用舉足輕重的作用。它直接關(guān)系到用戶檢索的響應(yīng)速度和檢索結(jié)果的質(zhì)量,這兩個參數(shù)都是評價一個搜索引擎優(yōu)劣的極其重要的參數(shù)。 在索引數(shù)據(jù)庫子系統(tǒng)的設(shè)計中貫穿了效率的思想,無論是在數(shù)據(jù)庫設(shè)計,數(shù)據(jù)庫更新的設(shè)計還是數(shù)據(jù)庫檢索的設(shè)計中。 正是上一章中描述的編碼的思想在這里發(fā)揮了巨大的作用。有了編碼,使得在數(shù)據(jù)庫中的詞匯都有了固定的長度(長整型),有了統(tǒng)一高效的處理方式。在以下索引數(shù)據(jù)庫子系統(tǒng)的詳細(xì)設(shè)計中,就 可以具體的體現(xiàn)到編碼思想所帶來的好處。 另一個提高效率的方法是悉心的設(shè)計算法,以時間復(fù)雜度為設(shè)計核心,來提高系統(tǒng)的運行速度。在以下的詳細(xì)設(shè)計中,可以看到設(shè)計和選擇和系統(tǒng)相適應(yīng)的算法給系統(tǒng)所帶來的運行效率的大大改善。 索引數(shù)據(jù)庫子系統(tǒng)的體系結(jié)構(gòu)圖如下: 圖 索引數(shù)據(jù)庫子系統(tǒng)的體系結(jié)構(gòu)圖 檢索數(shù)據(jù)庫子系統(tǒng) 信息發(fā)現(xiàn)子系統(tǒng) 用戶 用戶請求 索引庫 更新程序 索引庫 檢索程序 素材庫 檢索結(jié)果 索引庫 北京大學(xué)學(xué)士學(xué)位論文 中英文發(fā)現(xiàn)系統(tǒng)的轉(zhuǎn)接層子系統(tǒng)、索引子系統(tǒng)的設(shè)計與實現(xiàn) 第 23 頁 索引數(shù)據(jù)庫子系統(tǒng)的設(shè)計包含三個部分: 1。數(shù)據(jù)庫的設(shè)計 設(shè)計數(shù)據(jù)庫的數(shù)據(jù)結(jié)構(gòu)。 2。索引數(shù)據(jù)庫的更新和維護(hù) 負(fù)責(zé)索引數(shù)據(jù)庫的插入,刪除,更改。 3。索引數(shù)據(jù)庫的檢索 負(fù)責(zé)索引數(shù)據(jù)庫的簡單和邏輯組合檢索。 引數(shù)據(jù)庫的設(shè)計 圖 索引數(shù)據(jù)庫的結(jié)構(gòu)設(shè)計圖 中文詞碼表 中文對應(yīng)關(guān)系表族 英文詞碼表 英文對應(yīng)關(guān)系表族 文章庫 北京大學(xué)學(xué)士學(xué)位論文 中英文發(fā)現(xiàn)系統(tǒng)的轉(zhuǎn)接層子系統(tǒng)、索引子系統(tǒng)的設(shè)計與實現(xiàn) 第 24 頁 如圖 示,索引數(shù)據(jù)庫主要由三個部分構(gòu)成: 1。詞碼表: 對于一個關(guān)鍵詞,經(jīng)譯碼程序后被轉(zhuǎn)換為一個編碼,即詞碼。詞碼以下標(biāo)的方式命中詞碼表 中的表項。詞碼表表項中記錄了該詞所對應(yīng)的對應(yīng)關(guān)系表在對應(yīng)關(guān)系表族中的偏移量,還有這個對應(yīng)關(guān)系表的長度。 2。對應(yīng)關(guān)系表族: 該表族中每一項為一個對應(yīng)關(guān)系表,它為詞碼表中的表項所對應(yīng)。對應(yīng)關(guān)系表中的每一項含有一個編號,就是一篇文章在文章庫中的編號(關(guān)鍵碼)。對應(yīng)關(guān)系表表項還包含一個對應(yīng)關(guān)系表按照編號大小內(nèi)排序的指針,還有一個整數(shù)記錄該關(guān)鍵詞在文章中的權(quán)值。 3。文章庫: 文章庫中每一項記錄有文章的作者,摘要,長度等用戶可能需要了解的信息。文章庫用多個文件進(jìn)行模擬,本系統(tǒng)實現(xiàn)中使用了 64 個文件。 考慮中英文在編碼動態(tài)增長上的需要,在詞碼表和對應(yīng)關(guān)系表族上中英文加以分離,文章庫是統(tǒng)一存儲的(文章可以是中英文混合的)。 引數(shù)據(jù)庫的更新和維護(hù) 索引數(shù)據(jù)庫的更新分為三個步驟: 第一步:從素材庫(存放 頁和 章信息)中提取更新信息,包括刪除,增加,修改三個部分。這三個部分存放于兩個文件中,一個文件存放刪除信息,一個文件存放增加和修改信息。 第二步:根據(jù)更改信息,更新文章庫,同時生成更新索引所必須的備用文件。 第三步:根據(jù)第二步中所產(chǎn)生的備用文件,更新索引。 1。提取更新信息: 這一步主要目的是把索引數(shù)據(jù)庫的更新和對素材庫的操作隔離開來??紤]到素材庫和索引數(shù)據(jù)庫可能不在一個主機(jī)上,更考慮以后分布式索引數(shù)據(jù)庫的需要,這個使得索引數(shù)據(jù)庫和素材庫相對獨立的步驟是關(guān)鍵和必要的。 這一步的設(shè)計實現(xiàn)相對容易,它從素材庫中利用查詢語句,使用一定的查詢條件即可得到。 北京大學(xué)學(xué)士學(xué)位論文 中英文發(fā)現(xiàn)系統(tǒng)的轉(zhuǎn)接層子系統(tǒng)、索引子系統(tǒng)的設(shè)計與實現(xiàn) 第 25 頁 2。更新文章庫: 這一步主要目的是將從素材庫中提取的更新信息反映到文章庫中。它為每個刪除的信息做無效標(biāo)志;為更改信息做更改標(biāo)志,把更改的信息記錄到文章庫中;為增加的信息在文章庫中分配存放空間。 在這一步 里,涉及到對文章庫中碎片的管理和對建立索引部分的支持。對文章庫中碎片的管理采用可用塊表;對建立索引部分的支持采用作廢塊表和關(guān)鍵詞 一部分的設(shè)計參考下面的更新文章庫流程圖: 圖 更新文章庫流程圖開 始 開 始 N 還 有 文 章 刪 除 ?Y N 還 有 更 新 項 ?Y 將文章塊號記入可用塊號表 Y 該 文 章 在 庫 中 ? 加入: 給文章分配新塊號 更改: 記文章塊號入作廢表 結(jié) 束 文章寫入 指定塊號 分析更新項中的關(guān)鍵詞,加入關(guān)鍵詞 結(jié) 束 北京大學(xué)學(xué)士學(xué)位論文 中英文發(fā)現(xiàn)系統(tǒng)的轉(zhuǎn)接層子系統(tǒng)、索引子系統(tǒng)的設(shè)計與實現(xiàn) 第 26 頁 3。更新索引庫: 這一步利用上一步中產(chǎn)生的數(shù)據(jù),建立一個高效的索引。這一部分首先利用作廢塊表,作廢原有索引的無效部分,生成索引 A;然后利用關(guān)鍵詞 生成新索引 B;最后將索引 A 和索引 B 合并,生成目標(biāo)索引。以上三步實現(xiàn)了對索引的更新。其流程如圖 示。 圖 更新索引庫流程圖 引數(shù)據(jù)庫的檢索 索引庫檢索的設(shè)計是對效率的考驗。對于搜索引擎的最終用 戶,他們所能感受到的效率,關(guān)鍵就在這一部分的速度上。 由于系統(tǒng)的設(shè)計采用了編碼的思想,將對煩瑣的詞匯處理拋在了系統(tǒng)核心之外,使得系統(tǒng)檢索的復(fù)雜度大大降低。 在檢索的邏輯運算中,采用了兩重有序表結(jié)構(gòu),從而使得邏輯運算的復(fù)雜度有了極大程度的降低。 開 始 通過新的關(guān)鍵詞 通過作廢塊表重構(gòu)中英文詞碼表和對應(yīng)關(guān)系表族。 歸并兩個中英文詞碼表和對應(yīng)關(guān)系表族 結(jié) 束 北京大學(xué)學(xué)士學(xué)位論文 中英文發(fā)現(xiàn)系統(tǒng)的轉(zhuǎn)接層子系統(tǒng)、索引子系統(tǒng)的設(shè)計與實現(xiàn) 第 27 頁 1。關(guān)鍵詞的檢索: 系統(tǒng)處理單個關(guān)鍵詞的檢索時,它并不直接將該關(guān)鍵詞交給檢索子系統(tǒng),而是交給轉(zhuǎn)結(jié)層子系統(tǒng)。轉(zhuǎn)結(jié)層子系統(tǒng)對該詞匯進(jìn)行一系列的處理之后,將其轉(zhuǎn)換為一個長整型的整數(shù),再交給檢索子系統(tǒng)處理。檢索子系統(tǒng)根據(jù)該詞匯的編碼,以下標(biāo)的形式一次命中詞碼表中的 對應(yīng)項,提取出該詞匯的對應(yīng)關(guān)系表,即查詢的結(jié)果。 關(guān)鍵詞檢索的原理圖如下: 圖 關(guān)鍵詞檢索原理示意圖 2。對邏輯運算的支持: 邏輯運算相當(dāng)于對兩個表的處理,即求兩個表的交集,并集等一些運算。如果兩個表是無序的,那么這種運算的復(fù)雜度相當(dāng)與 M*N。這種間復(fù)雜度在表的大小較 小時,速度是十分迅速的。但是,當(dāng)表的大小變的十分大時,比如達(dá)到 1 萬時,那么 M*N = 1 億,這是不可忍受的。而在一個比較實用的搜索引擎中,其平均的每個關(guān)鍵詞命中的文章數(shù)大概也在萬的數(shù)量級。顯然將表設(shè)計成無序表,其處理延時是不能達(dá)到實用要求的。 在這時就需要將表實現(xiàn)為有序表。對于有序表,就可以利用歸并的思想,將兩個表的邏輯運算的時間復(fù)雜度降為 M+N。在這樣的時間復(fù)雜度情況下,我們在處理長達(dá) 1 萬的表時,其所需的時間單位為: M+N = 2 萬。這樣一個改進(jìn),在處理關(guān)鍵詞命中的 1 萬篇文章時,其速度能提高 5000 倍 ! 在本系統(tǒng)中,每個關(guān)鍵詞對應(yīng)一個對應(yīng)關(guān)系表。這時對對應(yīng)關(guān)系表中的文章譯碼 對應(yīng)關(guān)系表 詞表 詞匯 編碼 。文 章 庫。北京大學(xué)學(xué)士學(xué)位論文 中英文發(fā)現(xiàn)系統(tǒng)的轉(zhuǎn)接層子系統(tǒng)、索引子系統(tǒng)的設(shè)計與實現(xiàn) 第 28 頁 編號域考察:在一個關(guān)鍵詞對應(yīng)的表中,文章編號是唯一的(不會出現(xiàn)重復(fù)的現(xiàn)象),故文章編號可以作為表項的關(guān)鍵碼。通過對這個碼的排序,在表進(jìn)行邏輯運算是就可以實現(xiàn)歸并算法了。 由于關(guān)鍵詞對應(yīng)的表已經(jīng)按照該關(guān)鍵詞在對應(yīng)文章中的權(quán)值排序(表的前后順序),故對文章編號的排序就被設(shè)計為內(nèi)排序,通過表項中的一個指針域?qū)崿F(xiàn)。在對整個表的使用中,兩個排序同樣的有效,所以稱這個表為兩重有序表。 根據(jù)對實際應(yīng)用的統(tǒng)計,系統(tǒng)現(xiàn)在支持三種邏輯運算: 們在系統(tǒng)中的意義如下: :對于兩個關(guān)鍵詞都命中的文章為有效文章,其結(jié)果權(quán)值為兩個關(guān)鍵詞在該文章中的權(quán)值只和。 :對兩個關(guān)鍵詞中任何一個關(guān)鍵詞命中的文章即為有效文章。若文章只包含一個關(guān)鍵詞,則文章的結(jié)果權(quán)值即為該關(guān)鍵詞在文章中的權(quán)值。若文章中包含了兩個關(guān)鍵詞,則文章的結(jié)果權(quán)值為這兩個關(guān)鍵詞在文章中權(quán)值的和。 對兩個關(guān)鍵詞中任何一個關(guān)鍵詞命中的文章即為有效文章。若文章只包含一個關(guān)鍵詞,

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論