中級(jí)管工計(jì)算機(jī)適用電子商務(wù)技術(shù)

電子商務(wù)技術(shù)張文新

經(jīng)濟(jì)管理樓1213室講義大綱第一部分：理論認(rèn)識(shí)第01講：電子商務(wù)的概念和本質(zhì)第02講：電子商務(wù)產(chǎn)生與發(fā)展第03講：電子商務(wù)系統(tǒng)的運(yùn)營（1）-技術(shù)視角第04講：電子商務(wù)系統(tǒng)的運(yùn)營（2）-管理視角第二部分：技術(shù)解析第05講：商品展示技術(shù)第06講：搜索引擎技術(shù)第07講：商品推薦技術(shù)第08講：物流規(guī)劃技術(shù)第09講：物流信息集成技術(shù)第10講：物流運(yùn)營調(diào)度技術(shù)第11講：電子支付技術(shù)第12講：電子商務(wù)交易安全技術(shù)第三部分：案例探究第13講：C2C模式-淘寶網(wǎng)交易平臺(tái)第14講：B2C模式-圖書、服裝與消費(fèi)電子類電子商務(wù)第15講：B2B模式-鋼鐵與汽車產(chǎn)業(yè)電子商務(wù)第06講

搜索引擎技術(shù)→爬蟲-索引-排序內(nèi)容提要6.0-引言6.1-自然語言處理的機(jī)器方法6.2-網(wǎng)絡(luò)爬蟲技術(shù)6.3-網(wǎng)頁信息索引技術(shù)6.4-搜索結(jié)果排序技術(shù)6.5-相關(guān)研究趨勢(shì)本講小結(jié)6.0-引言谷歌面試產(chǎn)品經(jīng)理的一道題如何向你的奶奶解釋什么是互聯(lián)網(wǎng)搜索引擎？整個(gè)互聯(lián)網(wǎng)就像一個(gè)巨大的圖書館；一個(gè)網(wǎng)頁就像圖書館里所藏的一本書；······6.0-引言搜索引擎的基本原理搜集整理服務(wù)搜集：批量搜集，增量式搜集；搜集目標(biāo)，搜集策略整理：關(guān)鍵詞提??；重復(fù)網(wǎng)頁消除；鏈接分析；索引服務(wù):查詢方式和匹配；結(jié)果排序；文檔摘要搜索引擎三段式工作流程6.0-引言搜索引擎的基本原理一般的搜索引擎系統(tǒng)流程6.0-引言搜索引擎的基本原理一個(gè)實(shí)際的搜索引擎系統(tǒng)流程-天網(wǎng)搜索天網(wǎng)搜索-北京大學(xué)網(wǎng)絡(luò)實(shí)驗(yàn)室6.0-引言搜索引擎的關(guān)鍵技術(shù)網(wǎng)絡(luò)爬蟲（Spider,Robot,Crawler）索引技術(shù)（中文分詞）動(dòng)態(tài)搜索結(jié)果排序服務(wù)（PageRank)三大技術(shù)的基礎(chǔ)性技術(shù)：自然語言處理的機(jī)器方法——統(tǒng)計(jì)語言模型6.1-自然語言處理的機(jī)器方法計(jì)算機(jī)如何處理自然語言從規(guī)則到統(tǒng)計(jì)從1950’到1970’早期的20年，科學(xué)家對(duì)計(jì)算機(jī)處理自然語言的認(rèn)識(shí)都局限在人類學(xué)習(xí)語言的方式上；讓計(jì)算機(jī)像人一樣理解詞性、構(gòu)詞法和語法規(guī)則從而形成一個(gè)語法分析器，遇到了極大困難，因?yàn)樽匀徽Z言在演變的過程中，產(chǎn)生了詞義和上下文相關(guān)的特性：Thepenisinthebox.Theboxisinthepen.6.1-自然語言處理的機(jī)器方法計(jì)算機(jī)如何處理自然語言從規(guī)則到統(tǒng)計(jì)1970年以后，統(tǒng)計(jì)語言學(xué)的出現(xiàn)，使計(jì)算機(jī)處理自然語言的技術(shù)路線發(fā)生了重大轉(zhuǎn)變；關(guān)鍵人物：弗里德里克·賈里尼克（FrederickJelinek）和他領(lǐng)導(dǎo)的IBM化生實(shí)驗(yàn)室.統(tǒng)計(jì)語言模型：例：校長宣布將100萬獎(jiǎng)學(xué)金頒發(fā)給100名學(xué)生；

校長宣布給100名學(xué)生將100萬獎(jiǎng)學(xué)金頒發(fā)；100名學(xué)生宣布將100萬獎(jiǎng)學(xué)金頒發(fā)給校長。6.1-自然語言處理的機(jī)器方法計(jì)算機(jī)如何處理自然語言統(tǒng)計(jì)語言模型：判定一句話是否合理，看它出現(xiàn)的可能性大小如何？可能性可以用概率來衡量；假定表示某一個(gè)有意義的句子，由一連串特定順序排列的詞組成；求:

