View source for LZP (compression algorithm)

{{AFC submission|d|nn|u=RetroRetry|ns=118|decliner=Fermiboson|declinets=20251204214611|ts=20251012121253}} <!-- Do not remove this line! -->

{{AFC comment|1=Ok, so I kind of understand why the reviewers haven't got to this yet. But having some level of quantitative knowledge, I'm perplexed.

1. The article is not comprehensible for anyone who doesn't know information theory. It is not possible, for example, to tell what the differences are between the different variants, without knowing about them beforehand.

2. The article is also not comprehensible for anyone who does know information theory. All lossless data compression algorithms, to my knowledge, make use of the fact that character chains have a nontrivial kernel; it is in fact mathematically necessary for a compression algorithm to exist. What is different for this algorithm?

3. Most importantly for Wikipedia - I'm nearly 100% certain that the article subject ''is'' notable. The current references, however, are basically entirely primary, which means that the sources as they stand don't meet GNG. There is a massive academic corpus on compression algorithms, review of compression theory and its implementation, etc. Use it. [[User:Fermiboson|Fermiboson]] ([[User talk:Fermiboson|talk]]) 21:46, 4 December 2025 (UTC)}}

----

{{Short description|Lossless data compression algorithm introduced by Charles Bloom in 1996}}
{{Draft topics|computing}}
{{AfC topic|stem}}

<!-- Important, do not remove anything above this line before article has been created. -->
{{Infobox algorithm
|name           = LZP (Lempel-Ziv-Prediction)
|class          = Lossless data compression
|image          = 
|caption        = 
|data           = 
|time           = O(''n'')
|best-time      = O(''n'')
|average-time   = O(''n'')
|space          = O(''n'') total, O(TABLE_SIZE) auxiliary.
}}

'''LZP''' (short for ''Lempel-Ziv-Prediction'') is a lossless data compression algorithm that leverages the insight that the characters immediately prior a given position tend to be strong predictors for the immediately following characters<ref name="Bloom1996" /><ref name="Bloom1996-full" />. It's closely related to [[Prediction by partial matching|PPM]] context modeling and [[Markov chain|Markov chains]].

== Algorithm overview ==
For every input byte within the input stream, the previous N bytes are gathered to create a finite context of order N.
This context is hashed and used to retrieve the corresponding entry in a [[hashtable]], which returns a reference to an earlier position in the already‑processed data.
The upcoming sequence of bytes is then compared with the data at that reference point, and the length of the matching segment is determined.

The result of this comparison is written in the output stream using an encoding scheme such as:
* If the matching length is zero, a flag indicating a negative match is recorded followed by the literal byte itself.
* If the matching length is one or greater, a flag indicating a positive match is recorded and then the length of the match is written.<ref name="Bloom1996-full" /><ref name="hlevkin" /><ref name="Campos" />

== History ==
The technique was first described by Charles Bloom in 1996.<ref name="Bloom1996" /><ref name="Bloom1996-full" /> and later popularised in hobbyist publications related to the [[demoscene]] due to its low implementation footprint<ref name="Hugi12" />. It is often used as a ''pre-processor'' for stronger [[Lempel–Ziv|LZ]]-type or [[Entropy coding|entropy]] compressors to improve their compression ratio without a noticeable speed penalty<ref name="LTCB" />

=== Comparison with the PPP Predictor algorithm ===
In the same year of the publication of LZP, another similar algorithm was indipendently published as part of the [[Point-to-Point Protocol|PPP protocol]] called [[Predictor (compression algorithm)|Predictor]]<ref name="ppp-predictor" />. Multiple online sources have used their name interchangeably even thought the two algorithms are distinct<ref name="encosesu-predictor" /><ref name="github-lmcilroy" />. To be specific, Predictor is different to LZP in that it stores literals instead of pointers in the hashtable, doesn't require jumping to previous locations in the stream and matches single bytes only without attempting to find multi-byte matches.

== LZP variants ==
Documented variants of LZP involve different choices of parameters, further processing with entropy coders or different hashtable matching systems:

* '''LZP1''': A fixed order-3 hashed context model was used, with a hashtable of size 2<sup>12</sup> and match lengths were written using variable-length integers.
* '''LZP2''': Same as LZP1, but literals and match lengths were written with a Huffman coder.
* '''LZP3''': A order-4 context model was used with a 2<sup>16</sup> table size. Literals and match lengths were written with a order-I Huffman coder. Notably, the table also contains the contexts, together with a mechanism that finds the highest-order context that does have a match in the table.
* '''LZP4''': A order-5 context model was used and a table with 2<sup>16</sup> entries, with order-1 arithmetic encoding of match lengths and order-4 PPM encoding of literals. In this version, table entries aren't a single pointer, but contain instead a 2-dimensional linked list of pointers.<ref name="Bloom1996-full" /><ref name="hlevkin" />

