Method and apparatus for approximate pattern matching

• US 7,636,703 B2
• Filed: 05/02/2006
• Issued: 12/22/2009
• Est. Priority Date: 05/02/2006
• Status: Active Grant

• Current Assignee: Ip Reservoir, LLC
• Original Assignee: Exegy Incorporated
• Inventors: Taylor, David Edward
• Primary Examiner(s): Vincent; David R
• Assistant Examiner(s): COUGHLAN, PETER D
• Application Number:
  US11/381,214
• Publication Number:
  US 20070260602A1
• Time in Patent Office: 1,330 Days
• Field of Search: None
• US Class Current: 706/62
• CPC Class Codes: G16B 30/00 ICT specially adapted for sequence analysis involving nucleotides or amino acids
• CPC Class Codes: H04L 63/0245 Filtering by information in the payload
• CPC Class Codes: H04L 63/1416 Event detection, e.g. attack signature detection
• CPC Class Codes: H04L 63/145 the attack involving the propagation of malware through the network, e.g. viruses, trojans or worms
• CPC Class Codes: H04W 12/71 Hardware identity

Abstract

A system and method for inspecting a data stream for data segments matching one or more patterns each having a predetermined allowable error, which includes filtering a data stream for a plurality of patterns of symbol combinations with a plurality of parallel filter mechanisms, detecting a plurality of potential pattern piece matches, identifying a plurality of potentially matching patterns, reducing the identified plurality of potentially matching patterns to a set of potentially matching patterns with a reduction stage, providing associated data and the reduced set of potentially matching patterns, each having an associated allowable error, to a verification stage, and verifying presence of a pattern match in the data stream from the plurality of patterns of symbol combinations and associated allowable errors with the verification stage.

Claims

1. A method for inspecting a data stream for data segments approximately matching any of a plurality of patterns, the method comprising:

filtering a plurality of data substrings within the data stream with a plurality of parallel filter mechanisms to thereby detect a plurality of potential matches between the data substrings and a plurality of pattern pieces, each pattern piece corresponding to at least one pattern, each data substring comprising a plurality of symbols;

reducing the detected potential matches to a plurality of pattern sets, each pattern set comprising (1) data representative of at least one pattern corresponding to a pattern piece which was a potential match to a data substring, and (2) data representative of an allowable error associated with the at least one pattern;

providing the pattern sets to a verification stage; and

verifying with the verification stage whether a data segment within the data stream is an approximate match to a pattern within a provided pattern set on the basis of the allowable error data within that provided pattern set.

2. The method according to claim 1, further comprising, prior to the filtering step, receiving the data stream from a member of the group consisting of a communication link, a redundant array of independent disks (“

RAID”

), and a storage area network (“

SAN”

).

3. The method according to claim 1, wherein the plurality of parallel filter mechanisms is a member of the group consisting of a set of parallel Bloom filters, a set of parallel Bloom filter arrays and a set of parallel Bloom filter arrays that utilize a single hash key generator.

4. The method according to claim 3, wherein the reducing step further includes performing the following steps with a reduction stage that is in communication with the plurality of parallel filter mechanisms:

utilizing data from the plurality of parallel filter mechanisms to lookup one or more pattern piece identifiers for at least one pattern piece that produced a potential match in the plurality of parallel filter mechanisms;

utilizing the one or more pattern piece identifiers for retrieving at least one pattern identifier; and

utilizing the at least one retrieved pattern identifier for retrieving the data representative of at least one pattern and the data representative of the allowable error associated with the at least one pattern to thereby determine at least a portion of a pattern set.

5. The method according to claim 3, wherein the reducing step further includes performing the following steps with a reduction stage that is in communication with the plurality of parallel filter mechanisms:

utilizing each data sub string that produced a potential match for retrieving at least one pattern identifier; and

utilizing the at least one retrieved pattern identifier for retrieving the data representative of at least one pattern and the data representative of the allowable error associated with the at least one pattern to thereby determine at least a portion of a pattern set.

6. The method according to claim 1, further comprising performing the reducing step with a reduction stage that is in communication with the plurality of parallel filter mechanisms, wherein the plurality of parallel filter mechanisms are implemented on a member of the group consisting of at least one reconfigurable logic device and at least one integrated circuit, and wherein the reduction stage is implemented on a member of the group consisting of at least one reconfigurable logic device and at least one integrated circuit.

