CN111814009B - 一种基于搜索引擎检索信息的模式匹配方法 - Google Patents

Abstract

本发明公开了一种基于搜索引擎检索信息的模式匹配方法，采用BF改进算法，即先从待匹配模式串提取字符或者字符串形成新模式串，将新模式串与待匹配模式串进行对比，记录下这些字符或者字符串之间间隔的字符数，把组成新模式串的字符个数与字符间隔的字符数构成对象，然后用新模式串中的字符与目标串相应位置上的字符进行多轮比较，先比较对象中的偶数索引，直到新模式串与目标串中相应位置上的字符完全匹配，再比较对象中奇数索引，直到在目标串中找出待匹配模式串。通过优化模式串的比较结构和比较顺序，每一轮匹配不必从模式串的第一个字符一一与目标串中的相应字符进行比较，能减少比较次数，提高模式匹配效率。

Description

一种基于搜索引擎检索信息的模式匹配方法

技术领域

本发明涉及模式匹配领域，具体涉及一种基于搜索引擎检索信息模式匹配的BF改进算法。

背景技术

随着计算机网络技术的飞速发展，每时每刻产生的信息量呈爆炸式增长，包括文字、图片、音频、视频、地理位置等非结构化数据。计算机网络给人们带来了方便和快捷，但也被这些海量数据信息所淹没。无序、庞大的信息世界和形式多样的链接方式，让人们在查找所需信息时感到无所适从。数据信息量如此庞大且多为非结构化的数据格式，这就对搜索引擎检索信息提出了更高的要求，它不再只是帮助人们从海量数据中检索出更多的信息，而是更快速更高效更准确地查询出匹配的信息，并且要过滤掉与检索无关的信息或有害信息。

搜索引擎要从大量的数据中进行信息检索和内容过滤操作，就需要用到模式匹配。模式匹配是数据结构中字符串的一种基本运算，目的是在给定一个模式串后，再从某个目标串中找出与该模式串相同的所有模式串。具体运算过程是，假设P是给定的模式串，T是待查找的目标串，要求从T中找出所有与P相同的模式串。如果T中存在一个或多个为P的模式串，就给出该模式串在T中的位置，称为匹配成功，否则匹配失败。BF算法是模式匹配常用算法之一，它的思想是将目标串T的第一个字符与模式串P的第一个字符进行匹配，若相等，则继续比较目标串T的第二个字符和模式串P的第二个字符；反之若不相等，则比较目标串T的第二个字符和模式串P的第一个字符，依次一轮又一轮的比较下去，直至模式串P中的每个字符依次和目标串T中的一个连续的字符序列相等为止。

为了更好的理解传统的BF算法的原理，接下来以一个实例来说明BF算法的过程。这里要特别说明，实例只是为了说明算法原理，因此这个例子中目标串T长度较小，只有25位，且数据格式只包括了字母和特殊字符，但是实际情况下数据库中储存的需要遍历匹配的目标串T的长度远不止25，数据格式也更复杂。给定一个目标串T＝xyzabxyxyzaz％yyyxyza％xyyy，长度是25，模式串P＝xyza％xyyy，长度是9。其中，这里的目标串T代表搜索引擎数据库中存储的海量数据，模式串P代表用户在搜索引擎中想要匹配出检索结果的关键字。如图1所示，传统BF算法实例匹配过程步骤如下：

(1)第1轮匹配

将模式串P的第1个字符与目标串T的第1个字符进行比较，P₀等于T₀，依次往下继续比较，P₁等于T₁，P₂等于T₂，P₃等于T₃，第5次比较时，P₄不等于T₄，匹配失败。在第1轮匹配中，比较次数总共是5次。

(2)第2轮匹配～第5轮匹配

将模式串P的第1个字符与目标串T的第2个字符进行比较，P₀不等于T₁，匹配失败。在第2轮匹配中，比较次数总共是1次。按照BF算法思想，继续进行第3轮、第4轮、第5轮匹配，分别比较一次后即发现P₀不等于T₂，P₀不等于T₃，P₀不等于T₄，匹配失败，因此在第3轮匹配的比较次数总共是1次，第4轮匹配的比较次数总共是1次，第5轮匹配的比较次数总共是1次。

(3)第6轮匹配

将模式串P的第1个字符与目标串T的第6个字符进行比较，P₀等于T₅，依次往下继续比较，P₁等于T₆，第3次比较时，P₂不等于T₇，匹配失败。在第6轮匹配中，比较次数总共是3次。

(4)第7轮匹配

将模式串P的第1个字符与目标串T的第7个字符进行比较，P₀不等于T₆，匹配失败。在第7轮匹配中，比较次数总共是1次。

(5)第8轮匹配

