CN108197470A - 快速特征码扫描 - Google Patents

Abstract

在字符串字段上扫描特征码的方法和系统。在一个实施例中，本发明提供了一种特征码扫描方法。所述方法包括把一个或多个特征码处理成一个或多个格式，所述格式包括每个定长特征码或特征子码的一个或多个指纹和一个或多个后续查找数据结构，从而使得每个定长特征码或特征子码的指纹的数目等于特征码扫描操作的步长，并且使得所述特定定长特征码或特征子码在任何被扫描的字符串字段中的任何位置上都能被识别，接收特定字符串字段，识别所述特定字符串字段所包括的任何特征码，包括在每个以扫描步长为间距的位置上扫描所述指纹，和在有一个或多个匹配的指纹的位置上查找所述后续查找数据结构，和输出任何已识别的特征码。

Description

快速特征码扫描

技术领域

本发明涉及扫描字符串字段中的特征码。

背景技术

数字内容的物件(如文件，程序，网页，电子邮件，互联网数据包，或数字图像)可以包含一个或多个字符串字段。一个字符串字段是一个通常代表文字或可执行代码的数据值串。例如，一个互联网数据包可以包含网址，主机名，超文本传输协定(HTTP)报头，超文本传输协定报文，电子邮件附件，电子邮件标题和电子邮件内容。一个字符串字段的大小可从几个字节到数百万以上个字节。一个字符串特征码可以是一串特定的完全指明的数据值或是特定的数据值的表达式(如特定的正则表达式)，其目的是用来识别一个字符串物件(如特定的计算机病毒或特定的基因序列)。特征码可以被存储在一个征码数据库中。一个字征码数据库可以包含多个特征码。一个字符串特征码的大小可从几个字节到几千个字节。

字符串特征码和字符串字段都是包含很多基本单元的比特字符串。一个基本单元是最小的有语义的单位，因此通常在特征码扫描技术中作为扫描单元。一个基本单元的大小由应用而定。例如，英文字符串的基本单位通常是8比特位(即一个字节)，而一个电脑病毒特征码的基本单位通常是一个字节或半个字节。

每一个特征码的基本单元可以被指定为等于或不等于某个特定值，或在某个特定范围内(如在数字范围0至9内或英文字母范围a至z内)。每个基本单元可以为不区分大小写或区分大小写。每个基本单元可以支持简单的逻辑运算(如“非”)。此外，每个特征码可以包括通配符，例如，“*”(一个不定长通配符)或“？”(一个定长通配符)，其中“*”表示零个或任意多个任意基本单元和“？”表示一个任意基本单元。对于每一个不定长特征码符号，可进一步指明其任意长度范围。当一个特征码包括不定长字符，特征码的长度不定。如果一个特征码不包括不定长字符，其长度是固定的。

一个典型的特征码扫描过程可包括在一字符串字段内的所有可能的位置上，比较所述字符串字段和特征码数据库中所对应的特征码。扫描速度通常被特征码的大小和复杂性限制。此外，扫描速度还受特征码逐个更新的能力限制。

发明内容

本发明实施例提供了在字符串字段上扫描特征码的方法和系统。一般来说，本发明一个方面的实施例提供了字符串特征码扫描方法，所述方法包括把一个或多个特征码处理成一个或多个格式，所述格式包括每个定长特征码或不定长特征码的每个定长特征子码的一个或多个指纹和一个或多个后续查找数据结构，所述一个或多个指纹包括特定定长特征码或特征子码的第J个指纹，所述第J个指纹的第一基本单元在所述特定定长特征码或特征子码中的在扫描方向上的位置除以特征码扫描操作的步长的余数等于J，从而使得所述指纹的数目等于特征码扫描的步长，并且使得所述特定定长特征码或特征子码在任何被扫描的字符串字段中的任何位置上都能被识别，其中每个所述指纹包括特定定长特征码或特征子码的一个或多个片段，所述一个或多个片段具有在所述特定定长特征码或特征子码中的任何地方的特定位置，接收一个由数据值组成的特定字符串字段，识别所述特定字符串字段所包括的任何特征码，包括在每个以扫描步长为间距的位置上，扫描所述特定字符串字段，以查找一个或多个特征码的一个或多个所述指纹，和在有一个或多个匹配的所述指纹的位置上，查找所述特定字符串字段，以查找一个或多个后续查找数据结构，和输出所述特定字符串字段中的任何已识别的特征码。本发明的所述方面的其它实施例包括所述方法所对应的系统，装置，和计算机软件产品。

这些和其它实施例可选地包括一个或多个以下特性。每个定长特征码或特征子码有多个指纹，和所述扫描包括在每个以扫描步长为间距的位置上，扫描所述字符串字段，以查找一个或多个特征码的多个指纹，包括并行查找两个或两个以上指纹。特定特征码的一个或多个指纹中的每个指纹在原空间或在被投影到一个或多个影子空间之后是完全指明的，所述影子空间是比所述原空间格式更广的空间，所述影子空间通过引入一些模糊性到所述原空间，从而使得一个在特定影子空间的指纹影子对应于一个或多个在所述原空间的指纹。

所述字符串特征码扫描方法可进一步包括在每个以扫描步长为间距的位置上，在原空间扫描所述特定字符串字段，以查找一个或多个指纹，和先在每个以扫描步长为间距的位置上，在一个或多个指纹的一个或多个影子空间中的每个影子空间中，扫描所述特定字符串字段，以查找一个或多个指纹，然后再在一个或多个所述影子空间中的至少一个影子空间中有一个或多个已识别的指纹的位置上，在所述原空间中核实已识别的指纹中的一个或两个。引入一些模糊性到所述原空间进一步包括把原空间的大写和小写字母变成一个大小写相同的字母，把原空间的所有从0至9的数字变成一个相同的数字，和把原空间的空格和“-”变成空格或“-”中的一个或多个。

扫描以查找所述一个或多个特征码的所述一个或多个指纹可进一步包括使用一个或多个散列表和一个或多个布隆(Bloom)过滤器中的一个或多个进行扫描。扫描以查找所述一个或多个特征码的所述一个或多个指纹可进一步包括使用一个散列值解复用器和一个指纹长度解复用器中的一个或多个进行扫描。多个特征码的不同指纹长度的数目可比所述多个特征码的不同特征码长度的数目少，且所述扫描可进一步包括在每个以扫描步长为间距的位置上，扫描所述特定字符串字段，以查找所述多个特征码的多个指纹，包括并行查找两个或两个以上长度相同的指纹。所述一个或多个指纹可被选择，从而使得所述指纹的长度被限制为一组覆盖在一个或多个长度范围内的一个或多个长度的长度，以提供多分辨率的指纹扫描。每个所述指纹的长度可是特征码扫描操作的步长的整倍数。所述字符串特征码扫描方法可进一步包括使用一个或多个内容寻址存储器(CAM)和一个或多个有限自动机(FA)中的一个或多个进行扫描，以查找所述一个或多个特征码的所述一个或多个指纹。

所述字符串特征码扫描方法可进一步包括把多个特征码的多个指纹的每个指纹分解为一个或多个指纹段，从而使得所述特征码的不同指纹段长度的数目比所述特征码的不同指纹长度的数目少，在每个以扫描步长为间距的位置上，扫描所述特定字符串字段，以查找所述多个指纹段，包括并行查找两个或两个以上指纹段，和把已识别的指纹段合成为任何指纹匹配。所有指纹段可具有一个相同的长度，且所述扫描所述特定字符串字段以查找多个指纹段可用一个是所述指纹段长度的整倍数的特征码扫描操作的步长。一个说明特定指纹段在任何指纹内的一个或多个可能位置的指纹段位图可和所述特定指纹段储存在一起，以用于把已识别的指纹段合成为任何指纹匹配。说明一个或多个可能长度的指纹长度信息可和每个指纹的第一段或每一段储存在一起，以用于把已识别的指纹段合成为任何指纹匹配。一个或多个有限自动机(FA)可用来把已识别的指纹段合成为任何指纹匹配。

所述字符串特征码扫描方法可进一步包括存储每个指纹的假阳性匹配的概率，在有一个或多个匹配的指纹的位置上，检查所对应的假阳性匹配的概率，和当所述一个或多个假阳性匹配的概率中的一个假阳性匹配的概率不足够低时，查找所述特定字符串字段，以查找所述一个或多个后续查找数据结构。所述方法可进一步包括用一个指纹所对应的多个定长特征码或特征子码的一个或多个不同的基本单元构建一个差分查找数据结构，和查找所述特定字符串字段，以查找所述一个或多个后续查找数据结构，包括差分查找一个已识别的指纹所对应的多个定长特征码或特征子码。所述方法可进一步包括把每一个定长特征码或特征子码用一个或多个码膜比特编码，所述一个或多个码膜比特包括用于说明一个或多个以下匹配条件的一个或多个码膜比特：不用匹配，是否区分大小写，逻辑非，预定义范围，逻辑运算，和任意范围，所述一个或多个码膜比特包括一个或多个以下码膜比特：一个或多个基本单元或亚基本单元的码膜比特，一个或多个特征子码段的码膜比特，和一个或多个定长特征码或特征子码的码膜比特，查找所述特定字符串字段，以查找所述一个或多个后续查找数据结构，包括以查找所述被码膜比特编码的定长特征码或特征子码。所述方法可进一步包括把所述特定字符串字段规格化，包括把已编码的特定字符串字段解码，把已压缩的特定字符串字段解压，和把不需要的字符串数据删除中的一个或多个过程。

一般来说，本发明的一个方面的实施例提供字符串特征码扫描方法，所述方法包括把多个特征码中的每个特征码分解成一个或多个特征码段，接收一个由数据值组成的特定字符串字段，扫描所述特定字符串字段，以查找所述多个特征码的所述多个特征码段，包括并行查找两个或两个以上特征码段，把已识别的特征码段合成为任何特征码的匹配,和输出所述特定字符串字段中的任何已识别的特征码。本发明的所述方面的其它实施例包括所述方法所对应的系统，装置，和计算机软件产品。

具体实施可包括一个或多个以下特性。扫描以查找所述多个特征码段可进一步包括使用：一个或多个散列表，一个或多个布隆过滤器，一个或多个有散列值复用或长度复用或两者的散列表，和一个或多个有散列值复用或长度复用或两者的布隆过滤器中的一个或多个进行扫描。一个说明特定特征码段在任何特征码内的一个或多个可能位置的特征码段位图可以和所述特定特征码段存储在一起，以用来把已识别的特征码段合成为任何特征码匹配。说明一个或多个可能的特征码长度的特征码长度信息可进一步和每个特征码的第一段或每一段储存在一起，以用于把已识别的特征码段合成为任何特征码匹配。一个或多个有限自动机(FA)可被用来把已识别的特征码段合成为任何特征码匹配。

一般来说，本发明的一个方面的实施例提供字符串特征码扫描方法，所述方法包括把一个或多个特征码处理成一个或多个格式，包括把一个或多个特征码中的每个不定长特征码分解为多个定长特征子码和一个或多个不定长特征子码，接收一个由数据值组成的特定字符串字段，识别所述特定字符串字段所包括的任何特征码，包括扫描所述特定字符串字段，以查找多个所述定长特征码或特征子码，和在有一个或多个所述定长特征子码被识别的位置上，把已识别的所述定长特征子码合成为任何不定长特征码，和输出所述特定字符串字段中的任何已识别的特征码。处理一个或多个特征码成一个或多个格式可进一步包括储存每个定长特征子码的位置信息到静态特征码合成规则数据库，所述位置信息包括一个秩序和一个到下一定长特征子码的距离范围，和包括或不包括对每对定长特征子码之间的不定长特征子码的描述，和所述把已识别的定长特征子码合成为任何不定长特征码的匹配进一步包括检查每个已识别的定长特征子码的位置信息和核实或不核实每对相邻定长特征子码之间的所述不定长特征子码，和更新一个动态特征码合成状态表。一个或多个有限自动机(FA)可以被用来把已识别的定长特征子合成为任何不定长特征码。本发明的所述方面的其它实施例包括所述方法所对应的系统，装置，和计算机软件产品。

一般来说，本发明的一个方面的实施例提供字符串特征码扫描方法，所述方法包括为一个或多个字符串物件中的每个字符串物件选择多个定长特征码，所述特定字符串物件的多个定长特征码包括第J个定长特征码，所述第J个定长特征码的第一基本单元在所述特定字符串物件中的在扫描方向上的位置除以特征码扫描操作的步长的余数等于J，从而使得所述特定字符串物件的定长特征码的数目等于特征码扫描操作的步长，并且使得所述特定字符串物件在任何被扫描的字符串字段中的任何位置上都能被识别，接收一个由数据值组成的特定字符串字段，识别所述特定字符串字段所包括的任何字符串物件，包括在每个以扫描步长为间距的位置上，扫描所述特定字符串字段，以查找所述一个或多个字符串物件的所述多个定长特征码，其中包括并行扫描两个或两个以上定长特征码，和输出所述特定字符串字段中的任何已识别的字符串物件。所述方法可进一步包括为每个字符串物件选择多个基于多组不重叠的有序的定长特征码的不定长特征码，所述多个不定长特征码中的每个不定长特征码包括每组定长特征码中的一个定长特征码和一个把一对相邻的定长特征码连接起来的不定长特征码段，从而使得每个字符串物件的特征码的数目等于Sⁿ，其中S是扫描步长或每组定长特征码的特征码的数目和n是定长特征码的组数，和所述识别所述特定字符串字段中的任何字符串物件进一步包括扫描所述特定字符串字段，以查找一个或多个字符串物件的多个不定长特征码的多个定长特征子码，和在有一个或多个匹配的定长特征子码的位置上，把已识别的定长特征子码合成为任何不定长特征码。

