US 7,444,562 B2Granted

Trie-type memory device with a compression mechanism

AssigneeFrance Telecom

InventorsJoel Lattmann, Christian Duret, Valéry Laspreses, Francis Rischette

Life of this patent

Estimating the term…

Loading patent…

Abstract

The invention relates to a tri-type memory device comprising a compression mechanism. According to the invention, the memory stores binary patterns that are associated with respective references. Data chains are analyzed by successive section of K bits (K>1) in order to extract one of the references when there is a match with a stored binary pattern associated with said reference. The memory is organized into several successive memory cell states, the analysis of the (i+1)-th section of a chain providing access to a cell of stage i≧0. Each non-empty cell of a stage i≧0 contains one of the following: a register-type analysis tracking pointer designating a register of 2K cells of stage i+1; a linear-type analysis tracking pointer designating a zone of one or two cells forming a reduced register of stage i+1; or a reference associated with a stored binary pattern.

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.

9 more elements

Abstract

Claims7