利用條件概率公式：6.1-自然語言處理的機(jī)器方法計(jì)算機(jī)如何處理自然語言統(tǒng)計(jì)語言模型：根據(jù)馬爾可夫假設(shè)：如何計(jì)算根據(jù)條件概率定義：求概率：和6.1-自然語言處理的機(jī)器方法計(jì)算機(jī)如何處理自然語言統(tǒng)計(jì)語言模型：求概率：和借助語料庫，求這對(duì)詞在統(tǒng)計(jì)的文本中前后相鄰出現(xiàn)的次數(shù)：,以及本身在同樣的文本中出現(xiàn)的次數(shù)：;計(jì)算相對(duì)頻度：6.1-自然語言處理的機(jī)器方法計(jì)算機(jī)如何處理自然語言統(tǒng)計(jì)語言模型：計(jì)算相對(duì)頻度：根據(jù)大數(shù)定理，只要統(tǒng)計(jì)量足夠，相對(duì)頻度就等于概率，既有：則有：6.1-自然語言處理的機(jī)器方法計(jì)算機(jī)如何處理自然語言統(tǒng)計(jì)語言模型的工程引申：馬爾可夫假設(shè)句子中的每個(gè)詞只與它前面的詞有關(guān)，而和更前面的詞無關(guān)了，這似乎太簡(jiǎn)化了，更普遍的假設(shè)應(yīng)該是某個(gè)詞與前面的若干次有關(guān)；假設(shè)文本中的每個(gè)詞和前面?zhèn)€詞有關(guān)，因此，當(dāng)前詞的概率取決于前面?zhèn)€詞的概率：因此：這種假設(shè)稱為階馬爾可夫假設(shè)，對(duì)應(yīng)的語言模型為元模型，實(shí)際應(yīng)用中最多的是的三元模型，更高階的模型很少使用；6.1-自然語言處理的機(jī)器方法計(jì)算機(jī)如何處理自然語言統(tǒng)計(jì)語言模型的工程引申：為什么一般取值這么小呢？

元模型的大?。臻g復(fù)雜度）幾乎是的指數(shù)函數(shù)，即：

這里是一種語言詞典的詞匯量，一般在幾萬到幾十萬個(gè)；實(shí)際上，當(dāng)從1到2，再從2到3時(shí)，模型的效果上升顯著，而當(dāng)從3到4時(shí)，效果提升也不很顯著了，除非不惜資源為了追求極致，一般很少使用四元以上的模型；Google的羅塞塔翻譯和語言搜索系統(tǒng)，使用的是四元模型，該模型存儲(chǔ)于500臺(tái)以上的服務(wù)器中。

6.1-自然語言處理的機(jī)器方法計(jì)算機(jī)如何處理自然語言統(tǒng)計(jì)語言模型的工程引申：模型的訓(xùn)練、零概率和平滑問題

怎么辦？是否意味著：

怎么辦？根據(jù)大數(shù)定理增加數(shù)據(jù)量是否可行？漢語的詞匯量大約是20萬數(shù)量級(jí)，訓(xùn)練一個(gè)三元模型就有：2000003=8×1015個(gè)不同的參數(shù)，到哪里找這么大的文本庫？互聯(lián)網(wǎng)上全部約100億個(gè)網(wǎng)頁，每個(gè)網(wǎng)頁按1000字計(jì)算，依然只有1013，如果用直接的比值計(jì)算概率，大部分條件概率依然是零；6.1-自然語言處理的機(jī)器方法計(jì)算機(jī)如何處理自然語言統(tǒng)計(jì)語言模型的工程引申：解決方法：古德-圖靈估計(jì)；原理：對(duì)于沒有看見的事件，我們不能認(rèn)為它發(fā)生的概率就是零；將所看見的發(fā)生的事件概率調(diào)小一點(diǎn)，至于小多少，要根據(jù)“越是不可信的統(tǒng)計(jì)折扣越多”方法進(jìn)行?？匆姷氖录母怕士偭靠匆姷氖录母怕士偭课纯匆姷氖录母怕士偭?.1-自然語言處理的機(jī)器方法計(jì)算機(jī)如何處理自然語言統(tǒng)計(jì)語言模型的工程引申：解決方法：古德-圖靈估計(jì)；假定語料庫中出現(xiàn)次的詞有個(gè)，未出現(xiàn)的詞的數(shù)量為，語料庫的大小為，那么：

出現(xiàn)次的詞在整個(gè)語料庫中的相對(duì)頻度則是：；當(dāng)比較小時(shí)，它的統(tǒng)計(jì)可能不可靠，因此，計(jì)算概率時(shí)要使用一個(gè)更小一點(diǎn)的數(shù)，假設(shè)是，古德-圖靈給出計(jì)算公式：6.1-自然語言處理的機(jī)器方法計(jì)算機(jī)如何處理自然語言統(tǒng)計(jì)語言模型的工程引申：解決方法：古德-圖靈估計(jì)；一般說來，越大，越小，即；因此，一般情況下，；，這樣給未出現(xiàn)的詞賦予一個(gè)很小的非零值，從而解決了零概率問題。實(shí)際自然語言工程應(yīng)用中，一般設(shè)定一個(gè)閾值，出現(xiàn)次數(shù)超過閾值的詞，頻率不下調(diào)；出現(xiàn)次數(shù)低于閾值的詞才下調(diào)頻率，下調(diào)得到的頻率總和給未出現(xiàn)的詞。這樣所有詞的概率估計(jì)就平滑了。6.1-自然語言處理的機(jī)器方法計(jì)算機(jī)如何處理自然語言統(tǒng)計(jì)語言模型的工程引申：關(guān)于和的關(guān)系，可以參考Zipf定律：哈佛大學(xué)的語言學(xué)專家Zipf在研究英文單詞出現(xiàn)的頻率時(shí),發(fā)現(xiàn)如果把單詞出現(xiàn)的頻率按由大到小的順序排列,則每個(gè)單詞出現(xiàn)的頻率與它的名次的常數(shù)次冪存在簡(jiǎn)單的反比關(guān)系，這種分布就稱為Zipf定律。圖：一個(gè)較小語料庫中出現(xiàn)r次詞的數(shù)量Nr和r的關(guān)系6.1-自然語言處理的機(jī)器方法計(jì)算機(jī)如何處理自然語言統(tǒng)計(jì)語言模型的工程引申：對(duì)于二元組的條件概率估計(jì)也可以做同樣的處理：通過前一個(gè)詞預(yù)測(cè)后一個(gè)詞時(shí)，所有可能情況的條件概率總和為1，即：對(duì)于出現(xiàn)次數(shù)非常少的二元組，它們出現(xiàn)的次數(shù)需按照古德-圖靈的方法打折扣，這樣，同時(shí)意味著有一部分概率量沒有分配出去，留給了沒有看到的二元組

