Data compression with dynamically compiled dictionary

• US 5,253,325 A
• Filed: 06/25/1991
• Issued: 10/12/1993
• Est. Priority Date: 12/09/1988
• Status: Expired due to Fees

• Current Assignee: British Telecommunications PLC (BT Group PLC)
• Original Assignee: British Telecommunications PLC (BT Group PLC)
• Inventors: Clark, Alan D.
• Primary Examiner(s): MacDonald, Allen R.
• Assistant Examiner(s): Doerrler, Michelle
• Application Number:
  US07/688,552
• Time in Patent Office: 840 Days
• Field of Search: 381/29-47, 395/2, 341/51, 341/67, 341/65, 341/79, 341/87
• US Class Current: 704/200
• CPC Class Codes: H03M 7/3084 using adaptive string matching, e.g. the Lempel-Ziv method

Abstract

A data compression system in which a dictionary stored strings of characters and an encoder matches the longest of the stored string with a current string of a data stream input to the encoder. The index of the longest matched stored string is output by the encoder and the dictionary is updated by a new string consisting of the previous match concatenated with the first two characters only of the present match. If the present match has only one or two characters, it is added without reduction.

Claims

1. A data compression system comprising:

a dictionary arranged to store strings of characters with an index for each of said strings, and

means for matching strings of characters of a data stream with strings of characters stored in the dictionary and for outputting the index of a dictionary entry of a matched string when a following character of the data stream does not match with the stored strings,

said means for matching including means for determining, for a matched string having at least three characters, a sequence of characters from said at least three characters, said sequence including at least a first and a second of said at least three characters, but not including all of said at least three characters, to update the dictionary by extending an immediately- preceding string by said sequence.

2. A system according to claim 1, in which the means for matching determines said sequence so as to comprise only said first said second of said at least three characters.

3. In a method of data compression of individual sequences of characters in a data stream including the steps of storing strings in a dictionary, and determining the longest string in the dictionary which matches a current string in the data stream staring from a current input position, the improvement comprising the steps of:

determining, for a matched string having at least three characters, a single sequence of characters from said at least three characters, said single sequence including at least a first and a second of said at least three characters, but not including all of said at least three characters, and

updating the dictionary by extending an immediately-preceding string by said single sequence.

4. A method according to claim 3, wherein the determining step determines a single sequence constituted by only said first and said second of said at least three characters.

5. A method for updating dynamically compiled dictionary entries in a data compression system that generates an output code corresponding to a matched data string S'"'"' of successively encountered input characters found as an existing dictionary entry followed by a further matched string S of input characters also found as an existing dictionary entry, said method comprising the steps of

creating a new dictionary entry for a character string S'"'"'+S" where string S" is of shorter length than string S if string S is greater than two characters in length.