CN102023858A - 软硬件协同工作的字符匹配系统及其匹配方法 - Google Patents

Abstract

一种计算机识别技术领域的软硬件协同工作的字符匹配系统及其匹配方法，该系统包括：前端编译模块和后端匹配计算模块，前端编译模块实现对输入信息的前端处理并将执行码以及字符串头字母输出至后端匹配计算模块，后端匹配计算模块完成匹配计算并返回计算结果至前端编译模块。本发明结合了网络路由协议对字符串模式匹配的特定应用需求，通过软硬件协同工作、硬件高速运输的方式，实现了提高正则表达式的字符串模式匹配速度，它同时兼顾了通用性和灵活性。

Description

软硬件协同工作的字符匹配系统及其匹配方法 

技术领域

本发明涉及的是一种计算机识别技术领域的系统，具体是一种软硬件协同工作的字符匹配系统及其匹配方法。 

背景技术

当前，字符串模式匹配是一项热门技术，在网络检索、路由表查找、入侵检测系统、网络报文解析等各领域都得到了广泛的应用和发展，给人们提供了字符串检索的方法，也以不同的实现方法带来了不同的效率，故以一种高效率、特定的查找方式和特定查找结果给字符串匹配提出了调整和发展。研究字符串匹配，从方式上可分为精确匹配、模糊匹配和表达式匹配。其中表达式匹配包括了正则表达式和巴克斯范式等方法，它们在信息中能找出能够符合表达式规则的字符串信息和位置，它的优势是能够描述出具有一些复杂特征的字符串，是精确匹配和模糊匹配的增强模式。故人们集中研究如何以快速、高效的方式进行字符串模式匹配，提出了包括对正则表达式在内的一系列实现方法。提到正则表达式的实现方法，其经典实现方法是使用自动机方案，根据自动机和文法理论，正则表达式具有与自动机等价的描述能力，因此可以通过构造正则表达式对应的自动机来识别正则表达式的语言，完成对文本的匹配。自动机分为两种形式，一种是非确定有限自动机(Nondeterministic Finite Automaton，NFA)，另外一种是确定有限自动机(Deterministic Finite Automaton，DFA)。非确定有限自动机和确定有限自动机的主要区别在于：对于确定的状态和确定输入，非确定有限自动机允许有多个后继状态，而确定有限自动机则只能有唯一的后继状态。非确定有限自动机和确定有限自动机在描述能力上是等价的。 

故基于该自动机思想，人们提出了很多基于不同平台和实现细节的实现方法，诸如在软件平台和硬件平台上，正则表达式都能进行实现，分析利弊，软件平台的实现方案因为编程语言而显得实现地灵活多变和简易，而随着硬件工艺水平的提高和FPGA技术的发展，用硬件的并行结构来实现字符串模式匹配处理的研究大量涌现，它最大的优势就是运行速度快、效率高，这是软件平台所无法比拟的。在实际应用中，这些方案扬长避短，在某些不同的领域中发挥关键的作用。 

经对现有文献检索发现，“基于硬件的快速正则表达式匹配方法”(通信技术期刊，2010年第01期43卷)中提出一种分组模式处理方法，将序列庞大的正则表达式编译为少量的DFA， 然后利用多核处理器来并行地处理分组模式，在不明显增加内存耗费的情形之下增加了正则表达式的匹配速率，但其固定了正则表达式的匹配规则，再制作成硬件模块，使得模块不能根据不同的正则表达式来实现不同的匹配规则，不能适合灵活多变的应用背景；“正则表达式的高效硬件实现”(计算机工程与科学期刊，CN43-1258，2009年第31卷第10期)一文中先对实现正则表达式匹配的多模式确定有限自动机(MPDFA)方法进行研究，将多个正则表达式编译成一个组合DFA，并基于该方法提出基于硬件实现报文正则表达式匹配的微引擎结构，其虽然较先前单一模式的正则表达式有所进步，能实现更多的正则表达式匹配模式，但还是不能实现软件平台上灵活多变的特点，实现各种正则表达式的匹配模式；“正则表达式在垂直搜索引擎中的应用”(农业网络信息期刊，2010年第8期)，一文中着重分析了网页检索中常用的正则表达式，为搜索引擎的构建提供帮助，但其不足是虽然兼顾了软件平台对正则表达式模式实现的通用性，也同时忽略了软件平台较硬件平台的低效性，且其没有很好考虑使用专门定制的正则表达式匹配方法来进行这种特殊应用场景的需求。故总结上述，都是不能同时兼顾软件平台灵活多变和硬件平台并行高速的特点，也没有根据特殊应用场景来定制高效正则表达式匹配实现方法的特点。 

