Apparatus and method for compressing data signals and restoring the compressed data signals

US 4,464,650 A
Filed: 08/10/1981
Issued: 08/07/1984
Est. Priority Date: 08/10/1981
Status: Expired due to Term

First Claim

Patent Images

1. A data compression and decompression system for compressing digital data and recovering the original data from the compressed data, said system including means for reading the digital data from a medium to provide a stream of data symbol signals, said data symbol signals being members of an alphabet of symbol signals comprising a predetermined number of symbol signals, said system including compression apparatus responsive to said stream of data symbol signals for providing a compressed stream of code signals corresponding thereto and applying said code signals to a medium, said system further including decompression apparatus responsive to said code signals for recovering the original data therefrom, said compression apparatus comprising:

means for parsing said stream of data symbol signals into segments, each segment comprising a prefix and the next data symbol signal occurring in said stream after said prefix, said prefix comprising the longest match with a previous segment, said parsing means defining a first search tree having nodes and branches emanating from said nodes, each node having at most one incoming branch, the outgoing branches emanating from a node being representative of said symbol signals of said alphabet, respectively, said nodes having respective node labels associated therewith and respective addresses associated therewith, said first search tree having a unique root node without an incoming branch and leaf nodes without outgoing branches,said parsing means comprising means for tracing said stream of data symbol signals through said first search tree along a path from said root node to a leaf node, including means responsive to said stream of data symbol signals for determining the branches of said path in accordance with said symbol signals respectively,said parsing means comprisingfirst storage means comprising a plurality of storage locations corresponding respectively to said addresses of said nodes of said tree, said storage locations being utilized for storing said node labels, a node label stored at a particular storage location identifying the node whose address corresponds to said particular storage location,address generator means for generating an address signal and for providing said address signal to said first storage means for accessing said storage locations thereof, said first storage means providing, in response thereto, the node label stored in the storage location accessed by said address signal, said address generator means being responsive to a node label provided by said first storage means and to a data symbol signal from said stream of data symbol signal for generating said address signal in accordance therewith,first detecting means for detecting when an accessed storage location of said first storage means does not contain a node label, said storage location not containing a node label defining a leaf node of said first search tree, andnode counting means for inserting a node label into said accessed storage location of said first storage means detected by said first detecting means as not containing a node label;

said address generator means comprising means for sequentially generating said address signals and for providing said address signals to said first storage means, the node label provided by said first storage means in response to an address signal providing the node label for generating the next address signal, said address generator means sequentially generating said address signals in accordance with the node labels sequentially provided by said first storage means respectively and in accordance with successive symbol signals of said stream of data symbol signals respectively, said address generator means sequentially generating said address signals until said first detecting means detects an accessed storage location of said first storage means without a node label; and

means responsive to the address of said accessed storage location not containing a node label for generating a pointer signal in accordance therewith for each said segment, said pointer signal being representative of said previous segment matching said prefix and of said next occurring data symbol signal after said prefix,thereby providing pointer signals for segments of said stream of data symbol signals, respectively,said pointer signals comprising said compressed stream of code signals.

View all claims

2 Assignments

Timeline View

Assignment View

0 Petitions

Accused Products

Abstract

A compressor parses the input data stream into segments where each segment comprises a prefix and the next symbol in the data stream following the prefix. The prefix of a segment is the longest match with a previously parsed segment of the data stream. The compressor constructs a search tree data base to effect the parsing and to generate a pointer for each segment pointing to the previous segment matching the prefix. The search tree comprises internal nodes including a root and external nodes denoted as leaves. The nodes are interconnected by branches representative of symbols of the alphabet. Each parsed segment of the input data is represented by a path from the root to a leaf. The tree is adaptively constructed from the input data such that as each new segment is parsed, one new internal node of the tree is created from a leaf and new leaves are defined, one for each symbol already encountered by the encoder plus an additional branch to represent all potential but unseen symbols. The compressor transmits a leaf pointer signal for each parsed segment representative of the prefix thereof and the suffixed symbol of the alphabet. A decompressor constructs an identical search tree in response to the received leaf pointers so as to reconstitute the original data stream.

348 Citations

244 Claims

1. A data compression and decompression system for compressing digital data and recovering the original data from the compressed data, said system including means for reading the digital data from a medium to provide a stream of data symbol signals, said data symbol signals being members of an alphabet of symbol signals comprising a predetermined number of symbol signals, said system including compression apparatus responsive to said stream of data symbol signals for providing a compressed stream of code signals corresponding thereto and applying said code signals to a medium, said system further including decompression apparatus responsive to said code signals for recovering the original data therefrom, said compression apparatus comprising:
- means for parsing said stream of data symbol signals into segments, each segment comprising a prefix and the next data symbol signal occurring in said stream after said prefix, said prefix comprising the longest match with a previous segment, said parsing means defining a first search tree having nodes and branches emanating from said nodes, each node having at most one incoming branch, the outgoing branches emanating from a node being representative of said symbol signals of said alphabet, respectively, said nodes having respective node labels associated therewith and respective addresses associated therewith, said first search tree having a unique root node without an incoming branch and leaf nodes without outgoing branches,said parsing means comprising means for tracing said stream of data symbol signals through said first search tree along a path from said root node to a leaf node, including means responsive to said stream of data symbol signals for determining the branches of said path in accordance with said symbol signals respectively,said parsing means comprisingfirst storage means comprising a plurality of storage locations corresponding respectively to said addresses of said nodes of said tree, said storage locations being utilized for storing said node labels, a node label stored at a particular storage location identifying the node whose address corresponds to said particular storage location,address generator means for generating an address signal and for providing said address signal to said first storage means for accessing said storage locations thereof, said first storage means providing, in response thereto, the node label stored in the storage location accessed by said address signal, said address generator means being responsive to a node label provided by said first storage means and to a data symbol signal from said stream of data symbol signal for generating said address signal in accordance therewith,first detecting means for detecting when an accessed storage location of said first storage means does not contain a node label, said storage location not containing a node label defining a leaf node of said first search tree, andnode counting means for inserting a node label into said accessed storage location of said first storage means detected by said first detecting means as not containing a node label;
  
  said address generator means comprising means for sequentially generating said address signals and for providing said address signals to said first storage means, the node label provided by said first storage means in response to an address signal providing the node label for generating the next address signal, said address generator means sequentially generating said address signals in accordance with the node labels sequentially provided by said first storage means respectively and in accordance with successive symbol signals of said stream of data symbol signals respectively, said address generator means sequentially generating said address signals until said first detecting means detects an accessed storage location of said first storage means without a node label; and
  
  means responsive to the address of said accessed storage location not containing a node label for generating a pointer signal in accordance therewith for each said segment, said pointer signal being representative of said previous segment matching said prefix and of said next occurring data symbol signal after said prefix,thereby providing pointer signals for segments of said stream of data symbol signals, respectively,said pointer signals comprising said compressed stream of code signals.
- View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 239)
- - 2. The compression apparatus of claim 1 in which said address generator means comprises means for generating said address signal further in accordance with the number of symbol signals comprising said alphabet.
  - 3. The compression apparatus of claim 1 in which said means for tracing said stream of data symbol signals through said first search tree from said root node to a leaf node includes means for initiating said tracing by accessing said first storage means at said storage location corresponding to said root node.
  - 4. The compression apparatus of claim 1 in which said node counting means comprises means for generating successively increasing node labels in accordance with said first detecting means detecting accessed storage locations of said first storage means not containing node labels respectively.
  - 5. The compression apparatus of claim 4 in which said parsing means further comprisessymbol mapping means for assigning ordered symbol position signals to said symbol signals of said alphabet, respectively,said symbol position signals being provided to said address generator means for generating said address signals in accordance therewith.
  - 6. The compression apparatus of claim 5 in which said outgoing branches emanating from a node are representative of said symbol signals of said alphabet, respectively, in accordance with the order in which said symbol signals of said alphabet are received by said parsign means, said symbol mapping means comprising means for assigning said ordered symbol position signals to said symbol signals of said alphabet, respectively, in accordance with the order in which said symbol signals of said alphabet are received by said parsing means.
  - 7. The compression apparatus of claim 6 in which said outgoing branches emanating from a node have positions with respect to each other in accordance with the order in which said symbol signals of said alphabet are received by said parsing means, said symbol mapping means comprisingsecond storage means comprising a plurality of storage locations corresponding respectively to said symbol signals of said alphabet, said storage locations being utilized for storing said symbol position signals, a symbol position signal symbol signal of said alphabet indicating the order in which said particular symbol signal was received by said parsing means with respect to the other symbol signals of said alphabet, said second storage means being accessed by the symbol signals of said stream of data symbol signals to provide the symbol position signals stored at said storage locations corresponding to the accessing symbol signals,said symbol position signal provided by said second storage means being provided to said address generator means for generating said address signals in accordance therewith.
  - 8. The compression apparatus of claim 7 in which said symbol mapping means further includes second detecting means for detecting when an accessed storage location of said second storage means does not contain a symbol position signal.
  - 9. The compression apparatus of claim 8 in which said symbol mapping means further includes position counting means for inserting a symbol position signal into said accessed storage location of said second storage means detected by said second detecting means as not containing a symbol position signal.
  - 10. The compression apparatus of claim 9 in which said position counting means comprises means for generating successive symbol position signals in response to said second detecting means detecting storage locations of said second storage means not containing symbol position signals.
  - 11. The compression apparatus of claim 6 in which said address generator means comprises means for generating said address signal in accordance with the product of said node label provided by said first storage means with the number of symbol signals comprising said alphabet less said symbol position signal provided by said symbol mapping means.
  - 12. The compression apparatus of claim 11 in which said address generator means comprises means for generating said address signal in accordance with
    
    space="preserve" listing-type="equation">address signal=i|A|-p+2
    where i comprises said node label, |A| comprises the number of symbol signals of said alphabet and p comprises said symbol position signal.
