1、第11章 搜索引擎,主要內(nèi)容,語(yǔ)言和文字 語(yǔ)法分析 統(tǒng)計(jì)語(yǔ)言分析 中文分詞 網(wǎng)絡(luò)爬蟲(chóng) 文本分類(lèi) 搜索引擎,語(yǔ)言文字,在人類(lèi)文明中，語(yǔ)言文字和數(shù)學(xué)一樣都是信息的載體，但直到半個(gè)世紀(jì)前，香農(nóng)的信息論才把兩者結(jié)合在了一起。 1948年，貝爾實(shí)驗(yàn)室的香農(nóng)發(fā)表了“通信的數(shù)學(xué)原理”，奠定了現(xiàn)代信息理論的基礎(chǔ)。 香農(nóng)（Claude ElwoodShannon，19162001），美國(guó)數(shù)學(xué)家、電子工程師和密碼學(xué)家。,語(yǔ)言文字,古代文字象形文字 中國(guó)：殷墟文化遺址的甲骨文距今約3200年 古埃及：“亞尼的死亡之書(shū)”距今約33003400年,語(yǔ)言文字,古代文字拼音文字 古巴比倫：位于美索不達(dá)米亞平原，現(xiàn)伊拉克境內(nèi)

2、，距今約5000年。 楔形文字：約公元前3200年蘇美爾人發(fā)明了象形文字，后來(lái)發(fā)展、簡(jiǎn)化為楔形文字，常見(jiàn)于考古發(fā)現(xiàn)的大量泥板,語(yǔ)言文字,古代文字拼音文字 公元前七世紀(jì)，希臘人和羅馬人統(tǒng)治埃及，古埃及象形文字失傳，出現(xiàn)拼音文字 羅塞塔石碑：1799年由法軍上尉在埃及的羅塞塔發(fā)現(xiàn)，在戰(zhàn)爭(zhēng)中輾轉(zhuǎn)到英國(guó)，現(xiàn)為大英博物館鎮(zhèn)館之寶。制作于公元前196年，用3種文字刻有古埃及法老托勒密五世詔書(shū)，考古學(xué)家依此對(duì)照解讀失傳千余年的埃及象形文字，現(xiàn)代人得以了解3000多年前的古埃及。,語(yǔ)言文字,古代的計(jì)數(shù)方法 文字和數(shù)字幾乎是同時(shí)出現(xiàn)的 中國(guó)、古羅馬、巴比倫的數(shù)字都使用象形文字（橫、豎、楔形），古印度則使用抽象的

3、符號(hào) 中國(guó)人、印度人發(fā)現(xiàn)了倍數(shù)進(jìn)位制，如中國(guó)的個(gè)十百千萬(wàn)。羅馬人采用加減法進(jìn)位，如IV、XXII 其他進(jìn)制：瑪雅人使用20進(jìn)制；在印度、斯里蘭卡等地曾使用12進(jìn)制，見(jiàn)于混亂的英制（美國(guó)是唯一一個(gè)使用英制的國(guó)家）,語(yǔ)言文字,印歐語(yǔ)系 腓尼基人將楔形文字傳播到希臘后，與古希臘的文字結(jié)合，逐步發(fā)展成為現(xiàn)在的歐亞非大陸體系語(yǔ)言印歐語(yǔ)系 圣經(jīng)：猶太人將創(chuàng)世紀(jì)以來(lái)的歷史記錄在圣經(jīng)中，并廣為傳送。為防止抄錄錯(cuò)誤，發(fā)明了數(shù)字校驗(yàn)碼,語(yǔ)言文字,古文：因書(shū)寫(xiě)困難，不得不簡(jiǎn)化 中國(guó)古文：如詩(shī)經(jīng)、易經(jīng) 西方古文字：如舊約 但語(yǔ)言不是語(yǔ)法： 中國(guó)的白話文形如口語(yǔ)，口語(yǔ)幾千年未變，如嶺南客家話 莎士比亞喜劇的語(yǔ)言不符合語(yǔ)

