Apparatus and method for compressing data signals and restoring the compressed data signals
US4464650A · kind A · utility
Assignee
Inventors
Key dates
| Filing date | Aug 10, 1981 |
| Grant date | Aug 7, 1984 |
| Priority date | — |
| Expiry date | Aug 10, 2001 |
Classification
- Technology area (CPC Y)Emerging Cross-Sectional Technologies
- CPC primaryY10S707/99943
- WIPO fieldBasic communication processes
- WIPO sectorElectrical engineering
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 i…
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.