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

Details Method and system for creating a perfect hash using an offset ta Method and system for creating a perfect hash using an offset ta

1997-06-05

2000-01-11

Peikari, B. James

Electrical computers and digital processing systems: memory

Address formation

Hashing

711220, 711209, 711203, 711202, 711210, 711219, G06F 1210

Patent

active

060147334

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.

REFERENCES:
patent: 4115765 (1978-09-01), Hartke
patent: 4215402 (1980-07-01), Mitchell et al.
patent: 4433389 (1984-02-01), York et al.
patent: 4488256 (1984-12-01), Zolnowsky et al.
patent: 5111389 (1992-05-01), McAuliffe et al.
patent: 5133061 (1992-07-01), Melton et al.
patent: 5293593 (1994-03-01), Hodge et al.
patent: 5377340 (1994-12-01), Seroussi et al.
patent: 5584005 (1996-12-01), Miyaoku et al.
Sedgewick, Robert, Algorithms in C++, Chapter 16, "Hashing", pp. 231-243, 1992.

Affiliated with

Also associated with

Rating

Method and system for creating a perfect hash using an offset ta does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method and system for creating a perfect hash using an offset ta, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for creating a perfect hash using an offset ta will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1470675