Two-Pass Hash Extraction of Text Strings

• US 20090089048A1
• Filed: 09/28/2007
• Published: 04/02/2009
• Est. Priority Date: 09/28/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Pouzin, Dominic
• Granted Patent: US 8,078,454 B2
• Time in Patent Office: Days
• US Class Current: 704/10
• CPC Class Codes: G06F 40/143 Markup, e.g. Standard Generalized Markup Language [SGML] or Document Type Definition [DTD]
• CPC Class Codes: G06F 40/242 Dictionaries
• CPC Class Codes: H03M 7/3084 using adaptive string matching, e.g. the Lempel-Ziv method
• CPC Class Codes: H03M 7/3088 employing the use of a dictionary, e.g. LZ78

Abstract

Data compression and key word recognition may be provided. A first pass may walk a text string, generate terms, and calculate a hash value for each generated term. For each hash value, a hash bucket may be created where an associated occurrence count may be maintained. The hash buckets may be sorted by occurrence count and a few top buckets may be kept. Once those top buckets are known, a second pass may walk the text string, generate terms, and calculate a hash value for each term. If the hash values of terms match hash values of one of the kept buckets, then the term may be considered a frequent term. Consequently, the term may be added to a dictionary along with a corresponding frequency count. Then, the dictionary may be examined to remove terms that may not be frequent, but appeared due to hash collisions.

Claims

1. A method for recognizing text, the method comprising:

generating a plurality of generated terms used in a text string;

calculating a plurality of hash values from the plurality of generated terms;

creating a plurality of hash buckets respectively corresponding to the plurality of hash values;

maintaining a plurality of occurrence count values respectively corresponding to the plurality of hash buckets, each of the plurality of occurrence count values respectively indicating a number of times ones of the plurality of generated terms occur in the text string having a hash value that respectively correspond to the plurality of occurrence count values'"'"' respective hash bucket;

discarding ones of the plurality of hash buckets having respective occurrence count values less than a first predetermined value; and

adding dictionary terms to a dictionary, the dictionary terms comprising ones of the plurality of generated terms having respective hash values corresponding to any of the plurality of hash values respectively corresponding to the remaining plurality of hash buckets, the dictionary including a plurality of frequency count values respectively indicating the number of times each of the dictionary terms occurred in the text string.

2. The method of claim 1, further comprising ranking the dictionary terms.

3. The method of claim 1, further comprising ranking the dictionary terms using an evaluation function.

4. The method of claim 1, further comprising ranking the dictionary terms using an evaluation function configured for data compression.

5. The method of claim 1, further comprising ranking the dictionary terms using an evaluation function configured for data compression wherein the dictionary terms are ranked based upon a plurality respective indexes respectively corresponding to each of the dictionary terms, each of the plurality indexes respectively comprising the frequency count value of each respective dictionary term multiplied by a length of each respective dictionary term.

6. The method of claim 1, further comprising ranking the dictionary terms using an evaluation function configured for keyword recognition.

7. The method of claim 1, further comprising ranking the dictionary terms using an evaluation function configured for keyword recognition wherein the dictionary terms are ranked based upon their respective frequency count values.

8. The method of claim 1, further comprising using the dictionary to determine which of the generated terms to compress in the text string.

9. The method of claim 1, further comprising using the dictionary to determine which of the generated terms to characterize as keywords.

10. The method of claim 1, further comprising removing dictionary terms from the dictionary that have corresponding frequency count values less than a second predetermined value.

11. The method of claim 1, wherein generating the plurality of generated terms used in the text string comprises generating the plurality of generated terms used in the text string wherein each of the plurality of generated terms comprise individual strings.

12. The method of claim 1, wherein generating the plurality of generated terms used in the text string comprises generating the plurality of generated terms used in the text string wherein at least a portion of the plurality of generated terms comprise substrings.

13. The method of claim 1, wherein calculating the plurality of hash values from the plurality of generated terms comprises calculating the plurality of hash values based upon a perfect hash algorithm.

14. A computer-readable medium which stores a set of instructions which when executed performs a method for recognizing text, the method executed by the set of instructions comprising:

creating a plurality of hash buckets respectively corresponding to a plurality of hash values corresponding to a plurality of generated terms in a text string wherein at least a portion of the plurality of generated terms comprise sub-strings;

maintaining a plurality of occurrence count values respectively corresponding to the plurality of hash buckets, each of the plurality of occurrence count values respectively indicating a number of times ones of the plurality of generated terms occur in the text string having a hash value that respectively correspond to the plurality of occurrence count values'"'"' respective hash bucket;

discarding ones of the plurality of hash buckets having respective occurrence count values less than a first predetermined value;

adding dictionary terms to a dictionary, the dictionary terms comprising ones of the plurality of generated terms having respective hash values corresponding to any of the plurality of hash values respectively corresponding to the remaining plurality of hash buckets, the dictionary including a plurality of frequency count values respectively indicating the number of times each of the dictionary terms occurred in the text string; and

ranking the dictionary terms using an evaluation function configured for data compression wherein the dictionary terms are ranked based upon a plurality respective indexes respectively corresponding to each of the dictionary terms, each of the plurality indexes respectively comprising the frequency count value of each respective dictionary term multiplied by a length of each respective dictionary term.

15. The computer-readable medium of claim 14, further comprising using the dictionary to determine which of the generated terms to compress in the text string.

16. The computer-readable medium of claim 14, further comprising removing dictionary terms from the dictionary that have corresponding frequency count values less than a second predetermined value.

17. The computer-readable medium of claim 14, further comprising calculating the plurality of hash values based upon a perfect hash algorithm.

18. A system for recognizing text, the system comprising:

a memory storage; and

a processing unit coupled to the memory storage, wherein the processing unit is operative to;

create a plurality of hash buckets respectively corresponding to a plurality of hash values corresponding to a plurality of generated terms in a text string wherein each of the plurality of generated terms comprise individual strings;

maintain a plurality of occurrence count values respectively corresponding to the plurality of hash buckets, each of the plurality of occurrence count values respectively indicating a number of times ones of the plurality of generated terms occur in the text string having a hash value that respectively correspond to the plurality of occurrence count values'"'"' respective hash bucket;

discard ones of the plurality of hash buckets having respective occurrence count values less than a first predetermined value;

add dictionary terms to a dictionary, the dictionary terms comprising ones of the plurality of generated terms having respective hash values corresponding to any of the plurality of hash values respectively corresponding to the remaining plurality of hash buckets, the dictionary including a plurality of frequency count values respectively indicating the number of times each of the dictionary terms occurred in the text string; and

rank the dictionary terms using an evaluation function configured for keyword recognition wherein the dictionary terms are ranked based upon their respective frequency count values.

19. The system of claim 18, wherein the processing unit is further operative to remove dictionary terms from the dictionary that have corresponding frequency count values less than a second predetermined value.

20. The system of claim 18, wherein the processing unit is further operative to calculate the plurality of hash values based upon a perfect hash algorithm.