Method and system for searching compressed data

• US 5,737,733 A
• Filed: 09/26/1996
• Issued: 04/07/1998
• Est. Priority Date: 06/30/1993
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Eller, Marlin Jay
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Von Buhr, Maria N.
• Application Number:
  US08/721,558
• Time in Patent Office: 558 Days
• Field of Search: 364/DIG. 1, 364/DIG. 2, 364/715.02, 364/715.03, 395/600, 395/603, 395/606, 395/612, 341/50, 341/55, 341/67, 341/90, 341/106
• US Class Current: 707/708
• CPC Class Codes: G06F 16/3331 Query processing
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A method and system for searching a compressed document while a plurality of character strings stored in the compressed document are stored in a compressed code. A query request is received, the query request is converted into the compressed code, and the converted query request is compared with the compressed codes stored in the compressed document. The initiator of the query request is then informed about the results of the comparison.

Claims

1. An apparatus for searching a compressed document comprised of a plurality of variable length compressed codes which represent an uncompressed document, each variable length compressed code having a length indicator which indicates the length of the variable length compressed code, the apparatus comprising:

means for receiving a query request in an uncompressed code;

means for converting the query request from the uncompressed code into a converted query request of one of the plurality of variable length compressed codes;

means for determining the length of the converted query request;

means for comparing the converted query request with the variable length compressed codes of the compressed document, to determine if variable length compressed codes of the compressed document match the converted query request, wherein the converted query request is only compared with those variable length compressed codes whose length is equal to the length of the converted query request, and

means for responding to the determination that there is a match between the variable length compressed codes of the compressed document and the converted query request.

2. A method for searching a compressed document comprised of a plurality of variable length compressed codes which represent an uncompressed document, each variable length compressed code having a length indicator which indicates the length of the variable length compressed code, the method comprising the steps of:

receiving a query request in an uncompressed code;

converting the query request from the uncompressed code into a converted query request of one of the plurality of variable length compressed codes;

means for determining the length of the converted query request;

comparing the converted query request with the variable length compressed codes of the compressed document, to determine which variable length compressed codes of the compressed document match the converted query request, wherein the converted query request is only compared with those variable length compressed codes whose length is equal to the length of the converted query request; and

responding to the determination that there is a match between the variable length compressed codes of the compressed document and the converted query request.

3. A computer-readable memory device for controlling a computer system to perform the steps of claim 2.

4. An apparatus for searching a compressed document comprised of a plurality of fixed length compressed codes which represent an uncompressed document, the apparatus comprising:

means for receiving a query request in a uncompressed code;

means for converting the query request from the uncompressed code into a converted query request of the fixed length compressed code;

means for comparing the converted query request with the fixed length compressed codes of the compressed document to determine which fixed length compressed codes of the compressed document match the converted query request; and

means for responding to the determination that there is a match between the fixed length compressed codes of the compressed document and the converted query request.

5. The apparatus of claim 4 wherein the plurality of character strings stored in the compressed document include character strings of letters with capitalization classes, the capitalization classes including an all caps capitalization class wherein each letter of the character string is a capital letter, a first cap capitalization class wherein only the first letter of the character string is capitalized, and a no caps capitalization class wherein all of the letters of the character string are lower case letters, and wherein the converting means includes,

parsing means for retrieving from the query request a set of non-letter characters until a letter character is encountered, and a set of letter characters while the retrieved letter characters belong to one of the capitalization classes,

first means for converting the retrieved set of non-characters into the fixed length compressed code, and

second means for converting the retrieved set of letters into the fixed length compressed code which includes a representation of the capitalization class of the retrieved set of letters.

6. The apparatus of claim 4 wherein the converting means further comprises a dictionary for storing codes that represent character strings wherein the fixed length compressed code of the converted query request is retrieved from the dictionary, the dictionary including,

a word section which stores a plurality of uncompressed codes and associated fixed length compressed codes, with each uncompressed code and associated compressed code representing a word,

a pairs section which stores a variety of uncompressed codes and associated fixed length compressed codes, with each uncompressed code and associated compressed code representing a pair of letters,

a formatting and punctuation section which stores a plurality of uncompressed codes and associated fixed length compressed codes, with each uncompressed code and associated fixed length compressed code representing one of a punctuation character and a formatting pattern, and

an ASCII section which stores a plurality of uncompressed codes and associated fixed length compressed codes, with each uncompressed code and associated fixed length compressed code representing an ASCII character.

7. The apparatus of claim 4 wherein the converting means converts the query request into a single fixed length compressed code so that the comparing means can end comparing after the converted query request matches one of the fixed length compressed codes stored in the compressed document.

8. An apparatus for retrieving data, the apparatus comprising:

a compressed document including a plurality of character strings, each character string being stored in a compressed code;

