EP0380294A1 — String matching

Claim 1

Independent Claim 130 words

Apparatus for finding, within a stored sequence of data elements, preferably comprising 8-bit bytes, the longest string of stored data elements that matches a second string of given data elements, characterised in comprising: storage adapted for operatively storing said sequence of data elements; comparison circuitry adapted for operatively comparing a data element of said second string with corresponding data elements of said sequence, and for issuing signals when matches are found; and control circuitry adapted operatively to cause said comparison circuitry to operate iteratively, each iteration comprising a comparison of a data element of said second string with the data elements in said storage locations, and to determine the longest matching string based on when an iteration does not result in issuance of a match signal by said comparison circuitry.

Claim 2

Dependent Claim 130 words

Apparatus for finding, within a stored sequence of data elements, preferably comprising 8-bit bytes, the longest string of stored data elements that matches a second string of given data elements, characterised in comprising: storage adapted for operatively storing said sequence of data elements; comparison circuitry adapted for operatively comparing a data element of said second string with corresponding data elements of said sequence, and for issuing signals when matches are found; and control circuitry adapted operatively to cause said comparison circuitry to operate iteratively, each iteration comprising a comparison of a data element of said second string with the data elements in said storage locations, and to determine the longest matching string based on when an iteration does not result in issuance of a match signal by said comparison circuitry.

Claim 3

Dependent Claim 34 words

Apparatus according to Claim 1, further characterised in that the control circuitry includes means adapted for operatively counting the number of said iterations and for terminating the comparisons after a predetermined number of iterations.

Claim 4

Dependent Claim 119 words

Apparatus according to Claims 1 or 2, further characterised in that said storage comprises storage locations each adapted for holding one of said data elements of said sequence; in that said comparison circuitry comprises a series of comparators each adapted for comparing one of said data elements of said sequence with a given data element of said second string and for possibly issuing a signal when a match is found, and delay circuitry adapted for operatively storing a said signal issued by a said comparator temporarily and thereafter making it available to an adjacent comparator of said series for operative use by said adjacent comparator in connection with its comparison on the next data element in said second string.

Claim 5

Dependent Claim 43 words

Apparatus according to Claim 3, further characterised in that said comparison circuitry includes logic means operatively arranged to inhibit the issuance of said match signal except when the delayed signal made available by the delay circuitry from the adjacent comparator indicates a match.

Claim 6

Dependent Claim 58 words

Apparatus according to Claims 3 or 4, characterised in further comprising counter circuitry adapted for operatively 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.

Claim 7

Dependent Claim 31 words

Apparatus according to Claim 5, further characterised in that said counter is operatively arranged to issue a signal to cause the iterations to terminate, when the count reaches a predetermined value.

Claim 8

Dependent Claim 22 words

Apparatus according to any preceding claim, further characterised in that said storage and said comparison circuitry comprise an associative content addressable memory.

Claim 9

Dependent Claim 22 words

Apparatus according to any preceding claim, further characterised in comprising encoding circuitry adapted for operatively encoding said longest string as a codeword.

Claim 10

Dependent Claim 22 words

Apparatus according to Claim 8, further characterised in comprising decoding apparatus adapted for operatively decoding said codeword to recover said longest string.

Claim 11

Dependent Claim 37 words

Apparatus according to Claims 8 or 9, further characterised in that said encoding circuitry is adapted for operatively encoding said longest string as a codeword including a value indicative of the length of the longest matching string.

Claim 12

Dependent Claim 51 words

Apparatus according to any of Claims 8, 9 or 10, further characterised in that said encoding circuitry is adapted for operatively encoding said longest string as a codeword including a value indicative of the location of the longest matching string, and preferably a value in the form of an absolute address.

Claim 13

Independent Claim 107 words

A method for finding, within a stored sequence of data elements, the longest string of stored data elements that matches a second string of data elements, comprising the steps of: storing said ordered sequence of data elements; comparing a data element of said second string with corresponding data elements of said ordered sequence; issuing signals when matches are found; performing said comparing step in iterations, each iteration comprising comparing a data element of said second string with data elements in the storage locations; and determining the longest matching string based on when an iteration does not result in issuance of a match signal by said comparison circuitry.

Claim 14

Independent Claim 107 words

A method for finding, within a stored sequence of data elements, the longest string of stored data elements that matches a second string of data elements, comprising the steps of: storing said ordered sequence of data elements; comparing a data element of said second string with corresponding data elements of said ordered sequence; issuing signals when matches are found; performing said comparing step in iterations, each iteration comprising comparing a data element of said second string with data elements in the storage locations; and determining the longest matching string based on when an iteration does not result in issuance of a match signal by said comparison circuitry.

Claim 15

Dependent Claim 80 words

Apparatus for identifying, within a stored sequence of data elements, preferably comprising 8-bit bytes, a string of data elements that matches a given second string of data elements, characterised in comprising: storage locations adapted for operatively holding said data elements of said sequence, said storage locations being addressable by absolute addresses; and determination circuitry adapted for operatively determining which said storage locations hold the matching said string of stored data elements and for identifying said storage locations by absolute addressing.

Claim 16

Dependent Claim 80 words

Apparatus for identifying, within a stored sequence of data elements, preferably comprising 8-bit bytes, a string of data elements that matches a given second string of data elements, characterised in comprising: storage locations adapted for operatively holding said data elements of said sequence, said storage locations being addressable by absolute addresses; and determination circuitry adapted for operatively determining which said storage locations hold the matching said string of stored data elements and for identifying said storage locations by absolute addressing.

Claim 17

Dependent Claim 68 words

Apparatus according to Claim 13, further charcterised in that said determination circuitry comprises comparators adapted for operatively comparing each said data element of said sequence, as held in an addressable storage location, with a given data element of said second string, and address circuitry adapted for operatively determining and keeping track of the absolute address of at least one said addressable storage location whose comparator indicates a match.

Claim 18

Independent Claim 29 words

A method of variable length string matching by absolute addressing of a history buffer and determination of the longest matching string by use of an associative content addressable memory.

Claim 19

Independent Claim 29 words

A method of variable length string matching by absolute addressing of a history buffer and determination of the longest matching string by use of an associative content addressable memory.

String matching

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag