網(wǎng)絡(luò)搜索引擎關(guān)鍵技術(shù) 文本處理,主要內(nèi)容,本講稿對搜索引擎的關(guān)鍵技術(shù)進行了概 述，著重討論了信息預(yù)處理技術(shù)中的文本處 理。,一.搜索引擎的關(guān)鍵技術(shù),信息收集和存儲技術(shù) 包括兩種方式：人工和自動。 人工方式采用傳統(tǒng)的信息收集、分類、存儲、組織和檢索的方法。 自動方式通常是由網(wǎng)絡(luò)機器人來完成的。 一般來說，人工方式收集信息的準確性要遠優(yōu)于“網(wǎng)絡(luò)機器人”，但其收集信息的效率及全面性低于“網(wǎng)絡(luò)機器人”。,2.信息預(yù)處理技術(shù) 信息預(yù)處理系統(tǒng)的主要工作是從抓取的網(wǎng)頁中提取能夠代表網(wǎng)頁的屬性，并將這些屬性組成網(wǎng)頁的對象，然后根據(jù)一定的相關(guān)度算法進行計算，得到每一個網(wǎng)頁針對頁面內(nèi)容及鏈接每一個關(guān)鍵詞的相關(guān)度，并用這些信息建立索引數(shù)據(jù)庫。 關(guān)鍵詞的提取 重復或轉(zhuǎn)載網(wǎng)頁的消除 鏈接分析 網(wǎng)頁重要程度的計算,3.信息索引技術(shù) 信息索引就是創(chuàng)建文檔信息的特征記錄，以便用戶能夠快速地檢索到所需信息。 信息語詞切分和語詞詞法分析 進行詞性標注及相關(guān)的自然語言處理 建立檢索項索引 檢索結(jié)果處理技術(shù),二.文本處理,文本處理是指將網(wǎng)絡(luò)爬蟲搜集到的文本信息進行預(yù)處理，以便進行網(wǎng)絡(luò)信息檢索的下一個流程索引處理。,網(wǎng)頁噪聲去除,待處理網(wǎng)頁,干凈網(wǎng)頁,詞匯分析,詞序列,詞干提取,排除停用詞,有用詞序列,關(guān)鍵詞,HTML文檔預(yù)處理流程,文本處理的過程包括如下5個步驟： 文本的詞法分析 無用詞匯的刪除 詞干提取 索引詞條/詞干的選擇 構(gòu)造詞條的分類結(jié)構(gòu),1.詞法分析,詞法分析的過程是將字符串轉(zhuǎn)換成詞條的過程，因此詞法分析的主要目的就是識別文本中的詞條。 關(guān)于詞法分析，中英文存在較大的區(qū)別，英文單詞有空格分隔，易于識別，而中文文本以句子為自然分隔單位，要提取出詞語來，需要復雜的分詞技術(shù)。,在對英文進行分詞的過程中，除了空格分隔符，還有幾種特殊的情況要處理：數(shù)字、連字符、標點符號和字母的大小寫。 數(shù)字 數(shù)字一般不作為索引詞，因為如果沒有上下文的聯(lián)系，它們的含義是模糊不清的。 現(xiàn)在常用的做法是保留一些專門指出的（通過與正規(guī)表達式的匹配）數(shù)字，而將其他數(shù)字過濾掉。,連字符 對連字符來說，也有兩難情況。 一種方法是將連字符都忽略掉，例如state-of-the-art等同于state of the art。但是，有些帶有連字符的單詞本身是一個完整的單詞，如gilt-edged。 對于連字符的處理，目前常用的是首先采用一定的規(guī)則選出那些對詞義有影響的連字符號，然后將其他連字符都過濾掉。,標點符號 對于文本中的標點符號，一般說來在詞法分析過程中將被全部去除。但是，對于那些成為單詞中一部分的標點符號來說，又要慎重考慮是否刪除標點。 另外一種特殊情況是程序片段出現(xiàn)在文本中，這時就要區(qū)分變量x.id與xid了。這種情況下，標點符號應(yīng)該保留。,字母的大小寫 字母的大小寫對于區(qū)分索引詞條來說一般不是很重要，因此可以將文本中的所有詞條都轉(zhuǎn)換成大寫或者小寫。 但是也存在特殊情況，例如對于描寫UNIX命令的文檔，由于大小寫都是約定俗成的，因此用戶并不希望改變文檔中的大小寫。對于此種情況，就要特殊處理。,2.中文分詞技術(shù),中文分詞技術(shù)屬于自然語言處理技術(shù)范疇，對于一句話，人可以通過自己的知識來明白哪些是詞，哪些不是詞，但如何讓計算機也能理解？其處理過程就是分詞算法。 與英文相比，中文詞與詞之間沒有分界符，需要人為切分，而且漢語中存在大量歧義現(xiàn)象，對幾個字分詞可能有好多種結(jié)果，因此將中文分詞技術(shù)專門提出來做詳細總結(jié)。,中文分詞方式,單字切分 按照中文一個字、一個字地進行分詞。以這種方式切分出來的詞再進入索引，稱為字索引。 缺點：隨著索引的增大，相應(yīng)索引條目的內(nèi)容會不斷增大，嚴重影響效率。,二分法 二分法是指每兩個字進行一次切分。 該方法完全不考慮語義、語境，機械地對語句進行處理，不是很好的分詞方式。 詞庫分詞 該方法是用一個已經(jīng)建立好的詞的集合（按某種算法）去匹配目標，當遇上集合中已經(jīng)存在的詞時，就將其切分出來，是一種較理想的中文分詞方式。,中文分詞算法,基于字符串匹配的分詞方法 該方法又叫做機械分詞方法，基本思想是：截取一個字符串，把它與詞典中的詞條進行匹配，若在詞典中找到對應(yīng)的詞，該字符串就被識別為一個詞。 按照掃描方向的不同，可分為正向匹配和逆向匹配；按照不同長度優(yōu)先匹配的情況，可分為最大匹配和最小匹配；按照是否與詞性標注過程相結(jié)合，可分為單純分詞方法和分詞與標注相結(jié)合的一體化方法。,正向最大匹配法FMM（Forward Maximum Matching method）,主要思想：選取包含68個漢字的符號串作為最大符號串，把最大符號串與詞典中的單詞條目相匹配，如果不能匹配，就削掉最右邊一個漢字繼續(xù)匹配，直到在詞典中找到相應(yīng)的單詞為止。 正向是指匹配方式從左向右。 例：“計算機科學和工程”,逆向最大匹配法BMM（Backward Maximum Matching method）,其分詞過程與正向最大匹配法相同，不同的是每次是從待處理語料的末尾開始處理，每次匹配不成功時去掉的是前面一個漢字，即匹配方向是從右到左。 FMM方法的錯誤切分率為1/169，BMM方法的精度要高一些，其錯誤切分率為1/245。,雙向匹配法BM（Bi-direction Matching method）,基本原理：分別用FMM法和BMM法進行正向和逆向的掃描和切分，通過比較兩者的切分結(jié)果來決定正確的切分，而且可以識別出分詞中的交叉歧義。但是對于正、逆向的掃描結(jié)果一致但實際切分不正確的字段（如“結(jié)合成分子時”）仍不能正確處理。 缺點：時間復雜度增加，而且詞庫結(jié)構(gòu)比一般的分詞詞庫要復雜很多。,最少匹配算法FWM（Fewest Words Matching method） 該算法實現(xiàn)的分詞結(jié)果中含詞數(shù)最少。 設(shè)立切分標識法 該算法的思想是：優(yōu)先在待分析字符串中識別和切分出一些帶有明顯特征的詞，以這些詞作為斷點，可將原字符串分為較小的串，然后用FMM或BMM法進行細分。 例：“這種設(shè)計方法學的理論，不可能有用”,基于理解的分詞方法,這種分詞方法是通過讓計算機模擬人對句子的理解，達到識別詞的效果。 其基本思想就是在分詞的同時進行句法、語義分析，利用句法信息和語義信息來處理歧義現(xiàn)象。 該分詞方法需要使用大量的語言知識和信息。由于漢語語言知識的籠統(tǒng)、復雜性，難以將各種語言信息組織成機器可直接讀取的形式，因此目前基于理解的分詞系統(tǒng)還處在試驗階段。,基于統(tǒng)計的分詞方法,從形式上看，詞是穩(wěn)定的字的組合，因此在上下文中，相鄰的字同時出現(xiàn)的次數(shù)越多，就越有可能構(gòu)成一個詞。因此字與字相鄰共現(xiàn)的頻率或概率能夠較好地反映成詞的可信度。 于是可以對語料中相鄰共現(xiàn)的各個字的組合的頻度進行統(tǒng)計，計算它們的互現(xiàn)信息?；ガF(xiàn)信息體現(xiàn)了漢字之間結(jié)合關(guān)系的緊密程度。當緊密程度高于某一個閾值時，便可認為此字組可能構(gòu)成了一個詞。,分詞中的難題,歧義識別 歧義是指同樣的一句話，可能有兩種或者更多的切分方法，這是由中文本身的特性形成的。 包括： 交叉歧義，如“表面的”； 組合歧義，如“這個門把手壞了”； 真歧義，如“乒乓球拍賣完了”。,新詞識別,由于中文信息檢索系統(tǒng)中的索引項是基于一定的詞庫構(gòu)建而成的，定期更新，那么對于一些沒有收入詞庫而用戶提交查詢的新詞，檢索系統(tǒng)是無法按照用戶的本意來識別這些新詞的。 人名、機構(gòu)名、地名、產(chǎn)品名、商標名、簡稱、省略語等都可能是新詞，目前新詞識別準確率已經(jīng)成為評價一個分詞系統(tǒng)好壞的重要標志之一。,3.無用詞刪除,在網(wǎng)頁或文檔集合中出現(xiàn)頻率高于80%的單詞通常被稱為無用詞或停用詞（stopword），它們對文檔的含義沒有任何意義，不具有很好的文檔區(qū)分能力，需要被過濾、屏蔽掉。 刪除無用詞，一方面可以減小索引空間，另一方面可以提高檢索精度，但也可能會降低系統(tǒng)的召回率（查全率），使得用戶不能查到自己需要的網(wǎng)頁。,4.詞干提取,詞干是去除單詞的前綴和后綴后剩下的部分。詞干提取就是把同詞干同義的不同詞語中的相同部分提取出來。 優(yōu)點 a.在一定程度上提高信息獲取的性能 b.縮小索引空間的大小 缺點 可能會有勿截，造成詞義的改變，影響查詢的結(jié)果,詞干提取方法,查表法 詞綴刪除法 后繼變化數(shù) N個字符列 應(yīng)用最多的，最實際的詞干提取方法是去除詞綴法。 Porter算法是最著名的詞綴去除方法。,5.索引詞選擇,并不一定對文檔中出現(xiàn)的所有詞條都建立索引，而是選擇一些比較重要的詞條來建立索引。 科技文獻一般由專家來選擇索引詞匯，方法準確，但需消耗大量人力； 另一種可選的方法是通過對文檔的分析來自動選擇索引詞，該方法沒有第一種方法準確，但可由系統(tǒng)自動實現(xiàn)。,6.詞典,詞典是用來根據(jù)詞匯找到對應(yīng)詞匯信息的數(shù)據(jù)匯編。 詞典的主要內(nèi)容 a. 有關(guān)某個領(lǐng)域知識的重要詞匯； b.