Context redundancy text compression

• US 4,672,679 A
• Filed: 08/16/1983
• Issued: 06/09/1987
• Est. Priority Date: 08/16/1983
• Status: Expired due to Term

• Current Assignee: QNF Lvoeroewa INX ONW Insuareil CW Loqwll M 01851
• Original Assignee: Wang Laboratories Incorporated
• Inventors: Freeman, Ernest A.
• Primary Examiner(s): Boudreau, Leo H.
• Application Number:
  US06/523,739
• Time in Patent Office: 1,393 Days
• Field of Search: 382/40, 382/56, 358/260, 358/263
• US Class Current: 382/233
• CPC Class Codes: G06F 40/12 Use of codes for handling textual entities

Abstract

A generalized method and apparatus for compression and decompression of textual information. Compression is performed by reading in succession each character and an associated context of a text, selecting for each character and associated context a corresponding code character, and providing the resulting code characters as the compressed form of the text. Decompression is a symmetric, inverse operation wherein the contexts associated with the code characters are read from a known decompressed portion of text. The context of a character is a group of text characters associated with a text character and containing a fixed number of characters. Text and code characters and contexts are related through a table containing a relative alphabet for the contexts of the language of the text. Each relative alphabet contains the text characters occurring in association with a corresponding context, and text characters within a given relative alphabet are identified by code characters assigned from set of code characters shared by the relative alphabets.

Claims

1. In an information processing system, a method for decompressing context compressed textual information, comprising the steps of:

reading in succession each code character of a compressed text,

reading, for each said code character, an associated context from a known decompressed portion of said text,

selecting, for each said code character and associated context, a corresponding text character, and

providing said text characters to comprise said text in decompressed form.

2. The method of claim 1, wherein each said context comprises:

a group of text characters associated with said text character.

3. The method of claim 2, wherein each said context containes a fixed number of said text characters.

4. The method of claim 1, further comprising the initial step of generating a table relating said text and code characters and said contexts, comprising the steps of:

reading each said text character and associated context of a representative sample of text,

for each said context occuring in said sample text, generating a relative alphabet comprising said text characters occurring in association with said each said context, and

associating a corresponding code character with each said text character of each said relative alphabet.

5. The method of claim 4, wherein:

each of said code characters are selected from a set of code characters shared by said relative alphabets.

6. In an information processing system, a method for compressing textual information, comprising the steps of:

generating, for each text character and associated context of a sample text, a table relating each said text character to a corresponding code character, including the steps of

reading each said character and associated context of a representative sample of text,

generating, for each said context occurring in said sample text, a relative alphabet comprising said text characters occurring in association with said each said context, and

associating a corresponding code character with each said text character of said relative alphabet, and

compressing said textual information of a text by the steps of

reading in succession each character and an associated context of said text,

selecting, for each said text character and associated context, a corresponding code character, and

providing said code characters to comprise said text in compressed form.

7. The method of claim 6, wherein each said context comprises:

a group of text characters associated with said text character.

8. The method of claim 7, wherein each said context contains a fixed number of said text characters.

9. The method of claim 6, wherein:

each of said code characters are selected from a set of code characters shared by said relative alphabets.

10. In an information processing system, a method for compressing textual information, comprising the steps of:

reading each text character and associated context of a representative sample of text,

generating, for each said context occuring in said sample text, a relative alphabet comprising said text characters occuring in association with said each said context, and

associating a corresponding code character with each said text character of each said relative alphabet,

reading in succession each character and an associated context of a text,

selecting, for each said text character and associated context, a corresponding code character, and

providing said code characters to comprise said text in compressed form.

11. In an information processing system, a method for decompressing context compressed textual information, comprising the steps of:

reading each said text character and associated context of a representative sample of text,

generating, for each said context occuring in said sample text, a relative alphabet comprising said text characters occuring in association with said each said context, and

associating a corresponding code character with each said text character of each said relative alphabet,

reading in succession each code character of a compressed text,

reading, for each said code character, an associated context from a known decompressed portion of said text,

selecting a corresponding text character for each said code character and associated context, and

providing said text characters to comprise said text in decompressed form.

12. In an information processing system, a method for storing and retrieving textual information, comprising the steps of:

reading in succession each character and an associated context of a text,

selecting, for each said text character and associated context, a corresponding code character, and

storing said code characters to comprise said text in compressed form,

reading in succession each code character of said stored compressed text,

reading, for each said code character, an associated context from a known decompressed portion of said text,

selecting a corresponding text character for each said code character and associated context, and

providing said text characters to comprise said text in decompressed form.