一般来说，本发明的一个方面的实施例提供字符串特征码扫描方法，所述方法包括为一个或多个字符串物件中的每个字符串物件选择一个或多个定长特征码，把所述一个或多个字符串物件的所述一个或多个定长特征码处理成一个或多个格式，所述格式包括每个定长特征码的一个或多个指纹和一个或多个后续查找数据结构，所述特定字符串物件的多个指纹包括第J个指纹，所述第J个所述指纹的第一基本单元在所述特定字符串物件中的在扫描方向上的位置除以特征码扫描操作的步长的余数等于J，从而使得所述特定字符串物件的指纹数等于特征码扫描操作的步长，并且使得所述特定字符串物件在任何被扫描的字符串字段中的任何位置上都能被识别，其中每个所述指纹包括所述特定字符串物件的所述一个或多个定长特征码中的特定定长特征码的一个或多个片段，所述一个或多个片段具有在所述特定定长特征码中的任何地方的特定位置，接收一个由数据值组成的特定字符串字段，识别所述特定字符串字段中的任何字符串物件，包括在每个扫描步长为间距的位置上，扫描所述特定字符串字段，以查找所述一个或多个字符串物件的多个所述指纹，其中包括并行查找两个或两个以上所述指纹，和在有一个或多个匹配的所述指纹的位置上，查找所述特定字符串字段，以查找所述后续查找数据结构，和输出所述特定字符串字段中的任何识别的字符串物件。所述方法可进一步包括为每个字符串物件选择多个基于多组不重叠的有序的定长特征码的不定长特征码，所述多个不定长特征码中的每个不定长特征码包括每组定长特征码中的一个定长特征码和一个把一对相邻的定长特征码连接起来的不定长特征码段指纹，从而使得每个字符串物件的不定长特征码的数目等于各组定长特征码的定长特征码的数目的乘积，和所述识别所述特定字符串字段所包括的任何字符串物件包括扫描所述特定字符串字段，以查找一个或多个字符串物件的多个指纹，包括以并行查找两个或两个以上指纹，和在有一个或多个匹配的指纹的位置上，查找所述特定字符串字段，以查找所述后续查找数据结构。本发明的所述方面的其它实施例包括所述方法所对应的系统，装置，和计算机软件产品。

一般来说，本发明一个方面提供了一个字符串特征码扫描系统，所述系统包括一个包括计算机程序产品的机器可读的存储设备，和一个或多个可执行计算机程序产品和操作包括以下一个或多个模块的处理器：一个可把一个或多个特征码处理成包括每个定长特征码或不定长特征码的每个定长特征子码的一个或多个指纹和一个或多个后续查找数据结构的一个或多个格式的特征码预处理模块，所述一个或多个指纹包括特定定长特征码或特征子码的第J个指纹，所述第J个指纹的第一基本单元在所述定长特征码或特征子码中的在扫描方向上的位置除以特征码扫描操作的步长的余数等于J，从而使得所述指纹的数目等于特征码扫描的步长，并且使得所述定长特征码或特征子码在任何被扫描的字符串字段中的任何位置上都能被识别，其中每个所述指纹包括特定定长特征码或特征子码的一个或多个片段，所述一个或多个片段具有在所述特定定长特征码或特征子码中的任何地方的特定位置，一个可把一个由数据值组成的输入字符串字段处理为一个或多个扫描所需的格式的扫描预处理引擎，和一个可在所述输入字符串字段上识别一个或多个特征码的一个或多个指纹的指纹扫描引擎，所述识别包括在每个扫描步长为间距的位置上，扫描所述输入字符串字段，以查找所述一个或多个特征码的所述一个或多个指纹。所述系统可进一步包括一个可识别已识别的指纹所对应的定长特征码或不定长特征码的定长特征子码的定长特征码查找引擎。所述系统可进一步包括一个包括把已识别的不定长特征码的定长特征子码合成为任何不定长特征码的可识别不定长特征码的不定长特征码查找引擎。本发明的所述方面的其它实施例包括所述系统所对应的方法，装置，和计算机软件产品。

具体实施可包括一个或多个以下特性。所述特征码预处理模块可选择一个或多个影子空间并把一个或多个指纹投影到所述一个或多个影子空间去扫描。特征码预处理模块可把一个或多个指纹中的每个指纹分解为一个或多个长度的一个或多个指纹段，并把每个指纹段的指纹合成信息存储到一个指纹数据库，和所述指纹扫描引擎可识别所述输入字符串字段中的一个或多个特征码的多个指纹，所述识别包括在每个以扫描步长为间距的位置上，扫描所述输入字符串字段，以查找多个指纹段，和在有一个或多个已识别的指纹段的位置上，把已识别的指纹段合成为任何指纹匹配。

所述特征码预处理模块可用一个或多个码膜比特，对一个特征码的一个或多个特征码段进行编码，并把所述一个或多个码膜比特和所述特征码的一个或多个特征码段存储在一起。所述特征码预处理模块可用多个特征码的一个或多个不同的基本单元构建一个差分查找数据结构。所述特征码预处理模块可构建一个包括一个指纹数据库，一个定长特征码数据库，和当所述特征码扫描系统有至少有一个不定长特征码时的一个特征码规则数据库的特征码数据库。

所述扫描预处理引擎可进一步包括一个扫描输送器，一个投影器，一个字符串字段存储器，和一个影子字段存储器。所述扫描预处理引擎可按块处理一块或多块的字符串字段，所述处理包括输送，解码，规格化，和变换其中的一个或多个，所述一块或多块字符串块中的每个字符串块包括一个用于指纹扫描及特征码查找的指纹扫描区域，一个用于特征码查找的在指纹扫描区域之前的前特征码查找区域，和一个用于特征码查找的在指纹扫描区域之后的后特征码查找区域。一字符串块的所述三个区域的每个区域可存储到一个或多个尺寸相同的内存块中，所有所述三个区域的所有内存块单独或与一个或多个附加内存块可构成的一个由当前的前特征码查找区域的第一内存块开头的环，以减少数据在内存中的移动。

所述指纹扫描引擎可用一个或多个散列表和一个或多个布隆过滤器其中的一个或多个来检测一个或多个指纹。所述指纹扫描引擎可进一步包括一个指纹扫描控制器，一个指纹散列计算器，一个指纹查找器，一个指纹合成器，和一个指纹数据库。所述指纹散列计算器可用一个顺序散列函数在多个相互不重叠的散列键的前缀片段上，按顺序计算多个散列键的多个散列值。所述指纹扫描引擎可包括一个用一个指纹段比特位图和指纹长度信息中的一个或多个把多个指纹段并行或串行地合成为任何指纹的匹配的指纹合成器。所述指纹扫描引擎可包括一个进一步包括一个或多个有限自动机(FA)的指纹合成器。

一个或多个长度的一个或多个指纹可被分解为多个相同大小的指纹段，并被一个或多个有相同扫描步长的指纹扫描引擎扫描，所述一个或多个指纹扫描引擎的每个指纹扫描引擎覆盖一个或多个不重叠的交错的所述输入字符串字段的位置，从而使得所述一个或多个指纹扫描引擎的总扫描步长等于所述一个或多个指纹扫描引擎的数目和单个指纹扫描引擎的原扫描步长的乘积，或覆盖一个或多个部分重叠的交错的所述输入字符串字段的位置，从而使得所述一个或多个指纹扫描引擎的总扫描步长介于单个指纹扫描引擎的原扫描步长，和所述一个或多个指纹扫描引擎的数目和单个指纹扫描引擎的原扫描步长的乘积之间。扫描步长和内存速度的乘积较小的指纹扫描引擎的数目可多于扫描步长和内存速度的乘积较大的指纹扫描引擎的数目。

覆盖一个较短的指纹段的一个或多个指纹扫描引擎所用的一个或多个内存可等于或快于覆盖一个较长的指纹段的一个或多个指纹扫描引擎所用的一个或多个内存，和覆盖一个或多个平均长度较短的指纹所对应的一个或多个定长特征码查找引擎所用的一个或多个内存可等于或快于覆盖一个或多个平均长度较长的指纹所对应的一个或多个定长特征码查找引擎所用的一个或多个内存。一个或多个覆盖短于特定长度的指纹的指纹扫描引擎，单独或与所对应的定长特征码查找引擎的第一部分一起可用一个或多个在所述扫描系统中最快的内存。扫描相同的一个或多个指纹的多个指纹扫描引擎可共用一个多端口内存。所述指纹扫描引擎可进一步包括一个或多个内容寻址存储器(CAM)。

所述定长特征码查找引擎可进一步包括一个特征码搜寻器，一个特征码核实器，和一个定长特征码数据库。所述特征码搜寻器和所述特征码核实器可用一个特征码单元比较器和一个特征码段比较器来比较一个或多个带码膜的一个特征码的片段，以识别一个或多个定长特征码。所述特征码搜寻器可差分查找一个或多个定长特征码或特征子码。所述不定长特征码查找引擎可进一步包括一个特征码合成规则查找器，一个特征码状态验证器，一个特征码合成规则数据库，和一个特征码状态表格。所述不定长特征码查找引擎可包括一个有限自动机(FA)。一个或多个引擎可包括一个或多个内容寻址存储器(CAM)和一个或多个有限自动机(FA)其中的一个或多个。

本说明书所述具体实施例可用来实现以下一个或多个优点。本发明提供了一个扫描一个特征码库中的特征码的字符串扫描系统。所述字符串扫描系统灵活且容易被更新。一个字符串特征码扫描引擎即使当扫描大量的特征码(如几十万个特征码)，复杂的特征码(如长达几千字节，或带通配符“*”和“？”，范围，不区分大小写，逻辑非)，和一个动态的特征码库时，仍可提供极快的扫描速度(如100Gbps)。所述字符串扫描系统的扫描速度和特征码库的大小和复杂性可扩展性。此外，所述字符串扫描系统需求较小的内存和内存带宽。所述字符串扫描系统可以用软件或现场可编程门阵列(FPGA)或专用集成电路(ASIC)来实施。此外，所述字符串扫描系统的成本效益高，既适用于高端产品，也适用于低价产品。

本发明的一个或多个实施例详见如下说明书和附图。本发明的其它特征和优点由说明书、附图、和权利要求书显而易见。

附图说明

图1A示出了一个示例性快速字符串特征码扫描系统的结构图；

图1B示出了一个构建字符串特征码数据库的示例性流程图；

图1C示出了一个字符串特征码扫描的示例性流程图；

图2A-2C示出了一个指纹数据库的示例性数据结构；

图2D-E示出了一个散列条目块的示例性数据结构和一个指纹合成器的实施例；

图2F-2G示出了一个散列条目块的示例性数据结构和一个对应的指纹合成器的实施例；

图2H-I示出了一个散列条目块的示例性数据结构和一个对应的并行指纹合成器的实施例；

图3A-B示出了用于定长特征码查找的特征码群链表和特征码链表的示例性数据结构；

图4A-B示出了一个字符串字段的支持一个预定义的全局单元范围的一个示例性特征码单元比较器和一个特征码段比较器的结构图；

图4C示出了一个支持本地特征码单元范围的示例性特征码单元比较器的结构图；

图5A-C示出了一个用于定长特征码查找的选择单元树和特征码家庭链表的示例性数据结构；

图6示出了一个用于不定长特征码查找的特征码规则链表的示例性数据结构；

图7示出了一个特定字符串字段的特征码状态链表的示例性数据结构；

图8示出了一个被一个特征码状态布隆过滤器或散列表所指的散列条目块的示例性数据结构；

图9示出了一个示例性计算机系统。

在各附图中类似的附图标记和标示表示类似的元件。

具体实施方式

概观

本发明为针对一个字符串特征码数据库对一个字符串字段进行扫描的方法和系统。在一个实施例中，一个“分而治之”的扫描方法被用来以多个流水线阶段进行扫描。每个不定长特征码首先被分解成多个定长特征子码来扫描，而每个定长特征码或每个不定长特征码的每个定长特征子码再进一步被分解成多个特征码段来扫描。在一个实施例中，先“粗扫描”后“细扫描”的方法被用来以多流水线扫描阶段进行扫描，以查找字符串特征码。在每一个扫描位置上，定长特征码或定长特征子码的一个或多个指纹首先被扫描。进一步的检查只需要在有一个或多个指纹匹配的位置上进行。此外，指纹扫描可先在每一个扫描位置上扫描指纹影子(影子和影子相关的空间将在下面详细介绍)。只有在有一个或多个匹配的指纹影子的位置上，才需对所述指纹进行全面的检查。

所述指纹影子可进一步先分段在每个扫描位置上扫描，然后再通过仅检查指纹影子段在任何指纹中的可能的位置和可能的指纹长度把指纹影子段进行合成。指纹影子的全面的检查只需要在有一个或多个匹配的合成的指纹影子的位置上进行。此外，指纹影子段的扫描只需在每一个扫描位置上对其散列值进行扫描。进一步的检查指纹影子段只需在有一个或多个匹配的散列值的位置上进行。在一个实施例中，在扫描之前先把用于扫描字符串字段的字符串特征码预处理，并将预处理过的特征码存储到特征码数据库中，以提供给多流水线阶段扫描使用。

图1A示出了一个快速字符串特征码扫描引擎100。所述扫描引擎包括一个特征码预处理模块90，一个扫描预处理引擎120，一个指纹扫描引擎140，一个定长特征码查找引擎160，和一个不定长特征码查找引擎180。快速字符串特征码扫描引擎100针对一个或多个字符串特征码数据库，对字符串字段进行扫描，并可能送回已匹配的特征码的编号190和在所述字符串字段内的位置，以识别特定特征码。在一个实施例中，特征码数据库包括一个指纹数据库148，一个定长特征码数据库166，和一个特征码规则数据库186。

图1B示出了一个预处理每个字符串特征码的程序91。在一个实施例中，首先将一个不定长特征码分解为多个定长特征子码和不定长特征子码，并把定长特征子码之间的关系的信息存储到特征码规则数据库186中(步骤92)。

为了快速扫描，步骤92输出的一个定长特征码或特征子码可以进一步被分解成多个可按最佳次序检验的片段(步骤94)。在一个实施例中，第一个或前几个特征码段特别重要，可以作为定长特征码或特征子码的指纹。一个字符串特征码的指纹既可以被快速地扫描，又可以减少假阴性或假阳性匹配的概率。在一个实施例中，假阴性匹配的概率是零。在一个实施例中，多个特征码的不同指纹长度的数目比多个特征码的不同特征码长度的数目要少，从而加快要求对不同长度的模式进行单独扫描的扫描方法的速度。在一个实施例中，当扫描步长大于一个基本单元时，多个指纹可以用于一个字符串特征码，其中每个指纹的第一个基本单元在扫描方向上相对前一个指纹的第一个基本单元位移了一个或多个基本单元。扫描方向是一个扫描操作在一个输入字符串字段中扫描位置的移动的方向。

一个定长特征码或特征子码的指纹可以进一步分解为指纹段，根据需要可以进一步投影到一个或多个影子空间，然后加入到指纹数据库148并从而到特征码数据库中去(步骤96)。由于不同长度的指纹可能被独立扫描，指纹可以进一步分解成多个指纹段进行并行或串行扫描。在一些实施例中，指纹被分解成多个指纹段，从而使得不同指纹段长度的数目为一或远比不同指纹长度的数目少，从而加快要求对不同长度的模式进行单独扫描的扫描方法的速度。指纹段的扫描结果可以随后被合成到一起，以检测指纹。

