Marvell International Limited

Yissum Research Development Company of the Hebrew University of Jerusalem Ltd.

Shimrit Tzur-David

Tal Anker

Yaron Weinsberg

Danny Dolev

An apparatus having a content-addressable memory (CAM) that stores a plurality of entries comprising portions of a plurality of patterns; a memory that stores a shift value corresponding to each of the entries; and a controller that generates a first key based on a received string, applies the first key to the CAM to select an entry of the CAM, retrieves the shift value from the memory corresponding to the selected entry, in response to the shift value being equal to a predetermined value, identifies an initial match, and in response to the initial match corresponding to a first pattern of the plurality of patterns that is larger than the entries of the CAM, applies adjacent keys based on the received string to the CAM, and declares a complete match when each of the corresponding shift values from the memory is equal to the predetermined value.

High performance pattern matching

Apparatus having corresponding methods and computer programs, to detect a pattern in a string, comprises a memory circuit to store W-character segments of the pattern, where each segment comprises a fragment of the pattern; a key circuit to generate W-character keys each including a fragment of the string; a comparison circuit to compare the keys and the segments; where, when a segment matches a key, the comparison circuit indicates an initial match between the pattern and the string; and where, when one of the segments matches only a L-character fragment of one of the keys, wherein L&#x3c;W, the key circuit generates a new key including the L-character fragment and a K-character fragment of the string including K=W&#x2212;L consecutive characters from the string that are adjacent to the L matching characters in the string.

Growing community of inventors

Jerusalem, Israel

Shimrit Tzur-David