Prefix search method and data structure using compressed search tables

Data structure for determining an output information in response to an input search key, by a stepwise prefix search in the data structure comprising stored tables, and by evaluating successive segments of the search key each of given length, comprising for at least one search key segment to be evaluated:

• a) a stored index mask for selecting bit positions from the associated search key segment to obtain a compressed index;
• and
• b) a node table containing test values to be compared to a current value of the associated search key segment, which node table is accessed by the compressed index bits selected with the stored index mask, to obtain one of the stored test values.

A computer program product in a computer readable medium for use for determining an output information in response to an input search key, in response to an input search key, by a stepwise prefix search in a tree structured data base comprising stored tables, and by evaluating successive segments of the search key each of given length, the computer program product comprising:

• instructions for, in at least one step, evaluating a search key segment, where selected bits of the segment are used as compressed index for accessing a table of stored test values associated with that segment, wherein the test value accessed by the compressed index is compared to at least the remaining portion of the search key segment evaluated, and the comparison result determines the further processing or the result of the search procedure.