在一个实施例中，为了进一步提高扫描效率和扫描复杂特征码的能力，指纹及其它特征码段可以先被投影到一个或多个影子空间进行扫描，然后再在原始空间进行验证。影子空间可以选择既能够简化和加速扫描过程，同时还可以覆盖指纹或指纹段的所有可能的格式。一个影子空间可以覆盖多个指纹或特征码段的格式。例如，为了同时支持区分大小写和不区分大小写的单个字符，影子空间可以为只有小写或只有大写的空间。作为一个特例，影子空间可以就是原始空间。

完全指明的指纹或任何其它特征码段在任何影子空间的影子仍是完全指明的。因此，完全指明的指纹除在原始空间以外，总可以在任何影子空间扫描。在一个实施例中，为了减少所需扫描的空间的数目，所有的完全指明的指纹都在一个或多个影子空间中的一个影子空间扫描，使得没有指纹要在原始空间扫描。在另一个实施例中，一个特征码数据库的影子空间只有一个，所述特征码数据库的所有的指纹都在所述唯一的影子空间扫描。

在一个实施例中，指纹数据库包括一个或多个布隆过滤器或散列表。当原散列键太长或太昂贵在指纹扫描过程中进行比较时，为了进一步减少假阳性匹配和散列碰撞的概率，在另一个实施例中，指纹数据库包括一个或多个存有附加的散列值比特或一个指纹长度或两者的改进型布隆过滤器或散列表。

最后，所有定长特征码或不定长特征码的定长特征子码的片段被编码并被存储到定长特征码数据库166中，以查找定长特征码或特征子码(步骤98)。在一个实施例中，所述片段可以用单元膜或亚单元膜进行编码，以支持字符串特征码匹配的特定条件(如“不用匹配”，“相等”，“不相等”，“不区分大小写”，“区分大小写”，“在一个范围内”，“在一个范围外”)。在一个实施例中，带码膜的片段可以随后被编译成一个链表或任何其它查找结构(如树等)。在另一个实施例中，片段码膜或定长特征码或特征子码码膜可以被编译成查找结构，以节省存储空间。在另一个实施例中，一组字符串特征码可以进一步利用字符串特征码之间的不同单元进行差分编码，以形成可快速查找的差分数据结构(如差分树等)。

图1C演示了一个字符串特征码的扫描程序101。一个待扫描字符串字段首先要被解码并被变换到(如用扫描预处理引擎120)一个或多个后续扫描阶段所需要的格式(步骤102)。所述符串字段首先在影子空间通过对其影子与一个或多个字符串特征码的指纹的影子进行比较而被扫描(如用指纹扫描引擎140)，然后再在原始指纹空间对任何已识别的指纹影子(步骤104)进行核实。步骤106查看是否有一个指纹匹配。

在扫描之后，无匹配或有一个匹配分别产生一个表示没有特征码匹配的输出或一个表示有少数几个特征码匹配的输出。在一个实施例中，指纹扫描引擎140可提供零假阴性匹配和一个足够小的假阳性匹配几率。如果没有指纹匹配，当前扫描位置的扫描已完成，可以移动到下一个扫描位置(步骤108)。如果有指纹匹配，将对少数几个匹配的特征码作进一步的查找(如用定长特征码查找引擎160)，以更加明确地识别为定长特征码或不定长特征码的定长特征子码(步骤110)。

步骤112查看是否有一个定长特征码或特征子码匹配。如果没有匹配，当前扫描位置的扫描已完成，可移动到下一个扫描位置(步骤108)。如果有一个或多个定长特征码匹配，输出每个匹配的定长特征码的编号，且结束当前扫描位置的扫描(步骤118)。如果有作为一个或多个不定长特征码的一部分的定长特征子码被识别，已匹配的特征子码将被动态地合成(如用不定长特征码查找引擎180)以检测一个或多个不定长特征码(步骤114)。步骤116查看是否有一个不定长特征码匹配。如果没有匹配，当前扫描位置的扫描已完成，可以移动到下一个扫描位置(步骤108)。如果有一个或多个匹配，输出每个匹配的不定长特征码的编号，且结束当前扫描位置的扫描(步骤118)。

在特征码的预处理过程91中，在一个实施例中，每个指纹的假阳性匹配的概率被存储在指纹数据库148中。如果步骤106有一指纹匹配，所述匹配的指纹的假阳性匹配的概率将被查看。如果所述假阳性匹配的概率足够低(如低于指定的阈值)，当前扫描位置的扫描过程已完成，可以移动到下一个扫描位置(步骤108)。在另一个实施例中，所有数据库中的指纹的假阳性匹配的概率都足够低，因此不需储存和查看指纹的假阳性匹配的概率。当前扫描位置的扫描过程在指纹扫描后已完成，可以移动到下一个扫描位置(步骤108)。

在步骤102中，扫描预处理引擎120首先将所述字符串字段解码，规格化，并变换为与特征码数据库中的特征码相同的格式。在一个实施例中，字符串特征码扫描是在整个字符串字段上进行。然而，在另一个实施例中，由于一些系统的存储空间的限制或低延迟要求，储存整个字符串字段不可能。因此，在步骤102时，所述字符串字段可以被分解成几个预定大小的字符串块。字符串特征码扫描是在每一个预定大小的字符串字块上进行。

在加载一字符串块后，所述字符串块将被解码，规格化，并变换为以后扫描阶段所需要的不同格式。在一个实施例中，解码和规格化过程可以支持不同的压缩格式(如LZS，PKZip，和gzip)，不同的编码标准(如UU编码，MIME编码，HTML，和XML)，和删除随机“反扫描”垃圾数据。

在一个实施例中，解码后的字符串字段将被进一步投影到一个或多个特征码数据库要求的影子空间，以支持复杂的特征码。例如，解码后的字符串字段被转换为全小写字(如一个影子空间)，以支持不区分大小写的字符串特征码扫描。字符串特征码扫描可以先在全小写已解码字符串字段上进行，然后再用原区分大小写的已解码字符串字段和全小写已解码字符串字段进行验证。

在步骤104中，指纹扫描可首先识别其影子为完全指明的指纹。为了快速扫描大量且复杂的特征码，在一个实施例中，指纹扫描引擎140可以用一个或多个散列表或布隆过滤器同时扫描多个基本单元。在一个实施例中，指纹扫描引擎140可用散列值复用和指纹长度复用来提高储存器的使用效率和减小假阳性匹配和指纹碰撞的概率。散列值复用和指纹长度复用可以在保证零假阴性匹配(即错过一个特征码匹配)的同时，进一步减小假阳性匹配(即错误的特征码匹配)的概率。

步骤110扫描定长特征码。定长特征码或不定长特征码的定长特征子码可在所述定长特征码扫描阶段识别。定长特征码扫描只需当指纹扫描过程中至少有一个指纹匹配时才执行。已匹配的指纹所对应的定长特征码或特征子码可以被逐个进行匹配或用其它查找结构(如树等)进行匹配。在一个实施例中，基本单元或亚基本单元的带码膜比较可以用来支持字符串特征码匹配的特定条件(如“不用匹配”，“相等”，“不相等”，“不区分大小写”，“区分大小写”，“在一个范围内”，“在一个范围外”)。

步骤114扫描不定长特征码。在一个实施例中，不定长特征码扫描只需在扫描有一个或多个不定长字符的不定长特征码时才执行。不定长特征码的定长特征子码在定长特征码扫描阶段被识别，已识别的定长特征子码可在不定长特征码扫描阶段被动态地连接在一起，以合成为一个或多个原不定长特征码。所述合成可以用一个静态合成规则表和一个动态合成状态表来实现。所述合成规则表指明将定长特征子码合成为不定长特征码的规则，所述合成状态表则根据所述合成规则表维护当前的合成状态。

特征码数据库的预处理

在一个实施例中，为了提高扫描速度和内存效率，在扫描所述字符串字段之前，特征码预处理模块90对特征码进行预处理。在存入特征码数据库之前，特征码预处理模块90可以先把特征码分解，变换，和编码成一个或多个格式。在一个实施例中，特征码预处理模块90可以构建和维护一个指纹数据库148，一个定长特征码数据库166，和一个特征码规则数据库186。

当特征码数据库有一个或多个特征码含一个或多个不定长子码(如代表零个以上任意的基本单元的“*”或代表“bc”重复3至6次的“(bc){3-6}”)，每个这样的不定长特征码可以先用不定长特征子码被分解成多个定长特征子码。例如，如果一个特征码为“子码1*子码2*子码3”，其中子码1，子码2，和子码3都是不含不定长字符的定长子码，所述特征码可以被分解为子码1，子码2，子码3。子码1*子码2*子码3中的每个所述“*”可被一个不定长子码取代。在一个实施例中，每个所述定长特征子码可以先被独立地扫描，然后再将其合成为原不定长特征码。

在一个实施例中，特征码规则数据库186可用每个定长特征子码的位置信息(如次序，最后子码标志，到下一个定长子码的距离或距离范围)来构建，以用于合成定长特征子码。在一个实施例中，当两个连续的定长特征子码之间的不定长子码不为“不用匹配”，所述特征码规则数据库186可进一步含对所述不定长子码的描述，以用于合成定长特征子码。在另一个实施例中，可用所述定长特征子码和不定长特征子码构建一个或多个有限自动机(FA)，以用于合成定长特征子码，其中每个定长特征子码作为一个整体为一个输入符号。

在一个实施例中，一个定长特征码或特征子码将被进一步被分解成多个可以用最佳的顺序进行查找的片段(这些片段包括所述特征码或特征子码的所述指纹)。所述多个片段可以有不同的尺寸或相同的尺寸。为了防止假阴性匹配或不错过任何一个特征码，所有所述片段的集合等于原定长特征码。在特征码扫描的过程中，随着匹配的片段的数目的增加，假阳性匹配值将降低(即匹配的可信度增加)。扫描的过程将终止于第一个不匹配的片段或最后一个匹配的片段。在一个实施例中，特征码的片段的选择可以让无匹配终止或识别一个零假阳性匹配的特征码匹配尽早出现。

在一个实施例中，所述指纹包含多个片段。在另一个实施例中，所述指纹只有一个片段，并被编码为三元组{片段，长度，错位}，其中片段为字符串特征码的第一个被扫描的片段即所述特征码的指纹，长度为所述指纹的长度，错位为所述指纹在一个定长特征码或特征子码中的错位。特定指纹是一个定长特征码或不定长特征码的定长特征子码的特定片段。

在一个实施例中，所述影子空间可以被选择能够简化和加快所述特征码扫描的过程，同时能够覆盖所述多种指纹或特征码片段的格式。在理想情况下，所述影子值可以直接作为一个散列键。例如，为了同时支持区分大小写和不区分大小写的单元，所述影子空间可以是全小写或全大写的空间。例如，为了扫描由一个字母后接7个数字组成的驾驶证号码，其中每个字母和数字可以进一步指定为任意的字母和数字的范围，影子空间可以用一代码或任何一个字母(如“a”)代替所有的字母，并用另一代码或任何一个数字(如“0”)代替所有的数字。例如，为了扫描由三组被空格或“-”分隔开的三位数字所组成的社会安全号码(SSN)，其中每个数字可以进一步被指定为任意的数字范围，影子空间可以用一代码或任何一个数字(如“0”)代替所有的数字，并用另一代码或空格或“-”代替空格和“-”。作为一个特例，所述影子空间可以就是原空间。

在一个实施例中，指纹在影子空间被扫描完之后，指纹的验证可以在检测到指纹影子之后立刻在原空间进行。在另一个实施例中，所述验证可以在先验证其它片段的部分或全部后再进行。如果所述指纹完全被其它片段所覆盖，不需验证。

指纹的选择既要加快所述指纹扫描的速度，同时还要提供最小的在指纹扫描之后的假阳性匹配的概率。在一个实施例中，所述指纹可以为任意尺寸和在所述特征码中的任意位置上。在另一个实施例中，为了满足系统的要求，所述指纹的尺寸或在所述特征码中的位置受限制。例如，为了满足系统的延迟要求，所述指纹的错位不能超过某特定值。

在一个实施例中，指纹可以用以下一个或多个条件选择：

1)所述指纹的所述影子没有通配符或范围，以被较快扫描，

2)所述指纹在所述待扫描的字符串字段中出现的概率很小，

3)多个特征码共用的指纹的数目尽可能地小，和

4)有一个相同的指纹段的指纹的数目尽可能地小。

其它选择的条件可以根据系统的要求而增加。在常见的网络应用和非网络应用中，通常所有或大多数字符串特征码都至少含有一段相当长的，在投影到一个选定的影子空间中之后没有通配符或范围的片段。在一个实施例中，第一个选择条件为一个必要条件。在另一个实施例中，第一个选择条件可以进一步限制为所有指纹的每个指纹至少在一个影子空间中为完全指明。不含符合选择条件的指纹的特征码，可以被扩展为多个含有符合选择条件的指纹的特征码，或用一个不需特征码扩展的不同扫描方式扫描。

所述指纹可以通过检查所有符合第一选择条件的一个特征码的片段来选择。其它指纹的参数也可以在选择指纹的时候被加以考虑。根据第二选择条件，选择在所述待扫描的字符串字段出现的概率很小的特征码段作为指纹，可以减少假阳性指纹匹配的概率。此外，让有一个相同的指纹段的指纹的数目尽可能地小，可以进一步减少假阳性指纹匹配的概率。尽管所述指纹的长度可以少于8个基本单元或多于32个基本单元，但是通常在8至32基本单元之间。

由于所述特征码可以很长(如数百或上千个基本单元)，指纹的长度可能也很多。然而，在一个实施例中，不同长度的指纹要单独扫描，从而扫描速度较慢。在一个实施例中，为了减少扫描的复杂性，可以根据特定系统要求和系统架构来限制指纹长度的数目，如少于16。在一个实施例中，指纹的长度可以从一个预定的长度表中选定。此外，指纹的长度可以根据系统要求和系统架构，按指数递增关系(如2，4，8，16，和32)，线性递增关系(如4的倍数：4，8，12，16，20，24，28，和32)，或另一关系(如2，3，5，8，13，21，34)来选择。

在一个实施例中，一个特征码的指纹可以用一个算法来选择。例如，以下算法可以用来选择一个定长特征码或特征子码的指纹(假设扫描步长等于1，指纹的长度从最短至最长固定为l₀，l₁，l₂，…，l_m-1，l_m，指纹扫描分段进行，指纹扫描的影子空间已给定)：

1.找到所有在影子空间为完全指明的特征码子段。

2.对每一个长于的l_m的所述的子段，找到所有长度等于l_m的子段。

