Data compression and decompression system with immediate dictionary updating interleaved with string search

• US 5,861,827 A
• Filed: 12/03/1996
• Issued: 01/19/1999
• Est. Priority Date: 07/24/1996
• Status: Expired due to Term

• Current Assignee: Unisys Corporation
• Original Assignee: Unisys Corporation
• Inventors: Cooper, Albert B., Welch, deceased, Terry A.
• Primary Examiner(s): Williams, Howard L.
• Application Number:
  US08/753,871
• Time in Patent Office: 777 Days
• Field of Search: 341/51
• US Class Current: 341/51
• CPC Class Codes: H03M 7/3088 employing the use of a dictionary, e.g. LZ78
• CPC Class Codes: H03M 7/46 Conversion to or from run-length codes, i.e. by representing the number of consecutive digits, or groups of digits, of the same kind by a code word and a digit indicative of that kind

Abstract

A dictionary based data compression and decompression system where, in the compressor, when a partial string W and a character C are matched in the dictionary, a new string is entered into the dictionary with C as an extension character on the string PW where P is the string corresponding to the last output compressed code signal. An update string is entered into the compression dictionary for each input character that is read and matched. The updating is immediate and interleaved with the character-by-character matching of the current string. The update process continues until the longest match is found in the dictionary. The code of the longest matched string is output in a string matching cycle. If a single character or multi-character string "A" exists in the dictionary, the string AAA . . . A is encoded in two compressed code signals regardless of the string length. This encoding results in an unrecognized code signal at the decompressor. The decompressor, in response to an unrecognized code signal, enters update strings into the decompressor dictionary in accordance with the recovered string corresponding to the previously received code signal, the unrecognized code signal, the extant code of the decompressor and the number of characters in the previously recovered string.

Claims

1. Data compression apparatus for compressing a stream of data character signals into a stream of compressed code signals, comprising

storage means for storing strings of data character signals, each said string having a code signal associated therewith,

means for searching said stream of data character signals by comparing said stream to said stored strings to perform a character-by-character match therewith until a predetermined match is determined,

means for providing the code signal associated with said predetermined match so as to provide said stream of compressed code signals,

means for entering extended strings into said storage means, the entry of said extended strings being interleaved with the matching of the data character signals of said character-by-character match, an extended string PWC comprising a previously matched string P corresponding to a last provided code signal extended by a string WC, where W is a partial string in the process of being matched during said character-by-character match and C is a data character signal continuing the match of W during said character-by-character match, and

means for assigning respective code signals to said extended strings.

2. The apparatus of claim 1 wherein said means for entering is operative to enter one of said extended strings into said storage means as each said data character signal is matched and before a next data character signal is matched.

3. The apparatus of claim 2 wherein said predetermined match comprises the longest match between said stream of data character signals and said stored strings,

said means for providing being operative for providing the code signal associated with said longest match so as to provide said stream of compressed code signals.

4. The apparatus of claim 3 wherein said apparatus operates in successive string matching cycles, respective longest matched strings being determined in said successive cycles, a current cycle following a previous cycle,

said previously matched string being matched in said previous cycle with said last provided code signal being provided in said previous cycle,

said character-by-character match occurring in said current cycle with said previously matched string being extended by said each data character signal during said current cycle.

6. The apparatus of claim 4 wherein said means for searching is operative for determining when said longest match has been achieved by determining when a data character signal fails to match during said character-by-character match,

said means for searching includes means for beginning a next string matching cycle with said data character signal that failed to match.

7. The apparatus of claim 1 further including means for initializing said storage means with all single character strings with respective codes associated therewith.

8. The apparatus of claim 1 further including

means for outputting a data character signal encountered for the first time in uncompressed form following an indication that such a data character signal is being output, and

means for entering said data character signal encountered for the first time into said storage means as a single character string.

9. The apparatus of claim 8 wherein said indication comprises a zero code.

5. Data compression apparatus for compressing a stream of data character signals into a stream of compressed code signals, comprising

