Key-to-Address Transformations

This application repeats substantial portions of two earlier applications, now abandoned, and contains matter not disclosed in those earlier applications, Ser. No. 146,580, filed May 5, 1980 and Ser. No. 485,771 filed Apr. 18, 1983, both now abandoned.

This invention relates to information storage and retrieval. More particularly it pertains to key-to-address transformations or hashing procedures. An object of the invention is to produce a set of statistically randomly distributed storage addresses.

As set forth in U.S. Pat. No. 4,358,824 state of the art document storage and retrieval is based on manually selecting keywords to represent a document in the system's catalog or index and then effecting retrieval by recalling from memory appropriate keyword terms and either automatically or manually searching the index for an "appropriate" level of match against the prestored keywords. Procedures have been developed in the prior art of abstracting documents and retrieving them based on keyword matching. Each document or record has a unique identifier or key. Scanning a file or records to retrieve one particular document or record requires comparing its keyword or key with the key to one record after another. When a key match is obtained the record can be retrieved. This type of search required a careful organization of the records.

Direct addressing involves assigning each record to a specific location which is large enough to contain one or more records and which can be thought of as a bin or bucket. Since this operation usually requires much less time than a scan or other type of search, direct addressing is preferred as the most rapid means of accessing a single record in a file.

While being preferred, the process of transforming a document keyword or record key, to a corresponding main or external memory storage address, thought of as the bin or bucket location where the record can be found, is subject to certain disadvantages. Clusters and gaps frequently occur due to the manner addresses are assigned. Accordingly the memory, or bin address is frequently derived by means of a key conversion or transformation to randomize the address. This key-to-address transformation is intended to disperse the clusters, making the distribution of storage addresses more nearly uniform, and hence is known as hashing or randomizing. Thus, ideally, a key-transformation-technique should yield a unique address for each document or record and 100 percent utilization of the allocated memory storage space. The distribution should be uniform, and all the storage spaces should be filled.

Unfortunately neither complete randomization nor a completely uniform distribution results when keys are converted to addresses by the usual random conversion transformations or hashing techniques. Rather, known key-to-address transformations attempt, with limited success, to produce addresses intermediate between random and uniform. The results are often unpredictable and frequently result in undesirable overflows. That is, the assignment of more records to a location or bin than it can hold.

The storage and retrieval of information is the subject of various patents such as U.S. Pat. Nos. 3,350,695, 3,614,744, 3,681,781, 3,702,010 and 4,079,447. However, of these, only 3,681,781 pertains to hash addressing or hashing. That invention is not directed to the distribution of addresses, but to techniques for hashing which allow information to be found from approximate key values. For more specific descriptions of hashing techniques such articles as "Key-to-Address Transform Techniques: A Fundamental Performance Study on Large Existing Formatted Files", V. Y. Lum et al, Communications of the ACM, April 1971, and "Hashing Functions", G. D. Knott, The Computer Journal, Vol. 18, No. 3, 1975 are noted. The Art of Computer Programming, Vol. 3: Searching and Sorting, D. E. Knuth, 1973, Addison-Wesley also contains pertinent material. As described in these sources various key-to-address transformations have been developed in the form of conversions which randomize the addresses. Since the object of such transformations is statistical, the terms randomization, and hashing have become associated with them.

Obviously, no single transformation method can satisfy all of the speed, uniformity and simplicity requirements. A great deal of effort, with some remarkable results, has been expended in developing transformations producing a high degree of uniformity in the distribution of records throughout their storage space. However, in many cases the conversion method was tailored to the characters, range and length of the keys. Therefore, such methods lack generality. In accordance with the practice of this invention a transformation or hashing process is provided which not only leads to a greater degree of randomness than those heretofore known, but which does not lack generality. It is effective for both static and volatile files, and it works well with all types, ranges, and lenghts of keys. The procedure need not be modified for keys with irregular lenghts, regular or irregular separations, and different sets of characters. Hence this transformation method can be used for all files and different sets of keys at one or many data processing installations. In effect it takes whatever order may or may not exist in the keys and produces a state of chaos or randomization. The numbers or records which will be assigned to memory locations or bins can be calculated before the transformation procedure is actually used. Thus file space can be properly allocated, overflow problems minimized, and other file utilization characteristics can be optimized.

