您好,欢迎访问三七文档
当前位置:首页 > 商业/管理/HR > 人事档案/员工关系 > 国家集训队2004论文集 朱泽园
多串匹配算法及其启示南京市外国语学校朱泽园问题提出所谓多串匹配,就是给定一些模式串,在一段文章(只出现小写a到z这26个字母)中,找出第一个出现的任意一个模式串的位置,或者所有模式串出现的所有位置。例子模式串:“abcd”“bcde”正文:abcabcde实际应用含逻辑关键字的搜索引擎DNA序列搜索……广!因此用有效算法解决该问题能大大提高各行各业的工作效率!数据规模设共有m个模式串,长度分别为L1、L2…Lm正文为一个长度为n的数组T[1..n],限定900Kn,1000m,100KL朴素想法从小到大枚举每一个位置,并且对所有模式串进行检查。最坏情况下时间复杂度为对每一个模式串,使用kmp算法进行单串匹配,时间复杂度为)Ln(O)Lmn(O我的算法辅助算法1:Knuth-Morris-Pratt模式匹配辅助算法2:单词前缀树(自创)主算法1:线性算法辅助算法3:后缀树主算法2:平均性能更好的算法单词前缀树单词查找树前缀指针的定义单词前缀树之所以不同于单词树,是因为它的每一个非根结点上都有一个前缀指针(PrefixPointer)。设s为结点p在树中对应的字符串s的所有后缀中,找到在单词树中出现的,最长的一个,设为s1。p结点的前缀指针指向s1对应的结点。单词前缀树(续)举例abbabab“bab”不在树中“ab”在树中!所以前缀指针指向“ab”单词前缀树(续)前缀指针的生成从定义出发,穷举+扫描从kmp算法的前缀数组中吸取经验,通过父节点的前缀指针计算b单词前缀树(续)举例abbabab结点p结点q1结点q2主算法一kmp算法的启发kmp算法的精髓是减少重复的计算,根据自身的位移匹配(特征),确定模式串的右移量。×√zababaabc正文ababaca模式1ababaca模式1babaab模式2主算法一(续)单词前缀树的使用和附加标记Okay模式串是构成单词前缀树的基本元素模式“abcd”“bc”abccbdp也应该标记q附加标记附加标记传递性!主算法一(续)主过程abbabab正文:“abcbcabb……”abcbcabb找到匹配“bb”!主算法一(续)一点注意zababaabcbabaaaba主算法一(续)时间复杂性分析单词前缀树的构建正文的检索空间复杂性分析)(LO)(nO)26(LO)26(LO主算法一(续)优化方案二进制转化动态分配子结点+二分查找a01100001a01100001后缀树概述路经压缩McCreight(1976),On-lineConstruction(1995)单词:“ababc”abcbcabccabc主算法二单词前缀树的使用和扩展(TreeA)abbabab11111222主算法二(续)参数Shift,记录每一个结点到达任意一个Okay结点(自身除外)的最短路径(既可以通过树中的边,也可以通过前缀指针)主算法二(续)举例abbabab11111222主算法二(续)后缀树的使用和扩展(TreeB)由所有模式串倒置后的所有后缀组成。模式串为“abab”“ba”“bb”倒置:“baba”“ab”“bb”作用:在O(N)的时间内,从后向前地查看一段长度为N的字符,检测它是否为任意一个模式串的子串abbabab主算法二(续)TreeA上的函数ScanAFunctionScanA(Left,Right,P);如果Shift参数最短的模式串长度div2,继续读入字符并且P继续移动输出所有遇到的匹配xxxxxxxxRightLeftxxxxP主算法二(续)TreeB上的函数ScanBFunctionScanB(Left,Right);在TreeB中,将T[Left..Right]从右向左进行扫描,检查其是否为某个模式串的子串,返回最后扫描到的正文的位置。定义:当一个字符串是某个模式串的子串时,称其为“有效的”,反之为“无效的”。主算法二(续)主过程的基本思想:1、每次处理一个Left+1~Right的段落2、从Right向左通过ScanB检索,最后到达位置pos。3、从pos到Right进行ScanA检索。4、下一个过程的Left为ScanA检索到的正文位置,Right为Left+当前TreeA上的结点的Shift参数主算法二(续)举例模式串为“abcd”和“bcde”TreeAabcbcd653912478de编号123456789Shift432113214abcabcdecaRight主算法二(续)T=“abcabcde”,Left=0,Right=4,P=1从Right到Left+1逆向进行ScanB“a”为“有效的”“ca”为“无效的”,所以pos=4。Left+1模式串“abcd”“bcde”aaca没出现pos主算法二(续)1..3的正文位置上,不可能出现模式的匹配ScanA的检索需要从TreeA根结点重新开始,P指针重置为TreeA的根结点。abcabcde从pos到Right进行ScanA检索abcabcdeRight主算法二(续)posa主算法二(续)阶段1:正向ScanA检索字符串“a”abcbcd653912478de编号123456789Shift432113214PP23posabcabcdebcdRight主算法二(续)T=“abcabcde”Left=4,Right=Left+Shift[P]=7,P=2从Right到Left+1逆向进行ScanB有“bcd”为“有效的”,所以pos=5。Left+1模式串“abcd”“bcde”bcdpos=L+1主算法二(续)阶段1:正向ScanA检索字符串“bcd”再读入字符“e”abcbcd653912478de编号123456789Shift432113214P51PPP找到匹配“abcd”找到匹配“bcde”主算法二(续)时间复杂度分析:设最短的模式串长度为θ最坏情况O(N)设所有的模式串长度均为θ,θ足够大时,若正文随机。ScanB将所有的T[Left+1..Right]的字符扫描完毕的概率并不大,可以证明平均复杂度:)log(26nO算法总结——启示1的使用变大——ScanA将很难退出,平均复杂度变大!变小——Right-Left的差变小,ScanB的pos回到Left+1的可能性变大,平均复杂度变大!2323中间值!算法总结——启示2优劣得所的思想算术平均数——本算法几何平均数——Editor块状链表不断更新的数组A[1..10000],求max{A[1..i]}更新:O(10000)。取值:O(1)二叉树(不易实现)max1[i]记录A[1*100~(i-1)*100]中的最大值更新:O(100)。取值:O(100)启示一条铁链的强度,决定于最弱的铁环的强度一个水桶的水量,决定于最短的竹片的长度在算法深度达到一定程度的前提下,我们应该将算法的广度拓宽,多种算法并用,从最弱的点找到解决问题的钥匙。只要不断地从瓶颈处突破,解题将会“有山就有路,有河就能渡”!最重要的是领悟“融会贯通”的思想That’sall!Thankyouforlistening.
本文标题:国家集训队2004论文集 朱泽园
链接地址:https://www.777doc.com/doc-3309779 .html