storage means for storing strings of data character signals, each said string having a code signal associated therewith,

means for searching said stream of data character signals by comparing said stream to said stored strings to perform a character-by-character match therewith until a predetermined match is determined,

means for providing the code signal associated with said predetermined match so as to provide said stream of compressed code signals,

means for entering into said storage means, interleaved with said character-by-character match, extended strings comprising a previously matched string corresponding to a last provided code signal extended by each data character signal, in turn, as each data character signal is matched, and

means for assigning respective code signals to said extended strings,

said apparatus operating in successive string matching cycles, a current cycle following a previous cycle,

said means for searching and said means for entering being operative so that when a partial string W and a data character signal C are matched, one of said extended strings is entered into said storage means with said data character signal C as an extension character of a string PW where P is said previously matched string and W is in the process of being matched in said current cycle.

10. Data compression apparatus for compressing a stream of data character signals into a stream of compressed code signals, comprising

storage means for storing strings of data character signals, each said string having a code signal associated therewith,

means for searching said stream of data character signals by comparing said stream to said stored strings to perform a character-by-character match therewith until a predetermined match is determined,

means for providing the code signal associated with said predetermined match so as to provide said stream of compressed code signals,

means for entering into said storage means, interleaved with said character-by-character match, extended strings comprising a previously matched string corresponding to a last provided code signal extended by each data character signal, in turn, as each data character signal is matched, and

means for assigning respective code signals to said extended strings,

said strings being stored in said storage means in a linked tree structure and said stream of data character signals including a repeating character string comprised of a repeating character,

said apparatus being operative for compressing said repeating character string in two compressed code signals irrespective of the length thereof.

11. The apparatus of claim 10 wherein

said previously matched string comprises said repeating character,

said means for searching is operative to match said repeating character string on a path through said tree, and

said means for entering is operative to enter said extended strings on said path,

thereby compressing said repeating character string in two compressed code signals irrespective of the length thereof.

12. Data compression apparatus for compressing a stream of data character signals into a stream of compressed code signals, comprising

storage means for storing strings of data character signals, each said string having a code signal associated therewith,

means for searching said stream of data character signals by comparing said stream to said stored strings to perform a character-by-character match therewith until a predetermined match is determined,

means for providing the code signal associated with said predetermined match so as to provide said stream of compressed code signals,

means for entering into said storage means, interleaved with said character-by-character match, extended strings comprising a previously matched string corresponding to a last provided code signal extended by each data character signal, in turn, as each data character signal is matched, and

means for assigning respective code signals to said extended strings,

said strings being stored in said storage means, in a linked tree structure and said stream of data character signals including a repeating character group string comprised of a repeating character group,

said apparatus being operative for compressing said repeating character group string in two compressed code signals irrespective of the length thereof.

13. The apparatus of claim 12 wherein

said previously matched string comprises said repeating character group,

said means for searching is operative to match said repeating character group string on a path through said tree, and

said means for entering is operative to enter said extended strings on said path,

thereby compressing said repeating character group string in two compressed code signals irrespective of the length thereof.

14. Data decompression apparatus for receiving a stream of compressed code signals provided by a data compressor responsive to a stream of data character signals, said apparatus operative for recovering said stream of data character signals from said stream of compressed code signals, comprising

storage means for storing strings of data character signals, each said string having a code signal associated therewith,

means for accessing said storage means with a current received compressed code signal for recovering a string from said storage means corresponding to said current received compressed code signal so as to recover the data character signals thereof,

means for entering into said storage means, extended strings comprising a previously recovered string corresponding to a previously received compressed code signal extended by each data character signal, in turn, of said recovered string corresponding to said current received compressed code signal,

means for assigning respective code signals to said extended strings,

further means for entering into said storage means, further extended strings in response to receiving an unrecognized compressed code signal, said further extended strings comprising said previously recovered string corresponding to said previously received compressed code signal extended by each data character signal, in turn, of said previously recovered string, sequentially and repeatedly, until a string corresponding to said unrecognized compressed code signal is entered,