A method is provided herein for storing and retrieving documents wherein storage locations for them are based on record keys. The crux of the method is the formation of an arrangement of characters by randomly selecting characters of a number system and forming the arrangement so that each character is unique, and has a distinct position in the arrangement. The arrangement is in the form of an array of randomly positioned characters. To randomize the storage location, each letter of the record key is first converted to a number using its unique numerical equivalent in that number system. That numerical equivalent, or number, leads to a location in the number arrangement and a stored character in the array. The numeral stored in the array at that location is used to find yet another location in the arrangement and another character, leading to still another array location. The degree of randomness increases as the number of translations increases, leading to a randomized numeral for each original record key character. Using the numerical equivalents of the stored characters so located, each record key character is similarly serially repetitively translated.

Having obtained a random number for each record key character, a composite number for each character is then obtained. This is accomplished by concatenating the finally derived numeral with adjacent numerals in the character array so that one composite number is derived from each of the original characters of the record key. All of the composite numbers thus obtained are then combined into a single number through such known operations as mathematical and Boolean calculations. The single number thus obtained is scaled, if necessary, to form an ultimate number not exceeding the total number of available memory locations. Since the ultimate number thus derived is an address, the document is stored and retrieved using this random storage address.

There is no unique, and simple, method for transforming keys to storage addresses. All of the methods described in the articles referred to are available. Indeed it will be apparent that some of those methods can be used as steps in this invention. The invention herein is predicated on the obtainment of nearly random distribution of storage addresses. The steps involved are not new calculations, formulas or equations. Rather, a randomly developed number array is employed in which positions must be located physically or by a computer. The array is independent of a computer, and the well-known methematical operations involved are employed subsequent to its use. Using this array several of randomizing document key translations are made by going from position to position in the array. This will be better understood from the following specific example described in conjunction with the accompanying drawings.

In the drawings,

FIG. 1 is a numerical array.

FIG. 2 is a flow chart of the overall procedure.

FIG. 3 is a flow chart of the hash loop to be described.

As indicated, the invention herein is based, primarily, upon the use of a randomly constructed arrangement of characters. Ideally, the number system chosen will be that containing a number of characters, exceeding the number in the record or document key. Although the invention is not a computer program, its greatest application will be in the area of computers, that is, for randomizing computer memory storage locations. Considering computer applications, then, it is desirable that the number of characters in the array be correlated with the highest number of bits stored in a byte. Considering that computers are binary machines this number will be a power of 2. Thus in a four bit byte computer the number of bits stored in a byte will be 2.sup.4 or 16. The preferred numeration system, again considering a binary system, will be a numeration system with a radix of 4 since 4.sup.2 is 16. In the case of an eight bit byte computer, the number of bits stored will be 2.sup.8 or 256. Since this is 16.sup.2 the preferred numeration system will have a radix of 16, i.e., the hexadecimal system. The hexadecimal system was preferred by IBM because it contains 256 single digit unique characters. For the purpose of illustration the 256 characters of the hexadecimal system have been used in making up the array shown in FIG. 1. This record key character array, shown in FIG. 1, performs two functions in the invention. As will be shown later, it can also serve a third function. First the number array contains the characters of a number system such as the decimal, hexadecimal and duodecimal systems as explained. In addition, it is a "closed" table. Every entry must be distinct and must have a value equal to an address in the table itself. In a simple case of a table with ten entries, the addresses would range from 0 to 9 and the entries would also have the same set of values, 0 to 9. The addresses, by their nature, exist in sequential order but the entries are selected at random. Since each key character has a unique table entry, or array address, the array can be used for translating the characters of the record key or keyword employed, i.e., the document identifier. This is the first function of the array. Additionally, since every entry can also be considered to be an address, repeated translations may be performed. Following the translations, a logic operator can be used on the table entries, yielding a new table address. By "logic operator" I include any of the arithmetic or Boolean operations employed in methematical logic.

The results of some of the possible operations may give addresses outside the range of the table. When this occurs, the result is scaled or truncated in order to fall within the permissible range of addresses. Since the table entries are in random sequence, each use of the table to perform a translation function introduces an additional random attribute to the result.

Referring specifically to FIG. 1, a randomly formulated array is shown for the purpose of illustration. The table was constructed by pulling 256 hexadecimal values from a container and then listing them in the order in which they were drawn. As indicated the entries in the table have values which depend upon a computer, if one is used. In this instance a hexadecimal (hex) notation, of 00 to FF, corresponding to 0 to 255 table addresses is preferred. Each pair of hexadecimal numbers thus constitutes a computer "byte" in the range from 00 to FF (or in decimal from 0 to 255). It is to be understood that there are many ways in which such an arrangement or array can be generated using a predefined set of n key characters.