将模式串P的第1个字符与目标串T的第8个字符进行比较，P₀等于T₇，依次往下继续比较，P₁等于T₈，P₂等于T₉，P₃等于T₁₀，第5次比较时，P₄不等于T₁₁，匹配失败。在第8轮匹配中，比较次数总共是5次。

(6)第9轮匹配～第16轮匹配

将模式串P的第1个字符与目标串T的第9个字符进行比较，P₀不等于T₈，匹配失败。在第9轮匹配中，比较次数总共是1次。按照BF算法思想，继续进行第10轮至第16轮匹配，分别比较一次后即发现P₀不等于T₉，P₀不等于T₁₀，P₀不等于T₁₁，P₀不等于T₁₂，P₀不等于T₁₃，P₀不等于T₁₄，P₀不等于T₁₅，匹配失败，因此在第10轮至第16轮匹配中，每轮匹配的比较总次数均是1次。

(7)第17轮匹配

将模式串P的第1个字符与目标串T的第17个字符进行比较，P₀等于T₁₆，依次往下继续比较发现，模式串和目标串的每一次字符比较都相等，总共比较9次，匹配成功。

通过第1轮至第17轮比较总次数相加可得，在该实例中利用传统的BF算法实现匹配成功需要35次比较。

从上述BF传统算法流程可以看出，它每次匹配都是从模式串的第一个字符开始逐个字符往后匹配，当匹配完一次后，模式串相对于目标串往后移一个字符的距离继续逐个匹配，在整个过程中，一旦某个字符匹配失败就要从头开始，也就是从本次目标串起点的后一个字符开始跟模式串的逐个字符重新匹配，这样机械化地去逐个重复匹配，导致了比较次数多，匹配效率低。

发明内容

本发明针对BF传统算法在每一轮匹配中每个字符都要逐个比较且比较顺序固定单一，存在比较次数多、匹配效率低等缺陷，提出了一种改进算法，克服了上述BF算法的不足，它从目标串中找出模式串的过程中，优化了模式串的比较结构和比较顺序，减少了比较次数，提升了匹配效率。

为解决上述的技术问题，本发明的一种实施方式采用以下技术方案：

一种基于搜索引擎检索信息的模式匹配方法，采用BF改进算法，其具体技术方案如下：

步骤1：根据待匹配模式串的结构特点和内容特征，从里面提取出一些字符或者字符串形成一个新模式串。对新模式串的基本要求是它需要包括待匹配模式串的第一个字符和最后一个字；进一步的技术方案是，新模式串还需要包括待匹配模式串中区别于其他字符的特殊字符，或者新模式串还需要包括待匹配模式串中连续的有规律的字符串。由此可见，新模式串可以是待匹配模式串中第一个字符和最后一个字符组成的新模式串；也可以是第一个字符、区别于其他字符的特殊字符和最后一个字符组成的新模式串；也可以是第一个字符、连续的有规律的字符串、最后一个字符组成的新模式串；还可以是第一个字符、区别于其他字符的特殊字符、连续的有规律的字符串、最后一个字符组成的新模式串。也有可能的是，待匹配模式串的第一个字符或者最后一个字符就是区别于其他字符的特殊字符或者连续的有规律的字符串。由于目标串中存在特殊字符、规律字符串、连续字符串以及它们各自组合的几率较小，利用优化了结构的新模式串去与目标串进行匹配，可以提升字符匹配失败的几率，快速进入下一轮匹配中去。这里所指的特殊字符是相对的，它通常在待匹配模式串中出现的几率较小，类型也可能存在差异，举个例子，当待匹配模式串中具有若干个英文字母和一个标点符号或者数字，那么这个标点符号或者数字就可以作为特殊字符，当待匹配模式串中具有若干个数字和一个英文字母时，那么这个英文字母就可以作为特殊字符，待匹配模式串中可能不止一个特殊字符，这里仅举例说明特殊字符的选取模式，不作为限定。连续的有规律的字符串可能是一个字符重复得到的字符串，也可能是多个字符按顺序排列并重复得到的字符串，比如XX、XYXY、R1！R1！R1！等。

步骤2：将所述的新模式串与所述的待匹配模式串进行对比，记录下这些字符或者字符串之间间隔的字符数，把组成新模式串的字符或者字符串对应的字符个数与所述的字符或者字符串之间间隔的字符数构成一个对象。

这里提供一种具体的操作方法，所述对象的构成模式是：{N₀，N₁，N₂}，或者{N₀，N₁，N₂，N₃，N₄……N_X}，X为正整数，N₀，N₁，N₂，N₃，N₄……N_X的取值为自然数，相互之间可以相等也可以不等，N表示对象的索引，下标用于区分索引为奇数索引还是偶数索引；其中下标为偶数的索引为待匹配模式串中的第一个字符的字符数、或者区别于其他字符的特殊字符的字符数、或者连续的有规律的字符串的字符数、或者最后一个字符的字符数；下标为奇数的索引为前后两个相邻索引之间间隔的字符数。一般来说，将偶数索引对应的字符左右按顺序排列在一起就是所述的新模式串的字符。

