英语原文共 7 页，剩余内容已隐藏，支付完成后下载完整资料

混合关键字符串匹配算法

Abdulrakeeb M. Al-Ssulami

King Saud University, Saudi Arabia

摘要：模式匹配在文本处理、分子生物学、操作系统和网络搜索引擎中都很重要。许多算法已经被开发用来在一个文本中寻找一个特定的模式，但是一个有效的算法的需求还是一个未解决的问题。在本文中，我们提出了一个简单的和实用的字符串匹配算法。该算法是一种混合结合我们改进的Horspool算法从两方面进行字符串匹配。该算法从左到右扫描文字，从右到左的匹配模式。根据自然语文文本的实验结果，证明新算法与可用的算法是有竞争力的。

关键词：算法设计；实验算法；在线搜索

1. 介绍

准确字符串匹配的问题包括找到一个出现的模式X的长度在一个文本长度为n的一组字母集合中.我们用它来表示字母表的大小，并通过从这个文本开始，我们索引模式和文本。在字符串匹配问题上已经进行了大量的工作，特别是在过去的二十年中。Boyer和Moore提出了一组关于字符串匹配的言论。他们的观点认为最右边的字符不匹配模式。如果相应的文本字符Y[i]，mle;ile;n-1，不出现在模式中则模式必须由m右移，如果字符出现在模式，模式必须位移到匹配Y[i]。这种情况需要一个表来散列模式的字符，并将它们最后一个出现在模式中的移动的位数进行存储。这个想法已经在快速算法中得到了实现。另一个后缀模式匹配的观点；如果一个后缀X[i..m-1]匹配文本，其中1le;ile;m-1，另一个变化是必需记录模式中1le;ile;m-2的后缀最后出现的位置。综合性实验评价了47串匹配算法，它是基于不同的性格之间，如Boyer–Moore–Horspool的q-grams和SSEF，基于自动机如简化向后伸展ORACLE匹配，基于和位并行如小字母位并行、宽窗位并行，快速移动（FSO）和SBNDMq。他们将模式长度和字母表大小分为四类。他们的结论是，改变很短的模式和非常小的字母的大小是可以接受的，FJS适用于很短的模式和大或非常大的字母表，HASHq能快速应用于短或长的模式和小的字母。

在本文中，我们比较一组不同的字母大小的字符串匹配算法：非常小，小，大，非常大的字母–SBNDM2, SBNDM4, Horspool (H) , Maximal Shift (MS) , SA, HASHq, FJS和BSDM。这些算法对于非常小，小，大，非常大的字母是可用的。FJS算法结合了BM算法和KMP算法两个想法。这是早期的混合算法的延伸。FJS算法开始通过最右边的字符模式匹配；如果匹配模式时，必须向右移动。该算法通过不断匹配从左到右的模式，直到发生不匹配，使用KMP算法，然后模式必须由KMP右移。然后，该算法重复的第一步。该算法的性能优于短的、大的和非常大的字母表的其他算法。HASHq算法提高搜索性能的每个字符在q-grams模式和存储值（m - i 1）哈希表中的开头位置h_i (q-1le;ilt; m)，初始化哈希表的值（m - q 1），这是最大的模式右移，然后相应的变化。根据卡普–拉宾散列函数h_i=sum;q - 1 k = oY[i-k]2^K计算好需要时间O(q)。 HASHq算法的效率是由于概率|sum;|^-P，在模式或文字的任何位置出现的q-grams小于概率|sum;|^-1，哈希q-grams的特征随时问的增加变得更加高效，但它的性能由于短模式而降低。这是因为计算哈希值的成本变得大于与短的模式比较的成本。该算法速度快，但它只有当q = 1时遵循Horspool的转变。因此，使用其他的变化可能会增加算法的性能。最近，Faro 和 Lecroq提出一种新的算法，根据构建一个自动机模拟一个字符串中的每个字符可以出现在最多一次模式后缀。非常小的字母表和短模式算法变得无用。

