Associative cam apparatus and method for variable length string matching

• US 5,329,405 A
• Filed: 11/13/1992
• Issued: 07/12/1994
• Est. Priority Date: 01/23/1989
• Status: Expired due to Term

• Current Assignee: CIF Licensing LLC
• Original Assignee: Codex Corporation
• Inventors: Hou, Brian Ta-Cheng, Gutman, Michael, Pasco-Anderson, James A., Cohen, Craig D.
• Primary Examiner(s): Coleman, Eric
• Application Number:
  US07/976,298
• Time in Patent Office: 606 Days
• Field of Search: 395/250, 395/800, 382/14, 382/11, 365/189.07, 341/52, 341/95
• US Class Current: 365/189.07
• CPC Class Codes: G06F 16/90339 by using parallel associative memories or content-addressable memories
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: G06F 18/00 Pattern recognition
• CPC Class Codes: G06F 2207/025 String search, i.e. pattern matching, e.g. find identical word or best match in a string
• CPC Class Codes: G06F 7/02 Comparing digital values G06F7/06, G06F7/22, G06F7/38 take precedence
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding
• CPC Class Codes: G11C 15/00 Digital stores in which information comprising one or more characteristic parts is written into the store and in which information is read-out by searching for one or more of these characteristic parts, i.e. associative or content-addressed stores
• CPC Class Codes: H03M 7/3086 employing a sliding window, e.g. LZ77
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A variable length string matcher finds the longest string in a stored sequence of data elements (e.g., in a history buffer) that matches a string in a given sequence of data elements. The matcher includes circuitry that operates iteratively to compare data elements of the strings and determine the longest matching string based on when an iteration does not result in issuance of a match signal. In another aspect, the history buffer is an associative content addressable memory (CAM), and the string matcher uses absolute addressing of the CAM to determine the longest matching string.

Claims

1. Apparatus for finding, within a stored first sequence of data elements, a longest string of stored data elements that matches a string of a second sequence of given data elements, comprising:

storage for storing said first sequence of data elements,

comparison circuitry for comparing a single data element of said second sequence with multiple data elements of said first sequence, and for issuing match signals when matches are found, and

control circuitry for causing said comparison circuitry to operate iteratively, each iteration comprising a simultaneous comparison of a data element of said second sequence with the stored multiple data elements, said control circuitry being responsive to said match signals for determining the longest string of said stored data elements that matches a string of said second sequence immediately when the match circuitry, occurs, based on when an interation does not result in issurance of a match signal by said comparison circuitry,

wherein each of a plurality of cells includes at least the storage and the comparison circuitry, the cells are associated by signals between adjacent cells, the cells are provided in parallel each iteration with the data element of the second sequence for comparison and wherein said storage comprises locations each for holding one of said data elements of said first sequence,

said comparison circuitry comprises a series of comparators each in a different respective one of said cells for comparing one of said data elements of said first sequence with a given data element of said second sequence and for issuing a match signal when a match is found, and

delay circuitry for storing said match signal issued by a said comparator temporarily each in a different respective one of said cells for use in a next iteration on the next data element in said second sequence.

2. The apparatus of claim 1 wherein the control circuitry includes means for counting the number of said iterations and for terminating the comparisons after a predetermined number of iterations.

3. The apparatus of claim 1 wherein said storage comprises storage locations each for holding one of said data elements of said first sequence,

said comparison circuitry comprises a series of comparators each for comparing one of said data elements of said first sequence with a given data element of said second sequence and for issuing a match signal when a match is found, and

delay circuitry for storing a said match signal issued by a said comparator temporarily and thereafter coupling it to an adjacent comparator of said series for use by said adjacent comparator in connection with its comparison on the next data element in said second sequence.

4. The apparatus of claim 3 wherein

said comparison circuitry includes logic that inhibits the issuance of said match signal except when the delayed signal made available by the delay circuitry from the adjacent comparator indicates a match.

5. The apparatus of claim 3 further comprising

counter circuitry for counting the number of said iterations beginning with the first iteration and ending with an iteration that does not result in a match signal, and for determining the number of data elements in said longest matching string based on said counted number.

6. The apparatus of claim 5 wherein said counter issues a signal to cause the iterations to terminate, when the count reaches a predetermined value.

7. The apparatus of claim 1 wherein

said storage and said comparison circuitry comprise an associative content addressable memory.

8. The apparatus of claim 1 wherein

said data elements comprise 8-bit bytes.

9. The apparatus of claim 1 further comprising

encoding circuitry for encoding said longest string as a codeword.

10. The apparatus of claim 9 further comprising

decoding apparatus for decoding said codeword to recover said longest string.

11. The apparatus of claim 9 wherein said codeword includes a value indicative of the length of the longest matching string.

12. The apparatus of claim 9 wherein said codeword includes a value indicative of the location of the longest matching string.

13. The apparatus of claim 12 wherein the location value is an absolute address.

14. The apparatus of claim 1 wherein

the storage comprises storage locations for holding said data elements of said sequence, said storage locations being identifiable by absolute addresses, and

the comparison circuitry simultaneously determines, immediately when the match occurs, which said storage locations hold the matching said string of stored data elements and identifies said storage locations based on their absolute addresses.

15. The apparatus of claim 14 wherein

said comparison circuitry comprises comparators for comparing each said data element of said sequence, as held in a said storage location, with a given data element of said second string, and

address circuitry for determining and keeping track of the absolute address of at least one said storage location whose comparator indicates a match.

16. A method for finding, within a stored first sequence of data elements, a longest string of stored data elements that matches a string of a second sequence of data elements, comprising:

storing said first sequence of data elements,

comparing, simultaneously, a single data element of said second sequence with multiple data elements of said first sequence,

issuing match signals when matches are found,

performing said comparing step in iterations, each iteration comprising comparing a data element of said second sequence with multiple data elements in the stored first sequence, and

determining, immediately when the match occurs, the longest string of said stored data elements that matches a string of said second sequence based on when an iteration does not result in issuance of a match signal,

wherein the storing, comparing, and performing said comparing are performed in individual cells, and a signal is utilized to associate adjacent cells, the cells are provided in parallel each iteration with the data element of the second sequence for comparison and wherein storing includes storing at locations, each for holding one of said data elements of said first sequence,

comparing includes utilizing a series of comparators each in a different respective one of said cells for comparing one of said data elements of said first sequence with a given data element of said second sequence and for issuing a match signal when a match is found, and

performing said comparing includes storing said match signal issued temporarily in the step of comparing, wherein each match signal is in a different one of said cells for use in a next iteration on the next data element in said second sequence.