12随机串匹配算法 121随机串匹配及其串行算法 采用上一节所述的MP算法虽然能够找到所有的匹配位置,但是算法的复杂度十分高, 在某些领域并不实用。本节给出了随机串匹配算法,该算法的主要采用了散列(Hash)技术 的思想,它能提供对数的时间复杂度。其基本思想是:为了处理模式长度为m的串匹配问题, 可以将任意长为m的串映射到O(1ogm)整数位上,映射方法须得保证两个不同的串映射到同 整数的概率非常小。所得到的整数之被视为该串的指纹( Fingerprint),如果两个串的指 纹相同则可以判断两个串相匹配 1.指纹函数 本节中假定文本串和模式串取字符集∑={0,1}中的字母。 如上所述,随机串匹配算法的基本策略是将串映射到某些小的整数上。令T是长度为n 的文本串,P是长度为m≤n的模式串,匹配的目的就是识别P在T中出现的所有位置。考 虑长度为m的T的所有子串集合B。这样的起始在位置i(1≤i≤nm+1)的子串共有n-m+ 个。于是问题可重新阐述为去识别与P相同的B中元素的问题。该算法中最重要的是如何选 择一个合适的映射函数( Mapping function),下面将对此进行简单的讨论。 令F=n}me是函数集,使得J将长度为m的串映射到域D,且要求集合F满足下述 三个性质:①对于任意串X∈B以及每一个p∈S(S为模式串的取值域),f,(X)由O(logm) 位组成;②随机选择∫∈F,它将两个不等的串X和Y映射到D中同一元素的概率是很小 的;③对于每个p∈S和B中所有串,应该能够很容易的并行计算f(X)。 上述三个性质中,性质①隐含着f(X)和f(P)可以在1)时间内比较,其中f(x) 被称为串X的指纹;性质②是说,如果两个串X和Y的指纹相等,则X=Y的概率很高:性质 ③主要是针对该算法的并行实现的需求对集合F加以限制。对于串行算法函数∫,只需要满 足前两个性质即可 本节中我们采用了这样一类指纹函数:将取值{0,1}上的串X集合映射到取值整数环Z 上的2×2矩阵。令f(0)和f(1)定义如下 f(0)= f()= 该函数目前只满足性质2,为了使其同时满足性质1需要对该函数作如下更改 令p是区间[1,2,…,M中的一个素数,其中M是一个待指定的整数:令Z是取模p 的整数环。对于每个这样的p,我们定义厂(X)为f()modp,即f1(X)是一个2×2的 矩阵,使得fp(X)的(i,j)项等于f(X)的相应项取模p7 1.2 随机串匹配算法 1.2.1 随机串匹配及其串行算法 采用上一节所述的 KMP 算法虽然能够找到所有的匹配位置，但是算法的复杂度十分高， 在某些领域并不实用。本节给出了随机串匹配算法，该算法的主要采用了散列（Hash）技术 的思想，它能提供对数的时间复杂度。其基本思想是：为了处理模式长度为 m 的串匹配问题， 可以将任意长为 m 的串映射到 O(logm)整数位上，映射方法须得保证两个不同的串映射到同 一整数的概率非常小。所得到的整数之被视为该串的指纹（Fingerprint），如果两个串的指 纹相同则可以判断两个串相匹配。 1. 指纹函数 本节中假定文本串和模式串取字符集∑={0，1}中的字母。 如上所述，随机串匹配算法的基本策略是将串映射到某些小的整数上。令 T 是长度为 n 的文本串，P 是长度为 m≤n 的模式串，匹配的目的就是识别 P 在 T 中出现的所有位置。考 虑长度为 m 的 T 的所有子串集合 B。这样的起始在位置 i(1≤i≤n-m+1)的子串共有 n-m+1 个。于是问题可重新阐述为去识别与 P 相同的 B 中元素的问题。该算法中最重要的是如何选 择一个合适的映射函数（Mapping Function），下面将对此进行简单的讨论。 令 p p s F f =  { } 是函数集，使得 p f 将长度为 m 的串映射到域 D，且要求集合 F 满足下述 三个性质：①对于任意串 X∈B 以及每一个 p∈S（S 为模式串的取值域）， f (X ) p 由 O（logm） 位组成；②随机选择 f p  F ，它将两个不等的串 X 和 Y 映射到 D 中同一元素的概率是很小 的；③对于每个 p∈S 和 B 中所有串，应该能够很容易的并行计算 f (X ) p 。 上述三个性质中，性质①隐含着 f (X ) p 和 f (P) p 可以在 O(1)时间内比较，其中 f (X ) p 被称为串 X 的指纹；性质②是说，如果两个串 X 和 Y 的指纹相等，则 X=Y 的概率很高；性质 ③主要是针对该算法的并行实现的需求对集合 F 加以限制。对于串行算法函数 p f 只需要满 足前两个性质即可。 本节中我们采用了这样一类指纹函数：将取值{0，1}上的串 X 集合映射到取值整数环 Z 上的 2  2 矩阵。令 f (0) 和 f (1) 定义如下：       =       = 0 1 1 1 (1) 1 1 1 0 f (0) ， f 该函数目前只满足性质 2，为了使其同时满足性质 1 需要对该函数作如下更改： 令 p 是区间[1，2，…，M]中的一个素数，其中 M 是一个待指定的整数；令 Zp 是取模 p 的整数环。对于每个这样的 p，我们定义 f (X ) p 为 f (X )mod p ，即 f (X ) p 是一个 2  2 的 矩阵，使得 f (X ) p 的（i，j）项等于 f (X ) 的相应项取模 p