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

• US 6,014,733 A
• Filed: 06/05/1997
• Issued: 01/11/2000
• Est. Priority Date: 06/05/1997
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Bennett, John R.
• Primary Examiner(s): Peikari, B. James
• Application Number:
  US08/869,913
• Time in Patent Office: 950 Days
• Field of Search: 711/200, 711/202, 711/210, 711/216, 711/220, 711/221, 711/203, 711/128, 711/6, 711/205, 711/206, 711/207, 711/208, 711/209, 711/211, 711/219, 364/736.03, 345/202
• US Class Current: 711/216
• CPC Class Codes: G06F 16/9014 hash tables
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction

Abstract

A method and mechanism for converting a non-contiguous subset of values in a large range, such as selected Unicode code points, into a contiguous or mostly contiguous smaller range with a perfect hash. The large range is organized into a two-dimensional bitmap matrix of pages and offsets into the pages. The bits in the matrix equal one if the value is in the subset, and zero if not. The pages are then overlaid on one another into a one-dimensional bitmap by shifting each page as necessary to avoid conflicts with values on other pages. The shift amount is recorded and used in a hash computation, wherein a value of the large range is first separated into its page number and its offset into the page. The values are then hashed into the value of the dense subset range by looking up the shift amount for the page and adding the shift amount to the offset into the page.

Claims

1. 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.

2. 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.

3. 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.

4. 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.

5. 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.

6. 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.

7. 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.

8. 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.

9. 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.

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

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

12. 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.

13. 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.

14. 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.

15. 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.

16. 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.

17. 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.

18. 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.

19. 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.

20. 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.

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

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