- 13. The compression apparatus of claim 1 in which said first storage means includes a directly addressed portion and a hash addressed portion and said address generator means further compriseshashing limit comparator means for comparing said address signal to a predetermined hashing limit, andhashing means for hashing said address signal thereby providing a hashed address signal,said address generator means including means for providing either said address signal or said hashed address signal to said first storage means in accordance with the comparison between said address signal and said hashing limit.
- 14. The compression apparatus of claim 1 in which said means defining a first search tree comprises means defining a first search tree having alpha-branches emanating from said nodes representative of all of the symbol signals of said alphabet not yet encountered during said compressing of said stream of data symbol signals.
- 15. The compression apparatus of claim 10 in which said means defining a first search tree comprises means defining a first seach tree having alpha-branches emanating from said nodes representative of all of the symbol signals of said alphabet not yet encountered during said compressing of said stream of data symbol signals, an alpha-branch of said first search tree being encountered when said second detecting means detects an accessed storage location of said second storage means not containing a symbol position signal.
- 16. The compression apparatus of claim 10 in which said means for generating a pointer signal includes leaves-only converter means responsive to said address signals from said address generator means and said node labels from said first storage means for providing a leaves-only pointer signal in accordance therewith.
- 17. The compression apparatus of claim 16 in which said leaves-only converter means comprises means for providing said leaves-only pointer signal in accordance with the difference between said address signals and said node labels, respectively.
- 18. The compression apparatus of claim 17 in which said leaves-only converter means comprises means for providing said leaves-only pointer signal in accordance with
  
  space="preserve" listing-type="equation">D=C-E-1
  where D comprises said leaves-only pointer signal, C comprises said address signal and E comprises said node label.
19. The compression apparatus of claim 17 in which said leaves-only converter means includes means for inhibiting taking said difference between an address signal and a node label whenever the symbol signal that resulted in the address signal is a predetermined symbol signal of said alphabet.
20. The compression apparatus of claim 17 in which said leaves-only converter means includes means for inhibiting taking said difference between an address signal and a node label whenever the symbol signal that resulted in the addressing signal is the first symbol signal encountered by said encoding apparatus in compressing said stream of data symbol signals.
21. The compression apparatus of claim 17 in which said leaves-only converter means includes means responsive to said symbol position signals for inhibiting taking said difference between an address signal and a node label whenever the symbol position signal resulting in the address signal is that symbol position signal assigned to a predetermined symbol signal.
22. The compression apparatus of claim 17 in which said leaves-only converter means includes means responsive to said symbol position signals for inhibiting taking said difference between an address signal and a node label whenever the symbol position signal resulting in the address signal is that symbol position signal assigned to the first symbol signal of said alphabet encountered by said encoding apparatus in compressing said stream of data symbol signals.
23. The compression apparatus of claim 16 in which said means for generating a pointer signal further includes green-leaves converter means responsive to said leaves-only pointer signal for generating a green-leaves pointer signal corresponding thereto in accordance with the number of symbol signals of said alphabet not yet encountered by said encoding apparatus during said compressing of said stream of data symbol signals.
24. The compression apparatus of claim 16 in which said means for generating a pointer signal further includes green-leaves converter means responsive to said leaves-only pointer signal for generating a green-leaves pointer signal corresponding thereto in accordance with the number of symbol signals of said alphabet currently encountered by said encoding apparatus during said compressing of said stream of data symbol signals.
25. The compression apparatus of claim 23 in which greenleaves converter means includes means for generating said green-leaves pointer signal further in accordance with said number of symbol signals of said alphabet.
26. The compression apparatus of claim 25 in which said green-leaves converter means comprises means for generating said green-leaves pointer signal in accordance with

space="preserve" listing-type="equation">D.sub.g

space="preserve" listing-type="equation">=D+(1-NSYM)(D/(|A|-1))where D_g comprises said green-leaves pointer signal, D comprises said leaves-only pointer signal, NSYM comprises a signal representative of the number of symbol signals of said alphabet not yet encountered by said encoding apparatus during said compressing of said stream of data symbol signals, |A| comprises the number of symbol signals of said alphabet and D_g is generated utilizing integer arithmetic.

27. The compression apparatus of claim 23 in which said green-leaves converter means comprises means responsive to said symbol position signal for providing said number of symbol signals not yet encountered.

28. The compression apparatus of claim 26 in which said green-leaves converter means comprises means responsive to said symbol position signal for providing said NSYM signal.

29. The compression apparatus of claim 23 in which said means for generating a pointer signal further includes means responsive to said first detecting means for enabling said green-leaves converter means to convert said leaves-only pointer signal to said green-leaves pointer signal when said first detecting means detects an accessed storage location of said first storage means without a node label.

30. The compression apparatus of claim 29 in which said means for enabling said green-leaves converter means comprises gating means coupling said leaves-only converter means to said green-leaves converter means and responsive to said first detecting means for transferring said leaves-only pointer signal to said green-leaves converter means when said first detecting means detects an accessed storage location of said first storage means without a node label.

31. The compression apparatus of claim 23 further including symbol counting means for providing a symbol count signal in accordance with the number of symbol signals of said alphabet currently encountered by said encoding apparatus during said compressing of said stream of data symbol signals, said symbol counting means being responsive to said second detecting means for incrementing said symbol count signal when said second detecting means detects an accessed storage location of said second storage means not containing a symbol position signal.

32. The compression apparatus of claim 31 further including pointer counting means for providing a pointer count signal representative of the number of leaf nodes in said first search tree.

33. The compression apparatus of claim 32 in which said node counting means comprises means for generating a node count signal representative of the number of nodes of said first search tree that are not leaf nodes, said node count signal providing said node labels for insertion into said first storage means, said node counting means being responsive to said first detecting means for incrementing said node count signal when said first detecting means detects an accessed storage location of said first storage means not containing a node label, andsaid position counting means comprises means for generating a position count signal representative of the number of symbol signals of said alphabet not yet encountered by said encoding apparatus during said compressing of said stream of data symbol signals, said position count signal providing said symbol position signals for insertion into said second storage means, said position counting means being responsive to said second detecting means for decrementing said position count signal when said second detecting means detects an accessed storage location of said second storage means not containing a symbol position signal.

34. The compression apparatus of claim 33 in which said pointer counting means comprises means responsive to said node count signal and said symbol count signal and to said first and second detecting means for incrementing said pointer count signal by said symbol count signal when said first detecting means detects an accessed storage location of said first storage means not containing a node label and for incrementing said pointer count signal by said node count signal when said second detecting means detects an accessed storage location of said second storage means not containing a symbol position signal.

35. The compression apparatus of claim 34 in which said position counting means includes means for generating an inhibit signal when said position count signal attains a predetermined position count.

36. The compression apparatus of claim 35 in which said symbol counting means comprises means responsive to said inhibit signal for inhibiting said symbol count signal from being incremented beyond a predetermined symbol count.

37. The compression apparatus of claim 36 in which said symbol counting means comprises means responsive to said inhibit signal for inhibiting said symbol count signal from being incremented beyond one less than the number of symbol signals comprising said alphabet.

38. The compression apparatus of claim 35 in which said pointer counting means comprises means responsive to said inhibit signal for inhibiting said pointer count signal from being incremented by said node count signal.

39. The compression apparatus of claim 32 in which said means for generating a pointer signal includes pointer economy encoder means responsive to said green-leaves pointer signal for converting said green-leaves pointer signal into a corresponding pointer economy code signal in accordance with a predetermined prefix code.

40. The compression apparatus of claim 32 in which said means for generating a pointer signal includes pointer ecomony encoder means responsive to said green-leaves pointer signal for converting said green-leaves pointer signal to a corresponding pointer economy code signal in accordance with a predetermined left biased prefix code.

41. The compression apparatus of claim 39 in which said pointer economy encoder means comprisespointer threshold calculator means responsive to said pointer count signal for generating a pointer threshold in accordance therewith,pointer threshold comparator means responsive to said green-leaves pointer signal and said pointer threshold for determining when said green-leaves pointer signal exceeds said pointer threshold, andpointer output converter means responsive to said green-leaves pointer signal and said pointer threshold for converting said green-leaves pointer signal into a converted green-leaves pointer signal in accordance with said pointer threshold,said green-leaves pointer signal or said converted green-leaves pointer signal providing said pointer economy code signal in accordance with said green-leaves pointer signal exceeding said pointer threshold.

42. The compression apparatus of claim 41 in whichsaid pointer threshold calculator means comprises means for calculating said pointer threshold in accordance with

space="preserve" listing-type="equation">TB=2H-KB
where TB comprises said pointer threshold, H comprises said pointer count signal and KB comprises the least integer that is not less than log₂ (H), andsaid pointer output converter means comprises means for converting said green-leaves pointer signal to said converted green-leaves pointer signal in accordance with

space="preserve" listing-type="equation">Converted D.sub.g =(2D.sub.g

space="preserve" listing-type="equation">-TB)/2 where D_g comprises said green-leaves pointer signal.

43. The compression apparatus of claim 33 further comprising new symbol detecting means including said second detecting means for detecting that a symbol signal has been newly encountered by said encoding apparatus when said second detecting means detects a storage location of said second storage means not containing a symbol position signal.

44. The compression apparatus of claim 43 further including means enabled by said new symbol detecting means for assigning predetermined rank signals to said symbol signals of said alphabet respectively.

45. The compression apparatus of claim 44 in which said rank assigning means comprises third storage means comprising a plurality of storage locations corresponding respectively to said symbol signal of said alphabet, said storage locations being utilized for storing said rank signals corresponding to said symbols respectively, said third storage means being accessed by a newly encountered symbol to provide the rank signal stored at said storage location corresponding to the newly encountered symbol.

46. The compression apparatus of claim 45 in which said rank assigning means further includes means for deleting a storage location and the corresponding rank signal from said third storage means when the symbol signal corresponding thereto is first encountered by said encoding apparatus during said compressing of said stream of data symbol signals and for decrementing all rank signals subsequent to said deleted storage location.

47. The compression apparatus of claim 45 further including rank economy encoder means responsive to the rank signal provided by said third storage means for converting said rank signal into a corresponding rank economy code signal in accordance with a predetermined prefix code.