，基于這種思想，估計(jì)二元模型的概率公式如下：6.1-自然語言處理的機(jī)器方法計(jì)算機(jī)如何處理自然語言統(tǒng)計(jì)語言模型的工程引申：估計(jì)二元模型的概率公式如下：其中是一個(gè)閾值，一般在8-10左右，函數(shù)表示經(jīng)過古德-圖靈估計(jì)后的頻度，而這種平滑方法，有IBM科學(xué)家卡茨（S.M.Katz）提出,

故稱：卡茨退避法（Katzbackoff）6.1-自然語言處理的機(jī)器方法計(jì)算機(jī)如何處理自然語言統(tǒng)計(jì)語言模型的工程引申：語料庫的選取問題：騰訊搜索最早用《人民日?qǐng)?bào)》；后來使用網(wǎng)頁數(shù)據(jù)。6.2-網(wǎng)絡(luò)爬蟲技術(shù)網(wǎng)絡(luò)爬蟲（Spider,Robot,Crawler）對(duì)URL鏈接進(jìn)行遍歷基本數(shù)據(jù)結(jié)構(gòu)一個(gè)待擴(kuò)展的URL表一個(gè)已經(jīng)訪問過的URL地址表TODO表Visited表初始URL地址解析URL新解析出的URL圖：網(wǎng)絡(luò)蜘蛛基本數(shù)據(jù)結(jié)構(gòu)圖6.2-網(wǎng)絡(luò)爬蟲技術(shù)網(wǎng)絡(luò)爬蟲（Spider,Robot,Crawler）遍歷URL地址遍歷的策略廣度優(yōu)先(BFS,Breadth-FirstSearch)深度優(yōu)先(DFS,Depth-FirstSearch)ABCDGEFHIA→B,C,D,E,F→H,G→IA→F→GE→H→I······6.2-網(wǎng)絡(luò)爬蟲技術(shù)網(wǎng)絡(luò)爬蟲（Spider,Robot,Crawler）提取文檔中的文本內(nèi)容（網(wǎng)頁結(jié)構(gòu)化信息抽?。〩TML文件中提取文本識(shí)別網(wǎng)頁的編碼STEP-1:從Web服務(wù)器返回的contenttype中提取編碼；STEP-2:從網(wǎng)頁的Meta信息中識(shí)別字符編碼；STEP-3:從返回流的二進(jìn)制格式判斷，確定網(wǎng)頁語言。對(duì)HTML文件進(jìn)行解析（識(shí)別三類節(jié)點(diǎn)）RemarkNode（注釋）TagNode（標(biāo)簽）TextNode（文本）6.2-網(wǎng)絡(luò)爬蟲技術(shù)網(wǎng)絡(luò)爬蟲（Spider,Robot,Crawler）提取文檔中的文本內(nèi)容（網(wǎng)頁結(jié)構(gòu)化信息抽?。〩TML文件中提取文本（續(xù)）結(jié)構(gòu)化信息提取DOM（文檔對(duì)象模型）結(jié)構(gòu)HTML掃描器例如：<imgwidth=“”;height=“”;src=“123.jpg”>Node.getAttributes().getNamedItem(“src”)參考NekoHTML（）網(wǎng)頁去噪網(wǎng)頁結(jié)構(gòu)相似度計(jì)算6.2-網(wǎng)絡(luò)爬蟲技術(shù)網(wǎng)絡(luò)爬蟲DOM樹<Bodybgcolor=WHITE><Tablewidth=800height=200></Table><IMGsrc=“image.gif”width=800><Tablebgcolor=RED>

