US Patent 7446681 Lookup table array compression and indexing

A method of constructing, from a first array of entries, a second array of entries having a reduced number of entries compared with the first array is disclosed. According to one embodiment, the method comprises partitioning the first array into one or more groups of entries and then categorizing each group with a category categorizing relationships between entries of a respective group, or entries of a respective group and entries of another group. A compression code is then formed that contains a sequence of coded identifiers, each identifier identifying the category of a respective group. Finally, the second array is constructed to include selected entries from the first array. The selected entries depend on the category of each group and are arranged so as to be indexable by processing a first index into the first array and the compression code to derive a second index for retrieving an equivalent entry from the second array without decompressing the second array.