48. The compression apparatus of claim 45 further including rank economy encoder means responsive to the rank signal provided by said third storage means for converting said rank signal into a corresponding rank ecomony code signal in accordance with a predetermined left biased prefix code.

49. The compression apparatus of claim 47 in which said rank economy encoder means comprisesrank threshold calculator means responsive to said position count signal for generating a rank threshold in accordance therewith,rank threshold comparator means responsive to said rank signal and said rank threshold for determining when said rank signal exceeds said rank threshold, andrank output converter means responsive to said rank signal and said rank threshold for converting said rank signal into a converted rank signal in accordance with said rank threshold,said rank signal or said converted rank signal providing said rank economy code signal in accordance with said rank signal exceeding said rank threshold.

50. The compression apparatus of claim 49 in which said rank threshold calculator means comprises means for calculating said rank threshold in accordance with

space="preserve" listing-type="equation">TA=2NSYM-KA
where TA comprises said rank threshold, NSYM comprises said position count signal and KA comprises the last integer that is not less than log₂ (NSYM) andsaid rank output converter means comprises means for converting said rank signal to said converted rank signal in accordance with

space="preserve" listing-type="equation">Converted R=(2R-TA)/2 where R comprises said rank signal,said rank economy code signal being provided in said compressed stream of code signals.

51. The compression apparatus of claim 1 further including means for providing said successive symbol signals of said data stream in accordance with said first detecting means detecting accessed storage locations of said first storage means containing node labels respectively.

52. The compression apparatus of claim 1 in which said parsing means further comprisessymbol mapping means for assigning ordered symbol position signals to said symbol signals of said alphabet, respectively, andmeans responsive to said first detecting means for providing said successive symbol signals of said data stream to said symbol mapping means when said first detecting means detects accessed storage locations of said first storage means containing node labels respectively,said symbol position signals being provided to said address generator means for generating said address signals in accordance with said successive symbol signals of said stream of data symbols.

53. The compression apparatus of claim 33 further includingmeans for comparing said node count signal to a predetermined constant, andmeans for inhibiting said node counting means from incrementing said node count signal, for inhibiting said first storage means from inserting said node label therein and for inhibiting said pointer counting means from incrementing said pointer count signal by said symbol count signal, whenever said node count signal exceeds said predetermined constant.

54. The data compression and data recovery system of claim 1 in which said decompression apparatus comprises means for recovering said segments of said stream of data symbol signals from said poiner signals, respectively.

55. The decompression apparatus of claim 54 in which said segment recovery means comprises means defining a second search tree having nodes and branches emanating from said nodes, each node having at most one incoming branch, the outgoing branches emanating from a node being representative of said symbol signals of said alphabet respectively, said nodes having respective node labels associated therewith and respective addresses associated therewith, said second search tree having a unique root node without an incoming branch and leaf nodes without outgoing branches,said segment recovery means comprising means for tracing a path through said second search tree to said root from the leaf node corresponding to a pointer signal, extracting from the branches of said path the respective symbol signals associated with said branches,thereby recovering the segment corresponding to said pointer signal.

56. The decompression apparatus of claim 55 in which said segment recovery means comprisesfourth storage means comprising a plurality of storage locations corresponding respectively to said nodes of said second search tree, said storage locations being utilized for storing said addresses of said nodes, an address stored at a particular storage location being the address of the node corresponding to said particular storage location,label generator means for generating a node label signal and for providing said node label signal to said fourth storage means for accessing said storage locations thereof said fourth storage means providing, in response thereto, the address stored in the storage location accessed by said node label signal, said label generator means being responsive to an address provided by said fourth storage means for generating said node label signal in accordance therewith.

57. The decompression apparatus of claim 56 in which said label generator means comprises means responsive to said address provided by said fourth storage means for generating the node label signal corresponding to the father node of the node having said address provided by said fourth storage means.

58. The decompression apparatus of claim 56 in which said label generator means comprises means for generating said node label signal further in accordance with the number of symbol signals comprising said alphabet.

59. The decompression apparatus of claim 58 in which said label generator means comprises means for generating said node label signal in accordance with

space="preserve" listing-type="equation">node label=1+(C-2)/|A|
where C comprises said address provided by said fourth storage means, |A| comprises the number of symbol signals of said alphabet and said node label signal is generated utilizing integer arithmetic.

60. The decompression apparatus of claim 56 in which said segment recovery means further includes third detecting means for detecting when an accessed storage location of said fourth storage means contains the address for said root node.

61. The decompression apparatus of claim 56 in which said segment recovery means further comprises symbol extracting means responsive to the address provided by said fourth storage means and to the node label signal provided by said label generator means for providing the symbol signal corresponding thereto.

62. The decompression apparatus of claim 57 in which said segment recovery means includes means for inserting the address of said leaf node corresponding to said pointer signal into a storage location of said fourth storage means not containing an address, said storage location into which said address is inserted sequentially following the last storage location of said fourth storage means having an address stored thereat.

63. The decompression apparatus of claim 62 in which said means for inserting said address further includes means for applying said leaf address to said label generator means for generating a node label signal corresponding to the node label of said father node of said leaf node.

64. The decompression apparatus of claim 61 in which said segment recovery means includes leaf determining means responsive to the address corresponding to said pointer signal for determining the leaf address corresponding thereto and for providing a leaf address signal in accordance therewith.

65. The decompression apparatus of claim 64 in which said symbol signals of said alphabet have respective symbol position signals associated therewith and said leaf determining means comprises means defining a third search tree identical to said first search tree,said leaf determining means including means for tracing a path through said third search tree from a node thereof having said address corresponding to said pointer signal to a leaf node along said path comprised of branches representative of a predetermined symbol signal of said alphabet,the address of said leaf node providing said leaf address signal to said fourth storage means and to said label generator means.

66. The decompression apparatus of claim 65 in which said means for tracing a path through said third search tree comprises means for tracing said path through said third seach tree along said path comprised of branches representative of the first symbol signal of said alphabet encountered by said encoding apparatus in compressing said stream of data symbol.

67. The decompression apparatus of claim 65 in which said leaf determining means comprisesfifth storage means comprising a plurality of storage locations corresponding respectively to said addresses of said nodes of said third search tree, said storage locations being utilized for storing said node labels, a node label stored at a particular storage location identifying the node whose address corresponds to said particular storge location, andaddressing means for generating an address signal and for providing said address signal to said fifth storage means, said fifth storage means providing, in response thereto, the node label stored in the storage location addressed by said addressing signal, said addressing means being responsive to a node label provided by said fifth storage means for generating said address signal in accordance with said node label in accordance with said predetermined symbol signal of said alphabet.

68. The decompression apparatus of claim 67 in which said addressing means comprises means for generating said address signal in accordance with the first symbol signal encountered by said encoding apparatus during said compressing of said stream of data symbol signals.

69. The decompression apparatus of claim 67 in which said addressing means comprises means for generating said address signal in accordance with said symbol position signal representative of said predetermined symbol signal.

70. The decompression apparatus of claim 68 in which said addressing means comprises means for generating said address signal in accordance with said symbol position signal representative of said first encountered symbol signal.

71. The decompression of claim 70 in which said addressing means comprises means for generating said address signal in accordance with the product of said node label provided by said fifth storage means with said number of symbols comprising said alphabet less said symbol position signal representative of said first encountered symbol signal.

72. The decompression apparatus of claim 71 in which said addressing means comprises means for generating said address signal in accordance with

space="preserve" listing-type="equation">address signal=i|A|-|A|+2
where i comprises said node label, i|A| comprises said product of said node label with said number of symbol signals comprising said alphabel and |A| comprises said symbol position signal for said first encountered symbol signal.

73. The decompression apparatus of claim 67 in which said leaf determining means further includes fourth detecting means for detecting when an accessed storage location of said fifth storage means does not contain a node label,the address of said accessed storage location of said fifth storage means not containing a node label providing said leaf address signal to said fourth storage means and to said label generator means.

74. The decompression apparatus of claim 73 in which said leaf determining means further includes node counting means for inserting a node label into said accessed storage location of said fifth storage means detected by said fourth detecting means as not containing a node label.

75. The decompression apparatus of claim 74 in which said node counting means comprises means for generating successively increasing node labels in accordance with said fourth detecting means detecting accessed storage locations of said fifth storage means as not containing node labels repectively.

76. The decompression apparatus of claim 75 in which said node counting means comprises means for generating a node count signal representative of the number of nodes of said third search tree that are not leaf nodes, said node count signal providing said node label for insertion into said fifth storage means, said node counting means being responsive to said fourth detecting means for incrementing said node count signal as a result of said fourth detecting means detecting an accessed storage location of said fifth storage means as not containing a node label.

77. The decompression apparatus of claim 75 in which said node counting means comprises means for generating a node count signal representative of the number of nodes of said third search tree that are not leaf nodes, said node count signal providing said node label for insertion into said fifth storage means, said node counting means being responsive to said third detecting means for incrementing said node count signal when said third detecting means detects said storage location of said fourth storage means containing said address of said root node,said node count signal accessing said fourth storage means for insertion of said leaf address signal into the storage location of said fourth storage means accessed by said node count signal.

78. The decompression apparatus of claim 77 in which said leaf detecting means further includes means responsive to said leaf address signal, said node count signal and said fourth detecting means for transmitting said node count signal and said leaf address signal to said fourth storage means for insertion of said leaf address signal into the storage location of said fourth storage means accessed by said node count signal when said fourth detecting means detects a storage location of said fifth storage means as not containing a node label, said means for transmitting said leaf address further comprising means for providing said leaf address signal to said label generator means when said fourth detecting means detects a storage location of said fifth storage means as not containing a node label.

79. The decompression apparatus of claim 73 in which said addressing means comprises means for sequentially generating address signals and providing said address signals to said fifth storage means, the node label provided by said fifth storage means in response to an address signal providing the node label for generating the next address signal, said addressing means sequentially generating said address signals in accordance with the node labels sequentially provided by said fifth storage means respectively and in accordance with said predetermined symbol signal of said data alphabet, said addressing means sequentially generating said address signals until said fourth detecting means detects an addressed storage location of said fifth storage means without a node label.