== Typical parameters ==
* '''Hashtable size''': A value of 2<sup>16</sup> bytes or greater is typical on modern implementations<ref name="github-lmcilroy" />. Early implementations on memory-constrained hardware would choose a lower amount such as 2<sup>12</sup> <ref name="Bloom1996" /><ref name="Bloom1996-full" /> or 2<sup>8</sup> at the cost of a worse compression ratio.
* '''Context size''': How many most-recent input bytes should be taken into account when creating the hash. For example, the original implementation of LZP1 uses a size of 3 bytes.
* '''Hash function''': The hash function should be chosen to yield a hash with representable size equivalent to the hashtable size. For example, in the original implementation of LZP1, the function <code>{{nowrap begin}}H = ((C >> 11) ^ C) & 0xFFF{{nowrap end}}</code> was chosen, which yields a 12-bit hash that can be immediately used in a hashtable of size 2<sup>12</sup>.

== Performance characteristics ==
* '''Compression ratio''': In the worst case, LZP's output can be at most 12.5% larger than the input, as an all-miss string yields 9 bits per 8 input bits. The best case ratio is dependent on the maximum value representable by the chosen encoding of the match length. On real-world data, LZP alone provides modest compression, around 50% or worse for written text or worse for more general-purpose textual data with markup<ref name="Bloom1996-full" /><ref name="github-lmcilroy" />, but pairing it with an entropy coder has the potential to cut in half again the ratio.<ref name="SQUID" />
* '''Speed''': due to the lack of tree structures, search buffers or the need for dynamic allocations, LZP is always relatively faster than any algorithm that would employ these techniques such as [[Entropy coding|entropy]] coders and most [[LZ77 and LZ78|LZ]] variants.
* '''Memory usage''': The predictor table is fixed, no dynamic allocation is required during processing except for LZP4. It is recommended to choose a table size that would fit in the [[CPU cache]]<ref name="SQUID" /> to avoid the table overflowing into [[RAM]], which would cause substantial performance degradation.

== See also ==
* [[Lempel–Ziv]]
* [[Reduced Offset Lempel-Ziv]]
* [[Markov chain]]
* [[Prediction by partial matching]]
* [[Lossless compression]]

== References ==
{{Reflist|refs=
<ref name="Bloom1996">{{cite book |last=Bloom |first=Charles |chapter=LZP: A new data compression algorithm |title=Proceedings of Data Compression Conference - DCC '96 |year=1996 |pages=425– |doi=10.1109/DCC.1996.488353 |isbn=0-8186-7358-3 }}</ref>
<ref name="Bloom1996-full">{{cite web |title=LZP: a new data compression algorithm |url=https://cbloom.com/papers/lzp.pdf |website=cbloom.com |access-date=2025-10-12}}</ref>
<ref name="encosesu-predictor">{{cite web |title=PREDICTOR algorithm |url=https://encode.su/threads/1025-PREDICTOR-algorithm |website=encode.su |access-date=2025-10-12}}</ref>
<ref name="ppp-predictor">{{cite web |title=PPP Predictor Compression Protocol |url=https://www.ietf.org/rfc/rfc1978.txt |website=ietf.org |access-date=2025-10-12}}</ref>
<ref name="Hugi12">{{cite web |title=LZP Data Compression |url=https://hugi.scene.org/online/coding/hugi%2012%20-%20colzp.htm |website=Hugi 12 |access-date=2025-10-12}}</ref>
<ref name="github-lmcilroy">{{cite web |title=LZP - A streaming LZ Predictor compression tool |url=https://github.com/lmcilroy/lzp |website=Github |access-date=2025-10-12}}</ref>
<ref name="LTCB">{{cite web |title=Large Text Compression Benchmark |url=https://www.mattmahoney.net/dc/text.html |website=mattmahoney.net |access-date=2025-10-12}}</ref>
<ref name="SQUID">{{cite web |title=SQUID - a fast LZP-based file compressor |url=https://encode.su/threads/2681-SQUID-a-fast-LZP-based-file-compressor |website=encode.su |access-date=2025-10-12}}</ref>
<ref name="Campos">{{cite web |title="Lzp" by Arturo San Emeterio Campos |url=http://www.arturocampos.com/ac_lzp.html |archive-url=https://web.archive.org/web/20160427042628/http://www.arturocampos.com/ac_lzp.html |access-date=2025-10-12 |archive-date=27 April 2016 }}</ref>
<ref name="hlevkin">{{cite book |last1=Salomon |first1=David |last2=Motta |first2=Giovanni |date=18 January 2010 |title=Handbook of Data Compression Fifth Edition |url=https://www.hlevkin.com/hlevkin/12videoprocDoc/Handbook%20of%20Data%20Compression,%205th%20Edition.pdf |chapter=6.19 |publisher=Springer |isbn=978-1-84882-903-9 |access-date=2025-10-12}}</ref>
}}

{{Compression Methods}}
{{draft categories|
[[:Category:Lossless compression algorithms]]
[[:Category:Data compression]]
}}
{{⚠️🚨COPIED from EverybodyWiki ❗❕⚠️😡😤Please respect Licence CC-BY-SA ❗}}
{{Source Wikipedia}}