4、法規(guī)則，但為大家所接受,語(yǔ)法分析,語(yǔ)言的出現(xiàn)實(shí)現(xiàn)了通信，語(yǔ)句是信息的表現(xiàn)形式，文字、數(shù)字是信息的編碼方式，語(yǔ)法規(guī)則是編碼、解碼的算法 1950年，圖靈的“計(jì)算的機(jī)器和智能”就提出了機(jī)器智能（即人工智能）的問(wèn)題，但直到1970年代，隨著統(tǒng)計(jì)語(yǔ)言分析方法的研究，才取得了突破性的成績(jī) 兩個(gè)階段： 5070年代，讓機(jī)器學(xué)習(xí)人類(lèi)智能，分析語(yǔ)法 70年代以后，利用統(tǒng)計(jì)學(xué)規(guī)律,語(yǔ)義分析,早期研究是基于語(yǔ)言的句法分析的，主要考慮語(yǔ)法規(guī)則 例：徐志摩喜歡林徽因。 分析：每個(gè)句子可分為3部分，每個(gè)部分又可以進(jìn)一步分析，構(gòu)成語(yǔ)法分析樹(shù)分析句子的文法規(guī)則叫規(guī)則重寫(xiě),語(yǔ)義分析,重寫(xiě)規(guī)則包括： 句子主語(yǔ) 謂語(yǔ) 句號(hào) 主語(yǔ)

5、名詞 謂語(yǔ)動(dòng)詞 名詞短語(yǔ) 名詞短語(yǔ)名詞 名詞徐志摩 動(dòng)詞喜歡 名詞林徽因 句號(hào)。,語(yǔ)義分析,自然語(yǔ)言處理依靠人工書(shū)寫(xiě)文法規(guī)則，如機(jī)器翻譯公司SysTran，直到2000年后，仍采用人工方法 但復(fù)雜語(yǔ)句的規(guī)則重寫(xiě)困難重重，例：美聯(lián)儲(chǔ)主席本伯南克昨天告訴媒體7000億美元的救助資金將借給上百家銀行、保險(xiǎn)公司和汽車(chē)公司。這個(gè)句子的文法（其他略）為：主語(yǔ)美聯(lián)儲(chǔ)主席本伯南克 謂語(yǔ)昨天告訴媒體7000億美元的救助資金將借給上百家銀行、保險(xiǎn)公司和汽車(chē)公司 句號(hào)。,語(yǔ)法分析,70年代，基于規(guī)則的句法分析走到了盡頭。不僅是因?yàn)橐?guī)則的復(fù)雜性，同時(shí)還要考慮句子的多義性。例如（1966年，明斯基）： The pen

6、is in the box. The box is in the pen. 70年代，IBM賈里尼克領(lǐng)導(dǎo)的小組在研究語(yǔ)音識(shí)別系統(tǒng)時(shí)采用了統(tǒng)計(jì)學(xué)方法，極大地提高了識(shí)別率和速度，促進(jìn)了統(tǒng)計(jì)語(yǔ)言分析的發(fā)展 直到2005年，隨著Google推出基于統(tǒng)計(jì)學(xué)的翻譯系統(tǒng)，SysTran才放棄規(guī)則分析方法,統(tǒng)計(jì)語(yǔ)言分析,例：下面的句子合理嗎？ 美聯(lián)儲(chǔ)主席本伯南克昨天告訴媒體7000億美元的救助資金將借給上百家銀行、保險(xiǎn)公司和汽車(chē)公司。 本伯南克保險(xiǎn)美聯(lián)儲(chǔ)主席告訴昨天上百家7000億媒體美元的資金救助銀行、公司汽車(chē)和公司將借給。 百本伯美席助主司告聯(lián)南克儲(chǔ)和天訴體7000公車(chē)元險(xiǎn)的救億資將美昨借媒給上司銀金家行