80. The decompression apparatus of claim 67 in which said fifth storage means includes a directly addressed portion and a hash addressed portion and said addressing means includeshashing limit comparator means for comparing said address signal to a predetermined hashing limit, andhashing means for hashing said address signal thereby providing a hashed address,said addressing means including means for providing either said address signal or said hashed address to said fifth storage means in accordance with the comparison between said address signal and said hashing limit.

81. The decompression apparatus of claim 76 in whichsaid symbol signals of said alphabet have respective symbol position signals associated therewith, andsaid symbol extracting means includes position extractor means responsive to said node label signal from said label generator means and to said address from said fourth storage means for generating a symbol position signal in accordance therewith.

82. The decompression apparatus of claim 81 in which said position extractor means comprises means for generating said symbol position signal further in accordance with said number of symbol signals comprising said alphabet.

83. The decompression apparatus of claim 82 in which said position extractor means comprises means for generating said symbol position signal in accordance with the product of said node label signal and said number of symbol signals comprising said alphabet less said address.

84. The decompression apparatus of claim 83 in which said position extractor means comprises means for generating said symbol position signal in accordance with

space="preserve" listing-type="equation">p=|A|·

Cl-C+2
where p comprises said symbol position signal, |A| comprises said number of symbol signals of said alphabet, Cl comprises said node label signal and C comprises said address.

85. The decompression apparatus of claim 81 in which said symbol extracting means includes position-symbol converter means responsive to said symbol position signals from said position extractor means for providing a symbol signal corresponding to said symbol position signal.

86. The decompression apparatus of claim 85 in which said position-symbol converter means comprises a sixth storage means comprising a plurality of storage locations corresponding respectively to said symbol position signals, said storage locations of said sixth storage means being utilized for storing said symbol signals corresponding to said symbol position signals respectively, said sixth storage means being accessed by said symbol position signal from said position extractor means for providing the symbol signal stored at the storage location accessed by the symbol position signal.

87. The decompression apparatus of claim 86 in which said symbol extracting means further includes fifth detecting means for detecting when an accessed storage location of said sixth storage means does not contain a symbol signal.

88. The decompression apparatus of claim 87 in which said symbol extracting means includes means responsive to said fifth detecting means for providing a rank signal extracted from said compressed stream of code signals representative of a newly encountered symbol signal whenever said fifth detecting means detects a storage location of said sixth storage means not containing a symbol signal.

89. The decompression apparatus of claim 88 in which said symbol extracting means further includes means responsive to said rank signal for converting said rank signal to the newly encountered symbol signal of said alphabet corresponding thereto.

90. The decompression apparatus of claim 89 in which said means for converting said rank signal comprises seventh storage means comprising a plurality of storage locations corresponding respectively to said rank signals, respectively, said storage locations being utilized for storing said symbol signals corresponding to said rank signals, respectively, said seventh storage means being accessed by a rank signal to provide the symbol signal stored at said storage location accessed by said rank signal.

91. The decompression apparatus of claim 90 in which said means for converting said rank signal further includes means for deleting a symbol signal from said seventh storage means when the rank signal corresponding thereto is received by said decoding apparatus during said recovering of said segments of said stream of data symbols and for effectively decrementing the rank signals subsequent to said deleted symbol signal.

92. The decompressing apparatus of claim 90 in which said sixth storage means includes means for receiving said symbol signal from said seventh storage means and for storing said symbol signal at the storage location thereof accessed by said position signal that resulted in said fifth detecting means detecting that an accessed storage location of said sixth storage means does not contain a symbol signal.

93. The decompression apparatus of claim 89 further including symbol counting means for providing a symbol count signal in accordance with the number of newly encountered symbol signals received by said decoding apparatus, said symbol counting means being responsive to said fifth detecting means for incrementing said symbol count signal when said fifth detecting means detects a storage location of said sixth storage means not containing a symbol signal.

94. The decompression apparatus of claim 93 further including position counting means for generating a position count signal representative of said number of symbol signals comprising said alphabet less the number of newly encountered symbol signals encountered by said decoding apparatus, said position counting means being responsive to said fifth detecting means for decrementing said position count signal when said fifth detecting means detects a storage location of said sixth storage means as not containing a symbol signal.

95. The decompression apparatus of claim 94 further including pointer counting means for providing a pointer count signal representative of the number of leaf nodes in said second search tree.

96. The decompression apparatus of claim 95 in which said pointer counting means comprises means responsive to said node count signal and said symbol count signal and to said third and fifth detecting means for incrementing said pointer count signal by said symbol count signal when said third detecting means detects said storage location of said fourth storage means containing said address of said root and for incrementing said pointer count signal by said node count signal when said fifth detecting means detects a storage location of said sixth storage means as not containing a symbol signal.

97. The decompression apparatus of claim 96 in which said position counting means includes means for generating an inhibit signal when said position count signal attains a predetermined count.

98. The decompression apparatus of claim 97 in which said symbol counting means comprises means responsive to said inhibit signal for inhibiting said symbol count signal from being incremented beyond a predetermined count.

99. The decompression apparatus of claim 98 in which said symbol counting means comprises means responsive to said inhibit signal for inhibiting said symbol count signal from being incremented beyond one less than the number of symbol signals comprising said alphabet.

100. The decompression apparatus of claim 97 in which said pointer counting means comprises means responsive to said inhibit signal for inhibiting said pointer count signal from being incremented by said node count signal.

101. The decompression apparatus of claim 95 in which said pointer signals provided by said encoding apparatus comprise a pointer economy code signal,said decoding apparatus further comprising pointer economy decoder means responsive to said pointer economy code signal for converting said pointer economy code signal to a green-leaves pointer signal corresponding thereto utilizing a predetermined prefix code.

102. The decompression apparatus of claim 101 in which said pointer economy decoder means comprises means for converting said pointer economy code signal to said green-leaves pointer signal utilizing a predetermined left biased prefix code.

103. The decompression apparatus of claim 101 in which said pointer economy decoder means comprisespointer threshold calculator means responsive to said pointer count signal for generating a pointer threshold in accordance therewith,pointer threshold comparator means responsive to said pointer economy code signal and said pointer threshold for determining when said pointer economy code signal exceeds said pointer threshold, andpointer code converter means responsive to said pointer economy code signal and said pointer threshold for converting said pointer economy code signal into a converted pointer economy code signal in accordance with said pointer threshold,said pointer economy code signal or said converted pointer economy code signal providing said green-leaves pointer signal in accordance with said pointer economy code signal exceeding said pointer threshold.

104. The decompression apparatus of claim 103 in whichsaid pointer threshold calculator means comprises means for calculating said pointer threshold in accordance with

space="preserve" listing-type="equation">TB=2H-KB
where TB comprises said pointer threshold, H comprises said pointer count signal and KB comprises the least integer that is not less than log₂ (H), andsaid pointer code converter means comprises means for converting said pointer economy code signal to said converted pointer economy code signal in accordance with

space="preserve" listing-type="equation">Converted Y.sub.k =(Y.sub.k +TB)/2 where Y_k comprises said pointer economy code signal and said converted pointer economy code signal is generated utilizing integer arithmetic.

105. The decompression apparatus of claim 101 further comprising leaves-only converter means responsive to said green-leaves pointer signal and to said symbol count signal for converting said green-leaves pointer signal to a corresponding leaves-only pointer signal in accordance with said symbol count signal.

106. The decompression apparatus of claim 105 in which said leaves-only converter means includes means responsive to said position count signal for converting said green-leaves pointer signal to said leaves-only pointer signal in accordance with said position count signal.

107. The decompression apparatus of claim 106 in which said leaves-only converter means comprises means for converting said green-leaves pointer signal to said leaves-only pointer signal in accordance with

space="preserve" listing-type="equation">D=D.sub.g +CSYM((D.sub.g -1)/BSYM)
where D comprises said leaves-only pointer signal, D_g comprises said green-leaves pointer signal, CSYM comprises (NSYM-1) or zero when NSYM=0, NSYM comprises said position count signal, BSYM comprises said symbol count signal and said leaves-only pointer signal D is derived utilizing integer arithmetic.

108. The decompression apparatus of claim 105 in which said leaves-only converter means includes means responsive to said green-leaves pointer signal for determining when said green-leaves pointer signal equals zero and providing a zero valued leaves-only pointer signal in accordance therewith.

109. The decompression apparatus of claim 108 further including address converter means responsive to said leaves-only pointer signal for converting said leaves-only pointer signal to an address signal corresponding thereto.

110. The decompression apparatus of claim 109 in which said address converter means comprises means for providing said address signal in accordance with said number of symbol signals of said alphabet.

111. The decompression apparatus of claim 110 in which said address converter means comprises means for providing said address signal in accordance with

space="preserve" listing-type="equation">address signal=D+(D+2|A|-3)/(|A|-1)
where D comprises said leaves-only pointer signal, |A| comprises the number of symbol signals of said alphabet, and said address signal is generated utilizing integer arithmetic.

112. The decompression apparatus of claim 109 in which said address converter means includes means for providing said address signal from said address converter means to said leaf determining means for determining said leaf address signal corresponding thereto.

113. The decompression apparatus of claim 109 in which said address converter means includes means for providing said address signal from said address converter means to said addressing means of said leaf determining means resulting in said addressing means providing said address signal to said fifth storage means for commencing the tracing of said path through said third search tree from a node thereof having an address corresponding to said address signal from said address converter means.

114. The decompression apparatus of claim 94 in which said rank signal corresponding to said newly encountered symbol comprises a rank economy code signal,said decoding apparatus further including rank economy decoder means responsive to said rank economy code signal for converting said rank economy code signal into a corresponding decoded rank signal utilizing a predetermined prefix code.

115. The decompression apparatus of claim 94 in which said rank signal corresponding to said newly encountered symbol signal comprises a rank economy code signal,said decoding apparatus further including rank economy decoder means responsive to said rank economy code signal for converting said rank economy code signal into a corresponding decoded rank signal utilizing a predetermined left biased prefix code.