发明内容

本发明针对现有技术存在的上述不足，提供一种软硬件协同工作的字符匹配系统及其匹配方法，借鉴了POSXI库正则表达式中的实现思想，结合软硬件的优势，通过软硬件协同工作来达到了加速正则表达式匹配的目的。 

本发明是通过以下技术方案实现的： 

本发明涉及一种软硬件协同工作的字符匹配系统，包括：前端编译模块和后端匹配计算模块，其中：前端编译模块实现对输入信息的前端处理并将执行码以及字符串头字母输出至后端匹配计算模块，后端匹配计算模块完成匹配计算并返回计算结果至前端编译模块。 

所述的前端编译模块包括：执行码编译单元、fastmap生成单元和软硬件通信单元，其中：执行码编译单元对输入的正则表达式进行编译解析并生成机器能识别的执行码，fastmap生成单元根据输入的正则表达式分析出符合其要求的字符串头字母并与执行码一并输出至软硬件通信单元，软硬件通信单元分别与前端编译模块和后端匹配计算模块相连接并实现数据通信。 

所述的后端匹配计算模块包括：数据接口单元和匹配计算单元，其中：数据接口单元接收前端编译模块编译输出的执行码、fastmap数据和字符串信息并转发至匹配计算单元，匹配计算单元完成对字符串匹配计算，并获得匹配结果返回给前端编译模块。 

本发明涉及上述系统的匹配方法，包括以下步骤： 

第一步、用户调用前端编译模块，输入正则表达式和字符串信息进行前端处理，具体包括 以下步骤： 

1.1)前端编译模块的fastmap生成单元根据输入的正则表达式，判断符合相应要求的字符串起始头字符，并在32字节的fastmap缓存中的相应位置置“1”位，其它位置置“0”； 

1.2)前端编译模块的执行码编译单元把输入的正则表达式编译成长度为3个字节的执行码，该执行码的第一个字节表示操作种类，第二字节后第三字节为该执行码所附带的参数； 

1.3)软硬件通信单元把fastmap数据、正则表达式编译结果和字符串信息，通过LINUX用户层和内核层传输给后端匹配计算模块。 

第二步、后端匹配计算模块中的数据接口单元进行信息接收后，将字符串信息、执行码和32字节fastmap数据传输给匹配计算单元，匹配计算单元进行正则表达式匹配计算，具体步骤如下： 

2.1)设置一个用于指示当前执行码执行位置的执行码指针和用于指示当前字符串匹配位置的字符串指针； 

2.2)利用fastmap找到字符串中的头字符进行匹配计算，当执行码指针指示为执行码的尾端且实现匹配，则执行第三步，否则则执行步骤2.3)； 

2.3)利用fastmap找到字符串中的下一个头字符，并重新开始匹配，当字符串指针指示为字符串的尾端且未实现匹配，则匹配失败。 

第三步、后端匹配计算模块根据第二步的匹配结果以二进制码的方式，通过前端编译模块的软硬件通信单元返回给用户。 

与现有技术相比，本发明的有益效果是：结合了网络路由协议对字符串模式匹配的特定应用需求，通过软硬件协同工作、硬件高速运输的方式，实现了提高正则表达式的字符串模式匹配速度，它同时兼顾了通用性和灵活性。本发明定制一个适合诸如路由协议需求的正则表达式高速匹配系统。本专利在研究FPGA的体系结构设计过程中，设计了一些特殊的功能单元来提高处理器酌处理效率，这些功能模块会给从事该领域研究工作的人员带来一定的帮助和启发。 

附图说明

图1为本发明结构示意图。 

图2为后端匹配计算模块原理。 

具体实施方式

下面对本发明的实施例作详细说明，本实施例在以本发明技术方案为前提下进行实施，给出了详细的实施方式和具体的操作过程，但本发明的保护范围不限于下述的实施例。 

如图1所示，本实施例包括：前端编译模块和后端匹配计算模块，其中：前端编译模块实现对输入信息的前端处理，把将执行码以及字符串头字母输出至后端匹配计算模块，并等待结 其计算结果，使得最终返回给用户，它是基于LINUX系统软件实现的，其包含了执行码编译单元、fastmap生成单元和软硬件通信单元，执行码编译单元和fastmap生成单元都是基于linux用户层的，而软硬件通信单元是基于linux内核层的；后端匹配计算模块完成匹配计算，把最终计算结果返回给前端编译模块，它是采用FPGA硬件实现的。 