······</Table></Body>BODYTableIMGTableBODYbgcolor=WHITEwidth=800width=800圖：DOM樹6.2-網(wǎng)絡(luò)爬蟲技術(shù)網(wǎng)絡(luò)爬蟲提取文檔中的文本內(nèi)容（網(wǎng)頁結(jié)構(gòu)化信息抽?。〩TML文件中提取文本（續(xù)）網(wǎng)頁結(jié)構(gòu)相似度計(jì)算自動(dòng)提取結(jié)構(gòu)化信息的關(guān)鍵是：“從同樣類型的實(shí)例中發(fā)現(xiàn)編碼模板”。計(jì)算兩個(gè)網(wǎng)頁的結(jié)構(gòu)相似度方法一：從HTML編碼字符串檢測(cè)重復(fù)模式，檢測(cè)方法有：字符串編輯距離和樹編輯距離6.2-網(wǎng)絡(luò)爬蟲技術(shù)網(wǎng)絡(luò)爬蟲HTML文件中提取文本（續(xù)）正文提取STEP-1:根據(jù)正文特征進(jìn)行網(wǎng)頁去噪正文詳細(xì)頁面的特征：文字較多，有明顯段落，標(biāo)點(diǎn)符號(hào)較多，URL較長，鏈接較少；計(jì)算節(jié)點(diǎn)的“鏈接文字比”=“節(jié)點(diǎn)下鏈接數(shù)”/“節(jié)點(diǎn)下文字?jǐn)?shù)”刪除“鏈接文字比”大于某個(gè)閾值的節(jié)點(diǎn)；STEP-2:網(wǎng)頁鏈接中錨點(diǎn)文本（網(wǎng)頁標(biāo)題）與網(wǎng)頁正文關(guān)系分析STEP-3:自動(dòng)模板6.2-網(wǎng)絡(luò)爬蟲技術(shù)網(wǎng)絡(luò)爬蟲構(gòu)建網(wǎng)絡(luò)爬蟲的工程要點(diǎn)1.BFS還是DFS?如何在有限的時(shí)間內(nèi)最多地爬下最重要的網(wǎng)頁？爬蟲的調(diào)度程序：先爬哪個(gè)網(wǎng)頁？后爬哪個(gè)網(wǎng)頁？爬蟲下載服務(wù)器和網(wǎng)站服務(wù)器的“握手”成本問題。6.2-網(wǎng)絡(luò)爬蟲技術(shù)網(wǎng)絡(luò)爬蟲構(gòu)建網(wǎng)絡(luò)爬蟲的工程要點(diǎn)1.BFS還是DFS?2.頁面分析和URL提取直接用HTML語言書寫網(wǎng)頁；用腳本語言（如javaScript）生成的網(wǎng)頁，要模擬瀏覽器運(yùn)行一個(gè)網(wǎng)頁，腳本語言不規(guī)范的問題；6.2-網(wǎng)絡(luò)爬蟲技術(shù)網(wǎng)絡(luò)爬蟲構(gòu)建網(wǎng)絡(luò)爬蟲的工程要點(diǎn)1.BFS還是DFS?2.頁面分析和URL提取3.已經(jīng)下載過的URL的記錄問題一個(gè)網(wǎng)頁可能被多個(gè)超鏈接所指向，避免一個(gè)網(wǎng)頁被多次下載問題；借助哈希表（HashTable）；一臺(tái)服務(wù)器維護(hù)一張哈希表，當(dāng)哈希表大到一臺(tái)服務(wù)器存儲(chǔ)不下怎么辦？多臺(tái)服務(wù)器同時(shí)訪問哈希表的通訊瓶頸問題。6.3-網(wǎng)頁信息索引技術(shù)Google的搜索請(qǐng)求響應(yīng)邏輯6.3-網(wǎng)頁信息索引技術(shù)搜索引擎的關(guān)鍵技術(shù)中文分詞兩類方法：“機(jī)械匹配法”和“統(tǒng)計(jì)法”機(jī)械法：最大匹配法利用正向或反向或雙向最大匹配的方法來分詞；借助標(biāo)準(zhǔn)的詞典搜索詞典統(tǒng)計(jì)法：最大概率分詞法一個(gè)待切分的漢字串可能包含多種分詞結(jié)果將其中概率最大的那個(gè)作為該字符串的分詞結(jié)果6.3-網(wǎng)頁信息索引技術(shù)中文分詞機(jī)械法：最大匹配法例：“發(fā)展中國家”匹配算法數(shù)字搜索樹Trie(三叉搜索樹)6.3-網(wǎng)頁信息索引技術(shù)數(shù)字搜索樹例：“發(fā)展中國家”搜索最大高度是詞典中最長詞的長度；每個(gè)節(jié)點(diǎn)都需要消耗很多內(nèi)存；發(fā)財(cái)表展意中達(dá)國家見6.3-網(wǎng)頁信息索引技術(shù)Trie樹Trie樹，又稱字典樹，單詞查找樹。它來源于retrieval（檢索）中取中間四個(gè)字符構(gòu)成；用于存儲(chǔ)大量的字符串以便支持快速模式匹配。主要應(yīng)用在信息檢索領(lǐng)域。6.3-網(wǎng)頁信息索引技術(shù)Trie樹標(biāo)準(zhǔn)Trie樹的結(jié)構(gòu)：所有含有公共前綴的字符串將掛在樹中同一個(gè)結(jié)點(diǎn)下。實(shí)際上trie簡(jiǎn)明的存儲(chǔ)了存在于串集合中的所有公共前綴。假如有這樣一個(gè)字符串集合X{bear,bell,bid,bull,buy,sell,stock,stop}。它的標(biāo)準(zhǔn)Trie樹如下圖：6.3-網(wǎng)頁信息索引技術(shù)標(biāo)準(zhǔn)Trie樹的查找對(duì)于英文單詞的查找，可以在內(nèi)部結(jié)點(diǎn)中建立26個(gè)元素組成的指針數(shù)組。查找過程：假如我們要在上面那棵Trie中查找字符串bull(b-u-l-l)。(1)在root結(jié)點(diǎn)中查找第('b'-'a'=1)號(hào)子指針，發(fā)現(xiàn)該指針不為空，則定位到第1號(hào)子結(jié)點(diǎn)處——b結(jié)點(diǎn)。(2)在b結(jié)點(diǎn)中查找第('u'-'a'=20)號(hào)子指針，發(fā)現(xiàn)該指針不為空，則定位到第20號(hào)子結(jié)點(diǎn)處——u結(jié)點(diǎn)。(3)...一直查找到葉子結(jié)點(diǎn)出現(xiàn)特殊字符'$'位置，表示找到了bull字符串如果在查找過程中終止于內(nèi)部結(jié)點(diǎn)，則表示沒有找到待查找字符串。