7、、保公汽。 句子是否合理取決于語(yǔ)法、語(yǔ)義嗎？ 人類(lèi)智能符合這一規(guī)律，但下面的句子呢？ 乒乓球拍賣(mài)完了。 問(wèn)：“在嗎？”，答：“在?！?統(tǒng)計(jì)語(yǔ)言分析,賈里尼克：語(yǔ)句的合理性取決于它在語(yǔ)言中出現(xiàn)的可能性 語(yǔ)句出現(xiàn)的可能性由該語(yǔ)句在人類(lèi)語(yǔ)言中的出現(xiàn)概率決定，包括口語(yǔ)、文字記錄、文學(xué)、新聞報(bào)道等等 語(yǔ)句1、2、3的概率可能是10-20、10-25、10-80 因此語(yǔ)句1更合理,統(tǒng)計(jì)語(yǔ)言分析,顯然無(wú)法直接統(tǒng)計(jì)句子的出現(xiàn)概率 可采用條件概率：設(shè)語(yǔ)句s由n個(gè)詞（w1、w2、wn）組成，即s=w1w2wn，語(yǔ)句s出現(xiàn)的概率為p(s)=p(w1, w2, . wn)，利用條件概率公式，進(jìn)一步表示為p(s)=p(

8、w1)*p(w2|w1)*p(w3|w1,w2)*p(wn|w1,w2,wn-1)，其中，p(w2|w1)表示已知w1的條件下w2的出現(xiàn)概率若把wi的概率簡(jiǎn)化為只與wi-1有關(guān)，則簡(jiǎn)化為： p(s)=p(w1)*p(w2|w1)*p(w3|w2)*p(wn|wn-1)p(wi|wi-1)可通過(guò)統(tǒng)計(jì)語(yǔ)言中詞wi在wi-1之后的出現(xiàn)頻率獲得 因此，語(yǔ)句的概率可通過(guò)分析構(gòu)成語(yǔ)句的詞匯的條件概率計(jì)算出來(lái),中文分詞,分詞即把語(yǔ)句的詞分割、提取出來(lái) 拼音文字無(wú)需分詞 中文分詞： 基于字典的分詞 按最長(zhǎng)詞匹配 先從左到右、再?gòu)挠业阶蠖畏衷~,例：（1）乒乓球拍賣(mài)完了（2）乒乓球拍賣(mài)完了,中文分詞,統(tǒng)計(jì)學(xué)分詞

9、：先按一般方法分詞，再分析各種分詞方案形成語(yǔ)句的統(tǒng)計(jì)學(xué)概率語(yǔ)句s可有多種分詞方案，比如：SA=A1A2AnSB=B1B2BkSC=C1C2Cm則各種組合的概率為p(SA)、p(SB)、p(SC)若p(SA)p(SB)且p(SA)p(SC)則應(yīng)采用A方案 實(shí)際上，并不窮舉所有分詞方案,網(wǎng)絡(luò)爬蟲(chóng),網(wǎng)絡(luò)爬蟲(chóng)（crawler，spider，robot) 是一種按照一定規(guī)則，自動(dòng)搜索、下載網(wǎng)頁(yè)、提取信息的程序。 網(wǎng)頁(yè)的URL用以標(biāo)識(shí)和供瀏覽器訪問(wèn) 網(wǎng)頁(yè)中存在許多超鏈接，用于實(shí)現(xiàn)向其他網(wǎng)頁(yè)或網(wǎng)站的跳轉(zhuǎn)。相關(guān)聯(lián)的網(wǎng)頁(yè)通過(guò)超鏈接形成一個(gè)網(wǎng)絡(luò),網(wǎng)絡(luò)爬蟲(chóng),圖的遍歷 格尼斯堡七橋 廣度優(yōu)先 北京-天津-石家莊-濟(jì)南

10、-青島-上海-沈陽(yáng)-太原 深度優(yōu)先 北京-天津-濟(jì)南-青島-上海-石家莊-太原-沈陽(yáng) Web是一個(gè)較大（可能無(wú)限）的網(wǎng)，遍歷應(yīng)設(shè)定條件,文本分類(lèi),關(guān)鍵詞 通常，網(wǎng)頁(yè)可以用關(guān)鍵詞標(biāo)出 關(guān)鍵詞權(quán)重用于區(qū)分網(wǎng)頁(yè)的相關(guān)性 不能用關(guān)鍵詞出現(xiàn)的次數(shù)表示相關(guān)性，而常采用“頻率”TF-IDF（即出現(xiàn)次數(shù)除以總字?jǐn)?shù)） “停止詞”（如的、地、得、是等）不予考慮 通用詞（如“應(yīng)用”）比專(zhuān)用詞（如“原子能”）頻率高，因此應(yīng)設(shè)置“權(quán)重”（需要人為設(shè)定） 一般地，如果某關(guān)鍵詞出現(xiàn)次數(shù)很少，但已經(jīng)可以決定相關(guān)性，則權(quán)重應(yīng)較高。反之，則取較低的權(quán)重。,文本分類(lèi),新聞分類(lèi)：將相似的新聞放在一起作為一類(lèi)，以便編輯使用 通常，新聞