主要的问题是寻找最大的好的变化和必要的时间来计算这些变化之间的权衡；一些算法可以计算更大的安全位移的模式，但处理时间变得更大。在本文中，我们提出了一个快速的变化，这取决于出现的字符和它们之间的距离。这种方法用于计算字符出现的距离是非常相似的好后缀规则的方法，由Boyer 和 Moore，但我们的方法是更轻。好后缀规则需要时间O（m2），我们的方法计算的字符的距离在时间O（m）。尽管我们的方法有点弱，但速度更快。除了字符的距离，我们提出了两点意见，以加速这些算法错过的行为规则变化。最后，我们用Horspool坏字符规则来应对在模式右边的位置发生错配时。我们实现了我们的算法，我们称之为转变SSM（简单的字符串匹配），我们注意到，SSM表现出对自然语言文本的更好的性能， 基因和蛋白。

该文件的其余部分如下。第2节提出的算法，3节显示了实验结果和4节提供了我们的结论。

2.算法

SSM算法用来搜索文本Y找到一个X模式。扫描过程中从文本的最左端朝右端，匹配过程是从相反的方向进行。在扫描过程中完成，预处理阶段计算模式中的每个字符的最大安全位移。假设特征X_j有一个最近发生在离开的位置，然后最大的安全位移或字符X_j该距离是（j-i）。随后，该算法抓住的字符，有较大的安全位位移并使用它作为一个比较的支点，而不是在模式匹配过程中最右边的字符的位置文本的性质，称为Horspool算法。通过这个修改，我们确保了有关的最大字符安全位移。此外，我们做以下两点观察。首先，给定一个文本Y[alpha;₀alpha;₁..alpha;_n-1]。一个模式X[beta;₀beta;₁..beta;_m-1]，如果不匹配，出现在位置0le;K＜m和字符集{beta;_i，beta;_{i 1}，..，beta;_k-1，beta;_k}等于0le;i＜K，然而正确的匹配模式（K- i 1）向右位移是浪费时间，我们应该准确地逐步降低模式（K - i 1）定位。其次，如果不匹配，出现在位置j，使字符等于{beta;_j，..，beta;_k-1，beta;_k}且beta;_jne;beta;_{j 1}，然后将匹配模式（K -j 1）向右位移是浪费时间，我们必须将模式（K -J 1）准确定位。这两个观测相结合的最大字符的安全位移加快搜索过程非常小，小，大，非常大的字母和实际模式的长度（4–32）。

SSM算法如下。它与相应的文本字符的Y[i]模式的主要角色；如果发生不匹配的算法，转换模式的转变对Horspool比赛最后Y[i]模式或移的不是发生在模式案例m位置模式。如果存在匹配和特征模式，SSM在匹配的过程中从最右边的字符模式，如果遇到一个不匹配的是，我们应该采用混合变化。为了防止在每次换挡后文本的边界测试，我们把一个观察点放在HASHq文本的最后，复制模式X到的文本 Y结束。SSM算法的伪代码是2.1节中。

2.1算法的伪码

SSM算法由两部分组成。第一部分是在预处理阶段，如图1所示，第二部分是图2中的主SSM算法的伪代码。

在图1中计算了Horspool的转变和角色的距离（排3–16）。计算距离的时间复杂度，找到支点的时间是根据图1中的6号线来计算的。接下来，在图1中的算法被称为计算我们的转变，根据所提出的意见。第一个观测代表的是图1（排18 - 26），二次观察用线36 - 28。下面是最大化的步骤，这是由38条线表示42。最大化的步骤选择区中心和移动计算机的线路18–36图1之间的最大位移。这个预处理阶段需要的时间复杂度O（m），其中m是模式的长度。

搜索阶段表示在图2（排5 - 18）。该算法将该模式的字符与对应的文本字符进行比较。如果发生不匹配，应用Horspool的转变；否则，我们最大的转变是应用到文本结束。

大多数的不匹配发生在模式的最右端，为此SSM算法最大限度地在模式的结束偏移在特征位置做一个额外的比较。如图3所示，该模式的一端移动9，与其他移动相比，该偏移量大。

2.2.实例

使X = AAGTAAAACAAA。特征字符是X[8 ]= C这个特征字符的最大距离为9。位移的连续更新列表如图3所示，根据SSM预处理阶段图1。根据代码行第一次更新位移列表26至28；二次更新是根据18号线的36号线；和最后的更新是通过记录更高的位移根据代码行38至42。在这个例子中，我们看到，发生不匹配时，在任何位置0le;ile;11模式中的X，在i不在中心，八个文本Y的字符没有经过检验而通过。这种转变是应用在一个匹配发生在特征位置。匹配发生的概率是1 /|sum;|；如果文字Y有n个字符同样概率可能是特征，产生字符X[Pivot]和文本Y[i]的概率是n/|sum;|，那么大量的转换会产生。