6.3-網(wǎng)頁信息索引技術(shù)中文詞語的標(biāo)準(zhǔn)Trie樹由于中文的字遠(yuǎn)比英文的26個(gè)字母多的多。因此對(duì)于trie樹的內(nèi)部結(jié)點(diǎn)，不可能用一個(gè)26位的數(shù)組來存儲(chǔ)指針。如果每個(gè)結(jié)點(diǎn)都開辟幾萬個(gè)中國字的指針空間。不僅內(nèi)存消耗過大，就連磁盤也消耗很大。一般可以采取這樣種措施：(1)以詞語中相同的第一個(gè)字為根組成一棵樹。這樣的話，一個(gè)中文詞匯的集合就可以構(gòu)成一片Trie森林。這片森林都存儲(chǔ)在磁盤上。森林的root中的字和root所在磁盤的位置都記錄在一張以Unicode碼值排序的有序字表中。字表可以存放在內(nèi)存里。

(2)內(nèi)部結(jié)點(diǎn)的指針用可變長數(shù)組存儲(chǔ)。

6.3-網(wǎng)頁信息索引技術(shù)中文詞語的標(biāo)準(zhǔn)Trie樹特點(diǎn)：由于中文詞語很少操作4個(gè)字的，因此Trie樹的高度不長。查找的時(shí)間主要耗費(fèi)在內(nèi)部結(jié)點(diǎn)指針的查找。將指向字的指針按照字的Unicode碼值排序，然后加載進(jìn)內(nèi)存以后通過二分查找能夠提高效率。6.3-網(wǎng)頁信息索引技術(shù)中文詞語的標(biāo)準(zhǔn)Trie樹標(biāo)準(zhǔn)Trie樹的應(yīng)用和優(yōu)缺點(diǎn)(1)全字匹配：確定待查字串是否與集合的一個(gè)單詞完全匹配。(2)前綴匹配：查找集合中以匹配字為前綴的所有串。6.3-網(wǎng)頁信息索引技術(shù)中文索引的關(guān)鍵技術(shù)中文分詞兩類方法：“機(jī)械匹配法”和“統(tǒng)計(jì)法”機(jī)械匹配法：最大匹配法統(tǒng)計(jì)法：最大概率分詞法一個(gè)待切分的漢字串可能包含多種分詞結(jié)果將其中概率最大的那個(gè)作為該字符串的分詞結(jié)果6.3-網(wǎng)頁信息索引技術(shù)中文索引的關(guān)鍵技術(shù)中文分詞統(tǒng)計(jì)法：最大概率分詞法有意見分岐（1）有/意見/分歧（2）有意/見/分歧6.3-網(wǎng)頁信息索引技術(shù)中文索引的關(guān)鍵技術(shù)中文分詞統(tǒng)計(jì)法：最大概率分詞法有意見分岐W1:有/意見/分歧W2:有意/見/分歧S:有意見分歧分別計(jì)算：P(W1∣S)和P(W2∣S)6.3-網(wǎng)頁信息索引技術(shù)中文索引的關(guān)鍵技術(shù)中文分詞統(tǒng)計(jì)法：最大概率分詞法有意見分岐要計(jì)算P(W1∣S)和P(W2∣S)，先計(jì)算：P(W∣S)P(W∣S)=P(S∣W)×P(W)P(S)假設(shè)：每個(gè)詞之間的概率是上下文無關(guān)的，則：≈P(W)P(W∣S)=P(S∣W)×P(W)P(S)6.3-網(wǎng)頁信息索引技術(shù)中文索引的關(guān)鍵技術(shù)中文分詞統(tǒng)計(jì)法：最大概率分詞法有意見分岐P(W)=P(W1，W2,···，Wi)≈P(W1)×P(W2)×···×P(Wi)P(Wi)=Wi在語料庫中出現(xiàn)的次數(shù)n語料庫中的總詞數(shù)N6.3-網(wǎng)頁信息索引技術(shù)中文索引的關(guān)鍵技術(shù)中文分詞統(tǒng)計(jì)法：最大概率分詞法有意見分岐表：詞語概率表詞語概率······有0.0180有意0.0005意見0.0010見0.0002分歧0.0001······P(W1)=P(有)×P(意見)×P(分歧)=1.8×10-9P(W2)=P(有意)×P(見)×P(分歧)=1.0×10-11可得：P(W1)>P(W2)6.3-網(wǎng)頁信息索引技術(shù)中文分詞問題：比較計(jì)算出詞與詞之間組合的概率差異后，對(duì)于一個(gè)待分詞的詞串，如何盡快找到最佳的分詞路徑呢？最佳（概率最大）分詞路徑“左鄰詞”：對(duì)字串從左到右進(jìn)行掃描，可以得到W1,W2,…，Wi-1,Wi,…Wn；等若干候選詞，如果Wi-1的尾字與Wi

的首字鄰接，就稱Wi-1為Wi

的左鄰詞?！白罴炎筻徳~”：如果某個(gè)候選詞Wi有若干個(gè)左鄰詞Wj,Wk,…等

