搜索引擎开发实践.ppt

如何计算联合概率:P(“the”,”other”,”day”,”I”,”was”,”walking”,”along”,”and”,”saw”,”a”,”lizard”)构想:根据概率的链规则计算P(W)概率的链规则根据条件概率的定义重写:更通用的公式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)链规则应用到句子中的单词的联合概率P(“thebigreddogwas”)=P(the)*P(big|the)*P(red|thebig)*P(dog|thebigred)*P(was|thebigreddog)P(the|itswaterissotransparentthat)P(the|itswaterissotransparentthat)=C(itswaterissotransparentthatthe)_______________________________C(itswaterissotransparentthat)如何估计?很容易估计:有很多可能的句子没法得到足够的数据为这些长的前缀计算统计值P(lizard|the,other,day,I,was,walking,along,and,saw,a)或者P(the|itswaterissotransparentthat)但是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)01.二元版本02.马尔科夫假设动态规划把对复杂问题的求解分解成简单的步骤：01在计算一个对子问题的答案后，把它存储到表中。后续的计算检查这个表，避免重复工作03问题的最优解只取决于其子问题的最优解02以自底向上的方式计算答案04动态规划最长公共子串用来衡量两个字符串的相似度的一种方式例如：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,bb,d,c,a,b,a定义Xm和Yn的LCS的长度LenLCS(m,n)需要一个递归方程计算LenLCS(i,j)X0表示一个空前缀假设Xi是x[1..m]的第i个前缀x[1..i]写循环等式如果Xi和Yj以同样的字符xi=yj结束，则LCS必须包含这个字符。否则，可以通过增加公共的字符得到一个更长的LCS。如果Xi和Yj不是以同样的字符结束，则有两种可能性：1要么这个LCS不以xi结束，2或者这个LCS不以yj结束假设Zk是一个Xi和Yj的LCS3写递归方程Xi和Yj以xi=yj结束Xix1x2…xi-1xiYjy1y2…yj-1yj=xiZkz1z2…zk-1zk=yj=xiZk是Zk-1后接zk=yj=xi这里Zk-1是Xi-1和Yj-1的一个LCS，而且LenLCS(i,j)=LenLCS(i-1,j-1)+1Xi和Yj以xi1yj结束Xix1x2…xi-1xiYjy1y2…yj-1yjZkz1z2…zk-1zk1yjZk是一个Xi和Yj-1的LCSXix1x2…xi-1xiYjyjy1y2…yj-1yjZkz1z2…zk-1zk1xiZk是一个Xi-1和Yj的LCSLenLCS(i,j)=max{LenLCS(i,j-1),LenLCS(i-1,j)}递归方程动态规划求解L