means for assigning respective code signals to said further extended strings, and

means for providing the data character signals of said string corresponding to said unrecognized compressed code signal so as to recover said data character signals.

15. The apparatus of claim 14 wherein said further means for entering is operative for entering into said storage means, additional extended strings comprising said string corresponding to said unrecognized compressed code signal further extended by the data character signals of said previously recovered string, in turn, until a number of said additional extended strings are entered into said storage means, said number being equal to the number of data character signals comprising said previously recovered string,

means for assigning respective code signals to said additional extended strings.

16. The apparatus of claim 15 wherein said apparatus operates in successive string recovery cycles, respective strings being recovered in said successive cycles, a current cycle following a previous cycle,

said previously recovered string being recovered in said previous cycle with said previously received compressed code signal being received in said previous cycle,

said current received compressed code signal being received during said current cycle, and

said means for entering being operative for entering said extended strings into said storage means during said current cycle.

17. The apparatus of claim 16 wherein said unrecognized compressed code signal is received during said current cycle,

said further means for entering being operative for entering said further extended strings and said additional extended strings into said storage means during said current cycle.

18. The apparatus of claim 14 further including means for initializing said storage means with all single character strings with respective codes associated therewith.

19. The apparatus of claim 14 wherein said stream of compressed code signals includes a data character signal in uncompressed form following an indication that such a data character signal is being received,

said data character signal in uncompressed form corresponding to a data character signal encountered for the first time by said data compressor in said stream of data character signals,

said apparatus further including,

means for entering said data character signal received in uncompressed form into said storage means as a single character string, and

means for outputting said data character signal received in uncompressed form.

20. The apparatus of claim 19 wherein said indication comprises a zero code.

21. Data decompression apparatus for receiving a stream of compressed code signals provided by a data compressor responsive to a stream of data character signals, said stream of data character signals including a repeating character string comprised of a repeating character, said data compressor being operative for compressing said repeating character string into two consecutive compressed code signals, said apparatus operative for recovering said stream of data character signals from said stream of compressed code signals, comprising

storage means for storing strings of data character signals, each said string having a code signal associated therewith

said strings being stored in said storage means in a linked tree structure,

means for accessing said storage means with a current received compressed code signal for recovering a string from said storage means corresponding to said current received compressed code signal so as to recover the data character signals thereof,

means for entering into said storage means, extended strings comprising a previously recovered string corresponding to a previously received compressed code signal extended by each data character signal, in turn, of said recovered string corresponding to said current received compressed code signal,

means for assigning respective code signals to said extended strings,

further means for entering into said storage means, further extended strings in response to receiving an unrecognized compressed code signal, said further extended strings comprising said previously recovered string corresponding to said previously received compressed code signal extended by each data character signal, in turn, of said previously recovered string, sequentially and repeatedly, until a string corresponding to said unrecognized compressed code signal is entered,

means for assigning respective code signals to said further extended strings,

means for providing the data character signals of said string corresponding to said unrecognized compressed code signal so as to recover said data character signals,

said further means for entering being operative for entering into said storage means, additional extended strings comprising said string corresponding to said unrecognized compressed code signal further extended by the data character signals of said previously recovered string, in turn, until a number of said additional extended strings are entered into said storage means, said number being equal to the number of data character signals comprising said previously recovered string, and

means for assigning respective code signals to said additional extended strings.

22. The apparatus of claim 21 wherein

said previously received compressed code signal comprises a first of said consecutive compressed code signals and said unrecognized compressed code signal comprises a second of said consecutive compressed code signals,

said previously recovered string comprises said repeating character and said string corresponding to said unrecognized compressed code signal comprises said repeating character string,

said previously recovered string is stored on a path through said tree, and

said means for entering and said further means for entering are operative for entering said further extended strings and said additional extended strings on said path.

