单模式匹配加密算法

2022-10-28

在很多应用领域中，比如在DNA序列中寻找特殊的模式，都要用到模式匹配，所以模式匹配是一门重要的学科。由于模式匹配问题的求解效率的重要性，对模式匹配加密算法的研究很早就受到重视，模式匹配分为单模式匹配和多模式匹配，那么我们今天就先来介绍几款常用单模式匹配加密算法。

常用单模式匹配加密算法

1、BF加密算法

BF加密算法是最简单的算法，是从左到右进行匹配的。

（1）BF加密算法的思想

首先将T1与P1，进行比较，若不同，就将T2与P1进行比较，……，直到T的某一个字符Ti和P1相同，再将它们之后的字符进行比较，若也相同，则如此继续往下比较，当T的某一个字符Ti与P的字符Pj不同时，则T返回到本趟开始字符的下一个字符，即Ti-j+2，P返回到P1，继续开始下一趟的比较，重复上述过程。若P中的字符全部比较完，则说明本趟匹配成功，本趟的起始位置是i-j=1或i-t[0]，否则，匹配失败。

BF加密算法是较简单、直观的加密算法，但它可能产生不必要的回溯，所以减慢了模式匹配的速度，效率很低，时间复杂度为T（n）=O（m*n)。

2、KMP加密算法

由于BF加密算法的缺点。KMP加密算法产生了。KMP加密算法是由BF改进后不产生回溯的一种算法。

（1）KMP加密算法的思想

每当匹配过程中出现字符串比较不等时，不需回溯i指针，而是利用已经得到的”部分匹配”结果将模式向右”滑动”尽可能远的一段距离后，继续进行比较。

KMP加密算法将模式串向右滑动可以提高匹配算法的效率，但相对比较复杂，时间复杂度为T（n）=O（m+n)，空间复杂度为S（n）＝O（m）。

3、BM加密算法

受KMP加密算法的启发，提出了一种新的字符串快速匹配算法一BM加密算法。BM加密算法在实际的模式匹配中，跳过了很多无用的字符，这种跳跃式的比较方式，使BM加密算法获得了极高的效率，特别是在大字符集上进行字符串的模式匹配时。在实际的应用中，BM加密算法比KMP加密算法更有效率。

BM加密算法从另外一个角度出发，提出一种比较新颖的方法来求解模式匹配问题。

（1）BM加密算法的思想

从右向左的把模式同文本做比较。开始时仍是P的最左边与T的最左边对齐，当某趟比较中出现不匹配时，BM加密算法采用两条启发性规则计算模式串右移的距离，即坏字符启发规则和好后缀启发规则；当与最右的模式符号做比较的文本符号在模式中根本就没有出现，则模式可以在这个文本符号之后移位m个位置。

作如下定义：

串中出现的字符，

字符集：C＝｛C|C在正文中出现}

正文串T：T1T2…一Ti…Tim-j…Tn

模式串P：T1…Tj…T

坏字符规则：

在BM加密算法从右向左扫描的过程中，若发现某个字符x不匹配，则按如下两种情况讨论：

1）如果字符x在模式P中没有出现，那么从字符x开始的m个文本显然不可能与P匹配成功，直接全部跳过该区域即可。

2）如果x在模式P中出现，则以该字符进行对齐。

用数学公式表示，设Skip(x)为P右移的距离，m为模式串P的长度，max(x)为字符x在P中最右位置。

好后缀规则：

若发现某个字符不匹配的同时，已有部分字符匹配成功，则按如下两种情况讨论：

1）如果在P中位置t处已匹配部分P'在P中的某位置t'也出现，且位置t'的前一个字符与位置t的前一个字符不相同，则将P右移使t'对应t方才的所在的位置。

2）如果在P中任何位置已匹配部分P'都没有再出现，则找到与P'的后缀P''相同的P的最长前缀x，向右移动P，使x对应方才P''后缀所在的位置。

用数学公式表示，设Shift(j)为P右移的距离，m为模式串P的长度，j 为当前所匹配的字符位置，s为t'与t的距离（以上情况1）或者x与P''的距离（以上情况2）。

（2）BM加密算法流程图

在匹配过程中，取dist1和dist2中的最大者，其流程图如图所示。

其预处理阶段时间复杂度为O（m+s），空间复杂度为O（s）。搜索阶段时间复杂度为O（m*n），最坏情况下要比_较进行3n次比较，最好情况下时间复杂度为O（n/m）。

随着网络的发展，模式匹配加密算法的应用越来越广，因而提高模式匹配加密算法的效率也是当前研究的热点。

小知识之模式匹配

模式匹配是指将两个模式作为输入，计算模式元素之间语义上的对应关系的过程。在数据结构中模式匹配是字符串的基本运算之一。

有两个字符串T和Ｓ，字符串T称为正文，字符串S称为模式，要求找出模式S在正文T中的首次出现的位置。一旦模式S在正文T中找到，就说发生一次匹配。有些应用可能会要求找出所有的匹配位置。

TAG：

上一篇 : 多模式匹配加密算法

下一篇 : 复合混沌二级置乱图像加密算法

文章标签

文档加密软件

文档信息安全管理软件

上网行为管理软件

应用程序管控软件

敏感文件管理软件

U盘设备管控软件

文件分发软件

IT资产管理软件

电脑操作记录软件

远程控制软件

聊天管控软件

敏感信息报警

屏幕管控

内网管理

深度行为分析

电脑屏幕录像

实时管控

补丁管理

网络准入控制管理系统