本实施例通过以下步骤实现匹配： 

第一步、用户调用前端编译模块，输入正则表达式和字符串信息进行前端处理，前端编译模块的fastmap生成单元根据输入的正则表达式，判断符合相应要求的字符串起始头字符，最后在32字节(共256位，对应着256个ASCII码)fastmap缓存中的相应位置位。前端编译模块的执行码编译单元把输入的正则表达式编译成后端匹配计算模块能识别的执行码，一个执行码一般长度为3个字节，第一个字节表示操作种类，第二字节后第三字节为该执行码所附带的参数，根据不同的操作种类进行不同的计算操作。前端编译模块的软硬件通信单元把以上得出的fastmap数据、正则表达式编译结果和字符串信息，穿越LINUX用户层和内核层后，传输给后端匹配计算模块，并等待后端匹配计算模块返回最终结果。 

第二步、后端匹配计算模块中的数据接口单元进行信息接收后，将字符串信息、执行码和32字节fastmap数据传输给匹配计算单元，匹配计算单元进行正则表达式匹配计算。匹配计算过程大概是：设置一个执行码的位置指针(指示当前执行码执行到的位置)和字符串的位置指针(指示当前字符串匹配到的位置)，利用fastmap找到字符串中的头字符，然后开始匹配计算，若执行码的位置指针走到尾则表示最终匹配完成，否则该轮匹配失败(并不是最终匹配失败)，则再需要利用fastmap找到字符串中的下一个头字符，开始新的匹配。最终，若字符串的位置指针走到尾，还没有一次匹配发生，则表示最终的匹配失败。 

第三步、后端匹配计算模块把匹配结果以1(匹配)或0(不匹配)的方式，通过前端编译模块的软硬件通信单元，最终返回给用户。 

下面以输入正则表达式“ab＊c”和字符串“abaabbbcd”为实施例，对本发明的实施例作详细说明： 

1.所述的前端编译模块基于LINUX用户层实现，属于软件实现的方案，其包括：执行码编译单元、fastmap生成单元和软硬件通信单元，其中：执行码编译单元对输入的正则表达式进行编译解析并生成机器能识别的执行码；fastmap生成单元根据输入的正则表达式分析出符合其要求的字符串头字母并与执行码一并输出至软硬件通信单元；软硬件通信单元负责前端编译模块和后端匹配计算模块之间的数据通信。 

执行码编译单元负责正则表达式的编译，该单元是基于软件实现，它对输入的正则表达式进行前期处理，根据正则表达式中各运算符、匹配字符的特征和一定的逻辑关系，将其转换成 计算机可逐个执行的执行码，并且生成其它针对后期匹配具有辅助性的附带信息。一个执行码一般长度为3个字节，第一个字节表示操作种类，第二字节后第三字节为该执行码所附带的参数，根据不同的操作种类进行不同的计算操作，如输入正则表达式“ab＊c”，则其编译出的结果是“exactn/1/a+on_failure_jump to 12+exactn/1/b+pop_failure_jump to 3+exactn/1/c”5(后边会具体介绍各执行码意义)。不同的正则表达式符号会编译成为不同的执行码，以实现不同的匹配计算操作，每种不同的执行码都有各种的名称和自己附带的信息。如下表1所示，是按照正则表达式特征所转换成的各种执行码组合。 

表1正则表达式运算符的opcode组合 

如上表1所示，各种执行码的组合完美地把正则表达式不同的运算符转换成了计算机能够识别并运行计算的机器语言。这就是操作码起到的作用：把正则表达式编译成机器语言。前段 编译模块就是把正则表达式编译成了以上这些执行码的组合，而后端匹配计算模块按照以上各执行码的执行规则来进行字符串的匹配计算的。 

前端编译模块的fastmap生成单元是根据输入的正则表达式，来猜测出符合该正则表达式的字符串的头字母，记录该信息的好处是后端匹配计算模块可根据记录的可能字符串头字符，使得系统能快速定位字符串中可能起始的字符串头，完成匹配，这样就节省了很多无谓的匹配，从而提高了匹配效率。模块中使用了buffer_fastmap[31:0]的缓存来记录该信息，其是一个32字节的缓存，32＊8个位分别代表了256个ASCII码，若相应位置的值为1，则代表了该字符可能是正则表达式开始匹配的头字符，若值为0，则代表了该字符不是正则表达式开始匹配的头字符。如正则表达式是“^abc”，则符合要求的字符串头字符是“a”，其ASCII码是97，故把fastmap中的第97个位置为1，其它位为0。 

