High speed large scale dictionary matching
First Claim
1. A method, in a data processing system, for dictionary matching, the method comprising:
- loading a plurality of dictionary memory arrays with a set of dictionary words and updating a plurality of status arrays, wherein each status array of the plurality of status arrays corresponds to a respective one of the plurality of dictionary memory arrays and wherein each entry of a given status array stores a status bit that indicates whether a corresponding entry of the corresponding dictionary memory array stores a valid dictionary word;
receiving an input data word;
generating a hash value based on the input data word;
reading a dictionary word from each of the dictionary memory arrays and a status bit from each of the status arrays using the hash value as a read address; and
determining whether a dictionary memory array within the plurality of dictionary memory arrays stores a valid dictionary word that matches the input data word.
1 Assignment
0 Petitions
Accused Products
Abstract
A mechanism is provided for dictionary matching. The mechanism loads a plurality of dictionary memory arrays with a set of dictionary words and updates a plurality of status arrays. Each status array of the plurality of status arrays corresponds to a respective one of the plurality of dictionary memory arrays. Each entry of a given status array stores a status bit, which indicates whether a corresponding entry of the corresponding dictionary memory array stores a valid dictionary word. The mechanism receives an input data word and generates a hash value based on the input data word. The mechanism reads a dictionary word from each of the dictionary memory arrays and a status bit from each of the status arrays using the hash value as a read address. The mechanism determines whether a dictionary memory array within the plurality of dictionary memory arrays stores a valid dictionary word that matches the input data word.
-
Citations
22 Claims
-
1. A method, in a data processing system, for dictionary matching, the method comprising:
-
loading a plurality of dictionary memory arrays with a set of dictionary words and updating a plurality of status arrays, wherein each status array of the plurality of status arrays corresponds to a respective one of the plurality of dictionary memory arrays and wherein each entry of a given status array stores a status bit that indicates whether a corresponding entry of the corresponding dictionary memory array stores a valid dictionary word; receiving an input data word; generating a hash value based on the input data word; reading a dictionary word from each of the dictionary memory arrays and a status bit from each of the status arrays using the hash value as a read address; and determining whether a dictionary memory array within the plurality of dictionary memory arrays stores a valid dictionary word that matches the input data word. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
11. An apparatus for dictionary matching, the apparatus comprising:
-
a plurality of dictionary memory arrays loaded with a set of dictionary words; a plurality of status arrays, wherein each status array of the plurality of status arrays corresponds to a respective one of the plurality of dictionary memory arrays and wherein each entry of a given status array stores a status bit that indicates whether a corresponding entry of the corresponding dictionary memory array stores a valid dictionary word; hash logic configured to receive an input data word and generate a hash value based on the input data word; and a plurality of comparators, wherein each comparator within the plurality of comparators is configured to receive a dictionary word from a respective one of the plurality of dictionary memory arrays and a status bit from a respective one of the plurality of status arrays using the hash value as a read address and to determine whether the dictionary memory array stores a valid dictionary word that matches the input data word. - View Dependent Claims (12, 13, 14, 15, 16, 17, 18, 19, 20)
-
-
21. A dictionary matching apparatus comprising:
-
an input buffer, wherein the input buffer is configured to receive a stream of input words; a tokenizer, wherein the tokenizer is configured to identify whitespace and punctuation characters in the stream of input words in the input buffer to generate a tokenized stream of input words; extraction logic, wherein the extraction logic is configured to extract a next input data word from the tokenized stream of input words; hash logic, wherein the hash logic is configured to generate a hash value based on the next input data word; and a plurality of dictionary memory arrays loaded with a set of dictionary words and a plurality of status arrays, wherein each status array of the plurality of status arrays corresponds to a respective one of the plurality of dictionary memory arrays and wherein each entry of a given status array stores a status bit that indicates whether a corresponding entry of the corresponding dictionary memory array stores a valid dictionary word, wherein the plurality of dictionary memory arrays and the plurality of status arrays generate a match signal indicating whether a dictionary memory array within the plurality of dictionary memory arrays stores a valid dictionary word that matches the input data word. - View Dependent Claims (22)
-
Specification