US4464650A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Apparatus and method for compressing data signals and restoring the compressed data signals
Assignee: Unisys Corp
•
Filing: 1981-08-10
•
Granted: 1984-08-07
•
Expires: 2001-08-10
Abstract
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.
Inventors
- 👤 Willard L. Eastman
- 👤 Abraham Lempel
- 👤 Jacob Ziv
- 👤 Martin Cohn
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-24 20:44
CPC Classifications
H; H03; H03M; H03M7/00; H03M7/30; H03M7/3084; H03M7/3088; Y; Y10; Y10S; Y10S707/00; Y10S707/99941; Y10S707/99943
Claims Analysis
Total Claims: 246
Claim 1
Independent Claim
670 words
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 comprising first 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, and node 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.
Claim 2
Dependent Claim
670 words
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 comprising first 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, and node 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.
Claim 3
Dependent Claim
31 words
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.
Claim 4
Dependent Claim
52 words
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.
Claim 5
Dependent Claim
41 words
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.
Claim 6
Dependent Claim
49 words
The compression apparatus of claim 4 in which said parsing means further comprises symbol 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.
Claim 7
Dependent Claim
84 words
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.
Claim 8
Dependent Claim
168 words
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 comprising second 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.
Claim 9
Dependent Claim
36 words
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.
Claim 10
Dependent Claim
46 words
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.
Claim 11
Dependent Claim
40 words
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.
Claim 12
Dependent Claim
54 words
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.
Claim 13
Dependent Claim
47 words
The compression apparatus of claim 11 in which said address generator means comprises means for generating said address signal in accordance with 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.
Claim 14
Dependent Claim
92 words
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 comprises hashing limit comparator means for comparing said address signal to a predetermined hashing limit, and hashing 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.
Claim 15
Dependent Claim
51 words
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.
Claim 16
Dependent Claim
81 words
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.
Claim 17
Dependent Claim
47 words
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.
Claim 18
Dependent Claim
34 words
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.
Claim 19
Dependent Claim
42 words
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 D=C-E-1 where D comprises said leaves-only pointer signal, C comprises said address signal and E comprises said node label.
Claim 20
Dependent Claim
45 words
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.
Claim 21
Dependent Claim
55 words
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.
Claim 22
Dependent Claim
54 words
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.
Claim 23
Dependent Claim
70 words
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.
Claim 24
Dependent Claim
62 words
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.
Claim 25
Dependent Claim
61 words
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.
Claim 26
Dependent Claim
31 words
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.
Claim 27
Dependent Claim
88 words
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 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 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.
Claim 28
Dependent Claim
30 words
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.
Claim 29
Dependent Claim
25 words
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.
Claim 30
Dependent Claim
60 words
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.
Claim 31
Dependent Claim
66 words
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.
Claim 32
Dependent Claim
82 words
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.
Claim 33
Dependent Claim
29 words
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.
Claim 34
Dependent Claim
182 words
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, and said 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.
Claim 35
Dependent Claim
97 words
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.
Claim 36
Dependent Claim
29 words
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.
Claim 37
Dependent Claim
33 words
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.
Claim 38
Dependent Claim
40 words
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.
Claim 39
Dependent Claim
33 words
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.
Claim 40
Dependent Claim
46 words
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.
Claim 41
Dependent Claim
48 words
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.
Claim 42
Dependent Claim
117 words
The compression apparatus of claim 39 in which said pointer economy encoder means comprises pointer 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, and pointer 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.
Claim 43
Dependent Claim
85 words
The compression apparatus of claim 41 in which said pointer threshold calculator means comprises means for calculating said pointer threshold in accordance with 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 2 (H), and said pointer output converter means comprises means for converting said green-leaves pointer signal to said converted green-leaves pointer signal in accordance with Converted D.sub.g =(2D.sub.g -TB)/2 where D g comprises said green-leaves pointer signal.
Claim 44
Dependent Claim
51 words
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.
Claim 45
Dependent Claim
29 words
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.
Claim 46
Dependent Claim
73 words
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.
Claim 47
Dependent Claim
65 words
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.
Claim 48
Dependent Claim
42 words
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.
Claim 49
Dependent Claim
44 words
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.
Claim 50
Dependent Claim
109 words
The compression apparatus of claim 47 in which said rank economy encoder means comprises rank 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, and rank 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.
Claim 51
Dependent Claim
93 words
The compression apparatus of claim 49 in which said rank threshold calculator means comprises means for calculating said rank threshold in accordance with 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 2 (NSYM) and said rank output converter means comprises means for converting said rank signal to said converted rank signal in accordance with 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.
Claim 52
Dependent Claim
39 words
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.
Claim 53
Dependent Claim
100 words
The compression apparatus of claim 1 in which said parsing means further comprises symbol mapping means for assigning ordered symbol position signals to said symbol signals of said alphabet, respectively, and means 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.
Claim 54
Dependent Claim
72 words
The compression apparatus of claim 33 further including means for comparing said node count signal to a predetermined constant, and means 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.
Claim 55
Dependent Claim
33 words
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.
Claim 56
Dependent Claim
135 words
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.
Claim 57
Dependent Claim
136 words
The decompression apparatus of claim 55 in which said segment recovery means comprises fourth 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.
Claim 58
Dependent Claim
47 words
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.
Claim 59
Dependent Claim
32 words
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.
Claim 60
Dependent Claim
56 words
The decompression apparatus of claim 58 in which said label generator means comprises means for generating said node label signal in accordance with 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.
Claim 61
Dependent Claim
36 words
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.
Claim 62
Dependent Claim
46 words
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.
Claim 63
Dependent Claim
65 words
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.
Claim 64
Dependent Claim
46 words
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.
Claim 65
Dependent Claim
42 words
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.
Claim 66
Dependent Claim
107 words
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.
Claim 67
Dependent Claim
57 words
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.
Claim 68
Dependent Claim
141 words
The decompression apparatus of claim 65 in which said leaf determining means comprises fifth 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, and addressing 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.
Claim 69
Dependent Claim
40 words
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.
Claim 70
Dependent Claim
31 words
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.
Claim 71
Dependent Claim
32 words
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.
Claim 72
Dependent Claim
52 words
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.
Claim 73
Dependent Claim
59 words
The decompression apparatus of claim 71 in which said addressing means comprises means for generating said address signal in accordance with 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.
Claim 74
Dependent Claim
68 words
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.
Claim 75
Dependent Claim
44 words
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.
Claim 76
Dependent Claim
42 words
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.
Claim 77
Dependent Claim
92 words
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.
Claim 78
Dependent Claim
120 words
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.
Claim 79
Dependent Claim
129 words
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.
Claim 80
Dependent Claim
114 words
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.
Claim 81
Dependent Claim
87 words
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 includes hashing limit comparator means for comparing said address signal to a predetermined hashing limit, and hashing 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.
Claim 82
Dependent Claim
59 words
The decompression apparatus of claim 76 in which said symbol signals of said alphabet have respective symbol position signals associated therewith, and said 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.
Claim 83
Dependent Claim
32 words
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.
Claim 84
Dependent Claim
42 words
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.
Claim 85
Dependent Claim
52 words
The decompression apparatus of claim 83 in which said position extractor means comprises means for generating said symbol position signal in accordance with 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.
Claim 86
Dependent Claim
38 words
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.
Claim 87
Dependent Claim
84 words
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.
Claim 88
Dependent Claim
35 words
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.
Claim 89
Dependent Claim
59 words
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.
Claim 90
Dependent Claim
36 words
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.
Claim 91
Dependent Claim
73 words
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.
Claim 92
Dependent Claim
65 words
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.
Claim 93
Dependent Claim
64 words
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.
Claim 94
Dependent Claim
68 words
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.
Claim 95
Dependent Claim
77 words
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.
Claim 96
Dependent Claim
29 words
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.
Claim 97
Dependent Claim
96 words
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.
Claim 98
Dependent Claim
28 words
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.
Claim 99
Dependent Claim
32 words
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.
Claim 100
Dependent Claim
40 words
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.
Claim 101
Dependent Claim
33 words
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.
Claim 102
Dependent Claim
57 words
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.
Claim 103
Dependent Claim
34 words
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.
Claim 104
Dependent Claim
124 words
The decompression apparatus of claim 101 in which said pointer economy decoder means comprises pointer 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, and pointer 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.
Claim 105
Dependent Claim
100 words
The decompression apparatus of claim 103 in which said pointer threshold calculator means comprises means for calculating said pointer threshold in accordance with 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 2 (H), and said pointer code converter means comprises means for converting said pointer economy code signal to said converted pointer economy code signal in accordance with 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.
Claim 106
Dependent Claim
42 words
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.
Claim 107
Dependent Claim
38 words
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.
Claim 108
Dependent Claim
75 words
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 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.
Claim 109
Dependent Claim
40 words
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.
Claim 110
Dependent Claim
29 words
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.
Claim 111
Dependent Claim
30 words
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.
Claim 112
Dependent Claim
50 words
The decompression apparatus of claim 110 in which said address converter means comprises means for providing said address signal in accordance with 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.
Claim 113
Dependent Claim
37 words
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.
Claim 114
Dependent Claim
76 words
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.
Claim 115
Dependent Claim
57 words
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.
Claim 116
Dependent Claim
60 words
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.
Claim 117
Dependent Claim
125 words
The decompression apparatus of claim 114 in which said rank economy decoder means comprises rank 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, and rank 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.
Claim 118
Dependent Claim
124 words
The decompression apparatus of claim 116 in which said rank threshold calculator means comprises means for providing said rank threshold in accordance with 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 2 (NSYM), and said rank code converter means comprises means for converting said rank economy code signal to said converted rank economy code signal in accordance with 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.
Claim 119
Dependent Claim
53 words
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.
Claim 120
Dependent Claim
56 words
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.
Claim 121
Dependent Claim
72 words
The decompression apparatus of claim 95 further including means for comparing said node count signal to a predetermined constant, and means 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.
Claim 122
Dependent Claim
47 words
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.
Claim 123
Dependent Claim
76 words
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.
Claim 124
Dependent Claim
667 words
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 of storing 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, and inserting 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 of sequentially 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.
Claim 125
Dependent Claim
667 words
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 of storing 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, and inserting 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 of sequentially 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.
Claim 126
Dependent Claim
35 words
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.
Claim 127
Dependent Claim
52 words
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.
Claim 128
Dependent Claim
47 words
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.
Claim 129
Dependent Claim
49 words
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.
Claim 130
Dependent Claim
89 words
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.
Claim 131
Dependent Claim
182 words
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 of storing 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, and accessing 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.
Claim 132
Dependent Claim
39 words
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.
Claim 133
Dependent Claim
43 words
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.
Claim 134
Dependent Claim
46 words
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.
Claim 135
Dependent Claim
58 words
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.
Claim 136
Dependent Claim
51 words
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 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.
Claim 137
Dependent Claim
82 words
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 of comparing said address signal to a predetermined hashing limit, hashing said address signal thereby providing a hashed address signal, and 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.
Claim 138
Dependent Claim
48 words
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.
Claim 139
Dependent Claim
76 words
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.
Claim 140
Dependent Claim
39 words
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.
Claim 141
Dependent Claim
39 words
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.
Claim 142
Dependent Claim
47 words
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 D=C-E-1 where D comprises said leaves-only pointer signal, C comprises said address signal and E comprises said node label.
Claim 143
Dependent Claim
48 words
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.
Claim 144
Dependent Claim
58 words
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.
Claim 145
Dependent Claim
52 words
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.
Claim 146
Dependent Claim
64 words
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.
Claim 147
Dependent Claim
51 words
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.
Claim 148
Dependent Claim
48 words
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.
Claim 149
Dependent Claim
37 words
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.
Claim 150
Dependent Claim
87 words
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 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.
Claim 151
Dependent Claim
36 words
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.
Claim 152
Dependent Claim
31 words
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.
Claim 153
Dependent Claim
49 words
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.
Claim 154
Dependent Claim
61 words
The compression method of claim 145 further including the steps of generating a symbol count signal in accordance with the number of symbol signals of said alphabet currently encountered during the performance of said encoding method, and incrementing said symbol count signal when an accessed storage location of said second storage means is detected as not containing a symbol position signal.
Claim 155
Dependent Claim
28 words
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.
Claim 156
Dependent Claim
71 words
The compression method of claim 153 further including the steps of 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, and incrementing said node count signal when an accessed storage location of said first storage means is detected as not containing a node label.
Claim 157
Dependent Claim
77 words
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, and decrementing said position count signal when an accessed storage location of said second storage means is detected as not containing a symbol position signal.
Claim 158
Dependent Claim
78 words
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, and incrementing 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.
Claim 159
Dependent Claim
34 words
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.
Claim 160
Dependent Claim
39 words
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.
Claim 161
Dependent Claim
46 words
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.
Claim 162
Dependent Claim
39 words
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.
Claim 163
Dependent Claim
38 words
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.
Claim 164
Dependent Claim
40 words
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.
Claim 165
Dependent Claim
103 words
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 of generating 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, and 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.
Claim 166
Dependent Claim
98 words
The compression method of claim 163 in which said step of generatinng a pointer threshold comprises the step of calculating said pointer threshold in accordance with 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 2 (H), and said 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 converted D.sub.g =(2D.sub.g -TB)/2 where D g comprises said green-leaves pointer signal.
Claim 167
Dependent Claim
45 words
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.
Claim 168
Dependent Claim
31 words
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.
Claim 169
Dependent Claim
91 words
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 of storing 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, and acessing 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.
Claim 170
Dependent Claim
61 words
The compression method of claim 167 in which said step of assigning predetermined rank signals further includes the steps of deleting 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, and decrementing all rank signals subsequent to said deleted storage location.
Claim 171
Dependent Claim
35 words
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.
Claim 172
Dependent Claim
37 words
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.
Claim 173
Dependent Claim
95 words
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 of generating 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, and converting 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.
Claim 174
Dependent Claim
105 words
The compression method of claim 171 in which said step of generating a rank threshold comprises the step of calculating said rank threshold in accordance with 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 2 (NSYM), and said 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 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.
Claim 175
Dependent Claim
36 words
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.
Claim 176
Dependent Claim
97 words
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, and providing 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.
Claim 177
Dependent Claim
64 words
The compression method of claim 168 further including the steps of comparing said node count signal to a predetermined constant, and inhibiting 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.
Claim 178
Dependent Claim
41 words
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.
Claim 179
Dependent Claim
131 words
The decompression method of claim 176 in which said segment recovering step comprises the steps of 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, tracing a path through said second search tree to said root from the leaf node corresponding to a pointer signal, and extracting from the branches from said path the respective symbol signals associated with said branches, thereby recovering the segment corresponding to said pointer signal.
Claim 180
Dependent Claim
139 words
The decompression method of claim 177 in which said segment recovering step comprises the steps of storing 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, and 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 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.
Claim 181
Dependent Claim
42 words
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.
Claim 182
Dependent Claim
36 words
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.
Claim 183
Dependent Claim
61 words
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 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.
Claim 184
Dependent Claim
35 words
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.
Claim 185
Dependent Claim
38 words
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.
Claim 186
Dependent Claim
66 words
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.
Claim 187
Dependent Claim
44 words
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.
Claim 188
Dependent Claim
43 words
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.
Claim 189
Dependent Claim
131 words
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.
Claim 190
Dependent Claim
52 words
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.
Claim 191
Dependent Claim
142 words
The decompression method of claim 187 in which said leaf determining step comprises the steps of storing 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, and 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 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.
Claim 192
Dependent Claim
38 words
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.
Claim 193
Dependent Claim
36 words
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.
Claim 194
Dependent Claim
37 words
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.
Claim 195
Dependent Claim
59 words
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.
Claim 196
Dependent Claim
64 words
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 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.
Claim 197
Dependent Claim
76 words
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.
Claim 198
Dependent Claim
38 words
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.
Claim 199
Dependent Claim
38 words
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.
Claim 200
Dependent Claim
78 words
The decompression method of claim 197 in which said leaf determining step includes the steps of 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, and incrementing said node count signal as a result of detecting an accessed storage location of said fifth storage means as not containing a node label.
Claim 201
Dependent Claim
108 words
The decompression method of claim 197 in which said leaf determining step includes the steps of 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, incrementing said node count signal when said storage location of said fourth storage means containing said address of said root node is detected, and accessing 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.
Claim 202
Dependent Claim
101 words
The decompression method of claim 199 in which said leaf determining step includes the steps of 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 a storage location of said fifth storage means is detected as not containing a node label, and providing 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.
Claim 203
Dependent Claim
120 words
The decompression method of claim 195 in which said step of generating said address signal comprises the steps of 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 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.
Claim 204
Dependent Claim
84 words
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 of comparing said address signal to a predetermined hashing limit, hashing said address signal thereby providing a hashed address signal, and providing 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.
Claim 205
Dependent Claim
54 words
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.
Claim 206
Dependent Claim
32 words
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.
Claim 207
Dependent Claim
43 words
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.
Claim 208
Dependent Claim
53 words
The decompression method of claim 205 in which said position extracting step comprises the step of generating said symbol position signal in accordance with 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.
Claim 209
Dependent Claim
28 words
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.
Claim 210
Dependent Claim
83 words
The decompression method of claim 207 in which said position-symbol converting step comprises the steps of storing 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, and accessing 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.
Claim 211
Dependent Claim
34 words
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.
Claim 212
Dependent Claim
49 words
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.
Claim 213
Dependent Claim
32 words
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.
Claim 214
Dependent Claim
74 words
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, and accessing said seventh storage means by said rank signal to provide the symbol signal stored at said storage location accessed by said rank signal.
Claim 215
Dependent Claim
51 words
The decompression method of claim 212 in which said rank converting step includes the steps of deleting a symbol signal from said seventh storage means when the rank signal corresponding thereto is received during performance of said decoding method, and effectively decrementing the rank signals subsequent to said deleted symbol signal.
Claim 216
Dependent Claim
74 words
The decompression method of claim 212 in which said position-symbol converting step includes the steps of providing said symbol signal from said seventh storage means to said sixth storage means, and storing 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.
Claim 217
Dependent Claim
59 words
The decompression method of claim 211 further including the steps of providing a symbol count signal in accordance with the number of newly encountered symbol signals currently received during the performance of said decoding method, and incrementing said symbol count signal when an accessed storage location of said sixth storage means is detected as not containing a symbol signal.
Claim 218
Dependent Claim
66 words
The decompression method of claim 215 further including the steps of generating 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, and decrementing said position count signal when an accessed storage location of said sixth storage means is detected as not containing a symbol signal.
Claim 219
Dependent Claim
28 words
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.
Claim 220
Dependent Claim
78 words
The decompression method of claim 217 in which said step of providing a pointer count signal comprises the steps of incrementing 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, and incrementing 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.
Claim 221
Dependent Claim
33 words
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.
Claim 222
Dependent Claim
38 words
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.
Claim 223
Dependent Claim
46 words
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.
Claim 224
Dependent Claim
39 words
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.
Claim 225
Dependent Claim
51 words
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.
Claim 226
Dependent Claim
44 words
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.
Claim 227
Dependent Claim
108 words
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 of generating 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, and 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.
Claim 228
Dependent Claim
115 words
The decompression method of claim 225 in which said step of generating said pointer threshold comprises the step of calculating said pointer threshold in accordance with 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 2 (H), and said 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 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.
Claim 229
Dependent Claim
29 words
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.
Claim 230
Dependent Claim
44 words
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.
Claim 231
Dependent Claim
85 words
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 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.
Claim 232
Dependent Claim
48 words
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 of determining when said green-leaves pointer signal equals zero, and providing a zero valued leaves-only pointer signal when said green-leaves pointer signal equals zero.
Claim 233
Dependent Claim
22 words
The decompression method of claim 230 further including the step of converting said leaves-only pointer signal to an address signal corresponding thereto.
Claim 234
Dependent Claim
39 words
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.
Claim 235
Dependent Claim
59 words
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 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.
Claim 236
Dependent Claim
60 words
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.
Claim 237
Dependent Claim
86 words
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.
Claim 238
Dependent Claim
49 words
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.
Claim 239
Dependent Claim
51 words
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.
Claim 240
Dependent Claim
109 words
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 of generating 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, and 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.
Claim 241
Dependent Claim
146 words
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 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 2 (NSYM), and said 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 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.
Claim 242
Dependent Claim
44 words
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.
Claim 243
Dependent Claim
43 words
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.
Claim 244
Dependent Claim
63 words
The decompression method of claim 217 further including the steps of comparing said node count signal to a predetermined constant, and inhibiting 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.
Claim 245
Dependent Claim
51 words
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.
Claim 246
Dependent Claim
78 words
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.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1987-08-07 | 1988-02-06 | 1988-08-07 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1991-08-07 | 1992-02-06 | 1992-08-07 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1995-08-07 | 1996-02-06 | 1996-08-07 | $7700.00 | Window Closed / Lapsed |