Text compression transmitter and receiver

• US 5,974,180 A
• Filed: 01/02/1996
• Issued: 10/26/1999
• Est. Priority Date: 01/02/1996
• Status: Expired due to Term

• Current Assignee: Blackberry Limited
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Schwendeman, Robert John
• Primary Examiner(s): Au, Amelia
• Assistant Examiner(s): Johnson, Timothy M.
• Application Number:
  US08/581,953
• Time in Patent Office: 1,393 Days
• Field of Search: 382/232, 382/239, 382/244, 382/233, 382/235, 382/245, 382/246, 382/247, 341/51, 341/90, 341/106, 341/67, 341/107, 358/431, 358/261.1, 358/261.2, 358/427
• US Class Current: 382/232
• CPC Class Codes: H03M 7/3084 using adaptive string matching, e.g. the Lempel-Ziv method

Abstract

A text compression technique used in a transmitter subsystem (126, 148) and a receiver subsystem (132, 158) for compressively encoding and decoding a text portion of a message by using tokens having at least two data symbol lengths. During encoding, a quantity of fill symbols are added to a sequence of secondary tokens, wherein the quantity of fill symbols is determined such that a total quantity of the data symbols in the sequence is equal to an integral multiple of the quantity of the data symbols having a first data symbol length. Delimiting characters such as spaces which precede a sequence of characters corresponding to a primary token are indicated by setting one data symbol in each primary token to a predetermined value. Sequences of capitalized characters are indicated by predetermined command tokens.

Claims

1. A transmitter subsystem for compressively encoding and transmitting a text portion of a message, wherein the message comprises data symbols, and wherein characters in a text portion of a message are encoded using tokens, and wherein each token represents a unique sequence of one or more characters stored in two or more token tables and matched within the text portion of the message, and wherein primary tokens are tokens having a first data symbol length, and wherein secondary tokens are tokens having a second data symbol length different from the first data symbol length, and wherein the transmitter subsystem comprises:

a memory that stores the two or more token tables;

a processing system, coupled to said memory, that compressively encodes the characters by

generating a sequence by adding a quantity of fill symbols to a string of the secondary tokens that encode a subset of the characters, wherein the symbol length of the secondary tokens are not necessarily one of an integral multiple and divisor of the symbol length of the primary tokens, and wherein the string has a length not exceeding a maximum predetermined length, and wherein the quantity of fill symbols is determined such that a total quantity of the data symbols in the sequence is equal to an integral multiple of the quantity of the data symbols in the first data symbol length,

adding a command token immediately preceding the sequence, which indicates a start of the sequence, wherein the command token has the first data symbol length, and

encoding characters that follow the sequence using one or more primary tokens following the sequence; and

a transmitter that transmits a signal including the text portion of the message comprising the characters compressively encoded by said processing system.

2. The transmitter subsystem according to claim 1, wherein the command token includes data symbols which indicate the second data symbol length of the secondary tokens in the sequence.

3. The transmitter subsystem according to claim 1, wherein said processing system adds a token sequence header immediately after the command token, and wherein the token sequence header includes an indication of a length of the sequence as one of a quantity of first data symbol lengths and second data symbol lengths.

4. The transmitter subsystem according to claim 3, wherein the token sequence header has the first data symbol length.

5. The transmitter subsystem according to claim 3, wherein the token sequence header has the second data symbol length, and wherein when said processing system adds a quantity of fill symbols, the quantity of fill symbols is determined such that a total quantity of data symbols in the sequence includes the second data symbol length and is equal to an integral multiple of the first data symbol length.

6. The transmitter subsystem according to claim 1, wherein said processing system sets data symbols within the command token to indicate a unique sequence of one or more characters matched within the text portion of the message.

7. The transmitter subsystem according to claim 1, wherein said processing system sets data symbols within the command token to indicate a quantity of tokens having the second data symbol length, and wherein the tokens comprise the sequence.