means for receiving a query request; and

means for searching for the query request in the compressed document while the plurality of character strings stored in the compressed document are stored in the compressed code.

9. An apparatus for searching a compressed document comprised of a plurality of variable length compressed codes which represent an uncompressed document, the apparatus comprising:

means for receiving a query request in an uncompressed code;

means for converting the query from the uncompressed code into a converted query request of the variable length compressed code;

means for comparing the converted query request with the variable length compressed codes of the compressed document, to determine if variable length compressed codes of the compressed document match the converted query request; and

means for responding to the determination that there is a match between the variable length compressed codes of the compressed document and the converted query request.

10. The apparatus of claim 9 wherein each variable length compressed code includes a length indicator which indicates the length of the variable length compressed code.

11. The apparatus of claim 9 further including means for determining the length of the converted query request.

12. The apparatus of claim 11 wherein the comparing means only compares the converted query request with those variable length compressed codes whose determined length is equal to the length of the converted query request.

13. A method for searching a compressed document while a plurality of character strings stored in the compressed document are stored in a fixed length compressed code, the method comprising:

receiving a query request in a uncompressed code, wherein the uncompressed code represents the query request using a plurality of bits;

converting the query request from the uncompressed code into a converted query request of the fixed length compressed code;

comparing the converted query request with the plurality of fixed length compressed codes stored in the compressed document to determine which fixed length compressed codes from the compressed document match the converted query request; and

responding to the determination that there is a match between the fixed length compressed codes of the compressed document and the converted query request.

14. The method of claim 13 wherein the plurality of character strings stored in the compressed document include character strings of letters with capitalization classes, the capitalization classes including an all caps capitalization class wherein each letter of the character string is a capital letter, a first cap capitalization class wherein only the first letter of the character string is capitalized, and a no caps capitalization class wherein all of the letters of the character string are lower case letters, and wherein the converting includes,

retrieving from the query request a set of non-letter characters until a letter character is encountered,

retrieving a set of letter characters while the retrieved letter characters belong to one of the capitalization classes, converting the retrieved set of non-characters into the fixed length compressed code, and

converting the retrieved set of letters into the fixed length compressed code which includes a representation of the capitalization class of the retrieved set of letters.

15. The method of claim 13 wherein the converting converts the query request into a single fixed length compressed code so that the step of comparing stops comparing the converted query request with the plurality of fixed length compressed codes after the converted query request matches one of the plurality of fixed length compressed codes stored in the compressed document.

16. A method for retrieving data, the method comprising:

providing a compressed document including a plurality of character strings stored in a fixed length compressed code;

providing a query request in a fixed length compressed code; and

searching for the query request in the compressed document while the plurality of character strings stored in the compressed document are stored in the fixed length compressed code.

17. A method for searching a compressed document comprised of a plurality of variable length compressed codes which represent an uncompressed document, the method comprising:

receiving a query request in an uncompressed code;

converting the query from the uncompressed code into a converted query request of the variable length compressed code;

comparing the converted query request with the variable length compressed codes of the compressed document, to determine which variable length compressed codes of the compressed document match the converted query request; and

responding to the determination that there is a match between the variable length compressed codes of the compressed document and the converted query request.

18. The method of claim 17 wherein each variable length compressed code includes a size code which indicates the length of the variable length compressed code.

19. The method of claim 17 further including determining the length of the converted query request.

20. The method of claim 17 wherein comparing only compares the converted query request with those variable length compressed codes whose determined length is equal to the length of the converted query request.

21. A computer-readable medium containing instructions for causing a computer system to retrieve data by:

providing a compressed document including a plurality of character strings represented in a compressed form;

receiving a query request to locate a character string within the compressed document;

converting the character string to a compressed form; and

searching for an occurrence of the character string in compressed form in the compressed document whereby the compressed document is searched without decompressing the character strings of the document.

22. A computer-readable medium containing instructions for causing a computer system to search a compressed document comprised of a plurality of variable length compressed codes which represent an uncompressed document by:

receiving a query request in an uncompressed code;

converting the query request from the uncompressed code into a converted query request of the variable length compressed code;

comparing the converted query request with the variable length compressed codes of the compressed document to determine which variable length compressed codes of the compressed document match the converted query request; and

responding to the determination that there is a match between the variable length compressed codes of the compressed document and the converted query request whereby the compressed document can be queried without decompressing the document.

23. The computer-readable medium of claim 22 wherein each variable length compressed code includes a size code which indicates the length of the variable length compressed code.

24. The computer-readable medium of claim 22 further including determining the length of the converted query request.

25. The computer-readable medium of claim 22 wherein comparing only compares the converted query request with those variable length compressed codes whose determined length is equal to the length of the converted query request.