四. 上下无关文法的纠错剖析法.doc

《四. 上下无关文法的纠错剖析法.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、四.上下文无关文法的纠错剖析法距离：抽取基元出错容错1.出错分类：2.距离（句子）(1)列文斯坦距离从x导出y所需要的最小的转换数目例：(2)加权列文斯坦距离:从x导出y的转换序列(3)加权距离(对每一种方式都加以区分，如加a与b不同)例：x=a1w2I(a1,b1)a2w3b1a1w2y=b1a1w3S(a1,b1)D(a1)D(a1)I(a2,b1)x与L(G)之间的距离x与L(G)中与它距离最近的句子y之间的距离列文斯坦距离的计算已知：求：解：1.给一个距离矩阵Db1b2…bm012…ma11a22……ann2.写程序文法f

2、ori=1tondoforj=1tomdo{ifthene1=D[i-1,j-1]+1elsee1=D[i-1,j-1]e2=D[i-1,j]+1e3=D[i,j-1]+1D[i-1,j]=min(e1,e2,e3)//应该是D[i,j]}3.举例：cbbabbdb012345678c102233434567201122b221012345631a321112345b432121234d543222223b654332232b765443233§3随机文法与识别器1]随机文法与随机语言的概念其中，Q是概率的集合eg:G=({S},

3、{a,b},P,Q,S)P,Q：（1）不受限制的随机文法（unrestricted）概率为：若满足:=,=,=,则，该文法为不受限制的随机文法（2）模糊（ambiguous）不模糊(unambiguous)是指例：模糊的因为：&，即两条路径，总的概率为+（3）一致性（consistent）:==1(P<1)随机文法的作用：a）在生成过程中，若已知各生成式概率大小，则可先试概率大的，加快句法分析速度；b）当有重叠时，判断，还是，可以有概率判断；c）当基元提取有错时，也可以用概率判断。例:有两类句子和，则aaabbbb是属于还是，可以

4、用概率判断。2]概率的学习设有M类，收集到大量的样本字符串，已知字符串出现的次数n()且由产生的概率，是在生成过程中引用的次数则：在中引用规则的次数为：,又：，。例:两类问题，，其中P:已知：T:计算得：=25,=50,=5,=2.5得：P:3]随机有限自动机（规则文法）D是概率a,p3a,p1bbbbaba,p2,,,p1,p1,p1a,p1aa新：