搜索引擎开发实践.ppt
搜索引擎开发实践第一讲 搜索引擎简介,主讲人：罗刚,概 述,前导知识搜索引擎的查询语法搜索引擎的总体架构用户界面布局网站搜索的常用功能,前导知识,Core Java Java技术手册HashMapFileBitSet编译原理Modern compiler implementation in Java词法分析，有限状态机语法分析概率论应用随机过程：概率模型导论马尔可夫模型贝叶斯公式数据结构 Java程序设计：一种跨学科的方法动态规划,第3页,准备开发环境,JDK1.6增加虚拟内存到800M-Xmx800mEclipse 支持中文的语言包LuceneResinhttp:/download,准备开发环境(续),TortoiseSVNhttp:/Anthttp:/MavenLinuxCentOS()SecureCRT登录,词法分析(Lexical analysis),例如分析输入的用户查询串，输出该字符串中出现的所有的合法的单词(Token)。例如对查询串“NBA AND 比赛”的词法分析：Token NBA AND 比赛Type TERM AND TERMLucene中采用JavaCC实现词法分析。JavaCC有个Eclipse插件(/),词法分析的原理,Tokens,生成词法分析器,词法分析器如何工作?把用户输入定义的Token转换成为正规文法等价的形式把正规文法转换成NFA把NFA转换成DFA生成代码模拟DFA,语法分析,+DisNey WOrld,文本解析,BooleanQuery,ModifierQNREQ,FieldQN(content,WOrld),FieldQN(content,DisNey),缺省列:content,词法分析-JavaCC,JavaCC(Java Compiler Compiler)可以同时完成对文本的词法分析和语法分析的工作。,StandardSyntaxParser.jj,Token.javaStandardSyntaxParserConstants.javaStandardSyntaxParser.java,JavaCC,jj文件的结构,一个JavaCC文件由三部分组成:Options类的声明词法分析的声明(tokens)，和语法分析的声明options STATIC=false;PARSER_BEGIN(StandardSyntaxParser)PARSER_END(StandardSyntaxParser)/*Token Definitions*/,选项(options),STATIC是一个布尔选项，缺省值是真。如果是真，在生成出的解析器和token管理器中，所有的方法和类变量都声明成静态的。这样仅仅允许一个解析对象存在，但是查询分析器应该有很多个，所以这个值应该设成假。,词法分析-JavaCC,lucene-3.0.0contribqueryparsersrcjavaorgapachelucenequeryParserstandardparserStandardSyntaxParser.jjparse方法定义了对用户查询串的词法分析功能，并完成初步的语法分析public QueryNode parse(CharSequence query,CharSequence field)QueryNode对象包含了分析出来的语法树,概率,一本词典，从词典翻页看到的词是一个动词的概率？如何计算：全部的词=对词典中所有的词计数#得到一个动词的方法:是动词的单词数量如果一个词典有50,000项，10,000 是动词，则P(V)=10000/50000=1/5=0.2,计算P(W),如何计算联合概率:P(“the”,”other”,”day”,”I”,”was”,”walking”,”along”,”and”,”saw”,”a”,”lizard”)构想:根据概率的链规则,概率的链规则,根据条件概率的定义重写:更通用的公式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),链规则应用到句子中的单词的联合概率,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),但是,有很多可能的句子没法得到足够的数据为这些长的前缀计算统计值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)二元版本,马尔科夫假设,动态规划,动态规划把对复杂问题的求解分解成简单的步骤：问题的最优解只取决于其子问题的最优解在计算一个对子问题的答案后，把它存储到表中。后续的计算检查这个表，避免重复工作以自底向上的方式计算答案,最长公共子串,用来衡量两个字符串的相似度的一种方式例如：x=“高新技术开发区北环海路128号”y=“高技区北环海路128号”则x和y的最长公共子串为 LCS(x,y)=“高技区北环海路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,写循环等式,假设 Xi 是x1.m的第i个前缀 x1.iX0 表示一个空前缀定义Xm和Yn 的LCS 的长度 LenLCS(m,n)需要一个递归方程计算LenLCS(i,j),写递归方程,如果Xi和Yj 以同样的字符xi=yj 结束，则LCS 必须包含这个字符。否则，可以通过增加公共的字符得到一个更长的LCS。如果Xi和Yj 不是以同样的字符结束，则有两种可能性：要么这个LCS不以xi结束，或者这个LCS不以yj结束假设Zk是一个Xi和Yj的LCS,Xi和Yj以xi=yj结束,Xi和Yj 以xi yj结束,Zk 是一个Xi 和Yj-1 的LCS,Zk是一个Xi-1和Yj 的LCS,LenLCS(i,j)=maxLenLCS(i,j-1),LenLCS(i-1,j),递归方程,动态规划求解LCS代码,public static int lcsLen(E s1,E s2)int num=new ints1.length+1s2.length+1;/初始化为0的二维数组/实际算法 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);(最长公共子序列的长度是：+nums1.lengths2.length);return nums1.lengths2.length;,搜索引擎的查询语法,逻辑运算符与(+、空格)：查询词必须出现在搜索结果中。或(OR、|)：搜索结果可以包括运算符两边的任意一个查询词。非(-)：要求搜索结果中不含特定查询词。把搜索范围限定在网页标题中intitle把搜索范围限定在特定站点中site把搜索范围限定在url链接中inurl查找某种类型的文档filetype返回所有链接到某个URL地址的网页link,互联网搜索的常用功能,关键词搜索搜索结果关键词相关的摘要与高亮显示范围搜索高级搜索搜索查询语法相似文档搜索搜索结果分类统计用户搜索日志分析,搜索引擎结构,第32页,取得文档,文本提取,索引程序,索引库(Lucene),搜索查询服务器(Solr),用户界面,NBA,搜索,网页,邮件,数据库,爬虫,爬虫基本结构,互联网,请求网页,解析网页,存储系统,新解析出的URL,初始URL地址列表,用户界面,输入框搜索词提示,用户界面(续),搜索结果页面,用户界面(续),门户搜索搜索结果页面,用户界面(续),您是不是要找：.,用户界面(续),高级搜索,用户界面(续),搜索结果分类统计,用户搜索日志分析,作业,从SVN下载Lucene源代码把Lucene源代码导入Eclipse,感谢您对猎兔搜索的支持!,http:/,