7. The method according to claim 1, further comprising performing the reducing step with a reduction stage that is in communication with the plurality of parallel filter mechanisms, wherein the plurality of parallel filter mechanisms are implemented on a member of the group consisting of at least one Field Programmable Gate Array (“

FPGA”

) and at least one Application-Specific Integrated Circuit (“

ASIC”

), and wherein the reduction stage is implemented on a member of the group consisting of at least one Field Programmable Gate Array (“

FPGA”

) and at least one Application-Specific Integrated Circuit (“

ASIC”

).

8. The method according to claim 1, wherein the plurality of parallel filter mechanisms include at least one Bloom filter array that is programmed with the pattern pieces, wherein the at least one Bloom filter array utilizes a single hash key generator for computing hash values that correspond to a bit vector and positions in the bit vector that identify whether a data substring is a potential match with one of the pattern pieces, the bit vector being stored in the Bloom filter array.

9. The method according to claim 1, wherein the reducing step further includes performing the following steps with a reduction stage that is in communication with the plurality of parallel filter mechanisms:

utilizing data from the plurality of parallel filter mechanisms to lookup one or more pattern piece identifiers for at least one pattern piece that produced a potential match in the plurality of parallel filter mechanisms;

utilizing the one or more pattern piece identifiers for retrieving at least one pattern identifier; and

utilizing the at least one retrieved pattern identifier for retrieving the data representative of at least one pattern and the data representative of the allowable error associated with the at least one pattern to thereby determine at least a portion of a pattern set.

10. The method according to claim 9, wherein the reducing step further includes utilizing a first lookup function with a bin index.

11. The method according to claim 10, wherein the bin index is selected from the group consisting of different hash keys and portions of hash keys.

12. The method according to claim 1, wherein the reducing step further includes performing the following steps with a reduction stage that is in communication with the plurality of parallel filter mechanisms:

utilizing each data substring that produced a potential match for retrieving at least one pattern identifier; and

utilizing the at least one retrieved pattern identifier for retrieving the data representative of at least one pattern and the data representative of the allowable error associated with the at least one pattern to thereby determine at least a portion of a pattern set.

13. A system for inspecting a data stream for data segments approximately matching any of a plurality of patterns, the system comprising:

a plurality of parallel filter mechanisms each configured to filter a plurality of data substrings within the data stream to thereby detect a plurality of potential matches between the data substrings and a plurality of pattern pieces, each pattern piece corresponding to at least one pattern, each data substring comprising a plurality of symbols;

a reduction stage configured to reduce the detected potential matches to a plurality of pattern sets, each pattern set comprising (1) data representative of at least one pattern corresponding to a pattern piece which was a potential match to a data substring, and (2) data representative of an allowable error associated with the at least one pattern; and

a verification stage configured to receive the pattern sets and verify whether a data segment within the data stream is an approximate match to a pattern within a received pattern set on the basis of the allowable error data within that received pattern set.

14. The system according to claim 13, further comprising a data stream provider selected as at least one member from the group consisting of a communication link, a redundant array of independent disks (“

RAID”

), and a storage area network (“

SAN”

).

15. The system according to claim 13, wherein the plurality of parallel filter mechanisms is a member of the group consisting of a set of parallel Bloom filters, a set of parallel Bloom filter arrays and a set of parallel Bloom filter arrays that utilize a single hash key generator.

16. The system according to claim 15, wherein the reduction stage is further configured to:

look up, on the basis of data from the plurality of parallel filter mechanisms, one or more pattern piece identifiers for at least one pattern piece that produced a potential match in the plurality of parallel filter mechanisms;

retrieve, on the basis of the one or more looked up pattern piece identifiers, at least one pattern identifier; and

retrieve, on the basis of the at least one retrieved pattern identifier, the data representative of at least one pattern and the data representative of the allowable error associated with the at least one pattern to thereby determine at least a portion of a pattern set.

17. The system according to claim 15, wherein the reduction stage is further configured to:

retrieve, on the basis of each data substring that produced a potential match, at least one pattern identifier; and

retrieve, on the basis of the at least one retrieved pattern identifier, the data representative of at least one pattern and the data representative of the allowable error associated with the at least one pattern to thereby determine at least a portion of a pattern set.

18. The system according to claim 13, wherein the plurality of parallel filter mechanisms are implemented on a member of the group consisting of at least one reconfigurable logic device and at least one integrated circuit, and wherein the reduction stage is implemented on a member of the group consisting of at least one reconfigurable logic device and at least one integrated circuit.

