Patent ID: 7444562

Claim:
A TRIE memory device, comprising: means for storing bit patterns associated with respective references, and means for analyzing data strings by successive sections of K bits to extract one of the references when an analyzed data string matches a stored bit pattern associated with said reference, K being an integer greater than 1, wherein the storage means comprise a plurality of successive stages each including a plurality of memory cells, wherein each nonempty memory cell of a stage i, with i being an integer at least equal to 0, contains a cell type indicator and data including: a pointer designating another memory cell when the cell type indicator is in a first or a second state, the pointer being accompanied by a test value on K bits when the cell type indicator is in the second state; a reference associated with a stored bit pattern when the cell type indicator is in a third state, and wherein the analysis means comprise: means of reading a cell of a stage i, with i being an integer at least equal to 0, in relation with the analysis of the (i+1)th section of a data string; means of selecting a cell of stage i+1, to be read in relation with the analysis of a (i+2)th section of the data string, in response to the first state of the indicator in said cell of stage i, the selected cell being located relative to the designated cell by the pointer contained in said cell of stage i according to the value of the (i+1)th section of the data string; means of selecting the cell designated by the pointer contained in said cell of stage i, to be read in relation with the analysis of a (i+2)th section of the data string, in response to the second state of the indicator in said cell of stage i when the value of the (i+1)th section of the data string coincides with the test value contained in said cell of stage i; and means of extracting the reference contained in said cell of stage i in response to the third state of the indicator in said cell of stage i.