第2章 字符串精确匹配与比对
❖ 精确匹配问题及其Naïve方法 ❖ 字符串比对 ❖ 最长公共子序列 ❖ 多字符串比对
精确匹配问题及其Naïve方法
❖ 字符串精确匹配问题定义 给定一个字符串P（称为模式）和一个长字符 串T（称为文本）。字符串精确匹配问题定义 为查找T中所有P的出现位置 例如：P=gtg，T=ttgtgcgtgtga。则P在T中的位 置3，7和9三个位置出现。其中有两个P出现在 T中是交叠的
ttgtgcgtgtga
12 3 4 5 6 7 8 9 0 1 2
精确匹配问题及其Naïve方法
❖ 精确匹配问题的重要性 字符串的精确匹配问题可以应用到很多领域中
• 文字处理器：例如Unix的grep命令 • 信息检索系统：分词技术等 • Internet浏览器技术和爬虫技术 • 数字图书馆 • 分子生物学：当前在Internet上存在数以百计的专
精确匹配问题及其Naïve方法
❖ Naïve方法的改进分析
问题症结所在：P在T上的移动过慢，当出现 失配时一次只移动一个字符位置
• 如果有办法一次移动多个字符而又不错过T中P的 出现，这将有可能降低字符比较运算操作的数量
对于P=abxyabxz，T=xabxyabxyabxz
• 结果是P在T(6)这个位置开始出现1次
• S=aabcaabxaaz • Z2(S)=1, Z3(S)=0, Z4(S)=0, Z5(S)=3, • Z6(S)=1, Z7(S)=0, Z8(S)=0, Z9(S)=2, ……
精确匹配问题及其Naïve方法
❖ 模式预处理
• Zi-box：位置i开始，位置i+Zi-1结束的子串 • 对于任意的i，ri表示开始于i或i之前的所有Z-box的
P
T
精确匹配问题及其Naïve方法
❖ Naïve方法的复杂度分析 (|P||T|) 具体来讲，字符比较运算的次数在最坏情况下 是|P|(|T|-|P|+1)，例如P=aaa，T=aaaaaaaaaa， 则需要3*(10-3+1)=24个字符比较操作 如果|P|=1000，|T|=10,000,000，字符比较操作 的次数是不可想象的 如何改进Naïve算法，最好的目标应该是： (|P|+|T|)
30个字符的精确匹配查询需要4个小时以上的查询开销 – Genbank：仅是当今生物序列数据库中的很小一部分
• 字符串精确匹配问题是一个经典的计算机科学问题 ，同时它也是解决许多其它科学问题的基础
精确匹配问题及其Naïve方法
❖ 字符串定义和符号约定 字符串S是一个连续从左到右的字符有序列表
• |S|：表示字符串S的长度 • S[i..j]：表示字符串S从位置i开始到位置j结束的一
配的，这时算法将P移动并将P的左端与T(6)对齐，
节省了3次字符比较运算
1+8 +8 = 17
T：xabxyabxyabxz P： ababxyxayabbxxzyzabxz
采用什么样的技术？
• 从P中可以知道：第一个字符为a，且在P中下一次 出现a的位置为5
精确匹配问题及其Naïve方法
❖ Naïve方法的改进分析
一个更加智能的方法
• 如果算法知道，P的前三个字符(即abx)在P中下一 次出现的位置，则只需要从T(9)这里开始比较，又 省略了三次字符比较运算操作
T：xabxyabxyabxz P： ababxyxayabbxxzyzabxz
1+8 +5 = 14
^^^ • 以上智能处理算法所需要的信息隐藏在模式P中。
门数据库，存放着DNA，RNA和氨基酸序列
精确匹配问题及其Naïve方法
❖ 精确匹配问题的现实意义
精确匹配问题似乎已经被彻底解决
• 一预期的要快
• 如果使用GCG软件来搜索Genbank
– GCG：一种搜索生物数据库的非常流行的接口工具 – Genbank：美国DNA数据库 – 如果将Genbank数据库拷贝到本地数据库中，对于一个
– 如果它们相等，则称为匹配(match) – 否则称为失配(mismatch)
精确匹配问题及其Naïve方法
❖ Naïve方法 将P的左端与T的左端对齐，然后从左到右逐 个比较P和T的字符，直到一个失配出现或者P 中字符被比较完；如果是后一种情况的话，则 报告一次P的出现 将P在T上从左到右移动一个字符，并重新开 始这种比较 重复上述过程，直到P的右端移过了T的右端
Naïve方法：比较20次
T：xabxyabxyabxz P： abaabxbayxxbayybxaaybxbazxyxbzyazxabzbxxzz
1+8 +1+1+1+8 =20
如何减少比较次数？
精确匹配问题及其Naïve方法
❖ Naïve方法的改进分析
一个智能一点的方法
• 在第9个比较之后，它知道下面的三个比较将是失
个子字符串 • S[1..i]：表示字符串S在位置i结束的一个前缀 • S[i..|S|]：表示字符串S从位置i开始的一个后缀 • S[i..j]：表示一个空串如果i>j
精确匹配问题及其Naïve方法
❖ 字符串定义和符号约定 字符串S是一个连续从左到右的字符有序列表
• 真前缀、真后缀、真子串：即非原串又非空串 • S(i)：表示字符串S的第i个字符 • 使用小写希腊字符(, , , 等)来表示字符串变量 • 用小写罗马字符(a,b,c,d等)来表示单字符变量 • 对于两个字符串的比较
当然，我们也可以利用隐藏在文本T中的信息
– 这些信息的提取是需要经过预处理才能得到的
– 如果|T|>>|P|的话，|T|在算法复杂度中占有主导地位
精确匹配问题及其Naïve方法
❖ 模式预处理 在前面算法改进分析中，模式的前缀信息是非 常重要的 给定字符串S和位置i>1，Zi(S)表示位置i开始 且匹配S的一个前缀的最长子串的长度
最右端点，li表示结束于ri的Z-box的左端位置 • S=aabaabcaxaabaabcy
– Z10=7
– r15=16 aabaabcaxaabaabcy – l15=10 aabaabcaxaabaabcy • 上述Z值的计算将在很多经典的字符串处理算法中 使用