Browse Prior Art Database

Method for High-Speed Execution of Symbol Selection by Two-Stage Hashing

IP.com Disclosure Number: IPCOM000120096D
Original Publication Date: 1991-Mar-01
Included in the Prior Art Database: 2005-Apr-02
Document File: 3 page(s) / 73K

Publishing Venue

IBM

Related People

Komatsu, H: AUTHOR [+2]

Abstract

Disclosed is a method for executing symbol selection efficiently. This method is a kind of hashing technique. The unique point is that this method divides a hash function into two functions and that they are operated at different times, compile time and execution time. By doing this, it is possible to reduce the overhead of hash function execution and collision of hash values. Consequently, this method realizes high- speed execution of symbol selection.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 56% of the total text.

Method for High-Speed Execution of Symbol Selection by Two-Stage
Hashing

      Disclosed is a method for executing symbol selection
efficiently. This method is a kind of hashing technique. The unique
point is that this method divides a hash function into two functions
and that they are operated at different times, compile time and
execution time. By doing this, it is possible to reduce the overhead
of hash function execution and collision of hash values.
Consequently, this method realizes high- speed execution of symbol
selection.

      The goal of this method is to optimize the execution of symbol
selection. Symbol selection is a kind of procedure where a symbol is
inputted as an argument and selection of procedures occurs based on
the argument (Fig. 1). The premises of this method is the following:
1) a symbol is represented as a pointer cell which points to
character string area of the symbol, and 2) symbols that are expected
in each selection are fixed in advance. Therefore, symbol selections
are compiled.

      This method is a kind of hashing technique. It is quite natural
because of the premise 2, static symbol candidates in each selection.
However, because of the premise 1, the calculation of hash values
using an ordinal hash function would be tough. Because it is usual to
calculate hash values from symbol strings. Note that the pointer
value itself cannot be used because it cannot be known at compile
time. Almost all of calculation must be redundant b...