前端编译模块的软硬件通信单元，主要负责前端编译模块和后端匹配计算模块之间的数据通信，实现软硬件的衔接。因为前端编译模块是基于LINUX操作系统的用户层实现的，而后端匹配计算模块是基于FPGA硬件实现的，故它们之间需要使用内核的驱动程序来进行负责数据间的传输，即本单元。需要注意的是，本模块基于不同的是平台有所变化，因为不同的平台上包括硬件对应关系等平台结构不同，需要对该模块的关于平台定义进行重新修改，以适合不同的应用需求。具体来说，该单元向基于LINUX用户层的前端编译模块提供了驱动的mmap方法和ioctl方法，来实现把编译后得到的执行码、fastmap数据和原本输入的字符串输入到内核，然后把这些信息原封不动的通过具体平台的IO口传输给基于FPGA芯片的后端匹配计算模块，之后原地等待后端匹配计算模块把计算结果传输回来，最后把这个结果传输回给用户。 

根据本实施例的输入信息：正则表达式“ab＊c”和字符串“abaabbbcd”。得到的输出结果是：执行码“exactn/1/a+on_failure_jump to 12+exactn/1/b+pop_failure_jump to 3+exactn/1/c”，其中“exactn/1/a”表示精确匹配字符“a”，“on_failure_jump to 12”表示做一次压栈处理，压栈的位置是第12字节处，即指令“pop_failure_jump”处，“exactn/1/c”表示精确匹配字符“c”。fastmap中的第97位为1，其余位为0，这表示起始头字符为“a”，以及原封不动的字符串“abaabbbcd”。 

2.所述的后端匹配计算模块基于FPGA硬件实现，属于硬件实现方案，负责正则表达式的匹配计算，该后端匹配计算模块包括：数据接口单元和匹配计算单元，其中数据接口单元负责对数据接收和匹配计算单元的数据发送，匹配计算单元负责匹配计算。 

数据接口单元负责匹配计算单元和前端编译模块间数据传输，该单元先接收数据，把数据传输给匹配计算单元后，一直等待匹配计算单元的计算结果，最后把匹配结果返回给前端编译模块。 

匹配计算单元接收到数据包括字符串、生成的执行码和fastmap数据后，进行匹配计算，在进行工作原理介绍钱，以下先对子串管理和栈管理做介绍： 

首先要介绍的是子串管理，如正则表达式“12(3(45))6(78)”，称第一对圆括号中的字符串“3”为子串1，称第二对圆括号中的字符串“45”为子串2，称第三对圆括号中的字符串“78”为子串3，这样从左到右地把括号内的字符串进行划分，而当正则表达式匹配到3时，称只有子串1当前激活了，当匹配到45时，称只有子串1和2当前激活了，当匹配到78时，称只有子串3当前激活了。即在正则表达式中一个圆括号中的欲匹配字符串表示一组子串，而每个子串会根据遇到的先后顺序做好子串号的标记，并且，后边的子串或嵌套在前面的子串中，或存在其外，故为了区别在嵌套时的复杂匹配关系，做了子串的管理，在模块中，使用lowest_active_reg表示当前激活的最低子串号，highest_active_reg表示当前激活的最高子串号，reg_is_active[MAX_REG_NUMBER：1]数组储存各子串当前是否激活的信息，reg_matched_something[MAX_REG_NUMBER：1]用于存储各子串是否得到了匹配。在这里先介绍到子串和激活的原理，后边便会涉及到。 

