Lexical cache

• US 7,031,985 B1
• Filed: 03/08/1999
• Issued: 04/18/2006
• Est. Priority Date: 03/08/1999
• Status: Expired due to Term

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Pecheny, Boris
• Primary Examiner(s): Alam, Shahid
• Assistant Examiner(s): FLEURANTIN, JEAN B
• Application Number:
  US09/263,068
• Time in Patent Office: 2,598 Days
• Field of Search: 707200-206, 707100-1041, 707 1- 10, 704 9- 10, 704/1, 709/215, 711/1, 711/113, 711/118
• US Class Current: 1/1
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database

Abstract

A lexical cache comprises a collection of lexical containers, such as tuned hash table, that are organized according to the length of the keys to be looked up in the lexical cache. In one embodiment, the word is compressed to generate a key. Based on the length of the key and optionally a prefix, a hash table is identified from among the collection of hash tables. A hash value is computed for the key, and the hash table is searched for a slot holding a key value matching the key. If a slot having a key value matching the key was found, then the relative position of the key value within the corresponding sequence of slots is moved toward the beginning of the corresponding sequence.

Claims

1. A method of searching for a string in a lexical cache, comprising the computer-implemented steps of:

generating a key based on the string;

selecting a lexical container from among a plurality of lexical containers based on a length of the key, said lexical containers associated with respective key lengths and configured to hold respective maximum numbers of entries based on the respective key lengths; and

searching the selected lexical container for an entry associated with the string based on the key,

wherein at least one of the lexical containers is configured to hold a different maximum number of entries than at least another one of the lexical containers.

2. The method of claim 1, wherein the step of generating a key based on the string includes the step of compressing the string to produce the key.

3. The method of claim 2, wherein the step of compressing the string to produce the key includes the step of performing an n-gram compression on the string.

4. The method of claim 1, wherein the step of generating a key based on the string includes the step of using the string as the key.

5. The method of claim 1, wherein the step of selecting a lexical container includes the steps of:

generating a prefix based on the key; and

selecting the lexical container from among the plurality of the lexical containers based on the length of the key and the prefix.

6. The method of claim 1, wherein:

a first lexical container of the lexical containers is associated with a first key length;

a second lexical container of the lexical containers is associated with a second key length;

the first key length is less than the second key length; and

the first lexical container is configured to hold more entries than the second lexical container.

7. The method of claim 1, wherein the step of searching the selected lexical container includes searching only the selected lexical container.

8. A method of searching for a string in a lexical cache, comprising the computer-implemented steps of:

generating a key based on the string;

identifying a hash table from among a plurality of hash tables based on the length of the key, said hash table containing sequences of slots for holding entries associated with strings, each of said sequences of slots corresponding to a respective hash value, wherein at least one of the hash tables is configured to hold a different number of slots than at least another one of the hash tables;

computing a hash value based on the key; and

searching the hash table based on the hash value for a slot holding an entry associated with said string.

9. The method of claim 8, wherein the step of computing a hash value based on the key includes the step of computing the hash value based on the key and a prime number associated with the hash table.

10. The method of claim 9, wherein the step of searching the hash table based on the hash value includes the steps of:

indexing one or more fixed regions of the hash table, each of the fixed regions having the prime number of slots, based on the hash value to identify one or more respective slots; and

inspecting the one or more respective slots for a respective key value matching the key.

11. The method of claim 10, wherein the step of searching the hash table further includes the step of searching for the key in a linked list of slots stored in an expansion region of the hash table, if the key was not found in the one or more respective slots for the key.

12. The method of claim 8, further including the step of, if an entry for the string is not found at a first slot that corresponds to the hash value, but is found in a slot that belongs to a sequence of slots that correspond to keys that produce said hash value, then moving a relative position of the entry for the string within the sequence of slots toward the beginning of the sequence of slots.

13. The method of claim 8, further comprising the step of initializing a descriptor for the hash table, said descriptor storing a reference to the hash table and parameters for the hash table;

wherein the step of identifying a hash table includes the step of identifying a descriptor indicating the hash table and a prime number.

14. The method of claim 13, wherein the step of initializing a descriptor for the hash table includes the step of initializing a prime number for use in computing a hash value.

15. The method of claim 13, wherein the step of initializing a descriptor for the hash table includes the step of initializing a maximum number of slots for the hash table.

16. The method of claim 13, wherein the step of initializing a descriptor for the hash table includes the step of initializing a maximum length of the sequences of slots for the hash table.

17. A method of searching for a string in a lexical cache, comprising the computer-implemented steps of:

compressing the string to generate a key;

identifying a hash table from among a plurality of hash tables based on a length of the key, said hash table containing sequences of slots for holding respective key values, each of said sequences of slots corresponding to a respective hash value and a number of slots being based on a respective key length, wherein at least one of the hash tables is configured to hold a different number of slots than at least another one of the hash tables;

computing a hash value based on the key;

using said hash value to locate a beginning of the particular sequence of slots that correspond to said hash value;

searching the particular sequence of slots for a slot holding a key value matching the key; and

if a slot having a key value matching the key is found in the particular sequence of slots, but is not at the beginning of said particular sequence of slots, then moving a relative position of the key value within the particular sequence of slots toward the beginning of the particular sequence of slots.

18. A computer-readable storage medium bearing instructions for searching for a string in a lexical cache, said instructions arranged, when executed by one or more processors, to cause the one or more processors to perform the steps of:

generating a key based on the string;

selecting a lexical container from among a plurality of lexical containers based on a length of the key, said lexical containers associated with respective key lengths and configured to hold respective maximum numbers of entries based on the respective key lengths; and

