Patent ID: 6014733
Filing Date: 2000-01-11
Classification: G06F,H03M

Abstract:
In a computer system including a range of values, a method of converting a non-contiguous subset of values in the range into a contiguous or mostly contiguous smaller range with a perfect hash, comprising the steps of:selecting the subset of values from among the values in the range;organizing the range into a two-dimensional matrix, one dimension of the matrix representing pages and the other dimension representing offsets into the pages, the matrix at each intersection of a page and offset into the page including mapping information therein indicative of whether the value represented by that intersection is a selected value in the subset; andconverting the matrix into a one-dimensional array by selecting each page, testing the mapping information on each page for conflicts with mapping information in the one-dimensional array, shifting each page an amount until no conflicts are detected, overlaying the mapping information in the page onto the one-dimensional array at the shifted position, and recording the shift amount.