步骤3：先用所述的新模式串中的字符与目标串相应位置上的字符进行比较，遵循的比较顺序是：所述的对象中第偶数位索引控制需要比较的字符个数，第奇数位索引控制跳过或间隔不需要比较的字符个数；如果从左往右比较过程中，新模式串的某一个字符与目标串不匹配，则按相同的比较顺序进行下一轮匹配。这里指出的从左往右比较并不是单一的比较方式，也可以从右往左比较。

步骤4：如果新模式串中的每一个字符都比较结束且与目标串中相应位置上的字符都相等，则从所述的待匹配模式串中第一个没有比较的字符开始比较，此时新模式串的字符不需要再进行比较，遵循的比较顺序是：所述的对象中第偶数位索引控制跳过或间隔不需要比较的字符个数，第奇数位索引控制需要比较的字符个数；

步骤5：重复步骤3和4，直到在目标串中找出所述的待匹配模式串，算法终止。

通过上述步骤可知，本发明所述的模式匹配方法利用模式串的结构特点和内容特征，构造出一个新的模式串，新模式串中的字符是从整个模式串(即待匹配模式串)中挑选出来的，它体现了模式串的内容特征，最开始只比较这些特征位置上的字符而跳过其他字符，相较于BF传统算法的从头开始每一位依次匹配，能加快字符匹配失败的速度，一般新模式串的字符数是整个模式串的几分之一甚至更少，大多数情况下新模式串就能导致匹配失败，如果没有失败再从之前跳过的其他字符开始匹配，这时新模式串中的字符则可不用再比较。

模式匹配方法(BF改进算法)通过优化模式串的比较结构和比较顺序，每一轮匹配不必从模式串的第一个字符一一与目标串中的相应字符进行比较，能减少比较次数，提高模式匹配效率。

附图说明

图1是BF传统算法流程图。

图2是本发明BF改进算法流程图。

具体实施方式

为了使本发明的目的、技术方案及优点更加清楚明白，以下结合实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅仅用以解释本发明，并不用于限定本发明。

图2是本发明BF改进算法的实施流程图，采用跟BF传统算法一样的目标串T＝xyzabxyxyzaz％yyyxyza％xyyy，和模式串P＝xyza％xyyy，BF改进算法包括的步骤如下:

按照上述发明内容中，新模式串N的构成思想和方法，通过观察模式串P＝xyza％xyyy，它有区别于其他字符的特殊字符％，以及连续且规律的连在一起的3个字符yyy，再加上第一个字符x，构成新模式串N的字符是x％yyy，对比原模式串xyza％xyyy，这3个字符或串的间隔字符数分别是3、1，因此新模式串N的结构可以用对象表示为{1，3，1，1，3}，其中，第0、2、4偶数位索引表示需比较的字符个数，第1、3奇数位索引表示需跳过的不比较的字符个数，也就是说在整个模式匹配过程中，首先按照x(比较)yza(不比较)％(比较)x(不比较)yyy(比较)进行模式匹配，当新模式串N从左到右顺序出现不匹配时继续进行下轮匹配，直至新模式串N中的字符都比较完成且都相等时，再从第一个之前跳过没有比较的字符开始比较，这时需按照x(不比较)yza(比较)％(不比较)x(比较)yyy(不比较)进行每轮匹配。

(1)第1轮匹配

按照x(比较)yza(不比较)％(比较)x(不比较)yyy(比较)的顺序进行模式匹配，将模式串P的第1个字符与目标串T的第1个字符进行比较，P₀等于T₀，再跳过3个字符比较，P₄不等于T₄，匹配失败。在第1轮匹配中，比较次数总共是2次。

(2)第2轮匹配～第5轮匹配

将模式串P的第1个字符与目标串T的第2个字符进行比较，P₀不等于T₁，匹配失败。在第2轮匹配中，比较次数总共是1次。按照BF算法思想，继续进行第3轮、第4轮、第5轮匹配，分别比较一次后即发现P₀不等于T₂，P₀不等于T₃，P₀不等于T₄，匹配失败，因此在第3轮匹配的比较次数总共是1次，第4轮匹配的比较次数总共是1次，第5轮匹配的比较次数总共是1次。

(3)第6轮匹配

将模式串P的第1个字符与目标串T的第6个字符进行比较，P₀等于T₅，再跳过3个字符继续往下比较，P₄不等于T₉，匹配失败。在第6轮匹配中，比较次数总共是2次。

(4)第7轮匹配