searching the selected lexical container for an entry associated with the string based on the key,

wherein at least one of the lexical containers is configured to hold a different maximum number of entries than at least another one of the lexical containers.

19. The computer-readable medium of claim 18, wherein the step of generating a key based on the string includes the step of compressing the string to produce the key.

20. The computer-readable medium of claim 19, wherein the step of compressing the string to produce the key includes the step of performing an n-gram compression on the string.

21. The computer-readable medium of claim 18, wherein the step of generating a key based on the string includes the step of using the string as the key.

22. The computer-readable medium of claim 18, wherein the step of selecting a lexical container includes the steps of:

generating a prefix based on the key; and

selecting the lexical container from among the plurality of the lexical containers based on the length of the key and the prefix.

23. A computer-readable storage medium bearing instructions for searching for a string in a lexical cache, said instructions arranged, when executed by one or more processors, to cause the one or more processors to perform the steps of:

generating a key based on the string;

identifying a hash table from among a plurality of hash tables based on the length of the key, said hash table containing sequences of slots for holding entries associated with strings, each of said sequences of slots corresponding to a respective hash value, wherein at least one of the hash tables is configured to hold a different number of slots than at least another one of the hash tables;

computing a hash value based on the key; and

searching the hash table based on the hash value for a slot holding an entry associated with said string.

24. The computer-readable medium of claim 23, wherein the step of computing a hash value based on the key includes the step of computing the hash value based on the key and a prime number associated with the hash table.

25. The computer-readable medium of claim 24, wherein the step of searching the hash table based on the hash value includes the steps of:

indexing one or more fixed regions of the hash table, each of the fixed regions having the prime number of slots, based on the hash value to identify one or more respective slots; and

inspecting the one or more respective slots for a respective key value matching the key.

26. The computer-readable medium of claim 25, wherein the step of searching the hash table further includes the step of searching for the key in a linked list of slots stored in an expansion region of the hash table, if the key was not found in the one or more respective slots for the key.

27. The computer-readable medium of claim 23, wherein said instructions are further arranged to cause the one or more processors to perform the step of, if an entry for the string is not found at a first slot that corresponds to the hash value, but is found in a slot that belongs to a sequence of slots that correspond to keys that produce said hash value, then moving a relative position of the entry for the string within the sequence of slots toward the beginning of the sequence of slots.

28. The computer-readable medium of claim 23, wherein said instructions are further arranged to cause the one or more processors to perform the step of initializing a descriptor for the hash table, said descriptor storing a reference to the hash table and parameters for the hash table;

wherein the step of identifying a hash table includes the step of identifying a descriptor indicating the hash table and a prime number.

29. The computer-readable medium of claim 28, wherein the step of initializing a descriptor for the hash table includes the step of initializing a prime number for use in computing a hash value.

30. The computer-readable medium of claim 28, wherein the step of initializing a descriptor for the hash table includes the step of initializing a maximum number of slots for the hash table.

31. The computer-readable medium of claim 28, wherein the step of initializing a descriptor for the hash table includes the step of initializing a maximum length of the sequences of slots for the hash table.

32. A computer-readable storage medium bearing instructions for searching for a string in a lexical cache, said instructions arranged, when executed by one or more processors, to cause the one or more processors to perform the steps of:

compressing the string to generate a key;

identifying a hash table from among a plurality of hash tables based on a length of the key, said hash table containing sequences of slots for holding respective key values, each of said sequences of slots corresponding to a respective hash value and a number of slots being based on a respective key length, wherein at least one of the hash tables is configured to hold a different number of slots than at least another one of the hash tables;

computing a hash value based on the key;

using said hash value to locate a beginning of the particular sequence of slots that correspond to said hash value;

searching the particular sequence of slots for a slot holding a key value matching the key; and

if a slot having a key value matching the key is found in the particular sequence of slots, but is not at the beginning of said particular sequence of slots, then moving a relative position of the key value within the particular sequence of slots toward the beginning of the particular sequence of slots.

33. A method of storing a string in a lexical cache, comprising the computer-implemented steps of:

generating a key based on the string;

selecting a lexical container from among a plurality of lexical containers based on a length of the key, said lexical containers are associated with respective key lengths and configured to hold respective maximum numbers of entries based on the respective key lengths; and

storing the string in an entry in the selected lexical container based on the key,

wherein at least one of the lexical containers is configured to hold a different maximum number of entries than at least another one of the lexical containers.

34. The method of claim 33, wherein:

a first lexical container of the lexical containers is associated with a first key length;

a second lexical container of the lexical containers is associated with a second key length;

the first key length is less than the second key length; and

the first lexical container is configured to hold more entries than the second lexical container.

35. A computer-readable storage medium bearing instructions for storing a string in a lexical cache, said instructions arranged, when executed by one or more processors, to cause the one or more processors to perform the steps of:

generating a key based on the string;

selecting a lexical container from among a plurality of lexical containers based on a length of the key, wherein the lexical containers are associated with respective key lengths and configured to hold respective maximum numbers of entries based on the respective key lengths; and

storing the string in an entry in the selected lexical container based on the key, wherein at least one of the lexical containers is configured to hold a different maximum number of entries than at least another one of the lexical containers.

36. A method of providing a lexical cache, comprising the computer-implemented steps of:

allocating a plurality of lexical containers each configured to contain a respective maximum number of entries based on a function that includes a term that is inversely proportional to a logarithm of a key length associated with the lexical containers; and

searching for one of the entries associated with a string within one of the plurality of lexical containers corresponding to a key generated based on the string.