其次，该单元的最大特点就是栈的使用。在正则表达式中，有“？”、“+”、“*”、“[]”等匹配次数不确定的运算符，故字符串和正则表达式匹配的情况有多种组合情况，故会遇到某次匹配失败的情况，故引入栈点管理的办法，以便在后续匹配出现匹配失败时，可以弹栈来恢复现场，以尝试其他匹配情况。栈是由一层层栈点组成的，每个栈点都存储了当时需要保护的现场数据信息，栈有压栈和弹栈两种操作：弹栈取数据时，其取操作是按时间上最早存入的栈点先、最晚存入的栈点后的顺序来进行的，而压栈操作恰好相反。模块中使用fail_stack_avail指针指示栈点当前指向的存取位置，每压栈一次，它便递增1，每弹栈一次，它便递减1；fail_stack_str_place[MAX_POINTER_NUMBER:1]数组存储了压栈时字符串当前读取到的位置，MAX_POINTER_NUMBER定义了栈的大小；fail_stack_reg_place[MAX_POINTER_NUMBER:1]数组存储了压栈时系统欲存储的正则表达式执行码的位置，注意，这里并非压栈时系统所执行到的正则表达式执行码的位置；fail_stack_lowest_active_reg[MAX_POINTER_NUMBER:1]数组存储了压栈时的lowest_active_reg值；fail_stack_highest_active_reg[MAX_POINTER_NUMBER:1]数组存储了压栈时的highest_active_reg值；fail_stack_reg_is_active[MAX_POINTER_NUMBER:1]数组存储了压栈时的reg_is_active值；fail_stack_reg_matched_something[MAX_POINTER_NUMBER:1]数组存储了压栈时的reg_matched_something值。所以简单来说，遇到弹栈和压栈操作时，读取和存储的都是以上的数据。至于何时压栈，是在遇到可能存在不止一种匹配组合情况的执行码时，需要做压栈操作，以保存现场，以防将来匹配失败时做弹栈操作，以尝试当初没选择的 其它匹配情况；而弹栈操作是把栈点中所保存的值恢复给系统，若遇到栈点弹完时，便宣告了本次匹配的失败(不是最终的失败)。具体来说，遇到on_failure_jump、succeed_n、dummy_failure_jump和push_dummy_failure会实现压栈保护现场，而后两种只是压一次空栈，而pop_failure_jump涉及一次弹一次空栈的操作。 

通过介绍以上子串管理和栈管理的介绍，下面介绍匹配计算单元的整体工作流程，其工作原理如图2所示，具体细节如下： 

第一步，设置相关变量，并初始化，其中重要的有初始化字符串的位置指针为0(指示当前字符串匹配到的字符位置)，初始化执行码的位置指针为0(指示当前执行码匹配到的位置)，初始化fail_stack_avail为0(指示当前栈为空)，并把栈的各存储器清零等，跳转至第二步。 

第二步，寻找字符串中的下一个头字节。通过fastmap数据中的置位情况，得知哪些字符是符合要求的头字符，在字符串中寻找符合该要求的下一个头字符位置，字符串的位置指针同时也指示到该位置。若找到相应的字符，则开始新一轮匹配，进入第三步，否则当字符串的位置指针指向字符串末尾时，还没找到符合要求的字符，则宣告最终匹配失败，跳转至第八步。 

第三步，新一轮匹配初始化。把执行码的位置指针清零，把栈的各存储器清零，字符串的位置指针指向第二步中找到的新头字符位置，开始新一轮匹配，跳转至第四步。 

第四步，若当前执行码位置指针已指向末尾，则表示全部匹配要求已完成，宣告最终匹配成功，跳转至第七步，否则继续计算匹配，跳转至第五步。 

第五步，执行码计算匹配。根据当前字符串的位置指针和执行码位置指针，计算字符串的字符信息是否匹配当前的执行码匹配条件，值得注意的是，有的执行码在匹配计算前，会进行压栈处理，保护现场，所以这时便会产生了一些栈点。若当前执行码成功执行，则字符串的位置指针和执行码位置指针根据相应匹配情况指向下一个位置，跳转至第四步；若当前执行码执行不成功，跳转至栈，跳转至第六步。 

第六步，栈管理。弹出一个有效栈点，若成功，则根据栈点中保存的信息，把字符串位置指针、执行码位置指针等恢复现场。若不成功，则宣告本轮匹配失败，跳转至第二步。 

第七步，宣告最终匹配成功，把结果返回给前端编译模块。 

第八步，宣告最终匹配失败，把结果返回给前端编译模块。 

通过以上介绍，得知了匹配计算的详细工程，但没介绍到每个执行码的具体匹配细节，以下，介绍的便是各个执行码的操作原理细节，它们是实现正则表达式匹配计算的基本指令单元， 它们的原理如下： 

no_op执行码：不做任何操作，跳转出本操作码。 

succeed执行码：宣告匹配最终成功，结束匹配计算。 

exactn执行码：从当前指向的字符串字符开始，以附带参数中存储的欲匹配字符信息为参照，进行匹配计算，若全部欲匹配字符信息能够得到匹配，便进行子串信息更新(若本操作码的成功匹配满足了某子串的匹配需求，则对子串管理成员reg_matched_something数组中的该子串，做成功匹配标记)并顺利跳转出本操作码，否则失败，跳转入栈点管理进行弹栈操作。其中，附带参数1存储欲匹配字符的个数，附带参数2存储欲匹配字符。 