19. The system according to claim 13, wherein the plurality of parallel filter mechanisms are implemented on a member of the group consisting of at least one Field Programmable Gate Array (“

FPGA”

) and at least one Application-Specific Integrated Circuit (“

ASIC”

), and wherein the reduction stage is implemented on a member of the group consisting of at least one Field Programmable Gate Array (“

FPGA”

) and at least one Application-Specific Integrated Circuit (“

ASIC”

).

20. The system according to claim 13, wherein the plurality of parallel filter mechanisms includes at least one Bloom filter array that is programmed with the pattern pieces, wherein the at least one Bloom filter array is configured to utilize a single hash key generator for computing hash values that correspond to (1) a position of a particular Bloom filter in the at least one Bloom filter array and (2) a bit vector stored by the particular Bloom filter, and (3) positions of bits in the bit vector that identify whether a data substring is a potential match with at least one of the pattern pieces.

21. The system according to claim 13, wherein the reduction stage is further configured to:

look up, on the basis of data from the plurality of parallel filter mechanisms, one or more pattern piece identifiers for at least one pattern piece that produced a potential match in the plurality of parallel filter mechanisms;

retrieve, on the basis of the one or more looked up pattern piece identifiers, at least one pattern identifier; and

retrieve, on the basis of the at least one retrieved pattern identifier, the data representative of at least one pattern and the data representative of the allowable error associated with the at least one pattern to thereby determine at least a portion of a pattern set.

22. The system according to claim 21, wherein the reduction stage is further configured to utilize a first lockup function with a bin index.

23. The system according to claim 22, wherein the bin index is selected as a member from the group consisting of different hash keys and portions of hash keys.

24. The system according to claim 13, wherein the reduction stage is further configured to:

retrieve, on the basis of each data substring that produced a potential match, at least one pattern identifier; and

retrieve, on the basis of the at least one retrieved pattern identifier, the data representative of at least one pattern and the data representative of the allowable error associated with the at least one pattern to thereby determine at least a portion of a pattern set.

25. A method for processing a plurality of data substrings within a data string for facilitating a determination as to whether the data string contains an approximate match to any of a plurality of patterns, the data string comprising a plurality of data symbols, the method comprising:

querying a filter circuit with the data sub strings to detect a plurality of potential matches, each potential match representing a potential match between a data substring and a pattern piece, wherein each pattern of a plurality of the patterns comprises a plurality of corresponding pattern pieces, the filter circuit being programmed with the pattern pieces;

applying the detected potential matches to a reduction stage to determine a plurality of pattern sets, each pattern set corresponding to a detected potential match and comprising (1) data representative of a pattern which corresponds to the pattern piece which produced the corresponding potential match, and (2) data representative of an allowable error associated with that pattern; and

delivering the determined pattern sets to an approximate match engine for a determination as to whether at least a portion of the data string is an approximate match to any of the patterns within the delivered pattern sets taking into consideration the allowable error data within the delivered pattern sets.

26. The method according to claim 25 wherein the filter circuit comprises a Bloom filter circuit.

27. The method according to claim 26 further comprising:

determining with the approximate match engine whether any approximate matches exist between the data string portion and the patterns within the delivered pattern sets taking into consideration the allowable error data within the delivered pattern sets.

28. The method according to claim 27 further comprising:

slicing the patterns of at least a plurality of the patterns into a plurality of the pattern pieces; and

programming the Bloom filter circuit with the pattern pieces.

29. The method according to claim 27 further comprising:

performing the querying step and the applying step in a pipelined manner.

30. The method according to claim 29 further comprising:

performing the querying step and the applying step with reconfigurable hardware.

31. The method according to claim 30 further comprising:

performing the determining step with reconfigurable hardware.

32. The method according to claim 29 further comprising:

performing the querying step and the applying step with at least one integrated circuit.

33. The method according to claim 29 wherein the pattern pieces comprise a plurality of pattern pieces of different lengths.

34. The method according to claim 33 wherein the pattern pieces corresponding to the same pattern are non-overlapping with each other.

35. The method according to claim 34 wherein the Bloom filter circuit comprises a plurality of parallel Bloom filter circuits, each of the parallel Bloom filter circuits being programmed with pattern pieces of the same length such that each parallel Bloom filter circuit corresponds to a different pattern piece length than the other parallel Bloom filter circuits, and wherein the querying step comprises simultaneously providing the parallel Bloom filter circuits with a plurality of the data substrings in parallel.