116. The decompression apparatus of claim 114 in which said rank economy decoder means comprisesrank threshold calculator means responsive to said position count signal for generating a rank threshold in accordance therewith,rank threshold comparator means responsive to said rank economy code signal and to said rank threshold for determining when said rank economy code signal exceeds said rank threshold, andrank code converter means responsive to said rank economy code signal and said rank threshold for converting said rank economy code signal into a converted rank economy code signal in accordance with said rank threshold,said rank economy code signal or said converted rank economy code signal providing said decoded rank signal in accordance with said rank economy code signal exceeding said rank threshold.

117. The decompression apparatus of claim 116 in whichsaid rank threshold calculator means comprises means for providing said rank threshold in accordance with

space="preserve" listing-type="equation">TA=2NSYM-KA
where TA comprises said rank threshold, NSYM comprises said position count signal and KA comprises the least integer that is not less than log₂ (NSYM), andsaid rank code converter means comprises means for converting said rank economy code signal to said converted rank economy code signal in accordance with

space="preserve" listing-type="equation">new R=(R+TA)/2 where R comprises said rank economy code signal and said converted rank economy code signal is generated utilizing integer arithmetic,said decoded rank signal being provided to said means for converting said rank signal for conversion to said newly encountered symbol signal of said alphabet corresponding thereto.

118. The decompression apparatus of claim 114 including means responsive to said fifth detecting means for enabling said rank economy decoder means to provide said decoded rank signal representative of a newly encountered symbol signal whenever said fifth detecting means detects a storage location of said sixth storage means not containing a symbol signal.

119. The decompression apparatus of claim 61 further including decoded segment reversing means responsive to symbol signals provided by said symbol extracting means for reversing the order in which said symbol signals are received by said decoded segment reversing means thereby recovering the segments of said stream of data symbol signals corresponding to said pointer signals respectively.

120. The decompression apparatus of claim 95 further includingmeans for comparing said node count signal to a predetermined constant, andmeans for inhibiting said node counting means from incrementing said node count signal, for inhibiting said fifth storage means from inserting said node label therein and for inhibiting said pointer counting means from incrementing said pointer count signal by said symbol count signal, whenever said node count signal exceeds said predetermined constant.

121. The decompression apparatus of claim 55 in which said means defining a second search tree comprises means defining a second search tree having alpha-branches emanating from said nodes representative of all of the symbol signals of said alphabet not yet encountered during said recovering of said segments.

122. The decompression apparatus of claim 88 in which said means defining a second search tree comprises means defining a second search tree having alpha-branches emanating from said nodes representative of all of the symbol signals of said alphabet not yet encountered during said recovering of said segments, an alpha-branch of said second search tree being encountered when said fifth detecting means detects an accessed storage location of said sixth storage means not containing a symbol signal.

239. The decompression method of claim 28 in which said step of generating said rank threshold comprises the step of providing said rank threshold in accordance with

space="preserve" listing-type="equation">TA=2NSYM-KA
where TA comprises said rank threshold, NSYM comprises said position count signal and KA comprises the least integer that is not less than log₂ (NSYM), andsaid step of converting said rank economy code signal into a converted rank economy code signal comprises the step of converting said rank economy code signal to said converted rank economy code signal in accordance with

space="preserve" listing-type="equation">converted R=(R+TA)/2 where R comprises said rank economy code signal and said converted rank economy code signal is generated utilizing integer arithmetic,said decoded rank signal being utlilized during said step for converting said rank signal to said symbol signal for converting said rank signal to said newly encountered symbol signal of said alphabet corresponding thereto.

123. A data compression and decompression method for compressing digital data and recovering the original data from the compressed data, said method including reading the digital data from a medium to provide a stream of data symbol signals, said data symbol signals being members of an alphabet of symbol signals comprising a predetermined number of symbol signals, said data compression and decompression method including a compression method for providing a compressed stream of code signals corresponding to said stream of data symbol signals and applying said code signals to a medium, said data compression and decompression method further including a decompression method for recovering the original data from said code signals, said compression method comprising:
- parsing said stream of data symbol signals into segments, each segment comprising a prefix and the next data symbol signal occurring in said stream after said prefix, said prefix comprising the longest match with a previous segment, said parsing step defining a first search tree having nodes and branches emanating from said nodes, each node having at most one incoming branch, the outgoing branches emanating from a node being representative of said symbol signals of said alphabet respectively, said nodes having respective node labels associated therewith and respective addresses associated therewith, said first search tree having a unique root node without an incoming branch and leaf nodes without outgoing branches,said parsing step comprising the step of tracing said stream of data symbol signals through said first search tree along a path from said root node to a leaf node, including the step of determining the branches of said path in accordance with said symbol signals, respectively, of said stream of data symbol signals,said parsing step comprising the steps ofstoring said node labels at respective storage locations of a first storage means, said storage locations of said first storage means corresponding respectively to said addresses of said nodes of said tree, a node label stored at a particular storage location identifying the node whose address corresponds to said particular storage location,generating an address signal,accessing said storage locations of said first storage means with said address signal, said first storage means providing, in response thereto, the node label stored in the storage location accessed by said address signal,said step of generating said address signal comprising the step of generating said address signal in accordance with a node label provided by said first storage means and a data symbol from said stream of data symbols,detecting when an accessed storage location of said first storage means does not contain a node label, said storage location not containing a node label defining a leaf node of said first search tree,andinserting a node label into said accessed storage location of said first storage means detected as not containing a node label;
  
  said step of generating said address signal comprising the steps ofsequentially generating address signals,providing said address signals to said first storage means, the node label provided by said first storage means in response to an address signal providing the node label for generating the next address signal,said step of sequentially generating said address signals comprising the step of sequentially generating said address signals in accordance with the node labels sequentially provided by said first storage means, respectively, and in accordance with successive symbols of said stream of data symbols, respectively,said address signals being sequentially generated in response to said sequentially provided node labels until an accessed storage location of said first storage means is detected without a node label; and
  
  generating a pointer signal, for each said segment, in accordance with the address of said accessed storage location of said first storage means not containing a node label, said pointer signal being representative of said previous segment matching said prefix and of said next occurring data symbol signal after said prefix, thereby providing pointer signals for segments of said stream of data symbol signals, respectively, said pointer signals comprising said compressed stream of code signals.
- View Dependent Claims (124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191, 192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207, 208, 209, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, 223, 224, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 240, 241, 242, 243, 244)
- - 124. The compression method of claim 123 in which said step of generating said address signal comprises the step of generating said address signal further in accordance with the number of symbol signals comprising said alphabet.
  - 125. The compression method of claim 123 in which said step of tracing said stream of data symbol signals through said first search tree from said root node to a leaf node includes the step of initiating said tracing by accessing said first storage means at said storage location corresponding to said root.
  - 126. The compression method of claim 123 in which said step of inserting a node label includes the step of generating successively increasing node labels, respectively, in accordance with the occurrence of said step of detecting accessed storage locations of said first storage means not containing node labels.
  - 127. The compression method of claim 126 in which said parsing step further comprises the step of assigning ordered symbol position signals to said symbol signals of said alphabet, respectively,said step of generating address signals comprising the step of generating address signals in accordance with said symbol position signals.
  - 128. The compression method of claim 127 in which said outgoing branches emanating from a node are representative of said symbol signals of said alphabet, respectively, in accordance with the order in which said symbol signals of said alphabet are received during said parsing step, said step of assigning ordered symbol position signals comprising the step of assigning said ordered symbol position signals to said symbol signals of said alphabet, respectively, in accordance with the order in which said symbol signals of said alphabet are received during said parsing step.
  - 129. The compression method of claim 128 in which said outgoing branches emanating from a node have positions with respect to each other in accordance with the order in which said symbol signals of said alphabet are received during said parsing step, said step of assigning ordered symbol position signals comprising the steps ofstoring said symbol position signals at storage locations of a second storage means, said storage locations corresponding respectively to said symbol signals of said alphabet, a symbol position signal stored at a storage location corresponding to a particular symbol signal of said alphabet indicating the order in which said particular symbol signal was received during said parsing step with respect to the other symbol signals of said alphabet, andaccessing said second storage means with the symbol signals of said stream of data symbol signals to provide the symbol position signals stored at said storage locations corresponding to the accessing symbols,said step of generating said address signals comprising the step of generating said address signals in accordance with said symbol position signals provided by said second storage means.
  - 130. The compression method of claim 129 in which said step of assigning said symbol position signals further comprises the step of detecting when an accessed storage location of said second storage means does not contain a symbol position signal.
  - 131. The compression method of claim 130 in which said step of assigning said symbol position signals includes the step of inserting a symbol position signal into said accessed storage location of said second storage means detected as not containing a symbol position signal.
  - 132. The compression method of claim 131 in which said step of inserting said symbol position signal includes the step of generating successive symbol position signals respectively in response to the occurrence of detecting said storage locations of said second storage means not containing symbol position signals.
  - 133. The compression method of claim 129 in which said step of generating said address signal comprises the step of generating said address signal in accordance with the product of said node label provided by said first storage means with the number of symbol signals comprising said alphabet less said symbol position signal provided by said second storage means.
  - 134. The compression method of claim 133 in which said step of generating said address signal comprises the step of generating said address signal in accordance with
    
    space="preserve" listing-type="equation">address signal=i|A|-p+2
    where i comprises said node label, |A| comprises the number of symbol signals of said alphabet and p comprises said symbol position signal.
