算法合集之《多串匹配算法及其启示》.ppt

《算法合集之《多串匹配算法及其启示》.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、多串匹配算法及其启示南京市外国语学校朱泽园问题提出所谓多串匹配，就是给定一些模式串，在一段文章（只出现小写a到z这26个字母）中，找出第一个出现的任意一个模式串的位置，或者所有模式串出现的所有位置。例子模式串：“abcd”“bcde”正文：abcabcde实际应用含逻辑关键字的搜索引擎DNA序列搜索……广!因此用有效算法解决该问题能大大提高各行各业的工作效率！数据规模设共有m个模式串，长度分别为L1、L2…Lm正文为一个长度为n的数组T[1..n]，限定朴素想法从小到大枚举每一个位置，并且对所有模式串进行检查。最坏情况下时

2、间复杂度为对每一个模式串，使用kmp算法进行单串匹配，时间复杂度为我的算法辅助算法1：Knuth-Morris-Pratt模式匹配辅助算法2：单词前缀树（自创）主算法1：线性算法辅助算法3：后缀树主算法2：平均性能更好的算法单词前缀树单词查找树前缀指针的定义单词前缀树之所以不同于单词树，是因为它的每一个非根结点上都有一个前缀指针（PrefixPointer）。设s为结点p在树中对应的字符串s的所有后缀中，找到在单词树中出现的，最长的一个，设为s1。p结点的前缀指针指向s1对应的结点。单词前缀树（续）举例abbabab“ba

3、b”不在树中“ab”在树中！所以前缀指针指向“ab”单词前缀树（续）前缀指针的生成从定义出发，穷举+扫描从kmp算法的前缀数组中吸取经验，通过父节点的前缀指针计算b单词前缀树（续）举例abbabab结点p结点q1结点q2主算法一kmp算法的启发kmp算法的精髓是减少重复的计算，根据自身的位移匹配（特征），确定模式串的右移量。×√zababaabc正文ababaca模式1ababaca模式1babaab模式2主算法一（续）单词前缀树的使用和附加标记Okay模式串是构成单词前缀树的基本元素模式“abcd”“bc”abccb

4、dp也应该标记q附加标记附加标记传递性！主算法一（续）主过程abbabab正文：“abcbcabb……”abcbcabb找到匹配“bb”！主算法一（续）一点注意zababaabcbabaaaba主算法一（续）时间复杂性分析单词前缀树的构建正文的检索空间复杂性分析主算法一（续）优化方案二进制转化动态分配子结点+二分查找a01100001a01100001后缀树概述路经压缩McCreight(1976),On-lineConstruction(1995)单词：“ababc”abcbcabccabc主算法二单词前缀树的使用和扩展

5、（TreeA）abbabab11111222主算法二（续）参数Shift，记录每一个结点到达任意一个Okay结点（自身除外）的最短路径（既可以通过树中的边，也可以通过前缀指针）主算法二（续）举例abbabab11111222主算法二（续）后缀树的使用和扩展(TreeB)由所有模式串倒置后的所有后缀组成。模式串为“abab”“ba”“bb”倒置：“baba”“ab”“bb”作用：在O(N)的时间内，从后向前地查看一段长度为N的字符，检测它是否为任意一个模式串的子串abbabab主算法二（续）TreeA上的函数ScanA

6、FunctionScanA(Left,Right,P);如果Shift参数<最短的模式串长度div2，继续读入字符并且P继续移动输出所有遇到的匹配xxxxxxxxRightLeftxxxxP主算法二（续）TreeB上的函数ScanBFunctionScanB(Left,Right);在TreeB中，将T[Left..Right]从右向左进行扫描，检查其是否为某个模式串的子串，返回最后扫描到的正文的位置。定义：当一个字符串是某个模式串的子串时，称其为“有效的”，反之为“无效的”。主算法二（续）主过程的基本思想：1、每次处理

7、一个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到Lef

8、t+1逆向进行ScanB“a”为“有效的”“ca”为“无效的”，所以pos=4。Left+1模式串“abcd”“bcde”aaca没出现pos主算法二（续）1..3的正文位置上，不可能出现模式的匹配ScanA的检索需要从TreeA根结点重新开始，P指针重置为TreeA的根结点。abcabcde从pos到