36. The method according to claim 35 wherein the Bloom filter circuit further comprises a shift register for storing at least a portion of the data string, the method further comprising:

streaming the data symbols of the data string through the shift register; and

reading the data substrings for the querying step out of the shift register.

37. The method according to claim 36 wherein the streaming step comprises streaming a plurality of new symbols of the data string into the shift register per cycle, and wherein the reading step comprises reading a plurality of different sub strings for the querying step out of the shift register per cycle.

38. The method according to claim 35 wherein each parallel Bloom filter circuit is configured to store a plurality of bit vectors, each bit vector comprising a plurality of bits, each bit having a value, and wherein the querying step further comprises:

applying each data substring to at least one hash function to generate at least one hash key;

retrieving a bit vector from a parallel Bloom filter circuit based on the at least one generated hash key;

selecting a plurality of bit positions in the retrieved bit vector based on the at least one generated hash key; and

determining whether a potential match exists between that data substring and a pattern piece based on the values of the bits at the selected bit positions.

39. The method according to claim 38 wherein the step of applying each data substring to at least one hash function comprises applying each data substring to a plurality of hash functions to generate a plurality of hash keys, wherein the bit vector retrieving step comprises retrieving a bit vector from a parallel Bloom filter circuit based on a generated hash key, and wherein the bit position selecting step comprises selecting a plurality of bit positions in the retrieved bit vector based on a plurality of the other generated hash keys.

40. The method according to claim 38 wherein the step of applying each data substring to at least one hash function comprises applying each data substring to a single hash function to generate a single hash key, wherein the bit vector retrieving step comprises retrieving a bit vector from a parallel Bloom filter circuit based on a portion of the generated hash key, and wherein the bit position selecting step comprises selecting a plurality of bit positions in the retrieved bit vector based on another portion of the generated hash key.

41. The method according to claim 38 wherein the reduction stage is configured to (1) store a plurality of pattern piece identifiers, each pattern piece identifier being indexed by data produced as a result of the querying step, (2) store a plurality of pattern identifiers, each pattern identifier being indexed by a pattern piece identifier, and (3) store a plurality of pattern set pairs, each pattern set pair being indexed by a pattern identifier, each pattern set pair comprising (a) data representative of a pattern, and (b) data representative of an allowable error associated with that pattern, and wherein the potential match applying step comprises:

retrieving at least one of the stored pattern piece identifiers based on data produced as a result of the querying step;

retrieving at least one of the stored pattern identifiers based on each retrieved pattern piece identifier; and

retrieving at least one of the stored pattern set pairs based on each retrieved pattern identifier, the retrieved at least one pattern set pair defining at least a portion of a pattern set.

42. The method according to claim 41 wherein the pattern piece identifier retrieving step comprises retrieving at least one of the stored pattern piece identifiers based on data corresponding to the at least one generated hash key.

43. The method according to claim 38 wherein the reduction stage is configured to (1) store a plurality of pattern identifiers, each pattern identifier being indexed by a pattern piece, and (2) store a plurality of pattern set pairs, each pattern set pair being indexed by a pattern identifier, each pattern set pair comprising (a) data representative of a pattern, and (b) data representative of an allowable error associated with that pattern, and wherein the potential match applying step comprises:

retrieving at least one of the stored pattern identifiers based on the data substring that produced a potential match; and

retrieving at least one of the stored pattern set pairs based on each retrieved pattern identifier, the retrieved at least one pattern set pair defining at least a portion of a pattern set.

44. The method according to claim 43 wherein the reduction stage comprises a plurality of data structures for storing the pattern identifiers, each data structure corresponding to pattern pieces of the same length such that each data structure also corresponds to a different pattern piece length than the other data structures.

45. The method according to claim 44 wherein the data structures comprise a plurality of hash tables.

46. The method according to claim 44 wherein the data structures comprise a plurality of balanced search trees.

47. The method according to claim 29 wherein the applying step comprises eliminating any potential matches that are false positives.

48. The method according to claim 27 wherein the data representative of an allowable error comprises a predetermined number of allowable errors.