23. Data decompression apparatus for receiving a stream of compressed code signals provided by a data compressor responsive to a stream of data character signals, said stream of data character signals including a repeating character group string comprised of a repeating character group, said data compressor being operative for compressing said repeating character group string into two consecutive compressed code signals, said apparatus operative for recovering said stream of data character signals from said stream of compressed code signals, comprising

storage means for storing strings of data character signals, each said string having a code signal associated therewith,

said strings being stored in said storage means in a linked tree structure,

means for accessing said storage means with a current received compressed code signal for recovering a string from said storage means corresponding to said current received compressed code signal so as to recover the data character signals thereof,

means for entering into said storage means, extended strings comprising a previously recovered string corresponding to a previously received compressed code signal extended by each data character signal, in turn, of said recovered string corresponding to said current received compressed code signal,

means for assigning respective code signals to said extended strings,

further means for entering into said storage means, further extended strings in response to receiving an unrecognized compressed code signal, said further extended strings comprising said previously recovered string corresponding to said previously received compressed code signal extended by each data character signal, in turn, of said previously recovered string, sequentially and repeatedly, until a string corresponding to said unrecognized compressed code signal is entered,

means for assigning respective code signals to said further extended strings,

means for providing the data character signals of sail string corresponding to said unrecognized compressed code signal so as to recover said data character signals,

said further means for entering being operative for entering into said storage means, additional extended strings comprising said string corresponding to said unrecognized compressed code signal further extended by the data character signals of said previously recovered string, in turn, until a number of said additional extended strings are entered into said storage means, said number being equal to the number of data character signals comprising said previously recovered string, and

means for assigning respective code signals to said additional extended strings.

24. The apparatus of claim 23 wherein

said previously received compressed code signal comprises a first of said consecutive compressed code signals and said unrecognized compressed code signal comprises a second of said consecutive compressed code signals,

said previously recovered string comprises said repeating character group and said string corresponding to said unrecognized compressed code signal comprises said repeating character group string,

said previously recovered string is stored on a path through said tree, and

said means for entering and said further means for entering are operative for entering said further extended strings and said additional extended strings on said path.

25. Data decompression apparatus for recovering a stream of data character signals from a stream of compressed code signals, comprising

means for receiving said stream of compressed code signals,

storage means for storing strings of data character signals, each said string having a code signal associated therewith,

means for accessing said storage means with a current received compressed code signal for recovering a string from said storage means corresponding to said current received compressed code signal so as to recover the data character signals thereof,

means for entering into said storage means, extended strings comprising a previously recovered string corresponding to a previously received compressed code signal extended by each data character signal, in turn, of said recovered string corresponding to said current received compressed code signal,

further means for entering into said storage means, further extended strings in response to receiving an unrecognized compressed code signal,

means for assigning respective code signals to said extended strings and to said further extended strings,

said further means for entering being operative for generating said further extended strings in accordance with said previously recovered string, the number of data character signals comprising said previously recovered string, said unrecognized compressed code signal and said code signals being assigned to said further extended strings, one of said further extended strings being a string corresponding to said unrecognized compressed code signal, and

means for providing the data character signals of said string corresponding to said unrecognized compressed code signal so as to recover said data character signals.

26. A data compression method for compressing a stream of data character signals into a stream of compressed code signals, comprising

storing strings of data character signals in storage means, each said string having a code signal associated therewith,

searching said stream of data character signals by comparing said stream to said stored strings to perform a character-by-character match therewith until a predetermined match is determined,

providing the code signal associated with said predetermined match so as to provide said stream of compressed code signals,

entering extended strings into said storage means, the entry of said extended strings being interleaved with the matching of the data character signals of said character-by-character match, an extended string PWC comprising a previously matched string P corresponding to a last provided code signal extended by a string WC, where W is a partial string in the process of being matched during said character-by-character match and C is a data character signal continuing the match of W during said character-by-character match, and

assigning respective code signals to said extended strings.