It can be seen that each pair of characters (letter or number) in FIG. 1 corresponds to a number in the range from 0 to 255. Since 256 will generally be much greater than the number of characters in the record key, this particular table is both flexible and comprehensive. It can be used with several computer codes, for instance both EBCDIC (Extended Binary--Coded--Decimal Interchange Code) and USASCII (US Standard Code for Information Interchange) codes.

As an example, consider the record key X6. In the EBCDIC code the letter X is decimal 231. EBCDIC character 6 in decimal notation is 246. As indicated the key-to-address transformation procedure of the invention uses the table for two purposes. The first and most important is the use of the table in translation operations. One or more characters of the record key are considered to be addresses in the table for an initial translation. For example the address of the letter X (EBCDIC) is considered to be 231. Counting 231 squares in the table of FIG. 1, starting with zero leads to hex 73 (found in the 232nd square starting with 1). Similarly using the EBCDIC character 6, which is decimal 246, and starting with 0 and counting to 246, one finds hex 43 in the table. The array in FIG. 1 has thus been used for an initial translation of each record key character. Such translations can be repeated any desired number of times, and they can be performed in any desired order of key characters. For example hex 73, obtained as described, is decimal number 115, starting with 0 and counting 115 positions in the array of FIG. 1 yields A2. Similarly hex 43 is decimal 67. This leads to 0A, which is in the 67th position in the table in FIG. 1, starting with zero.

After a character has been translated it is combined, by means of the appropriate logic operator, the mathematical logic arithmetic and/or Boolean operation, with other key characters or table entries, for example key character 6, described hereinbefore, to give a new table address. Preferably the number of translations and logic operations is equal to the left-to right position number of the character in the key. The Boolean EXCLUSIVE OR operation is a desirable logic operator. It is used to combine two quantities on a "bit" basis. A bit position in the result is set equal to one if the corresponding bit positions in the two quantities are unlike; otherwise, the resulting bit is set equal to zero. The hex 73 previously extracted from the table can be EXCLUSIVE OR'ed with the hex value of F6, the representation of a key character 6. The result of the operation is, then, hex 85 (decimal 133). This, if desired, can be treated as an address in the table, and used as the basis for a subsequent translation. If such is the case this portion of the procedure is incorporated in a hash loop set up to effect translations of, and operations on, all the characters of the key. The hash looping can be repeated as deemed necessary. Each time the table is used a random attribute is introduced into the result. Randomization is at least partially determined by the number of iterations specified for the hash loop. Desirably therefore the looping is repeated until all the characters of the key have been treated. This normally yields a sufficiently randomized result. If a greater degree of randomization is desired because of duplicate results or other reasons the iterations can be repeated by further looping. Generally more than ten iterations beyond the number of characters of the key are unnecessary. Thus by this step the key characters are replaced by a set of numbers within the same numerical range as the table addresses. In order to effect this randomization each designated position in the table must be physically located.

The next step in the procedure is to convert this set of numbers or random bytes to one random number. Ideally this number will be uniquely associated with the key from which the random bytes are obtained. The range of values for these numbers will be based on convenient machine capabilities, such as the "word" size of the computer. A computer word is a larger storage unit than a byte. It is usually a multiple of a byte, and in many machines four sequential bytes constitute a word. The word can also be used as a basis for arithmetic, logical operations. Since the word value can be scaled down to a value in the range of the anticipated number of bin or bucket locations in main memory or external storage, the word can be virtually any single random number. This single random number, or computer word with a randomly distributed numerical value, is thus obtained from a set of randomly selected words. In the example table of FIG. 1 the random bytes associated with the key characters can take on 256 values. These values can then be used to generate, i.e., select, a set of random words. The random words are then combined by means of Boolean and/or arithmetic logic operations to yield the single desired number or word which has been transformed from the key.

As noted hereinbefore there is an additional use for the random array. It can be the source of the random words required in this third step of the procedure of the invention. Thus, each random byte in the set obtained from the key can be used as an address in the table. The byte at that address, and the next three bytes constitute a four byte word. The four byte word will have random characteristics because of the manner in which the array was constructed. Using this method one such word will be extracted from the table for each random byte of the converted key. Their final combination by the use of the logic operator is the ultimate hashed value for the key.

The distribution of bytes and words in the table or array and the nature of the procedure do not completely preclude the possibility that more than one key will be transformed to the same result. But such an occurrence is consistent with the purpose of achieving a random distribution. In most cases, however, the ranges of values and the types of operations can be selected in a way that minimizes such duplicates.