- 135. The compression method of claim 123 in which said first storage means includes a directly addressed portion and a hash addressed portion, said step of generating said address signal further comprising the steps ofcomparing said address signal to a predetermined hashing limit,hashing said address signal thereby providing a hashed address signal, andproviding either said address signal or said hashed address signal to said first storage means in accordance with the comparison between said address signal and said hashing limit.
- 136. The compression method of claim 123 in which said step of defining a first search tree comprises the step of defining a first search tree having alpha-branches emanating from said nodes representative of all of the symbol signals of said alphabet not yet encountered during said parsing step.
- 137. The compression method of claim 132 in which said step of defining a first search tree comprises the step of defining a first search tree having alpha-branches emanating from said nodes representative of all of the symbol signals of said alphabet not yet encountered during said parsing step, an alpha-branch of said first search tree being encountered when an accessed storage location of said second storage means is detected as not containing a symbol position signal.
- 138. The compression method of claim 132 in which said step of generating a pointer signal includes the step of generating a leaves-only pointer signal in accordance with said node labels from said first storage means and said address signals.
- 139. The compression method of claim 138 in which said step of generating said leaves-only pointer signal comprises the step of generating said leaves-only pointer signal in accordance with the difference between said address signals and said node labels, respectively.
- 140. The compression method of claim 139 in which said step of generating said leaves-only pointer signal comprises the step of generating said leaves-only pointer signal in accordance with
  
  space="preserve" listing-type="equation">D=C-E-1
  where D comprises said leaves-only pointer signal, C comprises said address signal and E comprises said node label.
141. The compression method of claim 139 in which said step of generating said leaves-only pointer signal includes the step of inhibiting taking said difference between an address signal and a node label whenever the symbol that resulted in the address signal is a predetermined symbol of said alphabet.
142. The compression method of claim 139 in which said step of generating said leaves-only pointer signal includes the step of inhibiting taking said difference between an address signal and a node label whenever the symbol signal that resulted in the address signal is the first symbol signal of said alphabet encountered during the performance of said encoding method.
143. The compression method of claim 139 in which said step of generating said leaves-only pointer signal includes the step of inhibiting taking said difference between an address signal and a node label whenever the symbol position signal resulting in the address signal is that symbol position signal assigned to a predetermined symbol.
144. The compression method of claim 139 in which said step of generating said leaves-only pointer signal includes the step of inhibiting taking said difference between an address signal and a node label whenever the symbol position signal resulting in the address signal is that symbol position signal assigned to the first symbol signal of said alphabet encountered during the performance of said encoding method.
145. The compression method of claim 138, in which said step of generating a pointer signal further includes the step of generating a green-leaves pointer signal corresponding to said leaves-only pointer signal in accordance with the number of symbols of said alphabet not yet encountered during the performance of said encoding method.
146. The compression method of claim 138 in which said step of generating a pointer signal further includes the step of generating a green-leaves pointer signal corresponding to said leaves-only pointer signal in accordance with the number of symbol signals of said alphabet currently encountered during said encoding method.
147. The compression method of claim 145 in which said step of generating said green-leaves pointer signal further includes the step of generating said green-leaves pointer signal in accordance with said number of symbol signals of said alphabet.
148. The compression method of claim 147 in which said step of generating said green-leaves pointer signal comprises the step of generating said green-leaves pointer signal in accordance with

space="preserve" listing-type="equation">D.sub.g =D+(1-NSYM)(D/ (|A|-1))
where D_g comprises said green-leaves pointer signal, D comprises said leaves-only pointer signal, NSYM comprises a signal representative of the number of symbol signals of said alphabet not yet encountered during the performance of said encoding method, |A| comprises the number of symbol signals of said alphabet and D_g is generated utilizing integer arithemtic.

149. The compression method of claim 145 in which said step of generating said green-leaves pointer signal includes the step of providing said number of symbol signals not yet encountered in response to said symbol position signal.

150. The compression method of claim 148 in which said step of generating said green-leaves pointer signal includes the step of providing said NSYM signal in response to said symbol position signal.

151. The compression method of claim 145 in which said step of generating a pointer signal includes the step of enabling said step of converting said leaves-only pointer signal to said greeen-leaves pointer signal when an accessed storage location of said first storage means is detected without a node label.

152. The compression method of claim 145 further including the steps ofgenerating a symbol count signal in accordance with the number of symbol signals of said alphabet currently encountered during the performance of said encoding method, andincrementing said symbol count signal when an accessed storage location of said second storage means is detected as not containing a symbol position signal.

153. The compression method of claim 152 further including the step of providing a pointer count signal representative of the number of leaf nodes in said first search tree.

154. The compression method of claim 153 further including the steps ofgenerating a node count signal representative of the number of nodes of said first search tree that are not leaf nodes, said node count signal providing said node labels for insertion into said first storage means, andincrementing said node count signal when an accessed storage location of said first storage means is detected as not containing a node label.

155. The compression method of claim 154 further including the steps of generating a position count signal representative of the number of symbol signals of said alphabet not yet encountered during the performance of said encoding method, said position count signal providing said symbol position signals for insertion into said second storage means, anddecrementing said position count signal when an accessed storage location of said second storage means is detected as not containing a symbol position signal.

156. The compression method of claim 155 in which said step of generating said pointer count signal comprises the steps of incrementing said pointer count signal by said symbol count signal when an accessed storage location of said first storage means is detected as not containing a node label, andincrementing said pointer count signal by said node count signal when an accessed storage location of said second storage means is detected as not containing a symbol position signal.

157. The compression method of claim 156 in which said step of generating a position count signal includes the step of generating an inhibit signal when said position count signal attains a predetermined position count.

158. The compression method of claim 157 in which said step of generating said symbol count signal includes the step of inhibiting said symbol count signal from being incremented beyond a predetermined symbol count in response to said inhibit signal.

159. The compression method of claim 158 in which said step of generating said symbol count signal includes the step of inhibiting said symbol count signal from being incremented beyond one less than the number of symbol signals comprising said slphabet in response to said inhibit signal.

160. The compression method of claim 157 in which said step of generating said pointer count signal includes the step of inhibiting said pointer count signal from being incremented by said node count signal in response to said inhibit signal.

161. The compression method of claim 153 in which said step of generating a pointer signal includes the step of converting said green-leaves pointer signal into a corresponding pointer economy code signal in accordance with a predetermined prefix code.

162. The compression method of claim 153 in which said step of generating a pointer signal includes the step of converting said green-leaves pointer signal to a corresponding pointer economy code signal in accordance with a predetermined left biased prefix code.

163. The compression method of claim 161 in which said step of converting said green-leaves pointer signal to a corresponding pointer economy code signal coprises the steps ofgenerating a pointer threshold in accordance with said pointer count signal,comparing said green-leaves pointer signal to said pointer threshold for determining when said green-leaves pointer signal exceeds said pointer threshold, andconverting said green-leaves pointer signal into a converted green-leaves pointer signal in accordance with said pointer threshold,said green-leaves pointer signal or said converted green-leaves pointer signal providing said pointer economy code signal in accordance with said green-leaves pointer signal exceeding said pointer threshold.

164. The compression method of claim 163 in whichsaid step of generatinng a pointer threshold comprises the step of calculating said pointer threshold in accordance with

space="preserve" listing-type="equation">TB=2H-KB
where TB comprises said pointer threshold, H comprises said pointer count signal and KB comprises the least integer that is not less than log₂ (H), andsaid step of converting said green-leaves pointer signal into a converted green-leaves pointer signal comprises the step of converting said green-leaves pointer signal to said converted green-leaves pointer signal in accordance with

space="preserve" listing-type="equation">converted D.sub.g =(2D.sub.g -TB)/2 where D_g comprises said green-leaves pointer signal.

165. The compression method of claim 155 further comprising the step of detecting that a symbol signal ha been newly encountered during the performance of said encoding method when a storage location of said second storage means is detected as not containing a symbol position signal.

166. The compression method of claim 165 further including the step of assigning predetermined rank signals to said symbol signals of said alphabet, respectively, in response to detecting newly encountered symbol signals.

167. The compression method of claim 166 in which said step of assigning predetermined rank signals to said symbol signals of said alphabet comprises the steps ofstoring said rank signals corresponding to said symbol signals respectively at storage locations respectively of a third storage means, said storage locations of said third storage means corresponding respectively to said symbol signals of said alphabet, andacessing said third storage means by a newly encountered symbol signal to provide the rank signal stored at said storage location corresponding to the newly encountered symbol signal.

168. The compression method of claim 167 in which said step of assigning predetermined rank signals further includes the steps ofdeleting a storage location and the corresponding rank signal from said third storage means when the symbol signal corresponding thereto is first encountered during the performance of said encoding method, anddecrementing all rank signals subsequent to said deleted storage location.

169. The compression method of claim 168 further including the step of converting said rank signal provided by said third storage means into a corresponding rank economy code signal in accordance with a predetermined prefix code.

170. The compression method of claim 168 further including the step of converting said rank signal provided by said third storage means into a corresponding rank economy code signal in accordance with a predetermined left biased prefix code.

171. The compression method of claim 169 in which said step of converting said rank signal into a corresponding rank economy code signal comprises the steps ofgenerating a rank threshold in accordance with said position count signal,comparing said rank signal with said rank threshold for determining when said rank signal exceeds said rank threshold, andconverting said rank signal into a converted rank signal in accordance with said rank threshold,said rank economy or said converted rank signal providing said rank economy code signal in accordance with said rank signal exceeding said rank threshold.

172. The compression method of claim 171 in whichsaid step of generating a rank threshold comprises the step of calculating said rank threshold in accordance with

space="preserve" listing-type="equation">TA=2 NSYM-KA
where TA comprises said rank threshold, NSYM comprises said position count signal and KA comprises the least integer that is not less than log₂ (NSYM), andsaid step of converting said rank signal into a converted rank signal comprises the step of converting said rank signal to said converted rank signal in accordance with

space="preserve" listing-type="equation">converted R=(2R-TA)/2 where R comprises said rank signal,said rank economy code signal being provided in said compressed stream of code signals.

173. The compression method of claim 123 further including the step of providing said successive symbol signals of said data stream in accordance with detecting accessed storage locations of said first storage means containing node labels respectively.

174. The compression method of claim 123 in which said parsing step comprises the steps of assigning ordered symbol position signals to said symbol signals of said alphabet, respectively, andproviding said successive symbols of said data stream for assigning said ordered symbol position signals thereto when accessed storage locations of said first storage means are detected as containing node labels respectively,said step of generating said address signals comprising the step of generating said address signals in response to said symbol position signals in accordance with said successive symbol signals of said stream of data symbol signals.

175. The compression method of claim 168 further including the steps ofcomparing said node count signal to a predetermined constant, andinhibiting said node count signal from being incremented, inhibiting said node label from being inserted into said first storage means and inhibiting said pointer count signal from being incremented by said symbol count signal, whenever said node count signal exceeds said predetermined constant.

