Multiple string searching using content addressable memory
View Patent ↗A method and apparatus for multiple string searching using a ternary content addressable memory. For one embodiment, the method includes selecting character groups from an input text string in a temporal sequence, each character group having more than one character. A first character group of the character groups is compared with a plurality of character fields and a current state of a state machine is compared with a plurality of states of the state machine that correspond to the plurality of character fields to identify information indicative of a subsequent state of the state machine. Comparison of the first character group with the plurality of sets of character fields is repeated if the information indicative of the subsequent state of the state machine indicates that a terminal number of characters of a desired character pattern has been located and that the terminal number of characters is fewer than the number of characters in the first character group.
1. A method for detecting a match between an input text string and a pattern performed by a state machine implemented using a ternary content addressable memory (TCAM) device, the method comprising:
selecting a character group from the input text string;
comparing the selected character group and a current state of the state machine with a plurality of character entries and a plurality of state entries, respectively, stored in the TCAM device;
generating a next state and a result code in response to the comparing; and
selectively repeating comparison of the same selected character group with the plurality of character entries and outputting the result code if the result code indicates a match between the input text string and the pattern and is encoded with a repeat flag indicating that comparison of the same selected character group is to be repeated with the character entries corresponding to the next state.
2. The method of claim 1 , wherein the selectively repeating further comprises comparing the next state of the state machine with the plurality of state entries stored in the TCAM device.
3. The method of claim 1 , wherein a rollback pointer is not used during the selectively repeating comparison.
4. An apparatus for detecting a match between an input text string and a pattern performed by a state machine implemented using a ternary content addressable memory (TCAM) device, the apparatus comprising:
means for selecting a character group from the input text string;
means for comparing the selected character group and a current state of the state machine with a plurality of character entries and a plurality of state entries, respectively, stored in the TCAM device;
means for generating a next state and a result code in response to the comparing; and
means for selectively repeating comparison of the same selected character group with the plurality of character entries and outputting of the result code if the result code indicates a match between the input text string and the pattern and is encoded with a repeat flag indicating that comparison of the same selected character group is to be repeated with the character entries corresponding to the next state.
5. The apparatus of claim 4 , wherein the means for selectively repeating further comprises:
means for comparing the next state of the state machine with the plurality of state entries stored in the TCAM device.
6. The apparatus of claim 4 , wherein a rollback pointer is not used during the selectively repeating comparison.