anychar执行码：若当前指向的字符串字符不是’\0’或是在字符串末尾位置，便进行子串信息更新(若本操作码的成功匹配满足了某子串的匹配需求，则对子串管理成员eg_matched_something数组中的该子串，做成功匹配标记)并顺利跳转出本操作码，否则失败，跳转入栈点管理进行弹栈操作。 

charset执行码：此操作码的附带参数1为32，表示附带参数2有32个字节(共256位，顺序代表了256个ASCII码的存储情况)，而附带参数2中的256个位存储了256个ASCII码是否能够匹配的信息，若相应位为1，表示能够匹配，否则不能匹配。本操作码的含义是：根据附带参数2中的256个ASCII码是否能够匹配的信息，若当前指向的字符串字符能匹配，便进行子串信息更新(若本操作码的成功匹配满足了某子串的匹配需求，则对子串管理成员reg_matched_something数组中的该子串，做成功匹配标记)并顺利跳转出本操作码，否则失败，跳转入栈点管理进行弹栈操作。 

charset_not执行码：本操作码的含义和charset操作类型相同，只不过附带参数2中的256个位存储了256个ASCII码是否能够匹配的信息，若相应位为1，表示不能够匹配，否则能匹配。 

start_memory执行码：本操作码和stop_memory操作码共同诠释了正则表达式中的原括号操作和子串管理，标志了一个子串匹配的开始。其附带参数1存储该子串的子串号，而附带参数2中存储了在本子串了还拥有的其它的子串的数目。本操作码对先前介绍到的lowest_active_reg，highest_active_reg，reg_is_active，reg_matched_something等子串管理变量做子串信息更新，其中，对reg_is_active，reg_matched_something数组中本子串做初始化操作，对highest_active_reg和lowest_active_reg作更新，分别赋予当前激活的各子串中子串号最大和最小的值。 

stop_memory执行码：本操作码和start_memory操作码共同诠释了正则表达式中的原括号操作和子串管理，标志了一个子串匹配的结束。其附带参数1和2都和其处于相同子串的 start_memory操作码的附带参数一样。本操作码首先更新子串管理的成员变量，在reg_is_active数组中关闭本子串的激活状态，由于本子串的关闭，更新lowest_active_reg和highest_active_reg的值，其次，根据reg_matched_something数组中存储的本子串匹配情况的历史记录来做判断，若曾匹配成功过，则顺利跳转出本操作码，否则需要察看该子串的结构(即察看该组子串的start_memory和stop_memory操作码前后)，若该子串所代表的正则表达式是诸如“()？”、“()+”和“()＊”等结构，则做一次压栈操作，并进入栈点管理做弹栈操作。 

Begline和begbuf执行码：该两个操作码都是判断当前指向的字符串字符位置是否在最开始，若是，则顺利跳出该操作码，否则宣告本轮匹配失败。 

Endline和endbuf执行码：该操作码判断当前指向的字符串字符位置是否在最开始，若是，则顺利跳出该操作码，否则宣告本轮匹配失败。 

jump执行码：该操作码和succeed_n或on_failure_jump组合出现，它们的组合之间会包含了其他的匹配操作码，而它们之间却相互呼应，组成了加号、星号、中括号的匹配边界。遇到该操作码，其会实现p值的跳转，即把p值赋为当前p值和一个特殊数值(即该操作码附带的两个参数所共同组成的数)之和，而实际上这个跳转目的就是和其遥相呼应的succeed_n或on_failure_jump操作码的位置。 

pop_failure_jump执行码：本操作码的操作是抛弃一个栈点，即fail_stack_avail自减1，然后把p值赋为当前p值加上一个特定值(即该操作码附带的两个参数所共同组成的数)所得到之和，然后顺利跳出本操作码。其含义同jump操作码相同，只是在操作上还要求做一次栈点抛弃操作。 

jump_past_alt执行码：该操作码的操作同jump相同，即跳转目的就是当前p值和一个特殊数值(即该操作码附带的两个参数所共同组成的数)之和，然后顺利跳出本操作码。 

