General purpose, hash-based technique for single-pass lossless data compression
US5406279A · kind A · utility
Assignee
Inventors
Key dates
| Filing date | Sep 2, 1992 |
| Grant date | Apr 11, 1995 |
| Priority date | — |
| Expiry date | Sep 2, 2012 |
Classification
- Technology area (CPC H)Electricity
- CPC primaryH03M7/3086
- WIPO fieldBasic communication processes
- WIPO sectorElectrical engineering
Abstract
A general-purpose, single-pass, adaptive, and lossless data compression invention implements an LZ1-like method using a hash-based architecture. It is suitable for use in data storage and data communications applications. Implementation efficiency, in terms of required memory and logic gates relative to the typical compression ratio achieved, is highly optimized. An easy-to-implement and quick-to-verify hash function is used. Differential copy lengths may be used to reduce the number of bits required to encode the copy-length field within copy tokens. That is, if multiple matches to a sequence of input bytes are found in the current window, then the length of the copy may be encoded as the difference between the lengths of the longest and the second-longest match, which results in a smaller copy length which likely has a shorter encoded representation. To further increase the compression achieved, literals are not used, but rather input bytes without window matches are mapped into alphabet tokens of variable length using a unary-length code. Other unary-length codes are used to represent the copy-length field and the displacement field within copy tokens.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.