，其中累計(jì)概率最大的候選詞稱為Wi的最佳左鄰詞。有意見分岐P’(Wi)=P’(Wi-1)×P(Wi)6.3-網(wǎng)頁信息索引技術(shù)中文分詞問題：根據(jù)以上數(shù)學(xué)原理，如何開發(fā)一個(gè)最大概率分詞算法呢？最大概率分詞算法描述STEP-1:對(duì)一個(gè)待分詞的字串S，按照從左到右的順序取出全部候選詞W1,W2,…，Wi,…Wn；STEP-2:到詞典中查出每個(gè)候選詞的概率值P(Wi)，并記錄候選詞的全部左鄰詞；STEP-3:按照

計(jì)算每個(gè)候選詞的累積概率，同時(shí)比較得到每個(gè)候選詞的最佳左鄰詞；STEP-4:如果當(dāng)前詞Wn是字串S的尾詞，且累計(jì)概率；P’(Wn)最大，則Wn就是S的終點(diǎn)詞；STEP-5:從Wn開始，按照從右到左的順序，依次將每個(gè)詞的最佳左鄰詞輸出，即為S的分詞結(jié)果。P’(Wi)=P’(Wi-1)×P(Wi)6.3-網(wǎng)頁信息索引技術(shù)中文分詞最佳（概率最大）分詞路徑計(jì)算示例：分析上述“有意見分歧”字符串；“分歧”有兩個(gè)左鄰詞有“見”和“意見”如何確定其最佳左鄰詞呢？因此“意見”是“分歧”的最佳左鄰詞因?yàn)椤胺制纭笔俏苍~，分詞過程結(jié)束。結(jié)果：“有”-“意見”-“分歧”有意見分岐詞語概率······有0.0180有意0.0005意見0.0010見0.0002分歧0.0001······P’(有)=P

(有)=0.0180P’(意見)=P’(有)×P(意見)=0.0180×0.0010=1.8×10-5P’(見)=P’(有意)×P(見)=0.0005×0.0002=1.0×10-7P’(有意)=P

(有意)=0.0005P’(分歧)=P’(見)×P(分歧)=1.0×10-7×0.0001=1.0×10-11P’(意見)=1.8×10-5P’(見)=1.0×10-7計(jì)算比較：6.3-網(wǎng)頁信息索引技術(shù)中文分詞進(jìn)一步深入探討的問題：新詞如何發(fā)現(xiàn)？詞庫如何補(bǔ)充？詞性如何區(qū)分并標(biāo)注？6.4-搜索結(jié)果排序技術(shù)搜索結(jié)果排序技術(shù)為什么要研究搜索結(jié)果排序技術(shù)以百度為例：搜索引擎里每天有400多萬被檢索的關(guān)鍵詞 （根據(jù)李彥宏報(bào)告的百度狀況）用戶每天使用到的被索引的頁面數(shù)為2400萬個(gè)左右在百度的平均更新周期（1個(gè)月）內(nèi)，用戶共可能訪問到的頁面總數(shù)為7.2億個(gè)。沒有人需要這么多信息！給我重要的！不重要的呢？把最重要的排在前面！6.4-搜索結(jié)果排序技術(shù)數(shù)據(jù)引自：[AdmitSinghal,GoogleInc.SIGIR’05keynotespeech]Google的客戶請(qǐng)求量與頁面處理量6.4-搜索結(jié)果排序技術(shù)搜索結(jié)果排序技術(shù)為什么要研究搜索結(jié)果排序技術(shù)沒有人需要這么多信息！給我做重要的！不重要的呢？把最重要的排在前面！搜索引擎何時(shí)做這種排序工作？6.4-搜索結(jié)果排序技術(shù)頁面質(zhì)量評(píng)估的過程應(yīng)當(dāng)