在比较Horspool，如果发生不匹配在任何位置0le;ile;10，位移总是由1。同样，HASH3模式向右位移4，如果错误匹配发生在任何位置0le;i＜9。Boyer 和Moore的算法有一个很好的后缀位移，但计算的位移成本较大，如果不匹配发生在9或10的位置，位移是由1；如果不匹配发生在位置8，位移是4，否则，在位置0 - 7，位移是9。

图3中的转换列表是从文本独立计算，它可以用于搜索任何文本，所以我们可以称之为SSM是一个在线算法。由2个观测的转变并没有出现在最后的位移列表中的例子，但它出现时的重心转向较小。因此，实验结果表明选择两个转变增幅的最大量可以产生快速算法。

3.实验结果

我们在Visual C #实现了SSM算法 ，为了公平起见与其他的算法在相同的环境下实现。我们使用的C代码，Faro和Lecroq的corpora。此外，我们测试了所有的算法是阿拉伯语文本。运行时间是以毫秒计上，运行在Intel Core^TM2 Duo CPU 3 GHz和2 GB内存的台式电脑。我们记录了经过时间的预处理和搜索阶段，所有的方法没有时间的读取数据。为了获得更准确的时间，我们平均年龄时间超过1000种模式从给定的文本中随机抽取。在所有的表格中，最优秀的时间是固定的。

分析结果见表1，SSM算法优于所有算法的各类文本中，除了一个中文文本BSDM ，对 基因的西部和BSDM2旅程。BSDM更好地工作在非常大的字母和很短的模式，而是变得不切实际，当模式长度很短，无法返回在某些情况下，模式出现（记为“-”表中）。

图1.预处理的SSM算法

在行4，SSM算法的运行时间比HASH3快约为50%，在运行时间是相似的除了 基因。从表1的结果，我们看到，BSDM算法具有较好的平均比SBNDM4，SBNDM2，MS，H，SA，FJS和HASH3，但是该算法没有对 基因的结果报告。该算法的问题源于现实，它不能建立在一个很小的字母表后缀自动机和很短的模式长度。

根据表2，SSM算法对于 基因记录运行次数比所有其他人更好除了HASH3算法，其中包含一个非常小的字母（A，C，G，T），这意味着位移会很小。

图2.SSM算法

图3.连续位移列表更新示例

关于模式的长度16（表3），SSM算法更好的记录运行次数对阿拉伯语、英语和汉语文本而SBNDM2记录更好的运行时间对意大利语，法语和蛋白文本，和HASH3对 基因更好。

同样，在模式长度32（表4），HASH3记录更好的运行时间比SSM除了中文文本。运行时间记录SSM非常接近运行HASH3和优于其余算法除了SBNDM2。

表1.从超过1000个模式的文本中随机选择的模式长度为4的平均运行时间。

表2.从超过1000个模式的文本中随机选择的模式长度为8的平均运行时间。

表3.从超过1000个模式的文本中随机选择的模式长度为16的平均运行时间。

表4.从超过1000个模式的文本中随机选择的模式长度为32的平均运行时间。

4.结论

一个简单的和有效的算法，精确的字符串匹配的自然语言文本， 基因和蛋白的介绍和实验结果显示。所提出的算法寻找一个模式的字符，具有最大的安全移和算法使用它作为一个支点进行比较。如果在位移特征匹配成功，SSM算法位移模式正确的混合移；否则，SSM算法采用Horspool的替换。SSM算法执行预相位在时间复杂度和空间复杂度为O(m)和行为在一个COM度类似的其他实验线性时间算法。实验结果表明，此算法对不同字母的实用性和有效性。SSM算法是阿拉伯语和英语的实践模式长度的文本，很短，短的模式ge;4或＜32。最好是意大利语，法语和蛋白的模式ge;4或＜16文本长度。对中文文本，SSM算法与模式的长度ge;8或le;32更好。SSM算法的效率来自最不匹配发生在文本最右端的事实，这是由动态旋转特性产生。

我们的目标发展未来的工作是扩展SSM算法解决带通配符的字符串匹配，多个字符串匹配和近似串匹配变量q-grams。

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[29071]，资料为PDF文档或Word文档，PDF文档可免费转换为Word