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

搜索引擎開發(fā)實踐 第一講 搜索引擎簡介,主講人： 羅剛 luogang,概 述,前導知識 搜索引擎的查詢語法 搜索引擎的總體架構(gòu) 用戶界面布局 網(wǎng)站搜索的常用功能,前導知識,Core Java Java技術(shù)手冊 HashMap File BitSet 編譯原理 Modern compiler implementation in Java 詞法分析，有限狀態(tài)機 語法分析 概率論 應用隨機過程：概率模型導論 馬爾可夫模型 貝葉斯公式 數(shù)據(jù)結(jié)構(gòu) Java程序設計：一種跨學科的方法 動態(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)的。 這樣僅僅允許一個解析對象存在，但是查詢分析器應該有很多個，所以這個值應該設成假。,詞法分析-JavaCC,lucene-3.0.0contribqueryparsersrcjavaorgapachelucenequeryParserstandardparserStandardSyntaxParser.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|x1xn-1),鏈規(guī)則應用到句子中的單詞的聯(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),馬爾科夫假設,做簡單的假設 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),對公式中的每個部件 用近似值替換(假設前綴N) 二元版本,馬爾科夫假設,動態(tài)規(guī)劃,動態(tài)規(guī)劃把對復雜問題的求解分解成簡單的步驟： 問題的最優(yōu)解只取決于其子問題的最優(yōu)解 在計算一個對子問題的答案后，把它存儲到表中。后續(xù)的計算檢查這個表，避免重復工作 以自底向上的方式計算答案,最長公共子串,用來衡量兩個字符串的相似度的一種方式 例如： 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)等式,假設 Xi 是x1m的第i個前綴 x1i 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é)束 假設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)=maxLenLCS(i, j-1), LenLCS(i-1, j),遞歸方程,動態(tài)規(guī)劃求解LCS代碼,public static int lcsLen(E s1, E s2) int num = new ints1.length+1s2.length+1; /初始化為0的二維數(shù)組 /實際算法 for (int i = 1; i = s1.length; i+) for (int j = 1; j = s2.length; j+) if (s1i-1.equals(s2j-1) numij = 1 + numi-1j-1; else numij = Math.max(numi-1j, numij-1); System.out.println(“最長公共子序列的長度是：“ + nums1.lengths2.length); return nums1.lengths2.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),搜索查詢服務器(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源代碼導入Eclipse,感謝您對獵兔搜索的支持!,