搜索引擎關(guān)鍵技術(shù)文本處理.ppt

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