3.对每一个长度等于l_m的子段，记下所述子段在所有特征码中已被选为指纹的次数N_c和与其它指纹有相同的第一指纹段的次数N_s，和用一个基于N_c，N_s，和l_m的成本函数算出成本值。

4.分别用长度等于l_m-1，…，l₂，l₁，和l₀的子段重复步骤2和3。

5.从步骤2到4中，找出最小成本的子段为一个指纹。

上述步骤与特征码的处理顺序有关。几个随机处理顺序可以根据需要用来找到不同的指纹。在一个实施例中，成本值等于把(m-i),N_c,和N_s从最高位到最低位联接起来，其中i＝0，1，2，…，m和i为指纹的长度。在一个实施例中，如果已找到特定长度的指纹，不需要再对所有更短的子段进行选择。

在另一个实施例中，指纹扫描引擎140每次移动一个扫描步长。在每个扫描位置上，指纹扫描引擎140串行或并行地扫描不同长短的指纹。因此，扫描速度与扫描步长(即连续两个扫描位置之间的基本单元的数目)成正比。在一个实施例中，为了提高扫描速度，指纹扫描可以同时扫描多个基本单元，而不是一个基本单元。为了确保零假阴性匹配，每个字符串特征码要用多个指纹且所述指纹的数目等于所述扫描步长。换言之，一个定长特征码或特征子码可以用多个指纹放入到特征码数据库且所述指纹的数目等于扫描步长。特定特征码的第J个指纹的第一个基本单元是所述特定特征码在扫描方向的第(J+k*S)个基本单元，其中S为扫描步长，k为一个非负整数，和J＝0，1，2，...，S-1。所述特征码就可以在所述待扫描的字符串段中的任何位置找到。例如，如果特定特征码为“[Rr][Ee][Aa][Dd][Mm][Ee]123.exe”，所述扫描步长为4，所述指纹长度包括4，8和12，可以选用以下四个指纹：“[Rr][Ee][Aa][Dd][Mm][Ee]123.ex”，“[Ee][Aa][Dd][Mm][Ee]123.exe”，“[Aa][Dd][Mm][Ee]123.”，和“[Dd][Mm][Ee]123.e”，其中[Rr]，[Ee]，[Aa]，[Dd]，和[Mm]分别为不区分大小写的英文字母r，e，a，d，和m。“[Rr][Ee][Aa][Dd][Mm][Ee]123.exe”用所述四个指纹放入到指纹数据库四次。当扫描步长为1时，只需一个指纹且只需放入一次。

所述多个指纹的扫描可以从输入字符串字段的前S个单元中(即在第一扫描步长内)的任何位置开始。例如，在一个实施例中，所述扫描从第0位置开始，将扫描第(k*S)位置，其中k为一个非负整数。在任何输入字符串字段中，第(k*S)位置被第0个指纹覆盖，第(k*S+1)位置被第(S-1)个指纹覆盖，第(k*S+2)位置被第(S-2)个指纹覆盖，...，和第(k*S+S-1)位置被第1个指纹覆盖。在另一个实施例中，扫描从第(S-1)位置开始，将扫描第(k*S+S-1)位置，其中k为一个非负整数。在任何输入字符串字段中，第(k*S)位置被第(S-1)个指纹覆盖，第(k*S+1)位置被第(S-2)个指纹覆盖，第(k*S+2)位置被第(S-3)个指纹覆盖，...，第(k*S+S-2)位置被第1个指纹覆盖，和第(k*S+S-1)位置被第0个指纹覆盖。

为了把所述扫描步长提高到S个基本单元，在一个实施例中，以上当扫描步长为1时的为每个定长特征码或特征子码选择一个指纹的算法可以做如下修改，以用来选择每个定长特征码或特征子码的所述S个指纹：步骤1至4和以前完全一样，步骤5则修改为从所有在步骤2中找到的、所述定长特征码或特征子码的在扫描方向的错位为(J+k*S)的子段中，找出最小成本值的子段为所述S个指纹中的第J个指纹，其中J＝0，1，2，...，S-1和k为一个非负整数。

通常每个字符串物件只有一个特征码，为支持S基本单元的扫描步长，每个定长特征码或不定长特征码的定长特征子码需要S个指纹。在另一个实施例中，为支持S基本单元的扫描步长，S个定长特征码可以用来识别一个字符串物件，从而使得每个定长特征码在扫描方向的第一个基本单元在所述字符串物件的错位为(J+k*S)，其中J＝0，1，2，...，(S-1)和k为一个非负整数。所述特定字符串物件就可以在任何待扫描字符串字段的任何位置上被识别。在一个实施例中，S个定长特征码的扫描可以不用指纹。在另一个实施例中，S个定长特征码中的每一个特征码可以用一个指纹来进行特征码扫描。

在一个实施例中，多个基于多组不重叠的有序的定长特征码的不定长特征码可以进一步被选择用来识别一个字符串物件。每组定长特征码有S个定长特征码，其中第J个定长特征码在扫描方向的第一个基本单元在所述字符串物件的错位为(J+k*S)，其中J＝0，1，2，...，(S-1)和k为一个非负整数，从而构成Sⁿ个不定长特征码，其中n是不重叠的有序的有S个定长特征码的码组的组数。从每组定长特征码中选择出一个定长特征码，然后再将这些定长特征码和一个或多个不定长字符串段组合成为Sⁿ个不定长特征码中的一个不定长特征码，从而使得所述特定字符串物件可以在任何待扫描字符串字段的任何位置上被识别。所述n组S定长特征码中的每个原定长特征码在合成后变为多个合成后的不定长特征码的一个定长特征子码。在一个实施例中，所述不定长特征码的扫描可以不用指纹。在另一个实施例中，所述不定长特征码中的每一个定长特征码可以选用一个指纹来扫描。

在一个实施例中，为支持S基本单元的扫描步长，特定字符串物件可以选用P个定长特征码，每个定长特征码可进一步选用一个或多个指纹，从而使得每个字符串物件的总指纹数等于S。所述特定字符串物件的S个指纹中的第J个指纹在扫描方向的第一个基本单元在所述特定字符串物件中的错位为(J+k*S)，其中J＝0，1，2，...，(S-1)和k为一个非负整数，从而使得所述字符串物件可以在任何待扫描字符串字段的任何一个位置上被识别。

在另一个实施例中，多个基于多组不重叠的有序的定长特征码的不定长特征码可以进一步被选择用来识别一个字符串物件。第i组不重叠且有序的定长特征码有P_i个定长特征码，其中每个定长特征码进一步有一个或多个指纹，从而使得第i组定长特征码的总指纹数等于S，其中i＝0，1，2，...，n-1和n为不重叠且有序的定长特征码组的组数。每组定长特征码的S个指纹中的第J个指纹在扫描方向的第一个基本单元在所述特定字符串物件中的错位为(J+k*S)，其中J＝0，1，2，...，(S-1)和k为一个非负整数。

从每组定长特征码中选择出一个定长特征码，然后再将这些定长特征码和一个或多个不定长字符串组合成P₀*P₁*P₂…*P_n-1个不定长特征码中的一个不定长特征码，从而使得所述特定字符串物件可以在任何待扫描字符串段的任何位置上被识别。所述n组定长特征码中的每个原定长特征码变为多个合成后的不定长特征码的一个定长特征子码。

在一个扫描系统的每个字符串物件的特征码，指纹，和影子空间确定以后，一个指纹的影子可以作为一个整体进行扫描。不同长度的指纹影子可以并行或串行扫描。在一个实施例中，不同长度的指纹的影子可以作为一个整体进行串行扫描。在一个实施例中，把一个字符串特征码编入所述特征码数据库可用以下伪代码：

其中S是扫描步长，h_i是第i个字符串特征码的指纹的长度，IV是初始散列值，和散列()是一顺序散列函数。指纹选择()为每个移位位置选择的最佳指纹，特征码编入()把特征码编入到所述定长特征码查找引擎160和不定长特征码查找引擎180的数据库中去，和指纹编入()将指纹编入到所述指纹数据库148中去。当扫描步长大于1时，每个特征码的指纹都要调用指纹编入()一次。但是，因为一个特征码的所有的指纹都指到同一个特征码查找数据结构，一个特征码的所有指纹一共只要调用特征码编入()一次。

在一个实施例中，从所述特征码数据库删除一个字符串特征码可以使用以下伪代码：

其中S是扫描步长，h_i是第i个字符串特征码的指纹的长度，IV是初始散列值，散列()是一顺序散列函数，指纹删除()将一个指纹从所述指纹数据库148中删除，和特征码删除()将所述特征码的特征码查找数据结构从所述定长特征码查找引擎160和不定长特征码查找引擎180的数据库中删除。当扫描步长大于1时，因为一个特征码有多个指纹，要从特征码数据库中删除一个特征码，指纹删除()要被调用多次。但是，特定特征码的所有指纹一共只要调用特征码删除()一次。

因为不同指纹段长度的数目通常远比不同指纹长度的数目少，在一个实施例中，为了提高扫描效率，一个指纹可以进一步被分解成多个指纹段。一个指纹的所有指纹段可以先并行或串行地扫描，所述指纹段的扫描结果再被并行或串行地合成，以检测指纹。所述指纹段的长度可以相同或不同，取决于特定的扫描引擎所支持的指纹的长度。

在一个实施例中，指纹段的数目和长度可以根据指纹的长度和特定扫描引擎的其它扫描参数而定。在另一个实施例中，指纹长度之间为线性关系且所有的指纹段的长度都相同。通常，一个指纹段的长度等于一个或多个扫描步长。在另一个实施例中，扫描步长是一个指纹段的长度的整数倍且多个指纹段将被并行地合成。

在一个实施例中，指纹数据库可以包含一个或多个布隆过滤器和一个或多个散列表中的一个或多个。通常使用布隆过滤器或散列表应权衡存储器的大小和带宽。当特征码的数目可以全部存入有足够大带宽的片上存储器，布隆过滤器或甚至多个散列表可能更好。相反，当特征码的码数较多，从而必须用片外存储器时，内存的带宽就成为主要的限制，所述散列表而不是所述布隆过滤器可能更好。

在一个实施例中，散列值的附加比特被存储在一个布隆过滤器或一个散列表中，以实现散列值复用。在另一个实施例中，指纹长度被存储在一个布隆过滤器或一个散列表中，以实现指纹长度复用。当原散列键太长或太昂贵在扫描指纹中进行比较时，散列值复用及指纹长度复用可以进一步降低假阳性匹配和指纹碰撞的几率。

在一个实施例中，当影子空间，指纹，指纹段和指纹数据结构被确定以后，一个定长特征码或不定长特征码的定长特征子码可以作为一个整体或分段在影子空间被编入到所述指纹数据库148和特征码数据库中去。

在一个实施例中，一个定长特征码或不定长特征码的一个定长特征子码的指纹以外的其它片段可以被编码和存储到定长特征码数据库166，以在指纹匹配后用来扫描整个定长特征码或特征子码。在一个实施例中，一个定长特征码或不定长特征码的一个特征子码的一个或多个片段可以用一个或多个基本单元或亚基本单元的码膜来编码成多个带码膜的片段，以支持字符串特征码匹配的特定条件(如“不用匹配”，“相等”，“不相等”，“不区分大小写”，“区分大小写”，“在一个范围内”，“在一个范围外”)。在一个实施例中，为了改进存储效率，一个或多个特征码片段码膜或一个或多个特征码或特征子码码膜可以单独使用，或和一个或多个基本单元或亚基本单元码膜一起使用。

在一个实施例中，带码膜的特征码段可以用链表按顺序或不按顺序连接在一起，或预处理成其它查找结构(如树)。在一个实施例中，所有带码膜的特征码段的长度可以全相等或不全等。所述带码膜的特征码段的长度可以根据特定内存的架构来最佳地选择。

在另一个实施例中，为了让字符串特征码的假阳性匹配尽可能快地收敛到零和让可能匹配的特征码尽可能快地收敛到零个或一个，一组字符串特征码可以进一步进行差分编码，以构建可快速查找的差分数据结构(如差分树)。差分树可以利用特征码之间的不同单元进行构建。

在一个实施例中，当添加一个或多个新的特征码，或当删除一个或多个现有的特征码时，特征码数据库预处理只能在特征码数据库的最初创建时进行。在另一个实施例中，特征码的数据库可以在特征码的扫描过程中动态地更新。

字符串字段的扫描预处理

所述扫描预处理引擎120根据字符串特征码数据库把字符串字段预处理为不同的格式，以简化和加速其后的扫描流水线阶段。在一个实施例中，在特征码数据库中的特征码以未编码的格式存储。因此，扫描预处理引擎120把已编码的字符串字段解码，以和所述特征码数据库中的特征码的解码格式一致。如图1A所示，扫描预处理引擎120包括一个扫描输送器122，一个字符串字段存储器124，一个格式解码器126，一个解码字段存储器128，一个投影器130，和一个影子字段存储器132。所述扫描输送器122先将待扫描数据从所述字符串字段存储器124加载到所述格式解码器126，所述格式解码器126再将对原始字段进行解码，解析和解压缩，其中可包括MIME解码，UU的解码，外语解码，除去包括毫无意义的字符串(如额外的空白空间)和反扫描垃圾字符串数据(如注入的反扫描垃圾数据)，HTML解析，XML解析，deflate解压缩，LZS解压缩，PKZip解压缩，和gzip解压缩。所述格式解码器126还可以根据特定系统的需要规格化字符串字段。此后，所述格式解码器126将解码和规格化后的字符串字段存入解码字段存储器128中去。

所述投影器130将解码后的字段投影到一个或多个影子空间，并把影子数据存储到影子字段存储器132中去。例如，一个特征码数据库可以包含不区分大小写的特征码。为了支持不区分大小写的特征码，所述投影器130将解码字段存储器128中的数据转换成全小写，并把全小写字符串字段存储到影子字段存储器132中去。全小写字符串字段可被指纹扫描引擎140用来进行指纹扫描。区分大小写的特征码和不区分大小写的特征码就可以同时进行扫描。区分大小写的特征码的匹配可以在其影子匹配后，再用区分大小写的解码后的字段来验证。

在一个实施例中，快速字符串特征码扫描引擎100包括可支持对整个字符串字段进行字符串特征码扫描的计算资源或网络设备。然而，在另一个实施例中，快速字符串特征码扫描引擎100包括无法存储整个字符串字段的计算资源或网络设备，由于例如受系统的存储空间限制和低时延要求。因此，所述字符串字段可以被分解成多个预定大小的字符串块。字符串特征码的扫描在每个预定大小的字符串块上进行。