176. The data compression and data recovery method of claim 123, in which said decompression method comprises the step of recovering said segments of said stream of data symbol signals from said respective pointer signals of said compressed stream of code signals.

177. The decompression method of claim 176 in which said segment recovering step comprises the steps ofdefining a second search tree having nodes and branches emanating from said nodes, each node having at most one incoming branch, the outgoing branches emanating from a node being representative of said symbol signals of said alphabet respectively, said nodes having respective node labels associated therewith and respective addresses associated therewith, said second search tree having a unique root node without an incoming branch and leaf nodes without outgoing branches,tracing a path through said second search tree to said root from the leaf node corresponding to a pointer signal, andextracting from the branches from said path the respective symbol signals associated with said branches,thereby recovering the segment corresponding to said pointer signal.

178. The decompression method of claim 177 in which said segment recovering step comprises the steps ofstoring said addresses of said nodes of said second search tree at storage locations of a fourth storage means, said storage locations corresponding respectively to said nodes of said second search tree, an address stored at a particular storage location being the address of the node corresponding to said particular storage location,generating a node label signal, andproviding said node label signal to said fourth storage means for accessing said storage locations thereof, said fourth storage means providing, in response thereto, the address stored in the storage location accessed by said node label signal,said step of generating said node label signal comprising the step of generating said node label signal in accordance with an address provided by said fourth storage means.

179. The decompression apparatus of claim 178 in which said step of generating said node label signl comprises the step of generating said node label signal corresponding to the father node of the node having said address provided by said fourth storage means.

180. The decompression method of claim 178 in which said step of generating said node label signal includes the step of generating said label signal further in accordance with the number of symbol signals comprising said alphabet.

181. The decompression method of claim 180 in which said step of generating said node label signal comprises the step of generating said node label signal in accordance with

space="preserve" listing-type="equation">node label=1+(C-2)/|A|
where C comprises said address provided by said fourth storage means, |A| comprises the number of symbol signals of said alphabet and said node label signal is generated utilizing integer arithmetic.

182. The decompression method of claim 178 in which said segment recovering step further includes the step of detecting when an accessed storage location of said fourth storage means contains the address of said root node.

183. The decompression method of claim 178 in which said segment recovering step further comprises a symbol extracting step providing the symbol signal corresponding to said node label signal and to the address provided by said fourth storage means.

184. The decompression method of claim 179 in which said segment recovering step includes the step of inserting the address of the leaf node corresponding to said pointer signal into a storage location of said fourth storage means not containing an address, said storage location into which said address is inserted sequentially following the last storage location of said fourth storage means having an address stored thereat.

185. The decompression method of claim 184 in which said step of generating said node label signal includes the step of generating, in response to said leaf address, a node label signal corresponding to the node label of said father node of said leaf node.

186. The decompression method of claim 183 in which said segment recovering step includes a leaf determining step comprising the step of determining the leaf address corresponding to the address corresponding to said pointer signal and providing a leaf address signal in accordance therewith.

187. The decompression method of claim 186 in which said symbol signals of said alphabet have respective symbol position signals associated therewith and said leaf determining step comprises the step of defining a third search tree identical to said first search tree,said leaf determining step including the step of tracing a path through said third search tree from a node thereof having said address corresponding to said pointer signal to a leaf node along a path comprised of branches representative of a predetermined symbol signal of said alphabet,the address of said leaf node providing said leaf address signal to said fourth storage means and said step of generating said node label signal including the step of generating a node label signal in accordance with said address of said leaf node.

188. The decompression method of claim 187 in which said step of tracing a path through said third search tree comprises the step of tracing said path through said third search tree along said path comprised of branches representative of the first symbol signal of said alphabet encountered in performing said encoding method.

189. The decompression method of claim 187 in which said leaf determining step comprises the steps ofstoring said node labels at storage locations of a fifth storage means, said storage locations of said fifth storage means corresponding respectively to said addresses of said nodes of said third search tree, a node label stored at a particular storage location identifying the node whose address corresponds to said particular storage location,generating an address signal, andproviding said address signal to said fifth storage means, said fifth storage means providing, in response thereto, the node label stored in the storage location accessed by said address signal,said step of generating said address signal comprising the step of generating said address signal in accordance with a node label provided by said fifth storage means and in accordance with said predetermined symbol signal of said alphabet.

190. The decompression method of claim 189 in which said step of generating said address signal comprises the step of generating said address signal in accordance with the first symbol signal encountered during the performance of said encoding method.

191. The decompression method of claim 189 in which said step of generating said address signal comprises the step of generating said address signal in accordance with the said symbol position signal representative of said predetermined symbol.

192. The decompression method of claim 190 in which said step of generating said address signal comprises the step of generating said address signal in accordance with said symbol position signal representative of said first encountered symbol signal.

193. The decompression method of claim 192 in which said step of generating said address signal comprises the step of generating said address signal in accordance with the product of said node label provided by said fifth storage means with said number of symbol signals comprising said alphabet less said symbol position signal representative of said first encountered symbol signal.

194. The decompression method of claim 193 in which said step of generating said address signal comprises the step of generating said address signal in accordance with

space="preserve" listing-type="equation">address signal=i|A|-|A|+2
where i comprises said node label, i|A| comprises said product of said node label with said number of symbol signals comprising said alphabet and |A| comprises said symbol position signal for said first encountered symbol signal.

195. The decompression method of claim 189 in which said leaf determining step further includes the step of detecting when an accessed storage location of said fifth storage means does not contain a node label,the address of said accessed storage location of said fifth storage means not containing a node label providing said leaf address signal to said fourth storage means and providing said leaf address signal for said step of generating said node label signal.

196. The decompression method of claim 195 in which said leaf determining step further includes the step of inserting a node label into said accessed storage location of said fifth storage means detected as not containing a node label.

197. The decompression method of claim 196 in which said leaf determining step includes the step of generating successively increasing node labels in accordance with detecting accessed storage locations of said fifth storage means not containing node labels respectively.

198. The decompression method of claim 197 in which said leaf determining step includes the steps ofgenerating a node count signal representative of the number of nodes of said third search tree that are not leaf nodes, said node count signal providing said node label for insertion into said fifth storage means, andincrementing said node count signal as a result of detecting an accessed storage location of said fifth storage means as not containing a node label.

199. The decompression method of claim 197 in which said leaf determining step includes the steps ofgenerating a node count signal representative of the number of nodes of said third search tree that are not leaf nodes, said node count signal providing said node label for insertion into said fifth storage means,incrementing said node count signal when said storage location of said fourth storage means containing said address of said root node is detected, andaccessing said fourth storage means by said node count signal for insertion of said leaf address signal into the storage location of said fourth storage means accessed by said node count signal.

200. The decompression method of claim 199 in which said leaf determining step includes the steps oftransmitting said node count signal and said leaf address signal to said fourth storage means for insertion of said leaf address signal into the storage location of said fourth storage means accessed by said node count signal when a storage location of said fifth storage means is detected as not containing a node label, andproviding said leaf address signal for utilization in said node label generation step when a storage location of said fifth storage means is detected as not containing a node label.

201. The decompression method of claim 195 in which said step of generating said address signal comprises the steps ofsequentially generating address signals, andproviding said address signals to said fifth storage means, the node label provided by said fifth storage means in response to an address signal providing the node label for generating the next address signal, said step of sequentially generating said address signal comprising sequentially generating said address signals in accordance with the node label sequentially provided by said fifth storage means respectively and in accordance with said predetermined symbol signal of said data alphabet, said address signals being sequentially generated until an accessed storage location of said fifth storage means without a node label is detected.

202. The decompression method of claim 189 in which said fifth storage means includes a directly addressed portion and a hash addressed portion and in which said step of generating said address signal includes the steps ofcomparing said address signal to a predetermined hashing limit,hashing said address signal thereby providing a hashed address signal, andproviding either said address signal or said hashed address signal to said fifth storage means in accordance with the comparison between said address signal and said hashing limit.

203. The decompression method of claim 188 in which said symbol signals of said alphabet have respective symbol position signals associated therewith, said symbol extracting step including a position extracting step of generating a symbol position signal in accordance with said address from said fourth storage means and in accordance with said node label signal.

204. The decompression method of claim 203 in which said position extracting step comprises the step of generating said symbol position signal further in accordance with said number of symbols comprising said alphabet.

205. The decompression method of claim 204 in which said position extracting step comprises the step of generating said symbol position signal in accordance with the product of said node label signal and said number of symbol signals comprising said alphabet less said address.

206. The decompression method of claim 205 in which said position extracting step comprises the step of generating said symbol position signal in accordance with

space="preserve" listing-type="equation">p+|A|·

C1-C+2
where p comprises said symbol position signal, |A| comprises said number of symbol signals of said alphabet, C1 comprises said node label signal and C comprises said address.

207. The decompression method of claim 203 in which said symbol extracting step includes a position-symbol converting step of providing a symbol signal corresponding to said symbol position signal.

208. The decompression method of claim 207 in which said position-symbol converting step comprises the steps ofstoring said symbol signals corresponding to said symbol position signals respectively at respective storage locations of a sixth storage means, said storage locations of said sixth storage means corresponding respectively to said symbol position signals, andaccessing said sixth storage means by said symbol position signal for providng the symbol signals stored at the storage location of said sixth storage means accessed by the symbol position signal.

209. The decompression method of claim 208 in which said symbol extracting step further includes the step of detecting when an accessed storage location of said sixth storage means does not contain a symbol signal.

210. The decoding method of claim 209 in which said symbol extracting step includes the step of providing a signal extracted from said compressed stream of digital data representative of a newly encountered symbol whenever a storage location of said sixth storage means is detected not containing a symbol signal.

211. The decompression method of claim 210 in which said symbol extracting step further includes the step of converting said rank signal to the newly encountered symbol signal of said alphabet corresponding thereto.