on_failure_jump执行码：该操作码和jump或jump_past_alt或maybe_pop_jump或pop_failure_jump组合(它们的组合并不是紧挨着，中间会夹杂其他操作码)，共同组合了一些正则表达式运算符，它们都处于边界位置，而这些组合都是代表了星号、加号、问号、中括号等匹配次数不确定的运算符，故需使用栈来管理，来尝试各种可行的匹配方案。该操作码的操作是把当前p值加上一个特定值(即该操作码附带的两个参数所共同组成的数)所得到之和(该值指向同本on_failure_jump相呼应的jump或jump_past_alt或maybe_pop_jump或pop_failure_jump操作码位置的下一个操作码)存入fail_stack_reg_place中，做一次压栈操作，然后顺利跳出本操作码。 

maybe_pop_jump执行码：本操作码只是一个中间过渡操作码，其最后会根据正则表达式中对字符的前后匹配关系来转化为jump或pop_failure_jump操作码。例如正则表达式“2＊2” 和“2＊3”，前者欲多次匹配的字符和随后的匹配字符相同，而后者欲多次匹配字符和随后的匹配字符不同，在这两种不同情况下，maybe_pop_jump最后会转换成pop_failure_jump和jump。dummy_failure_jump执行码：本操作码的操作是压入一个空栈点，即fail_stack_avail自加1，然后把p值赋为当前p值加上一个特定值(即该操作码附带的两个参数所共同组成的数)所得到之和，然后顺利跳出本操作码。 

push_dummy_failure执行码：本操作码的操作是压入一个空栈点，即fail_stack_avail自加1，然后顺利跳出本操作码。 

succeed_n执行码：该操作码和jump_n组合(它们的组合并不是紧挨着，中间会夹杂其他操作码)，共同组合了正则表达式运算符中的中括号的边界。若其附带参数2不为0，则将其减1后再存入附带参数2位置，然后顺利跳转出本操作码；若附带参数2为0，则把当前p值加上一个特定值(即该操作码的附带参数1)所得到之和(该值指向同本succeed_n相呼应的jump_n操作码位置的下一个操作码)存入fail_stack_reg_place中，做一次压栈操作，然后顺利跳出本操作码。 

jump_n执行码：该操作码和succeed_n组合(它们的组合并不是紧挨着，中间会夹杂其他操作码)，共同组合了正则表达式运算符中的中括号的边界。其操作是把附带参数2的值减1后再存入附带参数2位置，再把p值赋为当前p值加上一个特定值(即该操作码的附带参数1)所得到之和(该值指向同本jump_n相呼应的succeed_n操作码的位置)，然后顺利跳出本操作码。 

set_number_at执行码：该操作码的操作是在把当前p值加上一个特定值(即该操作码的附带参数1)所得到之和作为目标，在该目标位置存储上附带参数2的值。 

Wordchar和notwordchar执行码：对于wordchar操作码，若当前指向的字符串字符是大小写英文字母或数字或下划线，便进行子串信息更新(若本操作码的成功匹配满足了某子串的匹配需求，则对子串管理成员reg_matched_something数组中的该子串，做成功匹配标记)并顺利跳转出本操作码，否则失败，跳转入栈点管理进行弹栈操作。而notwordchar操作码的判断条件刚好相反。 

Wordbeg和wordend执行码：对于wordbeg操作码，若当前指向的字符串字符的位置是在单词首或句首，则顺利跳转出本操作码，否则失败，跳转入栈点管理进行弹栈操作。而wordend操作码的判断条件是当前指向的字符串字符的位置是在单词末或句末。 

Wordbound和notwordbound执行码：对于wordbound操作码，若当前指向的字符串字符的位置是出现在单词边界或句首或句末，则顺利跳转出本操作码，否则失败，跳转入栈点管理进行弹栈操作。而notwordbound操作码的判断条件是当前指向的字符串字符的位置不是在 单词边界或句首或句末。 

decimalFormat和notdecimalFormat执行码：对于decimalFormat操作码，若当前指向的字符串字符是数字，便进行子串信息更新(若本操作码的成功匹配满足了某子串的匹配需求，则对子串管理成员reg_matched_something数组中的该子串，做成功匹配标记)并顺利跳转出本操作码，否则失败，跳转入栈点管理进行弹栈操作。而notdecimalFormat操作码的判断条件刚好相反。 

根据本实施例的输入信息：正则表达式“ab＊c”和字符串“abaabbbcd”，它通过后端匹配计算的结果为：匹配。 

这样，通过以上介绍的工作原理，后端匹配计算模块便完成了对正则表达式和字符串间的匹配计算，最后便能得到字符串是否符合正则表达式的结果。 