13. In an information processing system, a method for communicating textual information, comprising the steps of:

reading in succession each character and an associated context of a text,

selecting, for each said text character and associated context, a corresponding code character, said code characters comprising said text in compressed form, and

communicating said code characters,

reading in succession each said communicated code character,

reading, for each said code character, an associated context from a known decompressed portion of said text,

selecting a corresponding text character for each said code character and associated context, and

providing said text characters to comprise said text in decompressed form.

14. In an information processing system, means for decompressing context compressed textual information, comprising:

means for reading in succession each code character of a compressed text,

means responsive to said code character reading means for reading, for each said code character, an associated context from a known decompressed portion of said text,

means responsive to said code character and context reading means for selecting, for each said code character and associated context, a corresponding text character and providing said text characters to comprise said text in decompressed form.

15. The decompressing means of claim 14, wherein each said context comprises:

a group of text characters associated with said text character.

16. The decompressing means of claim 15, wherein each said context containes a fixed number of said text characters.

17. The decompressing means of claim 14, further comprising:

means for storing a table relating said text and code characters and said contexts and responsive to said selecting means for providing said corresponding text characters,

said table including, for each context of the language of said text, an associated relative alphabet containing said text characters occurring in association with said contexts of said language, and wherein

each of said text characters of each of said relative alphabets is associated with a said corresponding code character.

18. The decompressing means of claim 17, wherein:

each of said code characters are selected from a set of code characters shared by said relative alphabets.

19. In an information processing system, means for compressing textual information, comprising:

means for storing a table relating text characters and associated contexts of a text with corresponding code characters,

said table including, for each context of the language of said text, an associated relative alphabet containing said text characters occurring in association with said contexts of said language, and wherein

each of said text characters of each of said relative alphabets is associated with a said corresponding code character,

means for reading in succession each character and an associated context of a text, and

means responsive to said reading means for selecting and reading from said table, for each said text character and associated context, a corresponding code character and providing said code characters to comprise said text in compressed form.

20. The compressing means of claim 19, wherein:

each of said code characters are selected from a set of code characters shared by said relative alphabets.

21. The compressing means of claim 19, wherein each said context comprises:

a group of text characters associated with said text character.

22. The compressing means of claim 21, wherein each said context containes a fixed number of said text characters.

23. In an information processing system, means for storing and retreiving textual information, comprising:

compressing means comprising

means for reading in succession each character and an associated context of a text, and

means responsive to said reading means for selecting for each said text character and associated context a corresponding code character,

means for storing said code characters to comprise said text in compressed form, and

decompressing means comprising

means for reading in succession from said storing means each code character of said compressed text,

means responsive to said code character reading means for reading, for each said code character, an associated context from a known decompressed portion of said text, and

means responsive to said code character and context reading means for selecting, for each said code character and associated context, a corresponding text character and providing said text characters to comprise said text in decompressed form.

24. The storing and retrieving means of claim 23, further comprising:

means for storing a table relating said text and code characters and said contexts and responsive to said code and text character selecting means for providing said corresponding code and text characters,

said table including, for each context of the language of said text, an associated relative alphabet containing said text characters occurring in association with said contexts of said language, and wherein

each of said text characters of each of said relative alphabets is associated with a said corresponding code character.

25. In an information processing system, means for communicating textual information, comprising:

means for compressing a text, comprising

means for reading in succession each character and an associated context of a text, and

means responsive to said reading means for selecting for each said text character and associated context a corresponding code character, said code characters comprising said text in compressed form,

means for communicating said code characters, and

means for decompressing said compressed text, comprising

means for reading in succession each said communicated code character,

means responsive to said code character reading means for reading, for each said code character, an associated context from a known decompressed portion of said text, and

means responsive to said code character and context reading means for selecting, for each said code character and associated context, a corresponding text character and providing said text characters to comprise said text in decompressed form.

26. The communicating means of claim 25, wherein:

said compressing means further comprises

means for storing a table relating said text and code characters and said contexts and responsive to said code character selecting means for providing said corresponding code characters,

said table including, for each context of the language of said text, an associated relative alphabet containing said text characters occurring in association with said contexts of said language, and wherein

each of said text characters of each of said relative alphabets is associated with a said corresponding code character, and

said decompressing means further comprises

means for storing a table relating said text and code characters and said contexts and responsive to said text character selecting means for providing said corresponding text characters,

said table including, for each context of the language of said text, an associated relative alphabet containing said text characters occurring in association with said contexts of said language, and wherein

each of said text characters of each of said relative alphabets is associated with a said corresponding code character.