49. The method according to claim 25 wherein the reduction stage is configured to (1) store a plurality of pattern piece identifiers, each pattern piece identifier being indexed by data produced as a result of the querying step, (2) store a plurality of pattern identifiers, each pattern identifier being indexed by a pattern piece identifier, and (3) store a plurality of pattern set pairs, each pattern set pair being indexed by a pattern identifier, each pattern set pair comprising (a) data representative of a pattern, and (b) data representative of an allowable error associated with that pattern, and wherein the potential match applying step comprises:

retrieving at least one of the stored pattern piece identifiers based on data produced as a result of the querying step;

retrieving at least one of the stored pattern identifiers based on each retrieved pattern piece identifier, and

retrieving at least one of the stored pattern set pairs based on each retrieved pattern identifier, the retrieved at least one pattern set pair defining at least a portion of a pattern set.

50. The method according to claim 49 wherein the querying step comprises applying each data substring to at least one hash function to generate at least one hash key, and wherein the pattern piece identifier retrieving step comprises retrieving at least one of the stored pattern piece identifiers based on data corresponding to the at least one generated hash key.

51. The method according to claim 25 wherein the reduction stage is configured to (1) store a plurality of pattern identifiers, each pattern identifier being indexed by a pattern piece, and (2) store a plurality of pattern set pairs, each pattern set pair being indexed by a pattern identifier, each pattern set pair comprising (a) data representative of a pattern, and (b) data representative of an allowable error associated with that pattern, and wherein the potential match applying step comprises:

retrieving at least one of the stored pattern identifiers based on the data substring that produced a potential match; and

retrieving at least one of the stored pattern set pairs based on each retrieved pattern identifier, the retrieved at least one pattern set pair defining at least a portion of a pattern set.

52. The method according to claim 51 wherein the reduction stage comprises a plurality of data structures for storing the pattern identifiers, each data structure corresponding to pattern pieces of the same length such that each data structure also corresponds to a different pattern piece length than the other data structures.

53. The method according to claim 52 wherein the data structures comprise a plurality of hash tables.

54. The method according to claim 52 wherein the data structures comprise a plurality of balanced search trees.

55. The method according to claim 25 wherein the patterns and the data string are representative of text.

56. The method according to claim 25 wherein the allowable error data comprises an edit distance value.

57. A system for processing a plurality of data substrings within a data string for facilitating a determination as to whether the data string contains an approximate match to any of a plurality of patterns, the data string comprising a plurality of data symbols, the system comprising:

a filter circuit configured to be queried by the data substrings to detect a plurality of potential matches, each potential match representing a potential match between a data substring and a pattern piece, wherein each pattern of a plurality of the patterns comprises a plurality of corresponding pattern pieces, the filter circuit being programmed with the pattern pieces; and

a reduction stage in communication with the filter circuit, the reduction stage being configured to (1) process the detected potential matches, (2) determine a plurality of pattern sets in response to the processing, each pattern set corresponding to a potential match and comprising (a) data representative of a pattern which corresponds to the pattern piece which produced the corresponding potential match, and (b) data representative of an allowable error associated with that pattern, and (3) output the determined pattern sets for communication to an approximate match engine for a determination as to whether at least a portion of the data string is an approximate match to any of the patterns within the determined pattern sets taking into consideration the allowable error data within the determined pattern sets.

58. The system according to claim 57 wherein the filter circuit comprises a Bloom filter circuit.

59. The system according to claim 58 further comprising:

an approximate match engine in communication with the reduction stage, the approximate match engine configured to determine whether any approximate matches exist between the data string portion and the patterns within the determined pattern sets taking into consideration the allowable error data within the determined pattern sets.

60. The system according to claim 59 wherein the Bloom filter circuit and the reduction stage are configured to operate in a pipelined manner.

61. The system according to claim 60 wherein the Bloom filter circuit and the reduction stage are implemented with as hardware circuitry.

62. The system according to claim 61 wherein the approximate match engine is implemented with hardware circuitry.

63. The system according to claim 61 wherein the hardware circuitry comprises reconfigurable hardware.

64. The system according to claim 61 wherein the hardware circuitry comprises at least one integrated circuit.

65. The system according to claim 64 wherein the at least one integrated circuit comprises at least one Application Specific Integrated Circuit (“

ASIC”

).

66. The system according to claim 60 wherein the pattern pieces comprise a plurality of pattern pieces of different lengths.

67. The system according to claim 66 wherein the pattern pieces corresponding to the same pattern are non-overlapping with each other.

