US5737733A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and system for searching compressed data
Assignee: Microsoft Technology Licensing LLC
•
Filing: 1996-09-26
•
Granted: 1998-04-07
•
Expires: 2016-09-26
Abstract
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.
Inventors
- 👤 Marlin Jay Eller
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 12:00
CPC Classifications
H; H03; H03M; H03M7/00; H03M7/30; G; G06; G06F; G06F16/00; G06F16/30; G06F16/33; G06F16/3331; G06F16/90; G06F16/903; G06F16/90335; G06F16/90344; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99941; Y10S707/99942
Claims Analysis
Total Claims: 35
Claim 1
Independent Claim
174 words
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.
Claim 2
Independent Claim
174 words
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.
Claim 3
Independent Claim
169 words
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.
Claim 4
Independent Claim
169 words
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.
Claim 5
Dependent Claim
16 words
A computer-readable memory device for controlling a computer system to perform the steps of claim 2.
Claim 6
Independent Claim
115 words
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.
Claim 7
Independent Claim
115 words
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.
Claim 8
Dependent Claim
167 words
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.
Claim 9
Dependent Claim
164 words
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.
Claim 10
Dependent Claim
46 words
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.
Claim 11
Independent Claim
61 words
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.
Claim 12
Independent Claim
61 words
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.
Claim 13
Independent Claim
114 words
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.
Claim 14
Independent Claim
114 words
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.
Claim 15
Dependent Claim
25 words
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.
Claim 16
Dependent Claim
17 words
The apparatus of claim 9 further including means for determining the length of the converted query request.
Claim 17
Dependent Claim
34 words
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.
Claim 18
Independent Claim
128 words
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.
Claim 19
Independent Claim
128 words
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.
Claim 20
Dependent Claim
157 words
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.
Claim 21
Dependent Claim
59 words
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.
Claim 22
Independent Claim
64 words
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.
Claim 23
Independent Claim
64 words
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.
Claim 24
Independent Claim
106 words
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.
Claim 25
Independent Claim
106 words
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.
Claim 26
Dependent Claim
25 words
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.
Claim 27
Dependent Claim
15 words
The method of claim 17 further including determining the length of the converted query request.
Claim 28
Dependent Claim
32 words
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.
Claim 29
Dependent Claim
80 words
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.
Claim 30
Dependent Claim
80 words
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.
Claim 31
Dependent Claim
124 words
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.
Claim 32
Dependent Claim
124 words
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.
Claim 33
Dependent Claim
26 words
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.
Claim 34
Dependent Claim
16 words
The computer-readable medium of claim 22 further including determining the length of the converted query request.
Claim 35
Dependent Claim
33 words
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.
References Cited (Backward Citations)
US3651483A
Cited
US3593309A
Cited
US3643226A
Cited
US4617663A
Cited
US4701851A
Cited
US4650927A
Cited
US5347632A
Cited
US5191635A
Cited
US5274805A
Cited
US5276868A
Cited
US5333313A
Cited
US5253341A
Cited
US5163094A
Cited
US5414838A
Cited
US5337233A
Cited
US5325091A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-04-06 | 2001-10-06 | 2002-04-07 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-04-06 | 2005-10-06 | 2006-04-07 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-04-06 | 2009-10-06 | 2010-04-07 | $7700.00 | Window Closed / Lapsed |