11、分類(lèi)不使用關(guān)鍵詞，而直接使用正文中的實(shí)詞（不是虛詞） 新聞中每個(gè)詞的重要性不同，但只要出現(xiàn)幾個(gè)特定的詞就可以確定新聞分類(lèi),文本分類(lèi),新聞分類(lèi) 將新聞涉及的所有詞匯排序構(gòu)成一個(gè)詞匯表（巨大！） 把某篇新聞中的詞匯統(tǒng)計(jì)出TF-IDF（即頻率） 把未出現(xiàn)的詞匯的TF-IDF標(biāo)為0 構(gòu)建一個(gè)“向量”，代表這篇新聞 利用余弦定理計(jì)算兩篇新聞向量的距離（即夾角），用于標(biāo)識(shí)相關(guān)性 將相關(guān)的新聞歸為一類(lèi),文本分類(lèi),新聞分類(lèi) 按主題分類(lèi)：如奧運(yùn)會(huì)、歐洲杯 按詞分類(lèi)：如足球、馬拉松 由于計(jì)算量巨大，不能直接計(jì)算兩篇新聞的向量的距離（大矩陣運(yùn)算）,文本分類(lèi),如果新聞詞有M個(gè)，新聞篇數(shù)為N，則A是一MxN的矩陣，其元

12、素為某篇文章中某個(gè)詞的TF-IDF 利用矩陣的奇異值運(yùn)算，可將A分解為3個(gè)矩陣的積，即A=XBY 這里，把所有新聞詞分為若干關(guān)鍵詞類(lèi)，矩陣X的元素為某個(gè)新聞詞與某個(gè)關(guān)鍵詞類(lèi)的相關(guān)性。把所有新聞分為若干主題類(lèi)，矩陣Y的元素為某篇新聞與某個(gè)主題類(lèi)的相關(guān)性。B為關(guān)鍵詞類(lèi)和主題詞類(lèi)的關(guān)聯(lián)矩陣，為一對(duì)角矩陣這樣，要處理的矩陣運(yùn)算就大大簡(jiǎn)化了,搜索引擎,搜索引擎的發(fā)展 1990年，加拿大麥吉爾大學(xué)開(kāi)發(fā)出Archie，實(shí)現(xiàn)了對(duì)FTP文件的搜索 1993年，斯坦福大學(xué)學(xué)生開(kāi)發(fā)了Excite系統(tǒng)實(shí)現(xiàn)了Web信息檢索 1994年，斯坦福大學(xué)、美籍華人楊致遠(yuǎn)和David Filo共同創(chuàng)辦了Yahoo！，支持目錄搜索。Yahoo！采用手工編錄，準(zhǔn)確率高，速度快 1994年，WebCrawler面世，支持全文檢索 1995年，元搜索引擎出現(xiàn) 1996年，Sohu；1998年，Google；2000年，百度,搜索引擎,搜索引擎數(shù)據(jù)庫(kù) 網(wǎng)頁(yè)的存儲(chǔ)：網(wǎng)絡(luò)爬蟲(chóng)下載的網(wǎng)頁(yè)，按一定規(guī)則存放在數(shù)據(jù)庫(kù)中 數(shù)據(jù)庫(kù)索引：數(shù)據(jù)庫(kù)中存放了萬(wàn)億以上的網(wǎng)頁(yè)，要進(jìn)行快速的查詢(xún)，就要依靠數(shù)據(jù)庫(kù)索引 搜索引擎數(shù)據(jù)庫(kù)的索引 一個(gè)較簡(jiǎn)單的方法是采用二進(jìn)制串索引，對(duì)于每一個(gè)關(guān)鍵詞，如果出現(xiàn)在某個(gè)網(wǎng)頁(yè)中就記為