Efficient method for compressing, storing, searching and transmitting natural language text

• US 5,991,713 A
• Filed: 11/26/1997
• Issued: 11/23/1999
• Est. Priority Date: 11/26/1997
• Status: Expired due to Term

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Fuller, Glen, Unger, Jay
• Primary Examiner(s): Thomas, Joseph
• Assistant Examiner(s): EDOUARD, PATRICK NESTOR
• Application Number:
  US08/979,181
• Time in Patent Office: 727 Days
• Field of Search: 704/1, 704/2, 704/7, 704/8-10, 707/500, 707/513, 707/530, 707/531, 707/532, 341/51
• US Class Current: 704/9
• CPC Class Codes: G06F 40/221 Parsing markup language streams streaming G06F40/149
• CPC Class Codes: H03M 7/3084 using adaptive string matching, e.g. the Lempel-Ziv method

Abstract

A method for compressing text includes steps of parsing words from text in an input file and comparing the parsed words to a predetermined dictionary. The dictionary has a plurality of vocabulary words in it and numbers or tokens corresponding to each vocabulary word. A further step is determining which of the parsed words are not present in the predetermined dictionary and creating at least one supplemental dictionary including the parsed words that are not present in the predetermined dictionary. The predetermined dictionary and the supplemental dictionary are stored together in a compressed file. Also, the parsed words are replaced with numbers or tokens corresponding to the numbers assigned in the predetermined and supplemental dictionary and the numbers or tokens are stored in the compressed file.

Claims

1. A method for compressing text into a compressed file, comprising the steps of:

parsing words from text in an input file;

comparing the parsed words to a first predetermined dictionary having a plurality of vocabulary words and corresponding numbers to the text;

determining which of the parsed words are not present in the first predetermined dictionary;

creating at least one supplemental dictionary including the parsed words not present in the first predetermined dictionary;

storing the first predetermined dictionary in a compressed file together with the supplemental dictionary;

replacing the parsed words with numbers corresponding to the numbers assigned in the first predetermined and supplemental dictionary; and

storing into the compressed file the numbers in place of the corresponding words of the text.

2. A method for compressing text according to claim 1, wherein the input file is a hypertext file.

3. A method for compressing text according to claim 1, wherein the input file is composed using at least two natural languages, further comprising the steps of

comparing the parsed words to a second predetermined dictionary;

determining which of the parsed words are not present in the second predetermined dictionary;

creating the at least one supplemental dictionary including the parsed words not present in the first and second predetermined dictionaries;

storing the first and second predetermined dictionaries in the compressed file together with the supplemental dictionary; and

replacing the parsed words with numbers corresponding to the numbers assigned in the first and second predetermined and supplemental dictionaries.

4. The method according to claim 3, wherein the tokens in the second predetermined dictionary are assigned an offset value.

5. The method according to claim 3, wherein the first and second predetermined dictionaries each include a header and first and second token ranges, the first token range including tokens corresponding to words having a first frequency of occurrence within the natural language represented by the first and second respective predetermined dictionaries and the second token range including tokens corresponding to words having a second frequency of occurrence within the natural language represented by the first and the second respective predetermined dictionaries.

6. The method according to claim 5, wherein the first and second token ranges within the first and second predetermined dictionaries are assigned non-conflicting offset values prior to the steps of replacing and storing.

7. The method according to claim 2, wherein the hypertext file resides on a remote server coupled to the internet, further comprising the steps of:

transmitting the compressed file from the remote server to a browser over the internet.

8. The method according to claim 1, wherein the compressed file is transmitted to the browser without the predetermined dictionary.

9. A method of uncompressing a compressed hypertext markup language file received from a remote server on the internet, comprising the steps of:

receiving at a system coupled to the internet a header of a compressed file, the compressed file including a plurality of tokens and a predetermined and supplemental dictionary that each relate tokens with corresponding text, and the header identifying the predetermined dictionary;

analyzing the header of the compressed file to determine whether the predetermined dictionary is stored on the system;

requesting transmission of the predetermined dictionary from the remote server when not present on the system;

receiving the compressed text from the remote server and replacing each token within the compressed text with the corresponding text based on the content of the predetermined and supplemental dictionaries.