数据结构中串的模式匹配算法演示系统的研究

Research of a Demonstration System for Pattern Matching Algorithms of Strings in Data Structure

摘要: 本文研究了数据结构中的朴素模式匹配算法(BF)和快速模式匹配算法(KMP)，并将其算法程序、中间变量、结果展示结合到一起，使用JavaSwing等进行相关图形界面开发，使得在同一界面上，不仅能展示BF算法和KMP算法的代码，并且能够显示字符串模式匹配算法执行过程中每一步的操作流程，还可以随时进行暂停、回退、继续等。该演示系统不仅可以帮助学生快速学习理解字符串模式匹配的原理，还可以有效地提高学生的实践能力，所见即所得地快速上手编程。

Abstract: This article has studied the naive pattern matching algorithm (BF) and the fast pattern matching algorithm (KMP) in data structures, and combined their algorithm programs, intermediate variables, and result display. Using JavaSwing and other related graphical interface development, it is possible to not only display the code of the BF algorithm and KMP algorithm on the same interface, but also display the operation flow of each step in the execution process of the string pattern matching algorithm. It also can be pause, rollback, resume, and so on at any time. The demonstration system can not only help students quickly learn and understand the principles of string pattern matching, but also effectively improve students’ practical abilities, namely, WYSIWYG, and fast hands-on programming.

1. 引言

字符串(简称串)是一种重要的数据结构。随着计算机科学的发展，信息变得越来越多，而字符串构成的文本资料是信息的重要载体之一。想要在海量的文本资料中查找到所需信息，那就需要进行信息检索，而好的字符串模式匹配算法可以极大地提高检索的效率和质量。除此之外串的模式匹配算法还广泛应用于搜索引擎 [1] 、模式识别 [2] 、数据挖掘 [3] 、信息安全 [4] 、网络入侵检测 [5] 、数据压缩 [6] 、拼写检查 [7] 等领域中。

为更好地学习这些串的模式匹配算法，一种较好的方式就是通过动画演示来帮助理解，快速入门。演示系统可以图文并茂的展示算法的原理、过程及结果，既有助于教师生动的教学，又帮助学生直观地理解。目前也有许多相关的演示系统 [8] [9] [10] ，本文在研究了这些系统的基础上，结合学生的需要研究并开发了更全面、更简洁、更方便的串模式匹配算法演示系统。

2. 串的模式匹配算法

串模式匹配算法是指在主串中找到与模式串相同的子串，并返回其在主串中的所在位置。假设主串长度为n，模式串长度为m。在数据结构中，主要的模式匹配算法有BF (Brute Force)算法和KMP (由D. E. Knuth，J. H. Morris和V. R. Pratt提出)算法 [11] 。其中BF算法是简单的模式匹配算法，而KMP算法是一种改进的快速模式匹配算法。

2.1. BF算法

BF算法就是将主串中所有长度为m的子串依次与模式串对比，直到找到一个完全匹配的子串，或所有的子串都不匹配为止。BF算法匹配原理如图1所示。

Figure 1. Matching principle of BF algorithm

图1. BF算法匹配原理

2.2. KMP算法

KMP算法，设i为主串中指向当前需要匹配字符的指针，j为模式串中指向当前需要匹配字符的指针，当i和j所指向的字符不匹配时，主串指针i不进行回溯，只令模式串指针j回溯到模式串的最大公共前后缀+1的位置，然后主串和模式串再进行模式匹配。具体过程如下：

1) 第1个元素匹配失败，匹配下一个相邻子串，j = 0，i++，j++；

2) 其他元素匹配失败，主串指针i不回溯，模式串指针j按next数组回溯，k = next[j]。其中next[j]里面存放的是模式串位置0至位置j − 1的子串中最大公共前后缀长度。

KMP算法匹配原理如图2所示。

Figure 2. Matching principle of KMP algorithm

图2. KMP算法匹配原理