是查詢無關(guān)完成的Google的頁面排序機(jī)制6.4-搜索結(jié)果排序技術(shù)搜索結(jié)果排序技術(shù)普通頁面高質(zhì)量索引頁面質(zhì)量評(píng)價(jià)算法搜索引擎系統(tǒng)結(jié)果查詢反饋頁面質(zhì)量評(píng)估算法作為搜索引擎層次索引機(jī)制的基礎(chǔ)6.4-搜索結(jié)果排序技術(shù)搜索結(jié)果排序技術(shù)頁面質(zhì)量評(píng)估技術(shù)宏觀粒度的質(zhì)量評(píng)估去除無用頁面/定位有用頁面清理“全局垃圾”微觀粒度的質(zhì)量評(píng)估去除頁面中的無用部分/找出頁面中最有用的部分清理“局部垃圾”6.4-搜索結(jié)果排序技術(shù)搜索結(jié)果排序技術(shù)宏觀粒度的頁面質(zhì)量評(píng)估目的：找出對(duì)用戶檢索信息有用的頁面當(dāng)前的研究重點(diǎn)：Web鏈接結(jié)構(gòu)分析如果存在超鏈接L從頁面P(source)指向頁面P(destiny)，則P(source)與P(destiny)之間滿足： 假設(shè)1：（內(nèi)容推薦假設(shè)）頁面P(source)的作者推薦頁面P(destiny)的內(nèi)容，且利用L的鏈接文本內(nèi)容對(duì)P(destiny)進(jìn)行描述。 假設(shè)2：（主題相關(guān)假設(shè)）被超鏈接連接的兩個(gè)頁面P(source)與P(destiny)比隨機(jī)抽取的兩個(gè)頁面有更大的概率有內(nèi)容相關(guān)性。PageRank（Google）,HITS（Kleinberg.）及眾多的改進(jìn)算法6.4-搜索結(jié)果排序技術(shù)搜索結(jié)果排序技術(shù)微觀粒度的頁面質(zhì)量評(píng)估目的：找出對(duì)用戶檢索信息有用的頁面的某個(gè)部分去除特定垃圾信息（利用機(jī)器學(xué)習(xí)方法和一定量的訓(xùn)練）去除廣告條去除頁面中的無關(guān)鏈接與垃圾鏈接頁面分塊模型依據(jù)語料統(tǒng)計(jì)信息計(jì)算頁面塊的信息量基于模板頻度檢測(cè)構(gòu)建站點(diǎn)模板基于頁面塊的絕對(duì)位置和機(jī)器學(xué)習(xí)方法計(jì)算塊的重要性6.4-搜索結(jié)果排序技術(shù)微觀粒度的質(zhì)量評(píng)估示例（頁面分塊）6.4-搜索結(jié)果排序技術(shù)搜索結(jié)果排序技術(shù)宏觀粒度的頁面質(zhì)量評(píng)估PageRank（Google）:網(wǎng)頁本身的質(zhì)量TF-IDF：網(wǎng)頁和查詢的相關(guān)性6.4-搜索結(jié)果排序技術(shù)搜索結(jié)果排序技術(shù)宏觀粒度的頁面質(zhì)量評(píng)估PageRank（Google）PageRank是著名網(wǎng)絡(luò)搜索引擎Google用于評(píng)測(cè)一個(gè)網(wǎng)頁“重要性”或“影響力”的一種方法；PageRank算法中使用的數(shù)學(xué)知識(shí)包括：正規(guī)矩陣性質(zhì)、特征值和特征向量、冪迭代算法等；PageRank得分是介于0和10之間的一個(gè)數(shù)，得分越大表示網(wǎng)頁越重要。6.4-搜索結(jié)果排序技術(shù)PageRank計(jì)算原理基于“從許多優(yōu)質(zhì)的網(wǎng)頁鏈接過來的網(wǎng)頁，必定還是優(yōu)質(zhì)網(wǎng)頁”的回歸關(guān)系，來判定所有網(wǎng)頁的重要性。若B網(wǎng)頁上有連接到A網(wǎng)頁的鏈接(稱B為A的導(dǎo)入鏈接)，說明B認(rèn)為A有鏈接價(jià)值，是一個(gè)“重要”的網(wǎng)頁。當(dāng)B網(wǎng)頁級(jí)別(重要性)比較高時(shí)，則A網(wǎng)頁可從B網(wǎng)頁這個(gè)導(dǎo)入鏈接分得一定的級(jí)別(重要性)，并平均分配給A網(wǎng)頁上的所有導(dǎo)出鏈接導(dǎo)入鏈接（也叫逆向鏈接）是指鏈接到你網(wǎng)站的站點(diǎn)；而當(dāng)你的網(wǎng)站上有鏈接指向另外一個(gè)站點(diǎn)時(shí)，這個(gè)站點(diǎn)就是你的“導(dǎo)出鏈接”。在PageRank算法中，一個(gè)網(wǎng)頁的級(jí)別（重要性）大致由下面兩個(gè)因素決定：該網(wǎng)頁的導(dǎo)入鏈接的數(shù)量和這些導(dǎo)入鏈接的級(jí)別（重要性）。6.4-搜索結(jié)果排序技術(shù)PageRank計(jì)算原理將下面的有向圖中的每個(gè)頂點(diǎn)看成一個(gè)網(wǎng)頁，并把每個(gè)弧看成是網(wǎng)頁間的“超級(jí)鏈接”，則此有向圖就代表一個(gè)小型的網(wǎng)絡(luò)，其中有6個(gè)網(wǎng)頁和9個(gè)超級(jí)鏈接。問：這6個(gè)網(wǎng)頁中哪個(gè)最重要？重要性的決定因素：導(dǎo)入鏈接的數(shù)量導(dǎo)入鏈接的重要性答：看誰的導(dǎo)入鏈接多？6.4-搜索結(jié)果排序技術(shù)PageRank計(jì)算原理基本的PageRank算法：設(shè)u

是某個(gè)網(wǎng)頁，其級(jí)別（重要性）為r(u)，記Fu

為u

的導(dǎo)出鏈接的集合，Bu

為u

的導(dǎo)入鏈接的集合，nu=|Fu

|即是u

的導(dǎo)出鏈接總數(shù)。設(shè)v

是u

的一個(gè)導(dǎo)入鏈接，根據(jù)PageRank

理論，u

從v

處分得的級(jí)別（重要性）為r(v)/nv

。將u

從所有導(dǎo)入鏈接處分得的重要性相加，即為網(wǎng)頁u

的最終級(jí)別。6.4-搜索結(jié)果排序技術(shù)基本的PageRank算法設(shè)共有m

個(gè)網(wǎng)頁，分別編號(hào)為1、2、3、...、m，它們的級(jí)別（重要性）分別記為r1、r2、r3、...、rm.設(shè)G

表示由這些網(wǎng)頁組成的有向圖的鄰接矩陣。根據(jù)有向圖理論：6.4-搜索結(jié)果排序技術(shù)基本的PageRank算法設(shè)共有m