在一个实施例中，一个字符串块的大小取决于最长字符串特征码。所述字符串块可以进一步分成三个区域：一个指纹扫描区域以覆盖所有特征码扫描位置，一个前于指纹扫描区域的区域以提供指纹之前或之中的参考数据，一个后于指纹扫描区域的区域以提供指纹之后或之中的参考数据。特定字符串字段的所有的指纹扫描区域的集合覆盖了在所述字符串字段中的所有可能的指纹起始位置。所述三个区域的大小可以相同或不同。在一个实施例中，前于指纹扫描区域的区域的最小尺寸为特征码数据库中所有特征码的最大指纹错位，后于指纹扫描区域的区域的最小尺寸为特征码数据库中所有特征码的长度和错位的最大差值，指纹扫描区域的最小尺寸为扫描步长。

在一个实施例中，所述扫描字符串块的大小可以根据所述扫描系统的参数，例如，最长的特征码的长度，内存结构，和扫描速度来选择。当最长的特征码较长时，扫描字符串块可为最长的特征码的长度的几倍，例如，2至4倍。当最长的特征码较短时，扫描字符串块可为最长的特征码的长度的更多倍。

在一个实施例中，扫描字符串块的三个区域的大小相同，都等于最长的特征码的长度。所述三个区域可以存储在以三块内存构成的环中，以减少数据在内存中的移动。在另一个实施例中，所述三个区域的大小不同，指纹扫描区域比其它两个区域小，其它两个区域的大小可以相同或不同。

在一个实施例中，一个扫描块的所述三个区域的每个区域可以被存储在一个或多个同样大小的内存块中，所有三个区域的所有内存块构成一个从前于指纹扫描区域的区域的第一个内存块开始，到后于指纹扫描区域的区域的最后一个内存块结束的环，以减少数据在内存中的移动。在扫描完指纹扫描区域的第一内存块以后，所述环的第一个内存块将退出所述环，可以用来加载新数据。在加载新的数据后，所述内存块将作为最后一个内存块加入所述环。在一个实施例中，一个或多个附加内存块可以加入所述环的环尾，以供加载新的数据。

在一个实施例中，所述字符串字段存储器124仅包括最后一个内存块。因此，所述字符串字段存储器124的大小等于一个内存块的大小。所述解码字段存储器128和所述影子字段存储器132包括所有三个区域的所有内存块，其大小为所有内存块大小之和。

由于边界条件，所述第一块和最后一块存在特殊条件。在一个实施例中，长度为最长特征码的长度的“不可能”基本单元可被填充到所述指纹扫描区域的所述前参考区域的第一块之前和所述指纹扫描区域的后参考区域的最后一块之后。“不可能”基本单元包括没有特征码以其开始或结尾的基本单元，因此，所述填充的区域不可能成为一个实际的特征码的一部分。如果指纹扫描引擎140，定长特征码查找引擎160，和不定长特征码查找引擎180中有扫描范围检查机制，所述填充就不需要。扫描范围检查机制可以防止扫描超出字符串字段的边界。

指纹扫描

在一个实施例中，所述指纹扫描引擎140可以包含一个或多个内容寻址存储器(CAM)和一个或多个有限自动机(FA)中的一个或多个。在另一个实施例中，当原始指纹或指纹在一个影子空间的影子为完全指明时，所述指纹扫描引擎140可为基于散列的引擎。如图1A所示，在一个实施例中，所述指纹扫描引擎140包含一个指纹扫描控制器142，一个指纹散列计算器144，一个指纹查找器146，一个指纹数据库148，和一个指纹合成器150。在一个实施例中，一个指纹作为一整体来扫描，因此，所述指纹合成器150为可选组件。

在另一个实施例中，每个指纹被分解成多段被独立扫描。所有的指纹段可以先被扫描，然后再被串行或并行合成(如使用指纹合成器150)以产生指纹的扫描结果。在一个实施例中，所述指纹扫描控制器142控制整个扫描过程。

所述指纹扫描引擎140可输出一个没有匹配项或与指纹数据库中的一项匹配的结果。所述匹配项对应于一个或多个可以随后由定长特征码查找引擎160和不定长特征码查找引擎180来查找的字符串特征码。如果没有匹配项，扫描过程就完成。

在一个实施例中，所述指纹散列计算器144包括多个独立的通用散列函数，h₀，h₁，…，h_I，以支持布隆过滤器。例如，当内存的大小而不是内存的带宽受限制时，可用布隆过滤器。例如，当扫描系统的特征码数据库足够小，可以全部存入片上存储器时，其内存的大小受限制。在另一个实施例中，所述指纹散列计算器144包括多个独立的通用散列函数，h₀，h₁，…，h_I，以支持多个散列表。例如，当假阳性匹配需要非常低(如10^-3或更小)，内存的带宽足够宽且大小足够大时，可以使用多个散列表。例如，当DRAM或其它较慢的片外存储器用来存储后续扫描阶段的数据结构，且片上存储器足够存储多个散列表时，希望假阳性匹配非常低。

在另一个实施例中，所述指纹散列计算器144仅包括一个散列函数h₀。例如，当内存的带宽而不是内存的大小受限制时，可以使用一个散列表。例如，当扫描系统的特征码数据库足够大，从而必须使用片外存储器时，内存的带宽受限制。

所述指纹散列计算器144从所述影子字段存储器132提取n个字节的数据，并计算其散列值。所述数据可以单独或与随机初始值或前散列值一起用来计算所有散列函数的当前散列值。在一个实施例中，其中一个散列函数(例如，第一个散列函数h₀)的散列值的比特位数比其它散列函数的散列值的比特位数更多，而其它散列函数的散列值的比特位数相同。

散列函数输出的散列值可以被指纹查找器146用来查找指纹数据库148。在一个实施例中，所述指纹查找器146包括一个布隆过滤器和一个散列值解复用器。所述布隆过滤器检查所述散列值所指向的有效标志。如果所有有效标志都有效，散列值解复用器进一步根据散列值的额外比特查找出一个相应的散列块。所述散列值解复用就是检查特定散列值的额外比特，散列值解复用可以单独进行或与检查指纹长度和其它与指纹相关的信息同时进行。散列解复用可以进一步降低假阳性特征码匹配的结果。在一个实施例中，所述布隆过滤器可缩为一个散列表。在另一个实施例中，所述布隆过滤器可扩为多个散列表。

不同长度的指纹可以被并行扫描或串行扫描。在一个实施例中，多个指纹查找器146可以同时用来进行并行扫描。例如，一个指纹查找器146可以用来扫描每一个不同长度的指纹。

在另一个实施例中，一个指纹查找器146能对不同长度的指纹进行串行扫描。例如，指纹的长度可以是扫描步长的整倍数。每个快速字符串特征码扫描引擎100支持一组指纹长度，{S，2*S，3*S，…，m*S}，其中S是扫描步长和m*S是最长指纹的长度。在每个扫描位置上，不同长度的指纹被串行扫描。一个输入S基本单元的顺序散列函数可以被用来进行所述扫描。在一个实施例中，所述指纹扫描引擎140的串行指纹扫描可以用以下伪代码描述：

其中S是扫描步长，m*S是最长的指纹长度，t是待扫描的字符串字段的总长度，IV是初始散列值，和散列函数()是一个顺序散列函数。指纹查找()用指纹查找器146和指纹合成器150来实现，特征码查找()用定长特征码查找引擎160和不定长特征码查找引擎180来实现。

图2A-C演示了一个当不同长度的指纹作为一个整体进行扫描时的指纹数据库148的数据结构，其中包括一个布隆过滤器表200，一个指纹散列块链表250，和一个散列条目块256块。用指纹散列计算器144所给的一组散列值，{散列值_0A，散列值₁，...，散列值_I}，指纹查找器146去读所述布隆过滤器表200。所述布隆过滤器表200的每项包含一个有效标志202和一个散列块链表指针204。有效标志202是当输入存在至少一个特征码时设置的标志。

在一个实施例中，散列块链表指针204仅被散列值_0A所指，并指向指纹散列块链表250的首项。如果所有散列值所指的有效标志202都被设置，进一步指纹扫描可在散列块链表指针204所指的指纹散列块链表250上进行。在另一个实施例中，散列块链表指针204等于散列值_0A，可以被省略，以减小布隆过滤器表或散列表，其代价为增大其后扫描阶段的数据结构。

在一个实施例中，散列值_0A被用来把指纹加入到布隆过滤器表200中去，而其它散列值可用来减少假阳性匹配。此外，为了不误删字符串特征码，布隆过滤器表200的每一项用一个计数器来跟踪其特征码的数目。在另一个实施例中，所述布隆过滤器表200可以缩为一个散列表，只需一个散列值(如散列值_0A)。在另一个实施例中，所述布隆过滤器表200可以扩为多个散列表。

在一个实施例中，所述指纹散列块链表250为一个链表。指纹散列块链表250的每一项包括一个末块252，一个下一块指针254，和一个散列条目块256。下一块指针254指向所述指纹散列块链表250的下一项。当所述指纹散列块链表250的一项为尾项时，末块252将被设置。因为尾项还可以通过查看下一块指针254是否为空指针而知，末块252是一个用来快速检测出尾项的可选域。每个散列条目块256包括最多n个指纹，其中n是任何大于零的整数。在一个实施例中，一个最佳的n可以根据扫描系统的内存架构来选择。例如，如果内存为SRAM，n可以等于1；如果内存为DRAM，n>1。

在一个实施例中，如图2C所示，所述散列条目块256的每一指纹项包括一个散列值(散列值_0B)260，一个指纹长度262，一个类型264，一个特征码群指针266或特征码指针268，和一个错位270。散列值_0B260和指纹长度262分别用来实现散列值复用和指纹长度复用。当类型264为零时，将为一个特征码群输出一个特征码群指针266；否则，将为一个特征码输出一个特征码指针268。错位270为指纹的第一个基本单元到下一个待比较的子段的第一个基本单元的错位。如果没有下一个数据结构，就不需错位270。当不需错位270时，错位270可以被设为零。在另一个实施例中，当n>1时，每个指纹项可以增加一个有效标志。当所述有效标志被设置时，可比较散列值_0B260和指纹长度262。

在一个实施例中，散列条目块256的每一指纹项存储一个指纹。然而，在另一个实施例中，因为指纹可以很长，大小又不同，而且因为指纹数据库查找之后有其它特征码查找阶段，原始指纹可以不被存储在每一指纹项中。因此，每一个匹配的指纹项可能由于假阳性匹配对应于零个指纹，或由于指纹碰撞对应于多个指纹。当用一个简单的散列表而不是一个布隆过滤器表来扫描指纹且(k/2^m)<<1时，假阳性匹配的概率的数量级为(k/2^m)和指纹碰撞的概率的数量级为(k²/2^2m)，其中k是在总指纹数和m是包括散列值_0A和散列值_0B的散列值₀的总位数。

当用一个布隆过滤器表时，以上两个概率将大幅下降。当用多个散列表时，所述两个概率将进一步下降。为了尽量减少后阶段特征码查找，假阳性匹配和指纹碰撞的概率可以减少至接近零。在一个实施例中，足够大的m和散列函数的数目可以用来减少假阳性匹配和指纹碰撞的概率。

为了减少存储空间，在一个实施例中，多个散列值可以复用到一个指纹项，以减少空项的概率。每个m位的散列值可以分为两个部分：m1位的散列值₁和(m-m1)位的散列值₂。散列值₁用来作为指纹数据库的地址，而散列值₂(如散列值_0B260)可用来解决散列碰撞和假阳性匹配。m1越小，所需的存储空间越少，但指纹散列块链表250就越长。在一个实施例中，当2^m1大大于两倍或更多倍的k时，指纹散列块列表的平均长度小于1。

为了节省存储空间和降低所述表的管理的复杂性，在另一个实施例中，所有不同长度的指纹可以复用到一个指纹数据库。指纹长度262可以进一步减少假阳性匹配和指纹碰撞的概率。

如图2A-C所示的查找数据结构可以用几种不同的方式实施。特定实施可以根据特征码表的大小，可用内存的大小和类型，如片上SRAM，片上DRAM，片外SRAM和片外DRAM而定。例如，在一个实施例中，如果特征码数目为128K，所述有效标志202可以存放在一个片上SRAM以实现快速访问，而散列块链表指针204则存放在一个片外SRAM中。有效标志202可用所有散列值访问，而散列块链表指针204仅可用散列值_0A访问。仅当所有散列值的有效标志202都为有效时，才需访问散列块链表指针204。末块252和下一块指针254可以存放在一个片外SRAM中，散列值_0B260和指纹长度262可以存放在一个片外SRAM或DRAM中，类型264，特征码群指针266或特征码指针268，和错位270可以存放在一个片外DRAM中。仅当散列值_0B260和指纹长度262匹配时，才需访问类型264，特征码群指针266或特征码指针268，和错位270。

在一个实施例中，为了提高扫描效率，一个字符串特征码的指纹可以分解成多个指纹段。可以先对这些指纹段进行并行或串行扫描，然后再用指纹合成器150将匹配的指纹段合成为指纹的扫描结果。因为不同指纹段长度的数目一般远小于不同指纹长度的数目，将指纹分为指纹段来扫描可以加快指纹扫描。将指纹分为指纹段来扫描，使支持更长的含更多指纹段的指纹成为可能，从而减少假阳性匹配。

在一个实施例中，指纹段的合成是精确的或完全的，无假阳性匹配。在另一个实施例中，为了加快指纹扫描，指纹段的合成是“粗糙”的或部分的，有假阳性匹配。为了减少假阳性匹配的概率，每个指纹段的一个或多个可能的位置和指纹的可能长度的信息可以被储存并被用于将指纹段并行或串行合成为任何指纹匹配。

当多个指纹段串行扫描时，“至少一个指纹匹配”的散列条目块和其对应的指纹合成器的一个不同实施例如图2D-E所示。在一个实施例中，只要至少有一个指纹匹配就报告一个匹配，但不能提供有关有多少指纹匹配和匹配的指纹的长度的信息。

如图2D所示，在一个实施例中，散列条目块257的每项包括特定指纹段的一个散列值_0B260，一个指纹段位图272，一个至少一指纹合成信息274，一个类型264，一个特征码群指针266或特征码指针268，和一个错位270。指纹段位图272是一个有效标志位图阵列，其比特位数和所述指纹合成器151所支持的指纹段的数目相同。当指纹段为一个指纹的第i个指纹段，指纹段位图272的第i位将被设置。指纹段位图272给出所述指纹段在所有指纹中的所有可能的位置。至少一指纹合成信息274给出含所述指纹段的指纹的最少段数，用于至少一个指纹段匹配的指纹合成。在一个实施例中，至少一指纹合成信息274被存储在所述指纹的第一个指纹段中。在另一个实施例中，至少一指纹合成信息274或任何其它指纹长度信息被存储在所述指纹的每一个指纹段中。在另一个实施例中，至少一指纹合成信息274被省略。