212. The decompression method of claim 211 in which said rank converting step comprises the steps of storing said symbol signals corresponding to said respective rank signals at respective storage locations of a seventh storage means, said storage locations of said seventh storage means corresponding respectively to said rank signals, andaccessing said seventh storage means by said rank signal to provide the symbol signal stored at said storage location accessed by said rank signal.

213. The decompression method of claim 212 in which said rank converting step includes the steps ofdeleting a symbol signal from said seventh storage means when the rank signal corresponding thereto is received during performance of said decoding method, andeffectively decrementing the rank signals subsequent to said deleted symbol signal.

214. The decompression method of claim 212 in which said position-symbol converting step includes the steps ofproviding said symbol signal from said seventh storage means to said sixth storage means, andstoring said symbol signal received from said seventh storage means at the storage location of said sixth storage means accessed by said position signal that resulted in detecting an accessed storage location of said sixth storage means as not containing a symbol signal.

215. The decompression method of claim 211 further including the steps ofproviding a symbol count signal in accordance with the number of newly encountered symbol signals currently received during the performance of said decoding method, andincrementing said symbol count signal when an accessed storage location of said sixth storage means is detected as not containing a symbol signal.

216. The decompression method of claim 215 further including the steps ofgenerating a position count signal representative of said number of symbol signals comprising said alphabet less the number of newly encountered symbol signals encountered during the performance of said decoding method, anddecrementing said position count signal when an accessed storage location of said sixth storage means is detected as not containing a symbol signal.

217. The decompression method of claim 216 further including the step of providing a pointer count signal representative of the number of leaf nodes in said second search tree.

218. The decompression method of claim 217 in which said step of providing a pointer count signal comprises the steps ofincrementing said pointer count signal by said symbol count signal when an accessed storage location of said fourth storage means is detected as containing said address of said root, andincrementing said pointer count signal by said node count signal when an accessed storage location of said sixth storage means is detected as not containing a symbol signal.

219. The decompression method of claim 218 in which said step of generating a position count signal includes the step of generating an inhibit signal when said position count signal attains a predetermined count.

220. The decompression method of claim 219 in which said step of generating said symbol count signal includes the step of inhibiting said symbol count signal from being incremented beyond a predetermined count in response to said inhibit signal.

221. The decompression method of claim 220 in which said step of generating said symbol count signal includes the step of inhibiting said symbol count signal from being incremented beyond one less than the number of symbol signals comprising said alphabet in response to said inhibit signal.

222. The decompression method of claim 219 in which said step of generating said pointer count signal includes the step of inhibiting said pointer count signal from being incremented by said node count signal in response to said inhibit signal.

223. The decompression method of claim 217 in which said pointer signal provided during the performance of said encoding method comprises a pointer economy code signal,said decoding method further comprising the step of converting said pointer economy code signal to a green-leaves pointer signal corresponding thereto utilizing a predetermined prefix code.

224. The decompression method of claim 223 in which said step of converting said pointer economy code signal to a green-leaves pointer signal comprises the step of converting said pointer economy code signal to said green-leaves pointer signal utilizing a predetermined left biased prefix code.

225. The decompression method of claim 223 in which said step of converting said pointer economy code signal to a green-leaves pointer signal comprises the steps ofgenerating a pointer threshold in accordance with said pointer count signal,comparing said pointer economy code signal with said pointer threshold to determine when said pointer economy code signal exceeds said pointer threshold, andconverting said pointer economy code signal into a converted pointer economy code signal in accordance with said pointer threshold,said pointer economy code signal or said converted pointer economy code signal providing said green-leaves pointer signal in accordance with said pointer economy code signal exceeding said pointer threshold.

226. The decompression method of claim 225 in whichsaid step of generating said pointer threshold comprises the step of calculating said pointer threshold in accordance with

space="preserve" listing-type="equation">TB=2H-KB
where TB comprises said pointer threshold, H comprises said pointer count signal and KB comprises the least integer that is not less than log₂ (H), andsaid step of converting said pointer economy code signal into a converted pointer economy code signal comprises the step of converting said pointer economy code signal to said converted pointer economy code signal in accordance with

space="preserve" listing-type="equation">converted Y.sub.k =(Y.sub.k +TB)/2 where Y_k comprises said pointer economy code signal and said converted pointer economy code signal is generated utilizing integer arithmetic.

227. The decompression method of claim 223 further including the step of converting said green-leaves pointer signal to a corresponding leaves-only pointer signal in accordance with said symbol count signal.

228. The decompression method of claim 227 in which said step of converting said green-leaves pointer signal to a corresponding leaves-only pointer signal further includes the step of converting said green-leaves pointer signal to said leaves-only pointer signal in accordance with said position count signal.

229. The decompression method of claim 228 in which said step of converting said green-leaves pointer signal to said leaves-only pointer signal comprises the step of converting said green-leaves pointer signal to said leaves-only pointer signal in acordance with

space="preserve" listing-type="equation">D=D.sub.g +CSYM((D.sub.g -1)/BSYM)
where D comprises said leaves-only pointer signal, D_g comprises said green-leaves pointer signal, CSYM comprises (NSYM-1) or zero when NSYM=0, NSYM comprises said position count signal, BSYM comprises said symbol count signal and said leaves-only pointer signal D is generated utilizing integer arithmetic.

230. The decompression method of claim 227 in which said step of converting said green-leaves pointer signal to said leaves-only pointer signal includes the steps ofdetermining when said green-leaves pointer signal equals zero, andproviding a zero valued leaves-only pointer signal when said green-leaves pointer signal equals zero.

231. The decompression method of claim 230 further including the step of converting said leaves-only pointer signal to an address signal corresponding thereto.

232. The decompression method of claim 231 in which said step of converting said leaves-only pointer signal to an address signal includes the step of providing said address signal in accordance with said number of symbol signals of said alphabet.

233. The decompression method of claim 232 in which said step of converting said leaves-only pointer signal to an address signal comprises the step of providing said address signal in accordance with

space="preserve" listing-type="equation">address signal=D+(D+2|A|-3)/(|A|-1)
where D comprises said leaves-only pointer signal, |A| comprises the number of symbol signals of said alphabet and said address signal is generated utilizing integer arithmetic.

234. The decompression method of claim 231 in which said step of converting said leaves-only pointer signal to said address signal includes the step of utilizing said address signal in said step of determining said leaf address signal,said step of determining said leaf address signal comprising the step of determining said leaf address signal in accordance with said address signal.

235. The decompression method of claim 231 in which said step of converting said leaves-only pointer signal to said address signal includes the step of providing said address signal generated from said leaves-only pointer signal for utilization during said address generating step of said leaf determining step to provide the address signal to said fifth storage means for commencing the tracing of said path through said third search tree from a node thereof having an address corresponding to said address signal generated from said leaves-only pointer signal.

236. The decompression method of claim 216 in which said rank signal corresponding to said newly encountered symbol signal comprises a rank economy code signal,said decoding method further including the step of converting said rank economy code signal into a corresponding decoded rank signal utilizing a predetermined prefix code.

237. The decompression method of claim 216 in which said rank signal corresponding to said newly encountered symbol signal comprises a rank economy code signal,said decoding method further including the step of converting said rank economy code signal into a corresponding decoded rank signal utilizing a predetermined left biased prefix code.

238. The decompression method of claim 236 in which said step of converting said rank economy code signal into a corresponding decoded rank signal comprises the steps ofgenerating a rank threshold in accordance with said position count signal,comparing said rank economy code signal to said rank threshold to determine when said rank economy code signal exceeds said rank threshold, andconverting said rank economy code signal into a converted rank economy code signal in accordance with said rank threshold,said rank economy code signal or said converted rank economy code signal providing said decoded rank signal in accordance with said rank economy code signal exceeding said rank threshold.

240. The decompression method of claim 236 including the step of enabling said step of converting said rank economy code signal into a corresponding decoded rank signal whenever an accessed storage location of said sixth storage means is detected as not containing a symbol signal.

241. The decompression method of claim 183 further including the step of reversing the order in which said symbol signals are provided during said symbol extracting step thereby recovering the segments of said stream of data symbol signals corresponding to said pointer signals respectively.

242. The decompression method of claim 217 further including the steps ofcomparing said node count signal to a predetermined constant, andinhibiting the incrementation of said node count signal, inhibiting said fifth storage means from inserting said node label therein and inhibiting the incrementation of said pointer count signal by said symbol count signal, whenever said node count signal exceeds said predetermined constant.

243. The decompression method of claim 177 in which said step of defining a second search tree comprises the step of defining a second search tree having alpha-branches emanating from said nodes representative of all of the symbol signals of said alphabet not yet encountered during the performance of said decoding method.

244. The decompression method of claim 210 in which said step of defining a second search tree comprises the step of defining a second search tree having alpha-branches emanating from said nodes representative of all of the symbol signals of said alphabet not yet encountered during the performance of said decoding method, an alpha branch of said second search tree being encountered when an accessed storage location of said sixth storage means is detected not containing a symbol signal.

Specification

Resources

Litigation Campaign Assessment

Current Assignee
American Telephone & Telegraph Company (AT&T, Inc.), Bell Telephone Laboratories, Inc. (Nokia Corporation), Sperry Corporation
Original Assignee
Sperry Corporation
Inventors
Lempel, Abraham, Eastman, Willard L., Cohn, Martin, Ziv, Jacob
Primary Examiner(s)
Miller, C. D.

Application Number

US06/291,870
Time in Patent Office

1,093 Days
Field of Search

340/347 DD, 364/200, 364/900
US Class Current

341/51
CPC Class Codes

H03M 7/3088 employing the use of a dict...

Y10S 707/99943 Generating database or data...

Apparatus and method for compressing data signals and restoring the compressed data signals

First Claim

2 Assignments

0 Petitions

Accused Products

Abstract

348 Citations

244 Claims

Specification

Use Cases

Quick Links

Others

Apparatus and method for compressing data signals and restoring the compressed data signals

First Claim

2 Assignments

Subscription Required

Subscription Required

0 Petitions

Subscription Required

Accused Products

Subscription Required

Abstract

348 Citations

244 Claims

Specification

Subscription Required

Use Cases

Quick Links

Others