《搜索引擎開發(fā)實踐》PPT課件.ppt

《《搜索引擎開發(fā)實踐》PPT課件.ppt》由會員分享，可在線閱讀，更多相關(guān)《《搜索引擎開發(fā)實踐》PPT課件.ppt（42頁珍藏版）》請在裝配圖網(wǎng)上搜索。

搜索引擎開發(fā)實踐 第一講 搜索引擎簡介,主講人： 羅剛 luogang@,概 述,前導(dǎo)知識 搜索引擎的查詢語法 搜索引擎的總體架構(gòu) 用戶界面布局 網(wǎng)站搜索的常用功能,前導(dǎo)知識,Core Java 《 Java技術(shù)手冊》 HashMap File BitSet 編譯原理 《Modern compiler implementation in Java》 詞法分析，有限狀態(tài)機 語法分析 概率論 《應(yīng)用隨機過程：概率模型導(dǎo)論》 馬爾可夫模型 貝葉斯公式 數(shù)據(jù)結(jié)構(gòu) 《 Java程序設(shè)計：一種跨學(xué)科的方法》 動態(tài)規(guī)劃,第3頁,準備開發(fā)環(huán)境,JDK1.6 增加虛擬內(nèi)存到800M -Xmx800m Eclipse http://www.eclipse.org http://www.eclipse.org/babel/downloads.php 支持中文的語言包 Lucene http://lucene.apache.org/java/docs/index.html Resin ,準備開發(fā)環(huán)境(續(xù)),TortoiseSVN http://tortoisesvn.tigris.org Ant http://ant.apache.org Maven http://maven.apache.org Linux CentOS(http://www.centos.org) SecureCRT登錄,詞法分析(Lexical analysis),例如分析輸入的用戶查詢串，輸出該字符串中出現(xiàn)的所有的合法的單詞(Token)。例如對查詢串“NBA AND 比賽”的詞法分析： Token NBA AND 比賽 Type TERM AND TERM Lucene中采用JavaCC實現(xiàn)詞法分析。 JavaCC有個Eclipse插件(http://eclipse-,詞法分析的原理,Tokens,生成詞法分析器,詞法分析器如何工作? 把用戶輸入定義的Token轉(zhuǎn)換成為正規(guī)文法等價的形式 把正規(guī)文法轉(zhuǎn)換成NFA 把NFA轉(zhuǎn)換成DFA 生成代碼模擬DFA,語法分析,+DisNey WOrld,,文本解析,,BooleanQuery,ModifierQN REQ,,FieldQN (content, WOrld),,,FieldQN (content, DisNey),缺省列: content,詞法分析-JavaCC,JavaCC(Java Compiler Compiler)可以同時完成對文本的詞法分析和語法分析的工作。,StandardSyntaxParser.jj,,Token.java StandardSyntaxParserConstants.java StandardSyntaxParser.java …,JavaCC,,jj文件的結(jié)構(gòu),一個JavaCC文件由三部分組成: Options 類的聲明 詞法分析的聲明(tokens)，和語法分析的聲明 options { STATIC=false; … } PARSER_BEGIN(StandardSyntaxParser) … PARSER_END(StandardSyntaxParser) /* Token Definitions */,選項(options),STATIC是一個布爾選項，缺省值是真。 如果是真，在生成出的解析器和token管理器中，所有的方法和類變量都聲明成靜態(tài)的。 這樣僅僅允許一個解析對象存在，但是查詢分析器應(yīng)該有很多個，所以這個值應(yīng)該設(shè)成假。,詞法分析-JavaCC,lucene-3.0.0\contrib\queryparser\src\java\org\apache\lucene\queryParser\standard\parser\StandardSyntaxParser.jj parse方法定義了對用戶查詢串的詞法分析功能，并完成初步的語法分析 public QueryNode parse(CharSequence query, CharSequence field) QueryNode對象包含了分析出來的語法樹,概率,一本詞典，從詞典翻頁看到的詞是一個動詞的概率？ 如何計算： 全部的詞 = 對詞典中所有的詞計數(shù) # 得到一個動詞的方法: 是動詞的單詞數(shù)量 如果一個詞典有50,000項， 10,000 是動詞，則 P(V) = 10000/50000 = 1/5 = 0.2,計算P(W),如何計算聯(lián)合概率: P(“the”,”other”,”day”,”I”,”was”,”walking”,”along”,”and”,”saw”,”a”,”lizard”) 構(gòu)想: 根據(jù)概率的鏈規(guī)則,概率的鏈規(guī)則,根據(jù)條件概率的定義 重寫: 更通用的公式 P(A,B,C,D) = P(A)P(B|A)P(C|A,B)P(D|A,B,C) 一般化 P(x1,x2,x3,…xn) = P(x1)P(x2|x1)P(x3|x1,x2)…P(xn|x1…xn-1),鏈規(guī)則應(yīng)用到句子中的單詞的聯(lián)合概率,P(“the big red dog was”)= P(the)*P(big|the)*P(red|the big)*P(dog|the big red)*P(was|the big red dog),很容易估計:,如何估計? P(the|its water is so transparent that) P(the|its water is so transparent that) = C(its water is so transparent that the) _______________________________ C(its water is so transparent that),但是,有很多可能的句子 沒法得到足夠的數(shù)據(jù)為這些長的前綴計算統(tǒng)計值 P(lizard|the,other,day,I,was,walking,along,and,saw,a) 或者 P(the|its water is so transparent that),馬爾科夫假設(shè),做簡單的假設(shè) P(lizard|the,other,day,I,was,walking,along,and,saw,a) = P(lizard|a) 或者可能是 P(lizard|the,other,day,I,was,walking,along,and,saw,a) = P(lizard|saw,a),對公式中的每個部件 用近似值替換(假設(shè)前綴N) 二元版本,馬爾科夫假設(shè),動態(tài)規(guī)劃,動態(tài)規(guī)劃把對復(fù)雜問題的求解分解成簡單的步驟： 問題的最優(yōu)解只取決于其子問題的最優(yōu)解 在計算一個對子問題的答案后，把它存儲到表中。后續(xù)的計算檢查這個表，避免重復(fù)工作 以自底向上的方式計算答案,最長公共子串,用來衡量兩個字符串的相似度的一種方式 例如： x = “高新技術(shù)開發(fā)區(qū)北環(huán)海路128號” y = “高技區(qū)北環(huán)海路128號” 則x和y的最長公共子串為 LCS(x, y) = “高技區(qū)北環(huán)海路128號” x = { a , b , c , b , d , a , b }，y = { b , d , c , a , b , a }，則從前往后找，x和y的最長公共子串為 LCS(x, y) = { b , c , b , a }，如圖所示,a , b , c , b , d , a , b,b , d , c , a , b , a,,,,,寫循環(huán)等式,假設(shè) Xi 是x[1m]的第i個前綴 x[1i] X0 表示一個空前綴 定義Xm和Yn 的LCS 的長度 LenLCS(m, n) 需要一個遞歸方程計算LenLCS(i, j),寫遞歸方程,如果Xi和Yj 以同樣的字符xi=yj 結(jié)束，則LCS 必須包含這個字符。否則，可以通過增加公共的字符得到一個更長的LCS。 如果Xi和Yj 不是以同樣的字符結(jié)束，則有兩種可能性： 要么這個LCS不以xi結(jié)束， 或者這個LCS不以yj結(jié)束 假設(shè)Zk是一個Xi和Yj的LCS,Xi和Yj以xi=yj結(jié)束,Xi和Yj 以xi yj結(jié)束,,,Zk 是一個Xi 和Yj -1 的LCS,Zk是一個Xi -1和Yj 的LCS,LenLCS(i, j)=max{LenLCS(i, j-1), LenLCS(i-1, j)},遞歸方程,動態(tài)規(guī)劃求解LCS代碼,public static int lcsLen(E[] s1, E[] s2) { int[][] num = new int[s1.length+1][s2.length+1]; //初始化為0的二維數(shù)組 //實際算法 for (int i = 1; i = s1.length; i++) for (int j = 1; j = s2.length; j++) if (s1[i-1].equals(s2[j-1])) num[i][j] = 1 + num[i-1][j-1]; else num[i][j] = Math.max(num[i-1][j], num[i][j-1]); System.out.println(“最長公共子序列的長度是：“ + num[s1.length][s2.length]); return num[s1.length][s2.length]; },搜索引擎的查詢語法,邏輯運算符 與(+ 、 空格) ：查詢詞必須出現(xiàn)在搜索結(jié)果中。 或(OR 、 | ) ：搜索結(jié)果可以包括運算符兩邊的任意一個查詢詞。 非( - ) ：要求搜索結(jié)果中不含特定查詢詞。 把搜索范圍限定在網(wǎng)頁標題中——intitle 把搜索范圍限定在特定站點中——site 把搜索范圍限定在url鏈接中——inurl 查找某種類型的文檔——filetype 返回所有鏈接到某個URL地址的網(wǎng)頁——link,互聯(lián)網(wǎng)搜索的常用功能,關(guān)鍵詞搜索 搜索結(jié)果關(guān)鍵詞相關(guān)的摘要與高亮顯示 范圍搜索 高級搜索 搜索查詢語法 相似文檔搜索 搜索結(jié)果分類統(tǒng)計 用戶搜索日志分析,搜索引擎結(jié)構(gòu),第32頁,,取得文檔,文本提取,索引程序,索引庫(Lucene),搜索查詢服務(wù)器(Solr),用戶界面,NBA,,,,,,,,,,,搜索,網(wǎng)頁,郵件,數(shù)據(jù)庫,爬蟲,爬蟲基本結(jié)構(gòu),互聯(lián)網(wǎng),請求網(wǎng)頁,,,解析網(wǎng)頁,存儲系統(tǒng),,新解析出的URL,初始URL地址列表,,用戶界面,輸入框搜索詞提示,用戶界面(續(xù)),搜索結(jié)果頁面,用戶界面(續(xù)),門戶搜索搜索結(jié)果頁面,用戶界面(續(xù)),您是不是要找：.,用戶界面(續(xù)),高級搜索,用戶界面(續(xù)),搜索結(jié)果分類統(tǒng)計,用戶搜索日志分析,作業(yè),從SVN下載Lucene源代碼 把Lucene源代碼導(dǎo)入Eclipse,感謝您對獵兔搜索的支持!,,