27. The method of claim 26 wherein said entering step includes entering one of said extended strings into said storage means as each said data character signal is matched and before a next data character signal is matched.

28. The method of claim 27 wherein said predetermined match comprises the longest match between said stream of data character signals and said stored strings,

said providing step comprises providing the code signal associated with said longest match so as to provide said stream of compressed code signals.

29. The method of claim 28 wherein said method operates in successive string matching cycles, respective longest matched strings being determined in said successive cycles, a current cycle following a previous cycle,

said previously matched string being matched in said previous cycle with said last provided code signal being provided in said previous cycle,

said character-by-character match occurring in said current cycle with said previously matched string being extended by said each data character signal during said current cycle.

31. The method of claim 29 wherein said searching step includes determining when said longest match has been achieved by determining when a data character signal fails to match during said character-by-character match,

said searching step including beginning a next string matching cycle with said data character signal that failed to match.

32. The method of claim 26 further including initializing said storage means with all single character strings with respective codes associated therewith.

33. The method of claim 26 further including

outputting a data character signal encountered for the first time in uncompressed form following an indication that such a data character signal is being output, and

entering said data character signal encountered for the first time into said storage means as a single character string.

34. The method of claim 33 wherein said indication comprises a zero code.

30. A data compression method for compressing a stream of data character signals into a stream of compressed code signals, comprising

storing strings of data character signals in storage means, each said string having a code signal associated therewith,

searching said stream of data character signals by comparing said stream to said stored strings to perform a character-by-character match therewith until a predetermined match is determined,

providing the code signal associated with said predetermined match so as to provide said stream of compressed code signals,

entering into said storage means, interleaved with said character-by-character match, extended strings comprising a previously matched string corresponding to a last provided code signal extended by each data character signal, in turn, as each data character signal is matched, and

assigning respective code signals to said extended strings,

said method operating in successive string matching cycles, a current cycle following a previous cycle,

said searching and said entering steps being performed so that when a partial string W and a data character signal C are matched, one of said extended strings is entered into said storage means with said data character signal C as an extension character of a string PW where P is said previously matched string and W is in the process of being matched in said current cycle.

35. A data compression method for compressing a stream of data character signals into a stream of compressed code signals, comprising

storing strings of data character signals in storage means, each said string having a code signal associated therewith,

searching said stream of data character signals by comparing said stream to said stored strings to perform a character-by-character match therewith until a predetermined match is determined,

providing the code signal associated with said predetermined match so as to provide said stream of compressed code signals,

entering into said storage means, interleaved with said character-by-character match, extended strings comprising a previously matched string corresponding to a last provided code signal extended by each data character signal, in turn, as each data character signal is matched, and

assigning respective code signals to said extended strings,

said storing step comprising storing said strings in said storage means in a linked tree structure,

said stream of data character signals including a repeating character string comprised of a repeating character,

said method compressing said repeating character string in two compressed code signals irrespective of the length thereof.

36. The method of claim 35 wherein

said previously matched string comprises said repeating character,

said searching step includes matching said repeating character string on a path through said tree, and

said entering step includes entering said extended strings on said path,

thereby compressing said repeating character string in two compressed code signals irrespective of the length thereof.

37. A data compression method for compressing a stream of data character signals into a stream of compressed code signals, comprising

storing strings of data character signals in storage means, each said string having a code signal associated therewith,

searching said stream of data character signals by comparing said stream to said stored strings to perform a character-by-character match therewith until a predetermined match is determined,

providing the code signal associated with said predetermined match so as to provide said stream of compressed code signals,

entering into said storage means, interleaved with said character-by-character match, extended strings comprising a previously matched string corresponding to a last provided code signal extended by each data character signal, in turn, as each data character signal is matched, and

assigning respective code signals to said extended strings,

said storing step comprising storing said strings in said storage means in a linked tree structure,

said stream of data character signals including a repeating character group string comprised of a repeating character group,

said method compressing said repeating character group string in two compressed code signals irrespective of the length thereof.

