KareemNaaz-Vasavi (KV)模式匹配算法

摘要

在计算机科学中，模式匹配是检查给定符号序列是否存在模式的过程。这些模式通常具有序列或树状结构的形式。模式匹配的用途包括输出模式在令牌序列中的位置、输出匹配模式的某些组件以及用其他令牌序列替换匹配模式。文本字符串等序列模式通常使用正则表达式进行描述，并使用回溯等技术进行匹配。模式匹配可以用来过滤某种结构的数据。它用于查找文本中相对较小的模式，而文本非常大。模式和文本可以是一维的，也可以是二维的。在One Dimensional的例子中，可以是文本编辑器。本文提出的KareemNaaz-Vasavi (KV)模式匹配算法适用于一维模式和文本。我们遵循软件开发生命周期的各个阶段来演示所提出的KV模式算法。 Pattern matching and proposed KareemNaaz-Vasavi (KV) pattern matching algorithm are introduced in detail. The proposed algorithm is analyzed and designed. The proposed algorithm is implemented by using C programming Language. We test the implementation of proposed algorithm using different test cases.

关键字

算法，程序，软件，开发。

简介

在计算机科学中，模式匹配是检查给定符号序列是否存在某种模式的过程。与模式识别相反，匹配通常必须精确。这些模式通常具有序列或树状结构的形式。模式匹配的用途包括在令牌序列中输出模式的位置、输出匹配模式的某些组件以及用其他令牌序列替换匹配模式。文本字符串等序列模式通常使用正则表达式进行描述，并使用回溯等技术进行匹配。第一个使用模式匹配的计算机程序是文本编辑器。模式匹配中最简单的模式是显式值或变量。可以从原始模式构建更复杂的模式。模式匹配可用于筛选某一结构的数据[1］．它适用于表达式的结构。到目前为止，最常见的模式匹配形式涉及字符串。在许多编程语言中，使用特定的字符串语法来表示正则表达式，正则表达式是描述字符串字符的模式。模式匹配是找到一个模式，在文本中相对较小，而文本应该非常大。模式和文本可以是一维的，也可以是二维的。在One Dimensional的例子中，可以是文本编辑器。在文本编辑器中，我们有26个字符和一些特殊符号。在二维的情况下，典型的应用是计算机视觉中的模式匹配。E_我在一维或二维的情况下，文本非常大，需要一种快速的算法来查找其中出现的图案。本文提出的KareemNaaz-Vasavi模式匹配算法以模式和文本为输入。将文本中与pattern的第一个字符相同的字符下标放入起始数组，s表示文本中与pattern的第一个字符相同的字符数。将文本中与图案的最后一个字符相同的字符下标放入end数组中，e表示文本中与图案的最后一个字符相同的字符数。计算起始数组和结束数组元素的差值，如果差值等于strlength(pattern)-1，则在text中从start[i]到end[j]的索引范围内比较从索引2到strlength(pattern) -2的pattern剩余字符。

本文算法的分析与设计

图1显示文本，由26个字符“INDIAISMYCOUNTRYALLINDIANS”组成，从索引0到索引25。因此，文本的长度(n)是26。

图2中所示的文本中显示要搜索的模式图1．由6个字符“TRYALL”组成，从索引0到索引5开始。所以，图案的长度m是6。

在本文提出的KareemNaaz-Vasavi (KV)模式匹配算法中，我们使用了索引为s的起始数组，用于存储与模式第一个字符相同的文本字符的索引。在图2T是pattern和in的第一个字符图1，文本中第一个字符的索引只有13个。因此将它放入start array中，s表示文本字符的下标数，下标数与pattern的第一个字符相同。在这个例子中，s为1，因为只有一个索引13的文本被放置到开始数组(图3）.

在本文提出的KV算法中，我们也使用了带有索引e的末端数组，用于存储文本字符的索引，这些索引与模式的最后一个字符相同。在图2 A图案的最后一个字符是在吗图1时，文本中最后一个字符的索引为17和18。这些文本的索引被放入end数组中，e表示文本字符的索引数量，这些索引与pattern的最后一个字符相同。在这个例子中，e是2，因为文本的两个索引{17,18}被放置在end数组中(图4）.

将文本字符的索引放入起始数组和结束数组后，每个元素E_我(i=1到s)从起始数组的每个元素E中减去_j(j=1到e)。如果我们发现差异等于strlength(pattern)-1，即。(E_j- E_我) = m - 1。然后余下的文本字符的范围(E_{我+ 1}E_{j - 1})与范围(1 ~ m-2)的模式特征进行比较。图5显示了范围为(14到17)的文本字符与范围为(1到4)的模式字符的比较。由于所有比较的equal状态都为YES，因此这意味着文本中存在模式。

算法1查找索引的pattern(1到m-1)的所有字符是否与索引的text (s+1到e-1)的字符相同。它有两个输入s和e, s表示文本字符的索引，与模式的第一个字符相同，e表示文本字符的索引，与模式的最后一个字符相同。如果索引的文本(s+1到e-1)中的所有字符都与索引的pattern(1到m-1)中的所有字符匹配，则算法1返回true，表示文本中存在模式，否则返回false，表示文本中不存在模式[2］．

在算法1While循环从(s+1到e)或(1到m-1)重复。所以算法found(s,e)所花费的总时间是O(m)M为图案长度，在文本中进行搜索。

在算法2各元素E_我(i=1到s)从起始数组的每个元素E中减去_j(j=1到e)。如果差值等于strlength(pattern)-1。(E_j- E_我)= m-1，则范围(E_{我+ 1}E_{j - 1})与范围(1 ~ m-2)的模式特征进行比较。如果范围为(E_{我+ 1}E_{j - 1})与范围为(1 ~ m-2)的pattern的所有字符相同，则在文本中存在pattern，否则在文本中不存在pattern。

在算法2中，外循环重复s+1次，内循环重复s.(e+1)次，算法found()被称为s.e次。每次found()都需要O(m)时间来匹配文本和模式的字符。算法2所花费的总时间为O(m.s.e)。O (m)。

算法3以模式和文本为输入，将与模式第一个字符相同的文本字符下标放入开始数组，将与模式最后一个字符相同的文本字符下标放入结束数组。在算法3中，s表示文本的字符数，与模式的起始字符数相同，e表示文本的字符数，与模式的结束字符数相同。

在算法3for循环从0开始重复n次，match()调用花费O(m)时间。所以算法3花费的总时间是O(n) + O(m)。

算法的C语言实现

该算法使用C语言实现，C语言是一种健壮的、面向结构的编程语言，它提供了不同的概念，如函数、指针、结构、数组等来解决复杂的问题。

所提出算法的测试

不同的测试用例被用来测试程序1的结果。考虑下面的测试用例，其中文本由26个字符“indiaismycountryallindians”组成，从索引0到索引25。模式由6个字符“tryall”组成，从索引0到索引5。对于给定的模式，显示结果" pattern tryall found " [3.］(图6)．

结论

我们得出结论，在本文提出的KareemNaaz-Vasavi (KV)模式匹配算法中，我们将模式和文本作为输入，将与模式第一个字符相同的文本字符下标放入开始数组，将与模式最后一个字符相同的文本字符下标放入结束数组。各元素E_我(i=1到s)从起始数组的每个元素E中减去_j(j=1到e)。如果差值等于strlength(pattern)-1。(E_j- E_我)= m-1，则范围(E_{我+ 1}E_{j - 1})与范围(1 ~ m-2)的模式特征进行比较。如果范围为(E_{我+ 1}E_{j - 1})与范围为(1 ~ m-2)的pattern的所有字符相同，则在文本中存在pattern，否则在文本中不存在pattern。

参考文献

1. 阿霍阿尔弗雷德V和杰弗里D u数据结构和算法。艾迪森·韦斯利，马萨诸塞州雷丁，1983年。
2. Cormen TH，等。算法导论。麦格劳-希尔，纽约，1990年。
3. 克努特唐纳德E.计算机编程的艺术，卷3，排序和搜索。Addison-Wesley, Reading，马萨诸塞州，1998年。