8. The transmitter subsystem according to claim 1, wherein said processing system includes a revert command indicating an end of the sequence immediately after a last secondary token of the sequence, and wherein the revert command has the second data symbol length.

9. A transmitter subsystem for compressively encoding and transmitting a text portion of a message, said transmitter subsystem comprising:

a processing system that compressively encodes the text portion by

determining a sequence of one or more characters stored in a token table and matched within the text portion of the message;

determining a token associated by the token table with the sequence of one or more characters;

setting a flag data symbol of the token to a first value and replacing, when the sequence of one or more characters is immediately preceded by a predetermined delimiting character the sequence of one or more characters and the immediately preceding predetermined delimiting character with the token; and

setting a flag data symbol of the token to a second value and replacing the sequence of one or more characters with the token when the sequence of one or more characters is not immediately preceded by the predetermined delimiting character;

a memory, coupled to said processing system, that stores the token table; and

a transmitter that transmits a signal including the text portion of the message compressively encoded by the processing system.

10. A receiver subsystem for receiving and decoding a compressed text portion of a message included in a signal, wherein the message comprises data symbols, and wherein characters in the compressed text portion have been encoded using tokens, and wherein each token represents a unique sequence of one or more characters stored in two or more token tables and matched within the compressed text portion of the message, and wherein primary tokens are the tokens having a first data symbol length, and wherein secondary tokens are tokens having a second data symbol length different from the first data symbol length, and wherein said receiver subsystem comprises:

a receiver that converts the signal into a demodulated signal;

a memory that stores the two or more token tables; and

a processing system, coupled to said memory and said receiver, that

decodes the data symbols from the demodulated signal;

separates the data symbols in the compressed text portion into data words having the first data symbol length, in order of receipt;

searches said data words for a command token indicating that a sequence of the secondary tokens follow consecutively thereafter; and

decodes the data symbols which follow said command token in a string of secondary tokens having a length not exceeding a maximum predetermined length, by

separating the data symbols in said sequence into secondary tokens;

replacing each secondary token in said sequence with a corresponding secondary character sequence found in the one or more token tables; and

decoding data words that occur more than the maximum determined length after said command token as primary tokens

wherein the symbol length of the secondary tokens are not necessarily one of an integral multiple and divisor of the symbol length of the primary tokens.

11. The receiver subsystem according to claim 10, wherein said processing system:

determines a length of the sequence included within the command token; and

identifies an end of the sequence from the length of the sequence, and wherein said processing system decodes the data symbols by replacing each of the data words after the end of the sequence with a corresponding primary character sequence found in the one or more token tables.

12. The receiver subsystem according to claim 10, wherein said processing system:

decodes a token sequence header immediately following the command token;

determines a length of the sequence identified within the token sequence header;

identifies an end of the sequence from the length of the sequence; and

replaces each of the data words after the end of the sequence with a corresponding primary character sequence found in the one or more token tables.

13. The receiver subsystem according to claim 10, wherein said processing system decodes the data symbols by

identifying a predetermined secondary token which indicates an end of the sequence, and

replacing each data word after the predetermined secondary token with a corresponding primary character sequence found in the one or more token tables.

14. The receiver subsystem according to claim 10, wherein the command token indicates a unique sequence of one or more characters matched within the compressed text portion of the message.

15. A receiver subsystem for receiving and decoding a compressed text portion of a message included in a signal, wherein the message comprises data symbols, and wherein characters in the compressed text portion have been encoded using tokens, wherein each token represents a unique sequence of one or more characters stored in one or more token tables in the receiver subsystem, said tables matched within the compressed text portion of the message, and wherein said receiver subsystem comprises:

a receiver that converts the signal into a demodulated signal;

a memory that stores the one or more token tables; and

a processing system, coupled to said memory and said receiver, that

decodes the data symbols from the demodulated signal;

separates the data symbols in the compressed text portion into data words;

replaces a data word with a sequence of the characters determined from a token table stored in said memory using a token derived from all but one data symbol of the data word; and

places a delimiting character before the sequence of the characters when the one data symbol has a first value.