将模式串P的第1个字符与目标串T的第7个字符进行比较，P₀不等于T₆，匹配失败。在第7轮匹配中，比较次数总共是1次。

(5)第8轮匹配

将模式串P的第1个字符与目标串T的第8个字符进行比较，P₀等于T₇，然后跳过3个字符比较，P₄不等于T₁₁，匹配失败。在第8轮匹配中，比较次数总共是2次。

(6)第9轮匹配～第16轮匹配

将模式串P的第1个字符与目标串T的第9个字符进行比较，P₀不等于T₈，匹配失败。继续进行第10轮至第16轮匹配，发现都是比较1次后就失败。

(7)第17轮匹配

将模式串P的第1个字符与目标串T的第17个字符进行比较，P₀等于T₁₇，依次往下继续比较发现，新模式串N中的每一个字符x％yyy与目标串中对应位置的每一次字符都相等，这时就要从模式串P中第一个之前跳过没有比较的字符开始比较，比较顺序是x(不比较)yza(比较)％(不比较)x(比较)yyy(不比较)，模式串P中其余的字符也相等，匹配成功，总共比较9次。

通过第1轮至第17轮比较总次数相加可得，在该实例中利用BF改进算法实现匹配成功需要28次比较，比BF传统算法减少了7次。对于长度越长的目标串和模式串，该改进算法的优势会更明显，减少比较次数会更多。新模式串N中的字符是从整个模式串P中挑选出来的，它体现了模式串的内容特征，最开始只比较这些特征位置上的字符而跳过其他字符，相较于BF传统算法的从头开始每一位依次匹配，能加快字符匹配失败的速度，一般新模式串的字符数是整个模式串的几分之一甚至更少，大多数情况下新模式串就能导致匹配失败，如果没有失败再从之前跳过的其他字符开始匹配，这时新模式串中的字符则可不用再比较。通过优化模式串的比较结构和比较顺序，克服了BF传统算法机械地从模式串第一个字符开始一一与目标串比较的缺点，减少了比较次数，提高了匹配效率。

以上所述仅为本发明的较佳实施例而已，并不用以限制本发明，凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等，均应包含在本发明的保护范围之内。

Claims (5)

1.一种基于搜索引擎检索信息的模式匹配方法，采用BF改进算法，其特征在于包括如下步骤：

步骤1：根据待匹配模式串的结构特点和内容特征，从里面提取出一些字符或者字符串形成一个新模式串；

步骤2：将所述的新模式串与所述的待匹配模式串进行对比，记录下这些字符或者字符串之间间隔的字符数，把组成新模式串的字符或者字符串对应的字符个数与所述的字符或者字符串之间间隔的字符数构成一个对象；

步骤3：先用所述的新模式串中的字符与目标串相应位置上的字符进行比较，遵循的比较顺序是：所述的对象中第偶数位索引控制需要比较的字符个数，第奇数位索引控制跳过或间隔不需要比较的字符个数；如果从左往右比较过程中，新模式串的某一个字符与目标串不匹配，则按相同的比较顺序进行下一轮匹配；所述索引用自然数排序后区分偶数位索引和奇数位索引；

步骤4：如果新模式串中的每一个字符都比较结束且与目标串中相应位置上的字符都相等，则从所述的待匹配模式串中第一个没有比较的字符开始比较，此时新模式串的字符不需要再进行比较，遵循的比较顺序是：所述的对象中第偶数位索引控制跳过或间隔不需要比较的字符个数，第奇数位索引控制需要比较的字符个数；

步骤5：重复步骤3和4，直到在目标串中找出所述的待匹配模式串，算法终止。

2.根据权利要求1所述的基于搜索引擎检索信息的模式匹配方法，其特征在于所述的新模式串需要包括待匹配模式串的第一个字符和最后一个字符。

3.根据权利要求2所述的基于搜索引擎检索信息的模式匹配方法，其特征在于所述的新模式串需要包括待匹配模式串中区别于其他字符的特殊字符。

4.根据权利要求2或3所述的基于搜索引擎检索信息的模式匹配方法，其特征在于所述的新模式串需要包括待匹配模式串中连续的有规律的字符串。

5.根据权利要求4所述的基于搜索引擎检索信息的模式匹配方法，其特征在于所述对象的构成模式是：{N₀，N₁，N₂}，或者{N₀，N₁，N₂，N₃，N₄……N_X}，X为正整数，N₀，N₁，N₂，N₃，N₄……N_X的取值为自然数，相互之间可以相等也可以不等；其中下标为偶数的索引为待匹配模式串中的第一个字符的字符数、或者区别于其他字符的特殊字符的字符数、或者连续的有规律的字符串的字符数、或者最后一个字符的字符数；下标为奇数的索引为前后两个相邻索引之间间隔的字符数。

Images