68. The system according to claim 67 wherein the Bloom filter circuit comprises a plurality of parallel Bloom filter circuits, each of the parallel Bloom filter circuits being programmed with pattern pieces of the same length such that each parallel Bloom filter circuit corresponds to a different pattern piece length than the other parallel Bloom filter circuits, and wherein the Bloom filter circuit is further configured to simultaneously provide the parallel Bloom filter circuits with a plurality of the data sub strings in parallel.

69. The system according to claim 68 wherein the Bloom filter circuit further comprises a shift register for storing at least a portion of the data string, and wherein the Bloom filter circuit is further configured to (1) stream the data symbols of the data string through the shift register and (2) read the data substrings out of the shift register for delivery to the parallel Bloom filter circuits.

70. The system according to claim 69 wherein the Bloom filter circuit is further configured to (1) stream a plurality of new symbols of the data string into the shift register per cycle, and (2) read a plurality of different substrings out of the shift register per cycle for delivery to the parallel Bloom filter circuits.

71. The system according to claim 68 wherein each parallel Bloom filter circuit is configured to store a plurality of bit vectors, each bit vector comprising a plurality of bits, each bit having a value, and wherein the Bloom filter circuit is further configured to (1) apply each data sub string to at least one hash function to generate at least one hash key, (2) retrieve a bit vector from a parallel Bloom filter circuit based on the at least one generated hash key, (3) select a plurality of bit positions in the retrieved bit vector based on the at least one generated hash key, and (4) determine whether a potential match exists between that data substring and a pattern piece based on the values of the bits at the selected bit positions.

72. The system according to claim 71 wherein each parallel Bloom filter circuit is further configured to (1) apply each data sub string to a plurality of hash functions to generate a plurality of hash keys, (2) retrieve a bit vector from a parallel Bloom filter circuit based on a generated hash key, and (3) select a plurality of bit positions in the retrieved bit vector based on a plurality of the other generated hash keys.

73. The system according to claim 71 wherein each parallel Bloom filter circuit is further configured to (1) apply each data sub string to a single hash function to generate a single hash key, (2) retrieve a bit vector from a parallel Bloom filter circuit based on a portion of the generated hash key, and (3) select a plurality of bit positions in the retrieved bit vector based on another portion of the generated hash key.

74. The system according to claim 71 wherein the reduction stage comprises a first table, a second table, and a third table, wherein the first table is configured to store a plurality of pattern piece identifiers, each pattern piece identifier being indexed by data produced by the Bloom filter circuit, wherein the second table is configured to store a plurality of pattern identifiers, each pattern identifier being indexed by a pattern piece identifier, and wherein the third table is further configured to store a plurality of pattern set pairs, each pattern set pair being indexed by a pattern identifier, each pattern set pair comprising (a) data representative of a pattern, and (b) data representative of an allowable error associated with that pattern, and wherein the reduction stage is further configured to (1) retrieve at least one of the stored pattern piece identifiers from the first table based on data produced by the Bloom filter circuit, (2) retrieve at least one of the stored pattern identifiers from the second table based on each retrieved pattern piece identifier, and (3) retrieve at least one of the stored pattern set pairs from the third table based on each retrieved pattern identifier, the at least one retrieved pattern set pair defining at least a portion of a pattern set.

75. The system according to claim 74 wherein the reduction stage is further configured to retrieve at least one of the stored pattern piece identifiers from the first table based on data corresponding to the at least one generated hash key.

76. The system according to claim 71 wherein the reduction stage comprises a first data structure and a second data structure, wherein the first data structure is configured to store a plurality of pattern identifiers, each pattern identifier being indexed by a pattern piece, and wherein the second data structure is configured to store a plurality of pattern set pairs, each pattern set pair being indexed by a pattern identifier, each pattern set pair comprising (a) data representative of a pattern, and (b) data representative of an allowable error associated with that pattern, and wherein the reduction stage is further configured to (1) retrieve at least one of the stored pattern identifiers from the first data structure based on the data substring that produced a potential match, and (2) retrieve at least one of the stored pattern set pairs from the second data structure based on each retrieved pattern identifier, the at least one retrieved pattern set pair defining at least a portion of a pattern set.

77. The system according to claim 76 wherein the first data structure comprises a plurality of the first data structures, each first data structure corresponding to pattern pieces of a different length such that each first data structure also corresponds to a different pattern piece length than the other first data structures.

