Block Entropy Encoding for Word Compression

• US 20130013574A1
• Filed: 07/06/2011
• Published: 01/10/2013
• Est. Priority Date: 07/06/2011
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Wu, Zhao
• Granted Patent: US 8,694,474 B2
• Time in Patent Office: Days
• US Class Current: 707/693
• CPC Class Codes: G06F 16/00 Information retrieval; Database structures therefor; File system structures therefor
• CPC Class Codes: H03M 7/3077 Sorting

Abstract

A computer-implemented method, computer-readable media, and a computerized system to compress words are provided. The computerized system includes a compression engine that compresses a list of words. The compression engine generates a symbol list from the list of words, decomposes the words using the symbol list and a cost function, and encodes the decomposed words. The words may be from a search index. The compression engine may be utilized to reduce the size of the search index and improve efficiency.

Claims

1. A computer-implemented method for compressing a list of words, the method comprising:

parsing all words to create a symbol list;

identifying substrings in each word by decomposing the word based on the symbol list;

encoding the identified substrings.

2. The computer-implemented method of claim 1, wherein parsing all words to create a symbol list further comprises:

generating a list of bi-grams from each word in the list of words;

storing the bi-grams in the symbol list;

counting occurrence of each bi-gram;

associating the occurrence count with the bi-gram;

determining whether the occurrence count is above a specified threshold; and

creating a super-gram that represents the bi-gram when the occurrence count is above the specified threshold.

3. The computer-implemented method of claim 2, further comprising:

replacing the bi-gram with the super-gram in the symbol list;

treating the super-gram as a single character;

forming new bi-grams using the super-gram; and

recalculating an occurrence count for the new bi-grams.

4. The computer-implemented method of claim 2, further comprising:

compressing the list of words using the symbol list and occurrence count.

5. The computer-implemented method of claim 4, wherein compressing the index comprises:

performing a Huffman encoding on the words in the index using the symbol list and occurrence count.

6. The computer-implemented method of claim 4, wherein compressing the index comprises:

performing an arithmetic encoding on the words in the index using the symbol list and occurrence count.

7. One or more computer-readable media storing instructions to perform a method for locating common n-grams in a list of terms, the method comprising:

generating n-grams for each word in the list;

calculating occurrence counts of each n-gram;

determining a cost of n-gram selection as a function of n-gram statistics that include the occurrence count of each n-gram; and

selecting n-grams that minimize the cost of n-gram selection as a function of n-gram statistics.

8. The media of claim 7, further comprising:

filtering n-grams having occurrence below a threshold.

9. The media of claim 8, wherein dynamic programming is utilized to select n-grams that minimize the cost of n-gram selection as a function of n-gram statistics.

10. The media of claim 8, further comprising:

storing the selected n-grams in a symbol list.

11. The media of claim 8, further comprising:

compressing the index using the symbol list and occurrence count.

12. The media of claim 11, wherein compressing the index comprises:

performing a Huffman encoding on the words in the index using the symbol list and occurrence count.

13. The media of claim 11, wherein compressing the index comprises:

performing an arithmetic encoding on the words in the index using the symbol list and occurrence count.

14. The media of claim 8, further comprising:

weighing the n-gram statistics as a percentage of the decompression progress.

15. The media of claim 14, wherein each weight is applied to a window of n-grams.

16. A computerized search system, the search system comprising:

a compression engine configured to provide access to a compressed search index, wherein the compression engine receives a search request, decomposes search terms in the search request based on a symbol list associated with the search index, and encodes the search request in accordance with the symbol list.

17. The system of claim 16, wherein the compression engine transmit the encoded search request to the search engine, which utilizes the encoded search request to traverse the compressed search index and determine whether one or more index terms match the search terms in the encoded search request.

18. The system of claim 17, wherein the search engine receives posting lists associated with index terms that match the search terms in the encoded search request and generates a search results page based on the posting lists identified by the compression engine.