【畢業(yè)學(xué)位論文】（Word原稿）中英文發(fā)現(xiàn)系統(tǒng)的轉(zhuǎn)接層子系統(tǒng)、索引子系統(tǒng)的設(shè)計與實現(xiàn)-計算機(jī)系網(wǎng)絡(luò)與分布式系統(tǒ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ù)目臁Ｒ虼?，詞匯的編碼方案只能是一個動態(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)鍵詞，