The final step of my method is that of scaling the single random number, or word, obtained from a key, to a relative address, that is, the sequential identification of the address of a bin or bucket. This number cannot exceed the number of bins to be used to store the records. For example if there are ten bins the random number would be scaled to the range of 0 to 9. It has been stated that randomizing methods of the prior art can be used as steps in this invention. It will be understood that in scaling down the single random number any of the methods available from other sources, such as the ones discussed in the Knuth text can be employed.

Use of the invention in a non-computer environment has been described. Since it will be especially useful in the computer field that aspect will now be described in conjunction with FIGS. 2 and 3 of the drawing. FIG. 2 is a flow chart showing a one overall realization of the procedure. FIG. 3 is a more detailed flow chart showing the randomizing or hash loop, which is Block 5 of FIG. 2. These are flow charts of the program module listing which follows. It is to be understood that whereas the use of the invention for storing and retrieving documents by computer is now being illustrated, the foregoing description of the invention shows that an algorithm is not preempted. An array such as the one shown in FIG. 1 is still the most important feature of the invention, and it is separate from any algorithm. In fact, referring to lines 14000 thru 15700 it can be seen that the number array of FIG. 1 is incorporated as data. Referring to this particular illustrative program, as can be seen, it is written in assembler language specifically for an IBM System/360.

The hashing module, Table I would be called by some other program. The "calling" program provides the hashing program with the addresses (in the main memory of the computer) of the record key, the number of storage bins specified for the file records, and the length of the key. The calling program also provides a main memory address where the relative bin address is to be stored after the transformation of the key has been completed. After the key-to-address transformation is made by means of the hashing module and the result returned to the calling program, the relative bin address is adapted and converted to a main memory or secondary storage address by the calling program. The calling program then uses this address to read, store, or update a record.

Referring now to the hashing module, lines 5800 and 6000 of this program correspond to Block 1 of FIG. 2. These instructions are standard initialization procedures for "calling" and "called" programs. The instructions in lines 6200 thru 7000 obtain the desired addresses and move the key and its length to the hashing program area (Blocks 2 and 3 FIG. 2).

The operations in Blocks 4 and 5 can be explained in terms of algebraic symbols. The quantity L is set equal to the length of the key. D represents a displacement into the random byte table, that is, a relative address in the table. H represents the combination of the random words extracted from the byte table and J is an index which identifies the character of the key being operated on during each of the iterations of the hash loop. Initially D, H and J are set equal to zero. When J=0, 1, 2, . . . the 1st, 2nd, 3rd, . . . characters are operated on during the 1st, 2nd, 3rd, . . . repetitions of the loop operations. The instructions on lines 7500 to 8000 of the program (Table I) set up the initial values for these quantities (Block 4) and for the hash loop of Block 5. The hash loop is shown more minutely in FIG. 3. The figure is a detailed diagram of Block 5 in FIG. 2.

In this embodiment of the invention most of the functions of the procedure are performed in the hash loop. The order in which they are preformed is mixed. The characters of the key are operated on both sequentially and simultaneously each time that the instructions of the loop are executed. That is, the various translations, the Boolean and/or arithmetic logic steps or operations, and the selection and combinations of the random words are all preformed for a character of the key everytime the instructions of the loop are executed.

The first instruction in the loop, line 8600 of the program (Block 11 of FIG. 3), uses the random byte table (lines 14100 to 15700) to translate the last L characters of the key. The instruction on line 8700 reduces the value of L by one (Block 12). The instructions on lines 8800 and 8900 select the Jth byte from the translated key and do an "exclusive or" operation with the current value of D (initially zero). This corresponds to Block 13, FIG. 3. Then the instructions on lines 9100 and 9200 use the value of D (relative address) to extract a four byte word from random table (Block 14). This random word is added to H (line 9400 and Block 15). The value of J is increased by one and a test is made to determine if all the characters of the key have been operated on (line 9700 and Block 17). The number of characters in the key is the number of times the loop instructions are executed.

In terms of the functions described previously, for individual characters of the key there is an initial translation, an exclusive or operation involving the various translated characters, repeated translations, and the use of the values obtained from the exclusive or operations to select a random word. The random words obtained for each key character are all added together to obtain the single final randomized word resulting from the transformation procedure.