78. The system according to claim 77 wherein the first and second data structures comprise a plurality of hash tables.

79. The system according to claim 77 wherein the first and second data structures comprise a plurality of balanced search trees.

80. The system according to claim 60 wherein the reduction stage is further configured to eliminate any potential matches that are false positives.

81. The system according to claim 59 wherein the data representative of an allowable error comprises a predetermined number of allowable errors.

82. The system according to claim 57 wherein the reduction stage comprises a first table, a second table, and a third table, wherein the first table is configured to store a plurality of pattern piece identifiers, each pattern piece identifier being indexed by data produced by the filter circuit, wherein the second table is configured to store a plurality of pattern identifiers, each pattern identifier being indexed by a pattern piece identifier, and wherein the third table is further configured to store a plurality of pattern set pairs, each pattern set pair being indexed by a pattern identifier, each pattern set pair comprising (a) data representative of a pattern, and (b) data representative of an allowable error associated with that pattern, and wherein the reduction stage is further configured to (1) retrieve at least one of the stored pattern piece identifiers from the first table based on data produced by the Bloom filter circuit, (2) retrieve at least one of the stored pattern identifiers from the second table based on each retrieved pattern piece identifier, and (3) retrieve at least one of the stored pattern set pairs from the third table based on each retrieved pattern identifier, the at least one retrieved pattern set pair defining at least a portion of a pattern set.

83. The system according to claim 82 wherein the filter circuit is further configured to apply each data substring to at least one hash function to generate at least one hash key, and wherein the reduction stage is further configured to retrieve at least one of the stored pattern piece identifiers from the first table based on data corresponding to the at least one generated hash key.

84. The system according to claim 58 wherein the reduction stage comprises a first data structure and a second data structure, wherein the first data structure is configured to store a plurality of pattern identifiers, each pattern identifier being indexed by a pattern piece, and wherein the second data structure is configured to store a plurality of pattern set pairs, each pattern set pair being indexed by a pattern identifier, each pattern set pair comprising (a) data representative of a pattern, and (b) data representative of an allowable error associated with that pattern, and wherein the reduction stage is further configured to (1) retrieve at least one of the stored pattern identifiers from the first data structure based on the data substring that produced a potential match, and (2) retrieve at least one of the stored pattern set pairs from the second data structure based on each retrieved pattern identifier, the at least one retrieved pattern set pair defining at least a portion of a pattern set.

85. The system according to claim 84 wherein the first data structure comprises a plurality of the first data structures, each first data structure corresponding to pattern pieces of a different length such that each first data structure also corresponds to a different pattern piece length than the other first data structures.

86. The system according to claim 85 wherein the first and second data structures comprise a plurality of hash tables.

87. The system according to claim 85 wherein the first and second data structures comprise a plurality of balanced search trees.

88. The system according to claim 57 wherein the patterns and the data string are representative of text.

89. A method comprising:

electronically processing a sub string of an input string with a filter circuit to find a possible match between the input substring and a substring of a query string, electronically determining an allowable error value with a reduction circuit based at least in part on the possible match; and

electronically delivering the input string and the determined allowable error value to a verification circuit for a determination as to whether the input string is an approximate match to the query string based at least in part on the determined allowable error value.

90. The method according to claim 89 further comprising:

electronically performing an approximate match operation with the verification circuit to determine whether the input string is an approximate match to the query string based at least in part on the determined allowable error value.

91. The method according to claim 89 wherein the filter circuit comprises a reconfigurable hardware circuit.

92. The method according to claim 89 wherein the reduction circuit comprises a reconfigurable hardware circuit.

93. An approximate matching apparatus comprising:

a circuit configured to (1) process a substring of an input string to find a possible match between the input substring and a substring of a query string, (2) determine an allowable error value based at least in part on the possible match, and (3) perform an approximate match operation to determine whether the input string is an approximate match to the query string based at least in part on the determined allowable error value.

94. The apparatus according to claim 93 wherein the circuit comprises a reconfigurable hardware circuit.

95. The apparatus according to claim 93 wherein the circuit comprises a filter circuit, a reduction circuit, and a verification circuit, the filter circuit configured to process a substring of an input string to find a possible match between the input substring and a sub string of a query string, the reduction circuit configured to determine an allowable error value based at least in part on the possible match, and the verification circuit configured to perform an approximate match operation to determine whether the input string is an approximate match to the query string based at least in part on the determined allowable error value.