Method and system for creating a perfect hash using an offset table

Claim 2

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; and converting 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.

Claim 3

The method of claim 1 wherein the matrix and one-dimensional array are bitmaps, and wherein the mapping information is stored in a value of the bitmap.

Claim 4

The method of claim 1 further comprising the step of ordering the pages into a ranking order, and wherein the step of selecting each page includes the step of selecting each page according to the ranking order.

Claim 5

The method of claim 3 wherein the step of ordering the pages includes the steps of counting the number of times that the mapping information indicates that a value on a page is a selected value in the subset, and ranking the pages from a highest count to a lowest count.

Claim 6

The method of claim 3 wherein the step of ordering the pages includes the step of selecting a first page in the matrix as a first page in the ranking order.

Claim 7

The method of claim 1 wherein the values of the range of values equal binary numbers consisting of a plurality of bits, and wherein the dimensions of the matrix correspond to a split of the bits representing the values.

Claim 8

The method of claim 6 further comprising the steps of selecting a plurality of bit splits, repeating the steps of organizing and converting with each of the bit splits, obtaining statistical information corresponding to the contiguous range of subset values for each bit split, and selecting the range of subset values based on a comparison of the statistics therefor with statistics for other subset ranges.

Claim 9

The method of claim 1 wherein the range of values corresponds to a table of information, and further comprising the step of writing information from the table into a hash table at a location corresponding to the recorded page shift information and offset into the page for the selected value corresponding thereto.

Claim 10

The method of claim 1 further comprising the steps of receiving a value of the non-contiguous range, and hashing the value into a value of the subset range by separating the value into a page number and an offset into the page, looking up the shift amount for the page and adding the shift amount to the offset into the page.

Claim 11

The method of claim 1 wherein the range of values ranges from 0 to 65535.

Claim 12

The method of claim 10 wherein the values represent possible Unicode code points, and wherein the subset of values represent selected Unicode code points.

Claim 13

In a computer system including a range of values, a mechanism for converting a non-contiguous subset of values in the range into a contiguous or mostly contiguous smaller range with a perfect hash, comprising: means for selecting the subset of values from among the values in the range; means for 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; and means for converting the matrix into a one-dimensional array by selecting each page, said means including means for testing the mapping information on each page for conflicts with mapping information in the one-dimensional array, means for shifting each page an amount until no conflicts are detected, means for overlaying the mapping information in the page onto the one-dimensional array at the shifted position, and means for recording the shift amount.

Claim 14

In a computer system including a range of values, a mechanism for converting a non-contiguous subset of values in the range into a contiguous or mostly contiguous smaller range with a perfect hash, comprising: means for selecting the subset of values from among the values in the range; means for 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; and means for converting the matrix into a one-dimensional array by selecting each page, said means including means for testing the mapping information on each page for conflicts with mapping information in the one-dimensional array, means for shifting each page an amount until no conflicts are detected, means for overlaying the mapping information in the page onto the one-dimensional array at the shifted position, and means for recording the shift amount.

Claim 15

The mechanism of claim 12 wherein the matrix and one-dimensional array are bitmaps, and wherein the mapping information is stored in a value of the bitmap.

Claim 16

The mechanism of claim 12 further comprising means for ordering the pages into a ranking order, and wherein the means for selecting each page includes means for selecting each page according to the ranking order.

Claim 17

The mechanism of claim 14 wherein the means for ordering the pages includes means for counting the number of times that the mapping information indicates that a value on a page is a selected value in the subset, and means for ranking the pages from a highest count to a lowest count.

Claim 18

The mechanism of claim 14 wherein the means for ordering the pages includes means for selecting a first page in the matrix as a first page in the ranking order.

Claim 19

The mechanism of claim 12 wherein the values of the range of values equal binary numbers consisting of a plurality of bits, and wherein the dimensions of the matrix correspond to a split of the bits representing the values.

Claim 20

The mechanism of claim 17 further comprising means for selecting a plurality of bit splits, means for repeatedly organizing and converting the range using each of the bit splits, means for obtaining statistical information corresponding to the contiguous range of subset values for each bit split, and means for comparing the statistics of each of the subset ranges for selecting a range of subset values.

Claim 21

The mechanism of claim 12 wherein the range of values corresponds to a table of information, and further comprising a hash table, means for writing information from the table into the hash table at a location corresponding to the recorded page shift information and the offset into the page for the selected value corresponding thereto.

Claim 22

The mechanism of claim 12 further comprising means for receiving a value of the non-contiguous range, and means for hashing the value into a value of the subset range including means for separating the value into a page number and an offset into the page, means for looking up the shift amount for the page and means for adding the shift amount to the offset into the page.

Claim 23

The mechanism of claim 12 wherein the range of values ranges from 0 to 65535.

Claim 24

The mechanism of claim 21 wherein the values represent possible Unicode code points, and wherein the subset of values represent selected Unicode code points.