综合上诉，本发明达到对正则表达式加速的创新点在于：使用了高效的FPGA硬件完成最耗时的匹配计算部分，放弃了“最长匹配”原则，放弃计算复杂且耗时的匹配细节(诸如匹配子串的开始和结尾位置等)，从而兼顾了软件平台灵活多变和硬件平台并行高效的特点，一反一般硬件平台只能实现单一正则表达式模式的缺点，结合软件平台，给软件平台带来了一个正则表达式加速匹配系统，符合了一些特性应用场景的需求。 

为了检测本系统的工作性能，在基于已经确保系统正常工作和能正确完成匹配运算后，在一个嵌入式平台上实现了性能测试。该嵌入式平台是构建在FPGA芯片SOPC系统，定制了一个运行LINUX嵌入式系统的CPU(其运行在200MHz的时钟频率上)和FPGA运行时钟是33MHz。把前端编译模块安装在CPU上，而后端匹配计算模块编译成FPGA硬件IP核，挂接到了CPU总线上。本测试的使用了POSIX库中的正则表达式做比较，通过输入相同的正则表达式和字符串信息，来对它们匹配时间进行计时，下表2是最终的测试结果。 

表2测试结果和加速效果比较 

以上结果显示，对于一般的正则表达式匹配计算，平均能达到3到4倍的效率提升，对于一些复杂的匹配计算，可以最高达到接近17倍的效率提升，获得了不错的加速效果。如果FPGA的时钟进一步提高，可以获得更好的加速效果。 

Claims (6)

1.一种软硬件协同工作的字符匹配系统，其特征在于，包括：前端编译模块和后端匹配计算模块，其中：前端编译模块实现对输入信息的前端处理并将执行码以及字符串头字母输出至后端匹配计算模块，后端匹配计算模块完成匹配计算并返回计算结果至前端编译模块。

2.根据权利要求1所述的软硬件协同工作的字符匹配系统，其特征是，所述的前端编译模块包括：执行码编译单元、fastmap生成单元和软硬件通信单元，其中：执行码编译单元对输入的正则表达式进行编译解析并生成机器能识别的执行码，fastmap生成单元根据输入的正则表达式分析出符合其要求的字符串头字母并与执行码一并输出至软硬件通信单元，软硬件通信单元分别与前端编译模块和后端匹配计算模块相连接并实现数据通信。

3.根据权利要求1所述的软硬件协同工作的字符匹配系统，其特征是，所述的后端匹配计算模块包括：数据接口单元和匹配计算单元，其中：数据接口单元接收前端编译模块编译输出的执行码、fastmap数据和字符串信息并转发至匹配计算单元，匹配计算单元完成对字符串匹配计算，并获得匹配结果返回给前端编译模块。

4.一种根据上述任一权利要求所述系统的匹配方法，其特征在于，包括以下步骤：

第一步、用户调用前端编译模块，输入正则表达式和字符串信息进行前端处理；

第二步、后端匹配计算模块中的数据接口单元进行信息接收后，将字符串信息、执行码和32字节fastmap数据传输给匹配计算单元，匹配计算单元进行正则表达式匹配计算；

第三步、后端匹配计算模块根据第二步的匹配结果以二进制码的方式，通过前端编译模块的软硬件通信单元返回给用户。

5.根据权利要求4所述的匹配方法，其特征是，所述的第一步包括：

1.1)前端编译模块的fastmap生成单元根据输入的正则表达式，判断符合相应要求的字符串起始头字符，并在32字节的fastmap缓存中的相应位置置“1”位，其它位置置“0”；

1.2)前端编译模块的执行码编译单元把输入的正则表达式编译成长度为3个字节的执行码，该执行码的第一个字节表示操作种类，第二字节后第三字节为该执行码所附带的参数；

1.3)软硬件通信单元把fastmap数据、正则表达式编译结果和字符串信息，通过LINUX用户层和内核层传输给后端匹配计算模块。

6.根据权利要求4所述的匹配方法，其特征是，所述的第二步包括：

2.1)设置一个用于指示当前执行码执行位置的执行码指针和用于指示当前字符串匹配位置的字符串指针；

2.2)利用fastmap找到字符串中的头字符进行匹配计算，当执行码指针指示为执行码的尾端且实现匹配，则执行第三步，否则则执行步骤2.3)；

2.3)利用fastmap找到字符串中的下一个头字符，并重新开始匹配，当字符串指针指示为字符串的尾端且未实现匹配，则匹配失败。

Images