在KMP算法中，需要首先计算模式串中每一个位置j的字符和主串中i位置字符不匹配时，在主串不回溯(i不变)的情况下主串i位置要和模式串的k = next[j]位置进行新的匹配。而求k = next[j]是与主串无关的，经过总结，可以得到next[j]的计算公式为

$\text{next}\left[\text{j}\right]=\{\begin{array}{ll}-1\hfill & j=0\hfill \\ k\hfill & 0\le k<j且使用"p_0\cdots p_{k-1}"="p_{j-k}\cdots p_{j-1}"的最大整数\hfill \end{array}$ 公式(1)

3. 串的模式匹配算法演示系统设计

在演示程序中，程序的展示界面要能够显示BF算法和KMP算法的Java代码，并且要能够显示字符串模式匹配算法执行过程中每一步的操作流程，包括确定当前正在进行模式匹配的主串的子串，确定当前主串指针i和模式串指针j的所在位置，以及突出显示当前操作对应模式匹配算法的某一句代码等细节，让使用者能够清楚明白程序运行的实时情况。而且在演示程序中要提供简单方便的操作，如连续执行，单步执行，暂停等，有助于使用者学习理解字符串模式匹配算法。当演示程序正在演示字符串模式匹配算法的执行过程时，主要能够展示通过主串指针i和模式串指针j所指位置，对主串中的子串和模式串进行所指当前位置的模式匹配，如果所指当前位置的模式匹配成功，则指针指向下一个相邻位置再进行模式匹配；如果所指当前位置模式匹配失败，则主串指针i和模式串指针j回溯到由字符串模式匹配算法所确定的位置，然后再进行新位置的模式匹配，直到模式串中所有位都匹配成功，则找到了模式串在主串中的位置，匹配过程成功，在屏幕上输出匹配成功的位置；或者主串中的没有一个子串与模式串能够匹配，则匹配过程失败，在屏幕上输出匹配失败。

3.1. 演示系统整体功能设计

演示系统为使用者提供三种模式匹配算法的演示执行，其中包括BF算法模式匹配演示，KMP算法模式匹配演示，改进KMP算法模式匹配演示。整体系统功能图如图3所示。

Figure 3. System function diagram

图3. 系统功能图

3.2. 演示系统中的详细功能

3.2.1. 输入字符串

在进行模式匹配算法的演示执行之前，使用者可以输入任意的、自己指定的主字符串和模式字符串来进行模式匹配算法演示。当使用者输入主串和模式串以后，使用者输入的主串和模式串会经过系统的自动处理，显示在系统的演示界面中，演示界面还包括模式匹配算法的主要代码，以及在模式匹配算法演示执行过程中所生成的中间变量，这些数据都会显示在演示界面中。输入字符串后处理流程如图4所示。

Figure 4. Input string function flowchart

图4. 输入字符串功能流程

3.2.2. 按钮功能

在演示过程中，使用者可以点击系统提供的相关演示按钮来进行演示操作，这些按钮包括单步按钮，执行按钮，暂停按钮，恢复按钮，修改按钮和返回按钮。使用者可以通过点击单步按钮，来单步执行模式匹配算法中的每一行的代码，根据模式匹配算法中的每一行的代码内容，系统会自动在演示界面中显示数据，并将字符串的模式匹配过程用图形界面编程使其形象化，供使用者学习和理解模式匹配算法的执行原理。点击执行按钮时，系统会自动执行模式匹配演示程序至模式匹配演示程序结束。点击暂停按钮，会在系统自动执行模式匹配演示程序时，终止系统自动执行模式匹配演示程序。点击恢复按钮，系统会恢复到使用者输入主串和模式串时的演示界面，即重新开始演示根据用户输入的主串和模式串的模式匹配程序。以BF算法为例的演示主界面如图5所示。

从图5可以看到，本演示系统还有一个其他演示系统中没有的功能按钮：修改按钮。因为在现实生活中，各种版本的数据结构算法模式匹配代码原理大致相同，但是，代码的中间变量名称却各不相同，为了方便使用者学习模式匹配算法，并且不会因自己所学代码和系统代码中的中间变量名称不同，而搞混淆模式匹配算法原理，系统为使用者提供修改功能，可以对系统代码中的中间变量名称进行修改，类似如主串指针名称和模式串指针名称，可以通过系统提供的修改按钮对主串指针名称和模式串指针名称进行修改，方便使用者对模式匹配算法代码的学习。还有返回按钮，当使用者浏览完演示界面中的模式匹配演示后，使用者想要观看其他算法的模式匹配演示过程，则使用者可以点击返回按钮，返回到可以选择模式匹配算法演示界面，对其他算法的模式匹配演示过程进行浏览观看。

Figure 5. System demonstration main interface (BF algorithm as an example)

图5. 系统演示主界面(BF算法为例)

4. KMP算法的演示过程实现

模式匹配算法中BF算法较为简单，这里以KMP算法为例介绍一下KMP算法的演示过程。

4.1. 求Next值的演示

Next数组值计算如公式(1)所示，实际上这个计算过程就是求模式串自身的模式匹配过程，所以在演示系统中用模式串当主串，模式串也是待匹配的子串模式串，进行从头开始的模式匹配过程，求得模式串中每个字符位置j之前的子串中前缀和后缀相同的位数。

演示系统中首先创建继承于JPanel类KMPNextRoot类用于求Next数组演示的根容器，然后在其中设置当前根容器的子控件布局，并设置下一步按钮方法，在其中设置单步按钮事件监听器的具体内容，记录求Next数组演示的执行次数，设置界面上具体的显示内容。演示界面如图6所示。

Figure 6. Demonstration interface for finding Next arrays

图6. 求Next数组的演示界面

4.2. KMP模式匹配过程的演示

求得Next数组后，再进行KMP无回溯的模式匹配过程，匹配过程参考图2所示。实现中首先创建KMPRoot类，其继承于JPanel类，用于作为KMP算法模式匹配演示的根容器。在其构造方法中，设置当前根容器的子控件布局，并设置下一步按钮方法，在其中设置单步按钮事件监听器的具体内容，KMP算法模式匹配演示的执行次数和突出显示KMP算法代码编号，设置界面上具体的显示内容。演示界面如图7、图8所示。

Figure 7. KMP demonstration process interface No. 1

图7. KMP演示过程界面1

Figure 8. KMP demonstration process interface No. 2

图8. KMP演示过程界面2

改进的KMP算法在演示系统中也进行了展示，篇幅原因，论文中不再描述。

在KMP算法及改进KMP算法的演示系统中，用户可以定制变量名称，以便与书中所讲内容相匹配。比如位置指针名称可以是i，j，也可以名称是t，k，由用户自由定制，如图9所示。并且在系统中还可以点击“恢复”按钮随时恢复到本次模式匹配最初的状态，方便上课过程中进行不断的重复演示。相对于传统的模式匹配演示系统，如文献 [8] 中提到的，自由定制指针名称和随时恢复最初状态是本系统为方便用户操作及理解做的一项创新性探索，并且通过实操发现这两项功能非常实用。

Figure 9. Modification of pointer name

图9. 修改指针名称

5. 总结与展望

在演示系统中，视频、文本、图片、交互动画和演示执行程序，相互配合，从而构建出了一个更有效率的学习环境。本次研究的字符串模式匹配算法演示系统的研究能让使用者通过直观的方法理解字符串模式匹配的原理，了解字符串模式匹配算法的执行过程。后续还会研究开发更多的演示系统，通过演示系统，可以把抽象难懂的数据结构理论数据模型变得容易理解，有助于更好地学习和运用数据结构中的内容，提高了数据分析计算的效率与效果。

基金项目

北京市人文社科基金重点项目：大数据背景下北京市属高校新工科人才培养质量过程性评价研究(19JYA001)资助。教学改革项目：促进高校分类发展–专业建设–计算机学院专业建设与人才培养模式改革资助。