38. The method of claim 37 wherein

said previously matched string comprises said repeating character group,

said searching step includes matching said repeating character group string on a path through said tree, and

said entering step includes entering said extended strings on said path,

thereby compressing said repeating character group string in two compressed code signals irrespective of the length thereof.

39. A data decompression method for receiving a stream of compressed code signals provided by a data compressor responsive to a stream of data character signals, said method recovering said stream of data character signals from said stream of compressed code signals, comprising

storing strings of data character signals in storage means, each said string having a code signal associated therewith,

accessing said storage means with a current received compressed code signal for recovering a string from said storage means corresponding to said current received compressed code signal so as to recover the data character signals thereof,

entering into said storage means, extended strings comprising a previously recovered string corresponding to a previously received compressed code signal extended by each data character signal, in turn, of said recovered string corresponding to said current received compressed code signal,

assigning respective code signals to said extended strings,

further entering into said storage means, further extended strings in response to receiving an unrecognized compressed code signal, said further extended strings comprising said previously recovered string corresponding to said previously received compressed code signal extended by each data character signal, in turn, of said previously recovered string, sequentially and repeatedly, until a string corresponding to said unrecognized compressed code signal is entered,

assigning respective code signals to said further extended strings, and

providing the data character signals of said string corresponding to said unrecognized compressed code signal so as to recover said data character signals.

40. The method of claim 39 wherein said further entering step includes entering into said storage means, additional extended strings comprising said string corresponding to said unrecognized compressed code signal further extended by the data character signals of said previously recovered string, in turn, until a number of said additional extended strings are entered into said storage means, said number being equal to the number of data character signals comprising said previously recovered string,

assigning respective code signals to said additional extended strings.

41. The method of claim 40 wherein said method operates in successive string recovery cycles, respective strings being recovered in said successive cycles, a current cycle following a previous cycle,

said previously recovered string being recovered in said previous cycle with said previously received compressed code signal being received in said previous cycle,

said current received compressed code signal being received during said current cycle, and

said entering step comprises entering said extended strings into said storage means during said current cycle.

42. The method of claim 41 wherein said unrecognized compressed code signal is received during said current cycle,

said further entering step including entering said further extended strings and said additional extended strings into said storage means during said current cycle.

43. The method of claim 39 further including initializing said storage means with all single character strings with respective codes associated therewith.

44. The method of claim 39 wherein said stream of compressed code signals includes a data character signal in uncompressed form following an indication that such a data character signal is being received,

said data character signal in uncompressed form corresponding to a data character signal encountered for the first time by said data compressor in said stream of data character signals,

said method further including,

entering said data character signal received in uncompressed form into said storage means as a single character string, and

outputting said data character signal received in uncompressed form.

45. The method of claim 44 wherein said indication comprises a zero code.

46. A data decompression method for receiving a stream of compressed code signals provided by a data compressor responsive to a stream of data character signals, said stream of data character signals including a repeating character string comprised of a repeating character, said data compressor compressing said repeating character string into two consecutive compressed code signals, said method recovering said stream of data character signals from said stream of compressed code signals, comprising

storing strings of data character signals in storage means, each said string having a code signal associated therewith,

said storing step comprising storing said strings in said storage means in a linked tree structure,

accessing said storage means with a current received compressed code signal for recovering a string from said storage means corresponding to said current received compressed code signal so as to recover the data character signals thereof,

entering into said storage means, extended strings comprising a previously recovered string corresponding to a previously received compressed code signal extended by each data character signal, in turn, of said recovered string corresponding to said current received compressed code signal,

assigning respective code signals to said extended strings,

further entering into said storage means, further extended strings in response to receiving an unrecognized compressed code signal, said further extended strings comprising said previously recovered string corresponding to said previously received compressed code signal extended by each data character signal, in turn, of said previously recovered string, sequentially and repeatedly, until a string corresponding to said unrecognized compressed code signal is entered,

assigning respective code signals to said further extended strings,