在一个实施例中，散列值_0B260和图2C中的散列值_0B260相同。类型264，特征码群指针266或特征码指针268，和错位270也和图2C中的对应值相同，被存储在指纹的第一个指纹段中，并在延迟“指纹段数减1”个时钟周期后使用。在一个实施例中，由于类型264，特征码群指针266或特征码指针268，和错位270只存储在指纹的第一个指纹段中，所有第一个指纹段相同的指纹都存储在一起。在一个实施例中，在指纹的选择过程中，要让有相同的第一个指纹段的多个指纹的概率为最小。

图2E演示一个当至少一指纹合成信息274只存储在每个指纹的第一个指纹段时的指纹合成器151的一个实施例。在一个实施例中，指纹段的大小选为和扫描步长相同。例如，指纹段的大小和扫描步长都为4，从而使得指纹的长度为4，8，12，和16。所述指纹合成器151包括12个D触发器280，3个2输入的与门282，和1个4输入的多路选择器284。指纹合成器151的输入为指纹段位图272和至少一指纹合成信息274。如果找到一个指纹，指纹合成器151将输出一个匹配290。所述匹配290仅当一个合成指纹的第一个指纹段是一个指纹的第一个指纹段时有效。

在一个实施例中，为了核实所述匹配290，4输入的多路选择器284可以被一个5输入的多路选择器取代，其中新加的输入端连到零且当指纹段不是第一个指纹段时被选。在一个实施例中，通过在不同的时延阶段增加逻辑门，指纹合成器151可以被扩展，以支持一个指纹的除第一指纹段以外的指纹段的指纹长度信息。在另一个实施例中，当至少一指纹合成信息274没有被存储在任何指纹段中时，指纹合成器151可以通过删除多路选择器284和所有的不用于特征码数据库中的最短的指纹的逻辑门而简化。在另一个实施例中，指纹合成器151可以很容易地修改为用其它扫描步长，指纹段的数目，和指纹长度。在一个实施例中，因为多个指纹匹配被合并为一个“至少一个指纹匹配”的匹配，指纹合成器151可以在每一个时钟周期输出一个指纹扫描的结果。

当多个指纹段串行扫描时，给出所有匹配的“所有指纹匹配”的散列条目块和其对应的指纹合成器的另一个实施例如图2F-G所示。当多个不同长度的指纹作为一个特征码匹配被匹配时，可能需要一个或多个后阶段扫描。

如图2F所示，所述散列条目块258的每一项包括特定指纹段的一个散列值_0B260，一个指纹段位图272，一个所有指纹合成信息276，一个类型264，一个特征码群指针266或特征码指针268，和一个错位270。所有指纹合成信息276是所有匹配的指纹合成信息，其位数和指纹合成器152所支持的指纹段的数目相同。当一个指纹段为有i个指纹段的指纹的一段时，所有指纹合成信息276的第i位将被设置。散列条目块258的其它域和图2D中的对应域相同。在一个实施例中，所述所有指纹合成信息276仅存储在指纹的第一个指纹段中。在另一个实施例中，所述所有指纹合成信息276或任何其它指纹长度信息存储在一个指纹的每一个指纹段中。在另一个实施例中，所述所有指纹合成信息276被省略。

图2G演示一个当所有指纹合成信息276仅存储在每个指纹的第一个指纹段中时的有多个指纹长度的指纹合成器152的一个实施例。所述指纹合成器152用和图2E相同的扫描步长，指纹段大小，和指纹长度。所述指纹合成器152包括16个D触发器280，5个2输入的与门282，和1个3输入的与门286。所述指纹合成器152输出一个匹配0292，一个匹配1294，一个匹配2296，和一个匹配3298，分别与一个，两个，三个，和四个指纹段长的指纹的匹配。

在一个实施例中，通过在不同的时延阶段增加逻辑门(如与门)或增加现有与门的输入，所述指纹合成器152可以被扩展，以支持一个指纹的除第一指纹段以外的指纹段的附加指纹长度信息。在另一个实施例中，当所有指纹合成信息276没有被存储在任何指纹段中时，用于所有指纹合成信息276的与门的输入和所有与指纹长度有关的逻辑门可以被删除，以简化所述指纹合成器152。在一个实施例中，图2F中的散列条目块258可以被扩展，包括多组类型264，特征码群指针266或特征码指针268，和错位270；每组域用于每个指纹长度。此外，在一个实施例中，有关指纹的准确长度的信息也可用于后续扫描阶段。

指纹合成器152可以同时扫描所有不同长度的指纹。但是，由于类型264，特征码群指针266或特征码指针268，和错位270仅存储在一个指纹段中，多个共有所述指纹段的指纹被存储在一起。特征码的指纹的适当选择可以使所述影响降到最低。然而，为了消除所述影响，所有匹配的指纹段的指纹的类型264，特征码群指针266或特征码指针268，和错位270可以被存储到另一个被已匹配的指纹段所指的表中。所有到已匹配的指纹段的地址可以用来查找所述表中的一个条目。

在另一个实施例中，除至少一指纹合成信息274或所有指纹合成信息276以外，指纹段位图272可以进一步被省略，从而没有任何指纹合成信息被存储在任何指纹段中。指纹段就可以根据所述特征码数据库内的所有指纹可能格式来合成。如果多个指纹段满足所有指纹的格式的任何一种格式，就认为一个指纹匹配。对于一种特殊情况，如果多个指纹段满足所有指纹格式的最低要求，就认为一个指纹匹配。

当多个指纹段并行扫描时，“至少一指纹指纹匹配”和“所有指纹匹配”的散列条目块和其对应的指纹合成器的一个不同实施例如图2H-I所示。如图2H所示，所述散列条目块259的每项包括一个散列值_0B260，一个指纹段匹配278，一个类型264，一个特征码群指针266或特征码指针268，和一个错位270。所述指纹段匹配278为指纹段的匹配比特，其它域和图2D中所对应的域相同。所述指纹段匹配278对如图2I所示的所述并行指纹合成器的某个特定的段匹配器(如段匹配器0，段匹配器1，段匹配器2，或段匹配器3)有特定的含义。当指纹段为任何指纹的第i个指纹段，第i个段匹配器的指纹段匹配278将被设置。在一个实施例中，第i个段匹配器仅存储指纹的第i个指纹段，从而指纹段匹配278总被设置，可以省略。在一个实施例中，为了进一步降低假阳性合成，类似至少一指纹合成信息274或所有指纹合成信息276的指纹长度信息可以存储在一个指纹的第一个指纹段或所有指纹段。

图2I演示一个不带指纹长度信息的并行指纹合成器153的一个实施例。所述指纹合成器153包括一个2输入的与门282，一个3输入的与门286，一个4输入的与门288，和一个4输入的或门285。所述指纹合成器153为所有指纹匹配输出一个匹配0292，一个匹配1294，一个匹配2296，和一个匹配3298，和为至少一指纹匹配输出一个匹配290。在一个实施例中，一个总体指纹长度过滤器可以用到匹配0292，匹配1294，匹配2296，匹配3298，和匹配290，以过滤掉不可能的指纹长度。在一个实施例中，通过增加逻辑门，所述指纹合成器153可以被扩展，以支持在每个指纹的第一个指纹段或所有指纹段中存储的指纹长度信息。在一个实施例中，并行指纹段扫描可以用一个等于指纹段长度数倍的长扫描步长，以加快扫描速度。

一般来说，在一个实施例中，每个定长特征码可以被分解成多个片段来进行独立地扫描。像扫描与合成指纹段一样，一个特征码的所有片段可以先被扫描，然后再被串行或并行合。通常，不同特征码段长度的数目，即使不是一，也比不同特征码长度的数目小很多，从而可以加快需要为每一个模式长度进行单独扫描的扫描方法的速度。在一个实施例中，两个或两个以上长度相同的特征码段被并行扫描。

在另一个实施例中，一个或多个散列表和一个或多个布隆过滤器中的一个或多个被用来扫描完全指明的特征码段。在一个实施例中，当至少有一个特征码匹配时，所述指纹合成器150可用来串行或并行地把已识别的特征码段合成为任何特征码匹配。图2D-I所示的数据结构和实施例可以用来合成特征码段。在另一个实施例中，一个或多个有限自动机(FA)和一个或多个内容寻址存储器(CAM)中的一个或多个被用来把已匹配的特征码段合成为任何特征码匹配。

定长特征码扫描

如图1所示，所述定长特征码查找引擎160包括一个特征码搜寻器162，一个特征码核实器164，和一个定长特征码数据库166。特征码搜寻器162可以识别一个可能的定长特征码，一个可能的不定长特征码的定长特征子码，或一个包括多个可能的定长特征码或定长特征子码的特征码家庭。已被特征码搜寻器162识别的可能的定长特征码或特征子码将被特征码核实器164核实。定长特征码数据库166则为特征码搜寻器162和特征码核实器164的数据库。

定长特征码数据库166可以用多种数据结构来实施。在一个实施例中，如图3A-B所示，定长特征码数据库166是一个将多个特征码链表350链接起来以构成特征码群链表300的二维链表。特征码群链表300的每一项包括一个下一码指针302，一个错位304，和一个特征码指针306。下一码指针302是一个指向特征码群链表300的下一项的指针，特征码指针306是一个指向特定特征码链表350的指针。错位304为从特定指纹的第一单元到特征码指针306所指的特定字符串特征码的第一单元的错位。

每个定长特征码或特征子码可以被分解为多个特征码段352，以形成特征码链表350。所述特征码段352可以从一个定长特征码或特征子码的第一基本单元开始，按扫描顺序连接起来。在一个实施例中，所述特征码段的尺寸不同。在另一个实施例中，所有所述特征码段的尺寸相同，其尺寸可以根据系统架构最佳地选择。特征码链表350的每一项包括一个特征码段352，一个特征码段膜354，一个末段356，一个下一段指针358，一个类型360，和一个编号362。下一段指针358是一个指向下一段的指针，末段356是末段标志。当类型360为0时，编号362为定长特征子码编号364；否则，编号362为特征码编号366。特征码段膜354用于指定每个基本单元或甚至亚基本单元的特定匹配条件，包括“不用匹配”，“相等”，“不相等”，“在一个范围内”，“在一个范围外”，“不区分大小写”，和“区分大小写”。所述匹配条件可以通过选择单元比较器的输入源和输出源来实现。如果一个定长特征码或特征子码不是特征码段352的尺寸的整数倍，可以在所述定长特征码或特征子码的尾部填以最多达“特征码段352的尺寸减一”个“0”或其它值，并将对应的填充单元的膜设置为“不用匹配”。

在一个实施例中，每个基本单元的特征码段膜354为3个比特位。“不区分大小写”时，第一比特位设置为0；“区分大小写”时，第一比特位设置为1。“相等”时后两个比特位设置为0，“不相等”时后两个比特位设置为1，“不用匹配”时后两个比特位设置为2，后两个比特位为3被保留。更多的膜比特位可以根据需要用来实现其它匹配条件，例如，预先定义的范围(数字字符或字母字符)，符号类，或任意范围。在另一个实施例中，为了提高存储效率，一个或多个特征码段或定长特征码或特征子码的码膜可以单独使用，或与基本单元或亚基本单元的码膜配合所用。

在一个实施例中，所述特征码搜寻器162可以查找特征码群链表300直到所述链表的尾项，即下一码指针302为空指针。特征码群链表300的每一项都返回一个指向一个特征码链表350的特征码指针306。

所述特征码核实器164可以验证为每个特征码链表350进行特征码验证。特征码核实器164从特征码链表350的第一段开始，按扫描顺序逐段检查每个特征码段。如果不匹配，特征码核实器164将停止下段检查；否则，特征码核实器164将检查整个特征码链表350直到其尾，即末段356为1。如果找到一个匹配，当类型为0时，匹配为不定长特征码的定长子码，特征码核实器164将输出一个定长特征子码编号364；当类型为1时，匹配为定长特征码，特征码核实器164将输出一个定长特征码编号366。

在另一个实施例中，为了使假阳性匹配随段数的增长迅速地降到零，特征码段352可按一最佳顺序链结在一起。代表当前特征码段到下一特征码段的错位将被加到特征码链表350的每一项中去。虽然特征码段的长度可以不相同，一个固定的特征码段的长度可被选择。

图4A-B演示了一个特征码单元比较器400和一个特征码段比较器450的一个实施例的方框图。所述特征码单元比较器400在定长特征码查找中进行单元比较。特征码单元比较器400包括一个码膜解码器402，一个2输入多路选择器404，一个相等比较器406，两个非门408，一个4输入多路选择器410，一个2输入或门412，和一个范围比较器414。码膜解码器402可把码膜比特解码为相等比较器406和范围比较器414的输入和输出的控制信号。在一个实施例中，范围比较器414可选地用来支持预定义的每个字符串字段的全局范围或每个特征码的全局范围。在一个实施例中，m个范围比较器414可以用来支持m个预定义的全局范围。在另一个实施例中，一个单元匹配416可以在与“不用匹配”比特逻辑或之后被输出。

多个特征码单元比较器400和一个多输入与门452可用来构建特征码段比较器450。特征码段比较器450的数据单元通常是一个字节，但也可为四个比特或任何其它尺寸。在另一个实施例中，特征码单元比较器400可以被如图4C所示的一个特征码单元比较器480取代，以支持特征码单元本地范围。所述特征码段352中的每一个带码膜的单元可以扩展为一个带码膜的单元范围，或一个带码膜的给定特征码单元的上界和下界的单元对。

在一个实施例中，图1A所示的定长特征码查找引擎160可能需要查找多个特征码链表。然而，需要查找多个特征码链表的概率通常非常低。当需要查找多个特征码链表时，可使用把一群特征码中的多个特征码进行相互编码的差分编码。

例如，在一个实施例中，如图5A所示的选择字符串单元树500可以作为图1A所示的特征码搜寻器162的查找数据结构。选择字符串单元树500包括树节520a-520e。选择字符串单元树500的每个树节520有两个树枝，一个匹配树枝被指针₁530所指，另一个不匹配树枝被指针₂532所指。如图5B所示，选择字符串单元树500有两种不同的树节520：类型528为1的树叶和类型528为0的非树叶。匹配的非树叶总指向另一个树节520，不匹配的非树叶指向树上的另一个树节520或空节。匹配的树叶总指向一个如图5C所示的特征码家庭链表550，不匹配的树叶指向树上的另一个树节520或空节。

