Overview
Lempel–Ziv–Stac (commonly abbreviated LZS) is a lossless data‑compression algorithm that builds upon the principles introduced by the original Lempel–Ziv family (LZ77 and LZ78). The algorithm was developed by Stac Electronics in the early 1990s and was marketed as a high‑speed, low‑overhead compression method for use in storage, networking, and modem technologies.
Development and Patent History
- Developer: Stac Electronics, a company based in Santa Clara, California, known for its data‑compression hardware and software products.
- Patent: The algorithm was patented by Stac Electronics (U.S. Patent No. 5,074,462, granted in 1991). The patent described a “sliding‑window” compression scheme with specific implementation details for hardware acceleration.
- Legal Issues: In 1994, Stac Electronics sued Microsoft for alleged infringement of its LZS‑related patents in the context of Microsoft Windows 3.1’s DoubleSpace compression utility. The case was settled in 1995, with Microsoft agreeing to pay licensing fees and to cease certain uses of the contested technology.
Technical Characteristics
- Sliding‑Window Model: Similar to LZ77, LZS maintains a dictionary of recent data in a sliding window (typically 2 KB to 64 KB).
- Match Encoding: Matches are encoded as (offset, length) pairs, with length values limited to a maximum of 255 bytes in the original specification.
- Literal Handling: Unmatched bytes are transmitted directly as literals.
- Compression Ratio: Reported compression ratios range from 1.5:1 to 2.0:1 on typical text and binary data, comparable to contemporaneous LZ‑based methods.
- Speed: Designed for hardware implementation, LZS achieved compression and decompression rates exceeding 1 MB/s on 1990s‑era processors, making it suitable for real‑time modem and storage applications.
Standardization and Usage
- PPP (Point‑to‑Point Protocol): An optional compression protocol defined in RFC 1978 (1996) specifies the use of LZS for compressing the payload of PPP links.
- NASA: Certain telemetry and command systems employed LZS to reduce bandwidth requirements for downlink data streams.
- Stac Software: Stac released commercial software libraries (e.g., “Stac LZS”) for integration into operating systems and embedded devices.
- Legacy Systems: Although largely supplanted by more modern algorithms (e.g., DEFLATE, LZMA), LZS remains supported in some legacy networking equipment and archival formats.
Variants and Extensions
Subsequent implementations introduced enhancements such as larger window sizes, variable‑length coding for match lengths, and hybrid schemes combining LZS with entropy coders. However, these extensions are not universally standardized and are typically confined to proprietary products.
References
- U.S. Patent No. 5,074,462, “Method and apparatus for data compression” (Stac Electronics, 1991).
- RFC 1978, “PPP Data Compression Protocol (Compressed PPP or CCP)”, 1996.
- “Stac LZS – A High‑Performance Compression Algorithm”, Stac Electronics Technical Manual, 1993.
See Also
- Lempel–Ziv–Welch (LZW)
- Lempel–Ziv–Stac (LZS) in PPP
- Data compression
Note
All statements are derived from publicly available technical documents, patents, and standards. No speculative or unverified information is presented.