providing the data character signals of said string corresponding to said unrecognized compressed code signal so as to recover said data character signals,

said further entering step including entering into said storage means, additional extended strings comprising said string corresponding to said unrecognized compressed code signal further extended by the data character signals of said previously recovered string, in turn, until a number of said additional extended strings are entered into said storage means, said number being equal to the number of data character signals comprising said previously recovered string, and

assigning respective code signals to said additional extended strings.

47. The method of claim 46 wherein

said previously received compressed code signal comprises a first of said consecutive compressed code signals and said unrecognized compressed code signal comprises a second of said consecutive compressed code signals,

said previously recovered string comprises said repeating character and said string corresponding to said unrecognized compressed code signal comprises said repeating character string,

said previously recovered string is stored on a path through said tree, and

said entering and said further entering steps include entering said further extended strings and said additional extended strings on said path.

48. A data decompression method for receiving a stream of compressed code signals provided by a data compressor responsive to a stream of data character signals, said stream of data character signals including a repeating character group string comprised of a repeating character group, said data compressor compressing said repeating character group string into two consecutive compressed code signals, said method recovering said stream of data character signals from said stream of compressed code signals, comprising

storing strings of data character signals in storage means, each said string having a code signal associated therewith,

said storing step comprising storing said strings in said storage means in a linked tree structure.

accessing said storage means with a current received compressed code signal for recovering a string from said storage means corresponding to said current received compressed code signal so as to recover the data character signals thereof,

entering into said storage means, extended strings comprising a previously recovered string corresponding to a previously received compressed code signal extended by each data character signal, in turn, of said recovered string corresponding to said current received compressed code signal,

assigning respective code signals to said extended strings,

further entering into said storage means, further extended strings in response to receiving an unrecognized compressed code signal, said further extended strings comprising said previously recovered string corresponding to said previously received compressed code signal extended by each data character signal, in turn, of said previously recovered string, sequentially and repeatedly, until a string corresponding to said unrecognized compressed code signal is entered,

assigning respective code signals to said further extended strings,

providing the data character signals of said string corresponding to said unrecognized compressed code signal so as to recover said data character signals,

said further entering step including entering into said storage means, additional extended strings comprising said string corresponding to said unrecognized compressed code signal further extended by the data character signals of said previously recovered string, in turn, until a number of said additional extended strings are entered into said storage means, said number being equal to the number of data character signals comprising said previously recovered string, and

assigning respective code signals to said additional extended strings.

49. The method of claim 48 wherein

said previously received compressed code signal comprises a first of said consecutive compressed code signals and said unrecognized compressed code signal comprises a second of said consecutive compressed code signals,

said previously recovered string comprises said repeating character group and said string corresponding to said unrecognized compressed code signal comprises said repeating character group string,

said previously recovered string is stored on a path through said tree, and

said entering and said further entering steps include entering said further extended strings and said additional extended strings on said path.

50. A data decompression method for recovering a stream of data character signals from a stream of compressed code signals, comprising

receiving said stream of compressed code signals,

storing strings of data character signals in storage means, each said string having a code signal associated therewith,

accessing said storage means with a current received compressed code signal for recovering a string from said storage means corresponding to said current received compressed code signal so as to recover the data character signals thereof,

entering into said storage means, extended strings comprising a previously recovered string corresponding to a previously received compressed code signal extended by each data character signal, in turn, of said recovered string corresponding to said current received compressed code signal,

further entering into said storage means, further extended strings in response to receiving an unrecognized compressed code signal,

assigning respective code signals to said extended strings and to said further extended strings,

said further entering step includes generating said further extended strings in accordance with said previously recovered string, the number of data character signals comprising said previously recovered string, said unrecognized compressed code signal and said code signals being assigned to said further extended strings, one of said further extended strings being a string corresponding to said unrecognized compressed code signal, and

providing the data character signals of said string corresponding to said unrecognized compressed code signal so as to recover said data character signals.