在一个实施例中，如图5B所示，选择字符串单元树500的每个树节520包括一个错位522，一个单元524，一个单元膜526，一个类型528，一个指针₁530，和一个指针₂532。类型528包括如上所述树叶和非树叶。所选的单元524可以在特征码的任何位置，当树节520不是树根时，其位置由前一个树节520的错位522给出(例如，节点520b的前节点是节点520a，但是因为节点520a是选择字符串单元树500的树根，所以520a没有前节点)，当树节520是树根(例如，节点520a)时，其位置由指纹散列块链表250(见图2B)中的匹配项的错位270给出。每个树节包括一个与特征码链表350中的特征码段膜354(见图3B)相对应的单元膜526。

任何两个字符串特征码至少有一个基本单元不同，只要其中一个字符串特征码不是另一个字符串特征码的子段。因此，一个单元524可以被选来区分至少两个字符串特征码，从而使得在比较所述单元524后，至少有一个字符串特征码可以被淘汰掉。通过对选择字符串单元树500的查找，至少有一个基本单元不同的特征码可以被区分。在一个实施例中，所示的选择字符串单元树500为二分树。在另一个实施例中，可以构建对应的选择字符串单元k分树。一个特征码群中的k个特征码在同一基本单元位置上的k个基本单元可以作为k分树的一个树节，尽管每个特征码还可以贡献多个基本单元到k分树的每个树节中去。

在一个实施例中，一个字符串特征码可以是另一个字符串特征码的一部分。这些有母子关系的特征码不能被选择字符串单元树500区分。在一个实施例中，只要找到其中的任何一个特征码，就不需进一步查找，没有必要区分有母子关系的特征码。因此，只需扫描其中最短的特征码。但是，在另一个实施例中，需要区分所有的特征码或需要识别最长的特征码。

为了支持有母子关系的特征码家庭，在一个实施例中，一个如图5C所示的特征码家庭链表550可以为特征码核实器164的查找数据结构(见图1A)。特征码家庭链表550的每一项包括一个类型552，一个错位554，一个特征码段556，一个特征码段膜558，一个下一项指针560，一个编号类型562，和一个编号564。在一个实施例中，为了支持特征码家庭，特征码家庭链表550有两个种项：类型552为0的查找项和类型552为1的结果项。在检查每一个查找项时，特征码段556将根据特征码段膜558被比较。特征码段556和特征码段膜558与特征码链表350中的对应域相同(见图3B)。但是，结果项不需任何特征码段比较。

在一个实施例中，所述系统查找所有匹配的特征码，并输出每一个匹配的特征码的编号564。然而，特征码的查找将一直继续到特征码家庭链表550的尾部或下一项指针560为空指针，以找到所有的母特征码。编号564有两种：特征子码编号566和特征码编号568。编号564的类型由编号类型562而定。当编号类型562为0时，编号564是特征子码编号566，代表一个不定长特征码的定长特征子码；否则，编号564是特征码编号568，代表一个定长特征码。

在一个实施例中，特征码家庭链表550的从最年轻的一代或最短的子码开始，一直连接到最老的一代或最长的子码。错位554指定从现特征码段556的第一单元到下特征码段556的第一单元的错位。如果现特征码段不匹配，特征码家庭链表550的查找可停止。给出定特征子码之间的任意错位554使基于不匹配的提前终止成为可能。

在一个实施例中，特征码家庭链表550的每一代只能支持一个特征码。如果一特定代有多个特征码，可以用多个特征码家庭链表550，所述特定代的每一个特征码需要一个特征码家庭链表550。多个特征码家庭链表550可以用选择字符串单元树500来区分。

在另一个实施例中，带码膜的特征码可以用一个或多个存储器包括一个内容寻址存储器(CAM)来存储和扫描。

不定长特征码扫描

如图1所示，所述定长特征码查找引擎160按扫描顺序输出所有匹配的不定长特征码的定长特征子码的编号，尺寸，在所述字符串字段内的位置。用已识别的定长特征子码的信息，不定长特征码查找引擎180把已识别的定长特征子码合成为任何不定长特征码。在一个实施例中，一个或多个有限自动机(FA)被用来合成定长特征子码。在另一个实施例中，不定长特征码查找引擎180包括一个特征码规则查找器182，一个特征码状态验证器184，一个特征码合成规则数据库186，和一个特征码状态表格188。特征码规则数据库186给出如何将不定长特征码的定长特征子码合成为不定长特征码的静态规则。特征码状态表格188动态地为一个输入字符串字段存储合成的进程的状态。

特征码规则查找器182从特征码规则数据库186中查找出与已匹配的定长特征子码编号相关的规则，并将所述相关的特征码规则提供给特征码状态验证器184。特征码状态验证器184根据特征码合成规则将已匹配的定长特征子码合成为不定长特征码，并更新特征码状态表格188。

特征码规则数据库186和特征码状态表格188可有各种不同的数据结构。在一个实施例中，特征码规则数据库186可以为如图6所示的特征码规则链表600。特征码规则链表600被定长特征码查找引擎160找到的特征子码的编号所指向。多个不定长特征码可包含相同的定长特征子码。特征码规则链表600可将所有包含特定特征子码编号所代表的定长特征子码的不定长特征码连接在一起。

在一个实施例中，特征码规则链表600的每一项对应一个不定长特征码。每一项包含一个特征码编号602，一个顺序604，一个末码606，一个下一码指针608，和一个距离范围信息610。特征码编号602代表特定不定长特征码。顺序604为所述特征子码编号所代表的定长特征子码在所述不定长特征码的所有定长特征子码中的顺序。末码606指明所述定长特征子码是否为不定长特征码的最后一个定长特征子码。末码606指明不定长特征码扫描的结束。下一码指针608指向600的下一项。距离范围信息610为指明该所述定长特征子码和下定长特征子码的距离范围(即两定长特征子码之间的最少和最多单元数)的可选域。例如，当所述范围或最长距离或最短距离已预先给定或为无限大时，距离范围信息610可以被省略或简化为最短距离或最长距离。

在另一个实施例中，特征码规则链表600的每一项可以包括一个或多个附加域，以描述一个或多个在两个或多个定长特征子码之间的不定长特征子码。例如，可以用一个“模式”或一个“模式的指针”把一个用来填补距离范围信息610的重复的一个“模式”加到特征码规则链表600的每一项中去，以描述不定长特征子码。

如图7所示，在一个实施例中，特征码状态表格188可以用一个或多个特征码状态链表700来实施。每个特征码状态链表700可以为特定连线的一个字符串字段，动态存储已识别的所有不定长特征码的所有定长特征子码的特征码状态。特征码状态链表700的每一项包括一个特征码编号702，一个前一子码顺序(lorder)704，一个下一子码位置706(nloc)，和一个下一码指针708(nptr)。特征码编号702为特定不定长特征码的编号。前一子码顺序704是所述特定不定长特征码的前一个定长特征子码的编号所给的特定定长特征子码的顺序。下一子码位置706是所述特定不定长特征码的下一个定长特征子码的编号所给的一个定长特征子码的有效位置范围。

在一个实施例中，每一连线的每一字符串字段有一个特征码状态链表700。通常，在每一时刻，每一连线只有一个字符串字段被扫描，只有一个特征码状态链表700。特征码状态链表700可包括特定连线的一个字符串字段的所有不定长特征码的所有已匹配的子码的整个有效历史。

特征码状态链表700可以是动态的。在一个实施例中，如果所述定长特征子码的编号所指的定长特征子码为一个不定长特征码的第一个定长特征子码，即其顺序604为1，且还没有所述特定不定长特征码的项，一个新项可被加入到特定连线的一个字符串字段的特征码状态链表700中去。如果现匹配的定长特征子码的第一个单元的位置不在下一子码位置706所给的有效的范围内或超时发生，所述特征码状态链表700的一项可以被删除。所述特征码状态链表700的一项也可以在找到基于所述项的一个匹配的不定长特征码之后被删除。在一个实施例中，特定连线的一个字符串字段的特征码状态链表700的所有项可以在一个字符串字段的末尾被删除。

如图1和图6所示，在一个实施例中，所述特征码规则查找器182从所述定长特征码查找引擎160接收一个定长特征子码的编号。所述特征码规则查找器182查找整个所述定长特征子码的编号所指的特征码规则链表600，并将所述特征码规则链表600的每一项所给的信息(如{特征码编号602，顺序604，末码606，距离范围信息610})和所述定长特征码查找引擎160所给的信息(如{定长特征子码的第一单元的位置，定长特征子码的长度，连线编号，字符串字段编号})一起依次送到特征码状态验证器184中去，一直到达所述特征码规则链表600的尾部(即下一码指针608为空指针)。

所述特征码状态验证器184用所述特征码规则查找器182所给的每一项的信息查找所述连线编号所指的特征码状态链表700。对特征码状态链表700的每一项，如果特征码编号602和特征码编号702相同，顺序604等于前一子码顺序704加一，且定长特征子码的第一个基本单元的位置在下一子码位置706所给的有效标志置范围内，就为一个匹配。对特征码状态链表700的每一匹配项，如果末码606为1，输出所述特征码编号602，并将所述项从特征码状态链表700中删除；否则，所述项被更新，让前一子码顺序的值704等于顺序604的值，下一子码位置706的值等于定长特征子码的第一个单元的位置，定长特征子码的长度，和距离范围信息610的值的总和。不需对不匹配的项做任何事。

在一个实施例中，当特征码状态链表700短且特定连线在特定时刻仅需扫描一个字符串字段，可以用所述特征码状态链表700来扫描。但是，如果特征码状态链表700长或特定连线在特定时刻需扫描多个字符串字段，其它查找数据结构可用于所述特征码状态表格188。在一个实施例中，所述特征码状态表格188可以是类似于图2A-C中的数据结构的一个特征码状态布隆过滤器或一个特征码状态散列表。特征码状态布隆过滤器或特征码状态散列表的散列键可以为3元组{连线编号，字符串字段编号，特征码编号}。在一个实施例中，当每一连线在特定时刻仅有一字符串字段被扫描，不需用字符串字段编号。

如图8所示，在一个实施例中，图2A-C中的散列条目块256可以被散列条目块856取代。散列条目块856的每一项包括特一个征码编号860，一个连线编号862，一个字符串字段编号864，一个前一子码顺序866，和一个下一子码位置868。前一子码顺序866和下一子码位置868的定义和所述图7中的前一子码顺序704和下一子码位置706的定义相同，散列键3元组{特征码编号860，连线编号862，字符串字段编号864}可被储存并被用来解决散列碰撞。对散列条目块856的每一项，如果原散列键相同，顺序604等于前一子码顺序866加一，且定长特征子码的第一单元的位置在下一子码位置868所给的有效位置范围之内，就为一个匹配。对散列条目块856的每一匹配项，如果末码606为1，输出所述特征码编号602，并将所述项从散列条目块856中删除；如果末码606为0，所述散列条目块856的项被更新，让前一子码顺序866等于顺序604，下一子码位置868等于定长特征子码的第一单元的位置，定长特征子码的长度，和距离范围信息610的总和。不匹配项则保持不变。

在一个实施例中，当两个连续的定长特征子码的顺序和距离范围满足特征码规则链表600中的一项或多项，特征码状态验证器184将进一步核实是否所述两个定长特征子码之间的字符串段和特征码规则链表600的一项或多项所指的一个或多个不定长特征子码匹配。当所述特定字符串字段中的在所述两个连续的定长特征子码之间的字符串和所述特征码规则链表600的一项或多项所指的一个不定长特征子码匹配时，所述特征码状态链表700将用所述新的定长特征子码更新。

扫描系统的设计和性能

在一个实施例中，快速字符串特征码扫描引擎100的速度受指纹扫描引擎140的速度限制，例如，当所述假阳性匹配足够小且后续扫描阶段被妥善设计时。当指纹作为一个整体被逐个长度扫描时，指纹扫描引擎140的速度取决于扫描步长，指纹长度的数目，和时钟速度组合。在一个实施例中，所述扫描引擎100的速度为(s/m)*R，其中s为扫描步长，m为指纹长度的数目，和R为时钟速度。例如，如果扫描步长为8字节，指纹长度4，8，16和32字节，时钟频率为500MHz，所述扫描引擎100的速度为8*(8/4)*500MB/s＝8Gbits/s。

在另一个实施例中，如果指纹先分段进行并行扫描，然后再用“至少一指纹匹配”串行合成，且指纹段长度和扫描步长相同，一个单独的扫描引擎100的速度为s*R。在一个实施例中，当s和R都取与前例相同的值时，所述扫描引擎100可以32Gbps速度扫描一个字符串字段。此外，在另一个实施例中，指纹可先分段进行扫描，然后再并行合成，扫描步长从而扫描速度可以进一步提高n倍，其中n是并行扫描和合成的指纹段的数目。当指纹段长和R都取与前例相同的值时，如果n为4，即4个指纹段被并行扫描和合成，扫描步长为32字节，所述扫描引擎100可以128Gbps速度扫描一个字符串字段。

以上讨论的扫描速度是一个单一的特征码扫描引擎的速度。在一个实施例中，当用数个特征码扫描机进行并行扫描时，特征码扫描速度可以进一步提高数倍。

在一个实施例中，一个特征码扫描系统的总体结构和参数的选择可以根据一个或多个以下因素：字符串特征码的扫描速度，定长特征码或不定长特征码的定长特征子码的尺寸，多个特征码或特征子码之间的相似性，和特征码数据库的大小来选择，以确保指纹扫描引擎140，定长特征码查找引擎160，和不定长特征码查找引擎180能满足特定的扫描系统的要求。例如，扫描步长可以根据系统要求来选择。如表1所示，扫描步长越长，快速字符串特征码扫描引擎100的速度就越快。但是，定长特征码或特征子码的最小尺寸就需越大，以及插入和删除的次数就越多。大扫描步长还限制每个特征码的指纹的选择，并增加指纹碰撞和指纹假阳性匹配的概率。

表1:扫描步长的选择

此外，扫描步长从而扫描速度特别会受最小定长特征码或特征子码的尺寸限制。在一个实施例中，为了避免将短特征码分开扫描，扫描步长可以按表1根据定长特征码或特征子码的最小尺寸来选择。