The instructions from lines 10300 to 11300 scale the final random word to produce a relative bin address (Block 6 of FIG. 2) in the range specified for the records of the file. Then the instructions on the lines from 11800 to 12600 store the relative bin address in the calling program and return control to the calling program. The hasher module will be called again when another key-to-address transformation is requested by any calling program.

The invention will be further illustrated by a specific, though somewhat simplistic, example. Assume that thirty records are identified by three-character keys. It has been decided that eleven bins should be used to store these records. Using the embodiment illustrated by the program of Table I, the relative bin address for a key having the value X6C would be determined in the following manner.

With the EBCDIC code the internal computer hex representation of the key is E7, F6, C3. The length of the key, L=3 and the number of bins is 11. These three items of information are provided to the hashing module by the calling program. Then, in algebraic terms, the values of D, H and J are set equal to zero. The hash loop will be executed three times.

The first step in the first execution of the loop is to translate the key. The decimal equivalents for the key values are 231, 246 and 195. The translation instruction extracts the (last) L=3 characters at these addresses in the byte table (FIG. 1) and replaces the E7, F6, C3 with 73, 43, A1. The value of L is reduced to 2. Since J=0, the first byte, 73, is exclusive or'ed with D. The initial value of D is also zero. Therefore the operation yields D=73 (decimal 115). Now the four-byte word at address 115 is extracted from the table. It has the value A2, 5B, B6, 1C. This is added to H=0 to yield H=A2, 5B, B6, 1C. As the final step in the loop the value of J is increased to 1 and status is tested. Since the loop has only been transversed once the procedure is repeated.

Now, in the second execution, L=2, so only the last two characters are translated and the key 73, 43, A1 (decimals 115, 67, 161) is replaced with 73, 0A, 4C. One is subtracted from L to give L=1. The Jth byte, 0A is exclusive or'ed with D=73 to yield hex 79 (decimal 121). The four bytes at address 121 are 09, D3, 5A, 21. This value is added to H=A2, 5B, B6, 1C to yield H=AC, 2F, 10, 3D. Then one is added to J to give J=2 and the status is tested. One more execution of the loop is required.

In the final repetition only the last (L=1) character is translated. The key now is 73, 0A, BF, and L is reduced to zero. Since J=2, the last byte BF is exclusive or'ed with D=79 to give hex C6 (decimal 198). This value is then used to address the random byte table and to extract the four byte word 64, 52, 60, 55. Adding this to the current value of H gives 10, 81, 70, 92. Overflows on these additions are ignored (dropped). The status test shows that this is the last execution required for the hash loop. The final value, H=10, 81, 70, 92, is the result of the hashing procedure.

Using the reduction (or scaling) technique given in the listing, and the value of 11 for the number of bins, the relative bin number is calculated. It's value of 0 (decimal) is the result of the key-to-address transformation and is the value passed back to the calling program. Thus the record with the key X6C will be stored in bin number 0 where the 11 bins are identified with the numbers 0, 1, 2, . . . 10. The key for each of the records in the file will be transformed in the same manner. It was assumed that the file consisted of 30 records and that they would be distributed randomly through the 11 bins.

The specific embodiment of the invention described herein was adapted to IBM/360 series computers. It is obvious therefore that variations can be made in the case of other computers. For instance the byte table need not contain 256 spaces, but can have a number appropriate for the computer. The characters assigned to these spaces will also be a matter of choice. Thus in making up the random byte table values in any computer code can be assigned randomly to the spaces.

Since the combining and scaling steps are well known operations and not the essence of this invention any of those discussed can be used. Thus whereas the Boolean EXCLUSIVE OR is preferred as the mathematical operator for combining each translation with the previous translation in hash looping, any logical Boolean and/or logical arithmetic operation, such as AND, OR, addition, subtraction, and multiplication can be employed. It has already been stated that when the four-byte-word numbers are combined the resulting single number can be converted into the final address by any of the known scaling transformation methods. The only requirement is that the result must be in a range corresponding to the number of storage bins. It should be pointed out that various logical and/or mathematical operations can also be used in combining the four-byte-word numbers. Although addition is preferred, any mathematical step yielding a single number can be used.

This single number will be a random address. When the invention is used in computer storage the ultimate number is a bin or storage address. It is used to store a new document or record, and it is also used to retrieve a a record previously stored at that address. The document or record which has been retrieved may be changed by additions or deletions, or it may be merely read. If it is altered the revised record will be stored at the designated address. Apart from the computer the random number deriving process of the invention will find use in, statistics, games and the like. Since such uses and other variations will be obvious to one skilled in the art, such ramifications are deemed to be within the scope of this invention.