数据分析网站开发,网站301如何做,广东省网站开发建设,遵义专业建站学习总结 在ER中#xff0c;有一类算法依靠参考结构化数据库的模型实现#xff0c;以便提高ER的速度。但是这类算法常常在运行中产生了大量重复计算#xff0c;降低了效率。由此#xff0c;通过介绍以下方法#xff0c;来解决这个问题#xff1a; 块分割 给定的字符串有一类算法依靠参考结构化数据库的模型实现以便提高ER的速度。但是这类算法常常在运行中产生了大量重复计算降低了效率。由此通过介绍以下方法来解决这个问题 块分割 给定的字符串 Xx1,...xn;其中既有单词又有标点子序列 s1,...,sp;对X进行分割后生成的包含一个或多个单词的字符串
sp(tp,up,y);tp起始位置up为结束位置y为特征特征集合 Yy1,..,yj先后有序令y表示X中子序列的特征例子x1x2x3表示一个人名x5x6x7x8表示一个题目人名题目用yj表示子序列s1x1x2x3。其中s1的起始位置用t1表示这里t12结束位置用u13表示。并且最大不超过X的长度最小不低于1. 第二个子串的起始位置在第一个子串结束位置之后的第一个单词也就是相邻子串之间没有空隙是连续的。 最后一个子串up结束的位置为X序列结束位置第一个子串s1起始位置为X序列第一个单词。注意up的下标p对应子序列sp中的p下标的计数p跟子串个数S相关把X分成10个子串那么P10且起始位置tp与结束位置up的下标是一致的例s1t1u1s2t2u2 特征提取函数 y表示前一个特征y表示当前特征X表示字符串tjuj同上描述。特征提取函数集g1,...gv每个一个特征函数就是一种分割方法都会有一个与其对应的权重wk。通过使用维特比算法从这些特征函数中找到使得权重和最大的特征提取函数序列换句话说权重和最大表示了该特征提取函数序列对X进行了最优化分割。这一过程是在训练中完成。接下来将介绍最优化分割。 最优化分割 s*表示在所有s1,...,sp中得分最高的一个si。由于每个特征提取函数g都会生成一个序列s1,...,sp所以需要维特比算法找到一条路径使得改路径上的每一个s都达到最大值。 表示可能的分割序列的集合所谓分割序列意思是由不同的特征提取函数生成不同的分割序列s1y---si:y 该算法将形成一条路径该路径上每一个siy都是整个Siy集合中的最大值,用表示 y表示前一个特征其作用是概率传递意思是在计算完第一个特征值后其值将影响下一个特征值的计算以此类推形成一条路径。若没有y则退化成简单最大值计算问题。 y1 y2 y3 . . . ym s1 s1max . . . . s1 s2max s2 . s2 s3 s3 . s3 . . . . . . . . . . . . . . . . . si si . . . . . . . . . si i行m个列每次计算从m个列中选取一个计算到下一个列的距离(从第i行的m个节点中挑一个计算到i1行m个节点的距离)m*m一共计算i行 其复杂度为O(IM2) σ(1,y)表示在序列s2中y1特征得到了最大值。依据公式1在对y2计算时将选取s2作为起点将其值传入下一步计算。也就是说y2的最大值受y1影响。从m个分词中挑选一个分词计算该分词到下一个分词的值以前一个分词为起点把下一个所有特征的分词都计算一遍。 维特比算法 维特比算法是一个特殊但应用最广的动态规划算法利用动态规划可以解决任何一个图中的最短路径问题。其优点是利用动态规划降低复杂度。而维特比算法是针对一个特殊的图——篱笆网络的有向图Lattice )的最短路径问题而提出的。 它之所以重要是因为凡是使用隐含马尔可夫模型描述的问题都可以用它来解码。假设整个篱笆有向图中每一列节点最多有m个也就是图的宽度为D并且图一共有N列那么每次计算至多计算m*m次从i列的m个节点中挑一个计算到i1列m个节点的距离。至多计算N次。那么复杂度骤减为ONm2m的平方远远小于穷举OmN)m的n次方。马尔科夫链是对多参数条件概率计算的化简假设某一点的条件概率只和其之前某点相关与其他点无关。这样就形成了概率传递链。 为了比较算法的优劣我们设计了一个时间下线即在最好的情况下的时间消耗。用空间换时间是优化算法的一个常用的方法。存储大量中间生成组件并重复利用避免了重新生成部件的过程减少了时间但存储空间变大了。