個(gè)網(wǎng)頁，分別編號(hào)為1、2、3、...、m，它們的級(jí)別（重要性）分別記為r1、r2、r3、...、rm.第i個(gè)網(wǎng)頁的級(jí)別計(jì)算為：為G中第j列的列和其中：6.4-搜索結(jié)果排序技術(shù)基本的PageRank算法第i個(gè)網(wǎng)頁的級(jí)別計(jì)算為：?jiǎn)栴}：怎么計(jì)算？先假定所有網(wǎng)頁都是一樣的，給一個(gè)初值；用一種迭代算法，根據(jù)第一次排名算出第二次排名，以此類推，網(wǎng)頁的排名估值能夠收斂；可以證明，不論如何選取初值，最后都能收斂到排名的真實(shí)值。6.4-搜索結(jié)果排序技術(shù)基本的PageRank算法PageRank算法描述：設(shè):為第一、第二、···第N個(gè)網(wǎng)頁的排名；矩陣：為網(wǎng)頁之間鏈接的數(shù)目；其中amn

代表第m個(gè)網(wǎng)頁指向第n個(gè)網(wǎng)頁的鏈接數(shù)。

A為已知，B為未知。6.4-搜索結(jié)果排序技術(shù)基本的PageRank算法PageRank算法描述：設(shè)：

為第i次迭代結(jié)果，那么：初始階段，所有網(wǎng)頁排名都是,即：迭代計(jì)算B1，B2，···，可以證明Bi

最終會(huì)收斂。

6.4-搜索結(jié)果排序技術(shù)基本的PageRank算法PageRank算法的工程引申：網(wǎng)頁數(shù)量是巨大的，假設(shè)有10億；矩陣A更是巨大的；但A又是稀疏的；可以用多臺(tái)服務(wù)器用MapReduce算法計(jì)算。6.4-搜索結(jié)果排序技術(shù)Google的PageRank計(jì)算工具可以下載Google的toolbar（約660K），安裝后就可以顯示所瀏覽的網(wǎng)頁的PageRank得分。

6.4-搜索結(jié)果排序技術(shù)搜索結(jié)果排序技術(shù)宏觀粒度的頁面質(zhì)量評(píng)估PageRank（Google）:網(wǎng)頁本身的質(zhì)量TF-IDF：網(wǎng)頁和查詢的相關(guān)性考慮用戶查詢關(guān)鍵詞在網(wǎng)頁中出現(xiàn)的頻率TF(TermFrequency)但僅采用TF有漏洞，因此，引入IDF(InverseDocumentFrequency)假定關(guān)鍵詞w在Dw個(gè)網(wǎng)頁中出現(xiàn)過，網(wǎng)頁的總數(shù)是D，則：6.5-相關(guān)研究趨勢(shì)傳統(tǒng)文本搜索引擎的優(yōu)勢(shì)和不足優(yōu)勢(shì)使用簡(jiǎn)便，面向最終用戶；只關(guān)心文本，具有通用性。不足完全不考慮文本結(jié)構(gòu)信息，限制了高級(jí)使用；其通用性也是不足之處，無法對(duì)于專業(yè)應(yīng)用提供有針對(duì)性的服務(wù)，不能實(shí)現(xiàn)在語義上的定域查詢，查詢精度差；不包含屬性信息，不符合信息網(wǎng)格的需求，無法對(duì)應(yīng)用程序?qū)崿F(xiàn)必需的支持6.5-相關(guān)研究趨勢(shì)引自：NigelBakeretal.QueryingLargePhysicsDataSetsOveranInformationGrid.InChep’01數(shù)據(jù)網(wǎng)格-信息網(wǎng)格-知識(shí)網(wǎng)格6.5-相關(guān)研究趨勢(shì)數(shù)據(jù)網(wǎng)格數(shù)據(jù)網(wǎng)格解決的問題：解決海量數(shù)據(jù)的存儲(chǔ)和共享問題主要為計(jì)算任務(wù)以及計(jì)算網(wǎng)格服務(wù)，是一種底層的海量數(shù)據(jù)倉儲(chǔ)體系數(shù)據(jù)網(wǎng)格不去解決的問題：多類的和復(fù)雜的信息格式信息表示和元數(shù)據(jù)智能化信息獲?。↖nformationretrieval）信息網(wǎng)格信息網(wǎng)格解決的問題信息的智能化獲取信息檢索信息的表示多類的元數(shù)據(jù)和結(jié)構(gòu)化給用戶和應(yīng)用程序提供特定內(nèi)容的信息服務(wù)6.5-相關(guān)研究趨勢(shì)信息網(wǎng)格信息網(wǎng)格不去解決的問題海量數(shù)據(jù)存儲(chǔ)，數(shù)據(jù)管理計(jì)算問題及強(qiáng)數(shù)據(jù)量（data-density）的計(jì)算和數(shù)據(jù)訪問方式知識(shí)網(wǎng)格知識(shí)網(wǎng)格解決的問題數(shù)據(jù)挖掘、知識(shí)挖掘規(guī)則的發(fā)現(xiàn)數(shù)據(jù)、信息的可視化知識(shí)網(wǎng)格不去解決的問題無結(jié)構(gòu)信息的半結(jié)構(gòu)化元數(shù)據(jù)格式的匹配和轉(zhuǎn)換信息智能化檢索6.5-相關(guān)研究趨勢(shì)基于屬性的半結(jié)構(gòu)化信息搜索引擎設(shè)計(jì)思