All-Match LZ77 Bit Recycling

Summary form only given. Recently, a technique called bit recycling (BR) was introduced to help reduce the redundancy caused by the multiplicity of encodings. It has been used to improve LZ77 compression, which is especially prone to allow for the existence of numerous different compressed files for some given original file F. The multiplicity of encodings causes redundancy. Instead of trying to eliminate or reduce the multiplicity itself, BR exploits it and extracts a compensation from it. It uses implicit communication that happens when, at some point in the compression process, we have that: 1. the compressor C has more than one option; and 2. the decompressor D is able to recognize that situation. The mere fact that C has the liberty to select one among many options allows it to implicitly send bits to D. The particularity of BR is that it avoids storing as many bits as possible in the compressed file by implicitly sending them instead. Previous work presented a technique that recycles bits based on the existence of multiple longest matches, called longest-match BR (LMBR). This work presents a more general, and more powerful, technique, called all-match BR (AMBR) that exploits shorter matches.