表1假设所有定长特征码和特征子码的每一个基本单元可以用为指纹。在一个实施例中，所有的定长特征码和特征子码至少在一个影子空间是完全指明的。另外，在另一个实施例中，扫描步长从而扫描速度进一步受所有定长特征码和特征子码的完全指明的影子的最小尺寸限制。因此，在表1的第三列标题可以改成“所有的定长特征码或特征子码的完全指明的影子的最小尺寸”。

在另一个实施例中，为了提高扫描速度，可以选择较大的扫描步长。短于所述扫描步长可扫描的特征码可以被另行扫描，例如，用上述扫描方法或任何其它扫描方法。当仅少数定长特征码或特征子码较短，增加扫描步长很有效。

在另一个实施例中，不同扫描流水线阶段的引擎数目可以不同。引擎可以根据所述特定系统的要求来选择。例如，对于特定系统，可以用一个扫描预处理引擎120，四个指纹扫描引擎140，一个定长特征码查找引擎160，和两个不定长特征码查找引擎180。

在一个实施例中，可以用多个指纹扫描引擎140，从而使得每个指纹扫描引擎140覆盖一组指纹长度，以提供多分辨率指纹扫描。在一个实施例中，所有的指纹都被分解成相同长度的指纹段且所有的指纹段都用相同的扫描步长来扫描。用于扫描所有指纹长度组的每组指纹长度的指纹扫描引擎的数目可以都相同。

在另一个实施例中，指纹被分解成不同长度的指纹段，不同长度的指纹段根据一组指纹长度的平均长度被用不同长度的扫描步长来扫描，从而使得一组平均长度较长的指纹长度的指纹用较长的指纹段和较大的扫描步长，一组平均长度较短的指纹长度的指纹用较短的指纹段和较小的扫描步长。例如，8个基本单元的指纹段和扫描步长可以用于长度为8，16，24，32，和40个基本单元的指纹，而2个基本单元的指纹段和扫描步长可以用于长度为2，4，和6个基本单元的指纹。

在一个实施例中，为了平衡用不同扫描步长扫描不同长度的指纹段的指纹扫描引擎140的速度，用较短扫描步长扫描较短指纹段的指纹扫描引擎140的数目可多于用较长扫描步长扫描较长指纹段的指纹扫描引擎140的数目。在另一个实施例中，为了平衡用不同速度的内存的指纹扫描引擎140的速度，用较慢内存的指纹扫描引擎140的数目可多于用较快内存的指纹扫描引擎140的数目。一般来说，在另一个实施例中，指纹扫描引擎140的数目可以由扫描步长和内存速度的乘积而定。较小扫描步长和内存速度的乘积的指纹扫描引擎140的数目可多于较大扫描步长和内存速度的乘积的指纹扫描引擎140的数目。

在一个实施例中，多个扫描步长相同的扫描同一组指纹的指纹扫描引擎140覆盖一输入字符串字段中的多个不重叠的交错的位置，从而使得所述多个指纹扫描引擎的总扫描步长为指纹扫描引擎的数目和原单个指纹扫描引擎的扫描步长的乘积。例如，为了提供相同的扫描速度，扫描步长为2个基本单元的指纹扫描引擎的数目可以是扫描步长为8个基本单元的指纹扫描引擎的数目的4倍。在另一个实施例中，多个扫描步长相同的扫描同一组指纹的指纹扫描引擎140覆盖一输入字符串字段中的多个部分重叠的交错的位置，从而使得所述多个指纹扫描引擎的总扫描步长大于原单个指纹扫描引擎的扫描步长，但比指纹扫描引擎的数目和原单个指纹扫描引擎的扫描步长的乘积小。

在一个实施例中，不同指纹段长度的指纹数据库148可存储在不同速度的内存中，从而使得用于较短的指纹段的内存比用于较长的指纹段的内存快。在一个实施例中，不同指纹长度组所对应的定长特征码数据库166可存储在不同速度的内存中，从而使得用于一组平均长度较短的指纹的内存比用于一组平均长度较长的指纹的内存快。

在一个实施例中，短于特定长度(例如，9个基本单元)的指纹的指纹数据库148可存储在扫描系统的最快的内存(例如，片上存储器或CPU的缓存)之一中。在一个实施例中，短于所述特定长度的指纹所对应的定长特征码数据库166的全部或部分也可和指纹数据库148一起存储在扫描系统的最快的内存之一中。在另一个实施例中，同一指纹组的多个指纹扫描引擎可以共用一个存储在一个多端口的内存中的指纹数据库148。

在一个实施例中，一个或多个以上所讨论的在不同流水线阶段的引擎可以被任何其它扫描方法替换。例如，在一个实施例中，一个内容寻址存储器(CAM)可以作为指纹扫描引擎140被用来扫描指纹的影子，而定长特征码查找引擎160和不定长特征码查找引擎180仍可用来进一步扫描特征码。在另一个实施例中，一个CAM可以作为指纹扫描引擎140被用来在原空间扫描一个或多个指纹。在一个实施例中，一个确定或不确定有限自动机(DFA或NFA)可以作为指纹合成器150被用来合成指纹段。在另一个实施例中，一个DFA或NFA可以作为不定长特征码查找引擎180被用来把定长特征子码合成为不定长特征码。

本发明的其它实施例可以扫描其它字符串数据。例如，在生物系统中，一个遗传代码序列可以作为一个字符串字段。描述特定基因的特征码可以用来从一个由遗传数据组成的字符串字段中识别出所述特定基因序列。例如，特定基因可以用所述扫描机被特定的特征码来识别。

本发明和本说明书所描述的所有功能操作，包括本说明书所描述的结构方法或相当的结构方法，或两者的组合，可以用数字电子电路或用计算机软件，固件，或硬件来实施。本发明可以实施于一个或多个计算机程序产品，即一个或多个储存在一个如一个机器可读的存储设备或一个传播信号的信息载体中，比如一个可编程处理器，一台或者多台计算机的数字处理设备所执行或控制其操作的计算机程序。一个计算机程序(也称为一个程序，软件，应用软件，或代码)可以写为包括编译或解释语言的任何编程语言格式，且可被部署为包括作为一个独立程序或作为一个模块，组件，子程序，或者其它适用于计算环境的单位的任何格式。一个计算机程序并不一定对应一个文件。一个程序可以和其它程序或数据一起存在一个文件中，可以为一个单一问题程序文件，可以为多个协调的文件(例如，存储一个或多个模块，子程序，或部分代码的多个文件)。一个计算机程序可以部署到一台计算机，在同一地点的多台计算机，或分布于多个地点的用通信网络互联的多台计算机上执行。

本说明书所描述处理程序和逻辑流程，包括本发明的方法步骤，可以用执行一个或多个计算机程序的一个或多个可编程处理器来执行，以通过操作输入数据和产生输出来施行本发明的功能。特殊用途的逻辑电路，如现场可编程门阵列(FPGA)或专用集成电路(ASIC)，也可以用来执行所述处理过程和逻辑流程和实施本发明的装置。

适用于执行计算机程序的处理器包括，如一般和特殊用途的微处理器，以及任何种类的数字计算机的任何一个或多个处理器。一般而言，一个处理器将从只读存储器或随机存取存储器或两者收到指令和数据。一台计算机的基本组件是一个用于执行指令的处理器和一个或多个存储指令和数据的存储器。一般来说，一台计算机还包括或有效地耦合到一个或多个用来存储数据的大容量存储设备(如，磁盘，磁光盘或光盘)，以接收，发送，或收发数据。适用于存储计算机程序指令和数据的信息载体包括所有格式的非挥发性存储器，包括如EPROM，EEPROM，快闪(flash)存储器的半导体存储器；如内部硬盘或可移动磁盘的磁盘；磁光盘；和CD-ROM和DVD-ROM光盘等等。处理器和存储器可以被特殊用途的逻辑电路补充或被纳入特殊用途的逻辑电路。

为了提供与用户的互动，本发明可以在一台有显示设备，一个键盘和一个指针设备的计算机上实施。显示设备，如一个阴极射线管(CRT)或液晶显示器(LCD)用来为用户显示信息；键盘和指针设备，如鼠标或轨迹球，则帮用户提供输入到计算机中去。其它类型的设备也可用于提供用户和计算机的互动；例如，计算机提供给用户的反馈可以是任何格式的感觉反馈，例如，视觉反馈，听觉反馈，或触觉反馈；用户输入到计算机的格式也可以为任何格式，包括声学，语音或触觉输入。

本发明可以在一个计算机系统上实施，所述系统包括一个如一个数据服务器的后端组件，或包含一个如一个应用服务器的中间组件(Middleware)，或包含一个如一个具有一个图形用户界面的客户端计算机或通过其用户可以和本发明的实施互动的网络(Web)浏览器的前端组件，或任何这类后端，中间，或前端组件的组合。所述系统的组件可以通过如通信网络的任何格式或媒介的数字数据通信相互连接。通信网络的例子包括本地网(LAN)和广域网(WAN)，如互联网。

本计算系统可以包括客户端和服务器。客户端和服务器通常远离对方，通常通过一个通信网络互动。客户端和服务器的关系产生于分别在各自的计算机上运行的有客户和服务关系的计算程序。

图9演示了一台这样的计算机的一个示例，一个可用于实施或执行本发明的装置或方法的可编程的处理系统(简称系统)910的方框图。所述系统910包括一个处理器920，一个随机存取存储器(RAM)921，一个只读存储器922(如一个如闪存只读存储器的可写只读存储器(ROM))，一个硬盘驱动器控制器923，一个图像控制器931，和一个输入/输出(I/O)的控制器924，并由处理器(CPU)总线925耦合。所述系统910可被预编程如于ROM中，也可以用另一个程序源(如软盘，CD-ROM，或另一台计算机)加载一个程序从而被编程(和被重新编程)。

硬盘驱动器控制器923和硬盘930耦合在一起可用于存储可执行的计算机程序。

输入/输出的控制器924是由一个输入/输出总线926连接到一个输入/输出接口927。输入/输出接口927在串行链路，局域网，无线连接和并行链接等等通信链路上，接收和传输模拟或数字数据(如一组剧照，图片，电影和动画)。

一个显示器928和一个键盘929也连接到输入/输出总线926上。此外，不同的连线(不同的总线)可以用来连接输入/输出接口927，显示器928和键盘929。

本发明以具体实施例的方式进行了描述。其它实施例在所附权利要求书的范围之内。例如，发明的步骤可以用不同的顺序执行，并且仍能达到期望的结果。

Claims (10)

1.一种字符串特征码扫描方法，所述方法用较大的扫描步长扫描一个或多个特征码，短于所述扫描步长可扫描的特征码用不同扫描方法被另行扫描。

2.一种字符串特征码扫描方法，所述方法用较大的扫描步长扫描一个或多个特征码，短于所述扫描步长可扫描的特征码用相同扫描方法但不同扫描步长被另行扫描。

3.一种字符串特征码扫描系统，所述系统包括用较大的扫描步长扫描一个或多个特征码，短于所述扫描步长可扫描的特征码用不同扫描方法被另行扫描的装置。

4.一种字符串特征码扫描系统，所述系统包括用较大的扫描步长扫描一个或多个特征码，短于所述扫描步长可扫描的特征码用相同扫描方法但不同扫描步长被另行扫描的装置。

5.一种字符串特征码扫描方法，所述方法包括：

把多个特征码分为多个特征码组，其中每组特征码包括一个或多个特征码；

识别一个字符串字段中的任何特征码，包括用多组扫描引擎扫描所述字符串字段以查找所述多组特征码，其中每组扫描引擎包括一个或多个相同的用于查找一组特征码的扫描引擎以覆盖一组或多组交错的所述字符串字段的位置，其中不同扫描引擎组的扫描引擎用不同的扫描步长并且扫描步长较短的扫描引擎组的扫描引擎的数目较扫描步长较长的扫描引擎组的扫描引擎的数目多；和

输出所述字符串字段中的任何匹配的特征码。

6.一种字符串特征码扫描系统，所述系统包括：

一个可把多个特征码分为多个特征码组的特征码预处理模块，其中每组特征码包括一个或多个特征码；和

一个可识别一个字符串字段中的任何特征码的特征码扫描模块，所述特征码扫描模块包括多组可扫描所述字符串字段以查找所述多组特征码的扫描引擎，其中每组扫描引擎包括一个或多个相同的用于查找一组特征码的扫描引擎以覆盖一组或多组交错的所述字符串字段的位置，其中不同扫描引擎组的扫描引擎用不同的扫描步长并且扫描步长较短的扫描引擎组的扫描引擎的数目较扫描步长较长的扫描引擎组的扫描引擎的数目多。

7.一种字符串特征码扫描方法，所述方法包括：

把多个特征码分为多个特征码组，其中每组特征码包括一个或多个特征码；

识别一个字符串字段中的任何特征码，包括用多个扫描引擎扫描所述字符串字段以查找所述多组特征码，其中每个扫描引擎用于查找一组特征码，其中不同扫描引擎在一个或多个扫描流水线阶段中使用不同速度的内存；和

输出所述字符串字段中的任何匹配的特征码。

8.一种字符串特征码扫描系统，所述系统包括：

一个可把多个特征码分为多个特征码组的特征码预处理模块，其中每组特征码包括一个或多个特征码；和

一个可识别一个字符串字段中的任何特征码的特征码扫描模块，所述特征码扫描模块包括多个可扫描所述字符串字段以查找所述多组特征码的扫描引擎，其中每个扫描引擎用于查找一组特征码，其中不同扫描引擎在一个或多个扫描流水线阶段中使用不同速度的内存。

9.一种字符串特征码扫描方法，所述方法包括：

把多个特征码分为多个特征码组，其中每组特征码包括一个或多个特征码；

识别一个字符串字段中的任何特征码，包括用多组扫描引擎扫描所述字符串字段以查找所述多组特征码，其中每组扫描引擎包括一个或多个相同的用于查找一组特征码的扫描引擎以覆盖一组或多组交错的所述字符串字段的位置，其中不同扫描引擎组的扫描引擎用不同的扫描步长或在一个或多个扫描流水线阶段中使用不同速度的内存；和

输出所述字符串字段中的任何匹配的特征码。

10.一种字符串特征码扫描系统，所述系统包括：

一个可把多个特征码分为多个特征码组的特征码预处理模块，其中每组特征码包括一个或多个特征码；和

一个可识别一个字符串字段中的任何特征码的特征码扫描模块，所述特征码扫描模块包括多组可扫描所述字符串字段以查找所述多组特征码的扫描引擎，其中每组扫描引擎包括一个或多个相同的用于查找一组特征码的扫描引擎以覆盖一组或多组交错的所述字符串字段的位置，其中不同扫描引擎组的扫描引擎用不同的扫描步长或在一个或多个扫描流水线阶段中使用不同速度的内存。