What are the commonly used lossless compression algorithms?

Commonly used lossless compression algorithms are: 1. LZ77 algorithm, which is the basis of many other lossless compression algorithms; 2. LZR algorithm, which is an algorithm designed to improve LZ77; 3. LZSS algorithm, which The goal is to become a linear time replacement algorithm for LZ77; 4. DEFLATE algorithm; 5. LZMA algorithm, etc.

#Data compression is the process of reducing file size while retaining the same or most of the data. It works by eliminating unnecessary data or reorganizing it into a more efficient format. When compressing data, you can choose to use lossy or lossless methods. Lossy methods permanently erase some data, while lossless methods ensure that all data is retained. Which method to use depends on how accurate you want your file to be.

This article will introduce you to 6 different lossless data compression algorithms and 4 image/video compression algorithms based on deep learning.

6 Lossless Data Compression Algorithms

Lossless compression algorithms are usually used for archiving or other high-fidelity purposes. These algorithms allow you to reduce file size while ensuring that the file is fully recoverable. There are many lossless compression algorithms for you to choose from. The following introduces 6 commonly used algorithms:

1. LZ77

The LZ77 algorithm was released in 1977. As the basis for many other lossless compression algorithms, it uses the concept of "sliding windows". In this concept, LZ77 manages a dictionary. The dictionary uses triples: Offset: the distance between the beginning of the phrase and the beginning of the file

Run length: the number of characters that make up the phrase

Deviation character: indicates the marker of the new phrase. After the match is completed, the first symbol in the forward buffer

When the file is parsed, the dictionary will be updated in real time to reflect the latest of compressed data and size. For example, if a file contains the string "abbadabba", then the item compressed into the dictionary is "abb(0,1,'d')(0,3,'a')". You can look at the disassembly process in the following table:

In this example, the compressed data is not much smaller than the initial data. But generally, this compression effect will show up when the file is very long.

2. LZR

LZR was proposed by Michael Rodeh in 1981. It was developed on the basis of LZ77. The goal of this algorithm is to become a linear time replacement algorithm of LZ77, but after encoding, the Udell pointer may point to any offset of the file, which means that it requires considerable memory consumption, so the performance is not as good as LZ77.

3. LZSS

LZSS, full name Lempel-Ziv-Storer-Szymanski, was proposed in 1982. It is also an algorithm designed to improve LZ77. It introduces a method to detect whether the file size is actually reduced. If the compression effect cannot be achieved, the original input format will be maintained. LZSS also removes the use of offset characters, using only pairs. This compression algorithm is widely used in archive formats such as RAR and in the compression of network data.

4. DEFLATE

DEFLATE algorithm was proposed in 1993. The author is Phil Katz. This algorithm combines the LZ77 or LZSS preprocessor with Huffman coding. Huffman coding is a law proposed in 1952. It is an entropy coding that assigns codes mainly based on the frequency of occurrence of characters.

5. LZMA

LZMA algorithm, the full name is Lempel-Ziv Markov chain Algorithm (LZMA), was proposed in 1998. It is an improved version of LZ77 and aims to realize 7- ZIp file archive. It uses a chain compression method that applies a modified LZ77 algorithm at the bit level instead of the byte level. The output of this compression algorithm is later processed by arithmetic coding for subsequent further compression. Depending on the specific implementation, additional compression steps may be introduced.

6. LZMA2

The LZMA2 algorithm was proposed in 2009 and is an improved version of LZMA. It improves the performance of LZMA in terms of multi-threading capabilities and improves the performance of processing incompressible type data.

4 Deep Learning-Based Image/Video Compression Algorithms

In addition to the static compression algorithms introduced above, there are also deep learning-based compression algorithms to choose from.

1. Compression algorithm based on multi-layer perceptron

Multi-Layer Perceptron (MLP) technology uses multiple layers of neurons to obtain, process and output data. It can be applied to data dimensionality reduction tasks and data compression. The first MLP-based algorithm was proposed in 1988 and has been applied to:

Binary encoding - standard two-symbol encoding

Quantization - restricting from continuous sets to discrete sets Input

Conversion within a specific domain - pixel-level data changes

The MLP algorithm uses the output of the previous step of the decomposed neural network to determine the best combination of binary codes. Later, prediction techniques are used to optimize this method. Prediction techniques can improve data accuracy based on adjacent data through backpropagation.

2. DeepCoder -- deep neural network based on video compression

DeepCoder is a framework based on convolutional neural networks (CNN), which is an alternative to traditional video compression technology. This model uses separate CNNs for the predicted signal and residual signal. It uses scalar quantization techniques and a traditional file compression algorithm - Huffman coding - to map the encoding features into a binary stream. It is generally believed that the performance of this model is better than the famous H.264/AVC video coding specification.

3. CNN-based compression algorithm

CNN is a layered neural network, usually used for image recognition and feature detection. When applied to compression, these neural networks use convolution operations to calculate correlations between adjacent pixels. CNN demonstrates better compression results than MLP-based algorithms, improves performance at super-resolution and reduces artifacts. In addition, CNN-based compression also improves the quality of JPEG images because it reduces the peak signal-to-noise ratio (PSNR) and structural similarity (SSIM). CNN-based compression also achieves HEVC performance by using entropy estimation methods.

4. Compression algorithm based on Generative Adversarial Network (GAN)

GAN is a type of neural network that uses two neural networks to compete with each other to produce more accurate analysis and predict. The earliest GAN-based compression algorithm was proposed in 2017. The file compression ratio of these algorithms is 2.5 times that of other common methods (such as JPEG, WebP, etc.). You can use GAN-based methods to achieve real-time compression by parallelizing the processing. The main principle is to compress images based on the most relevant features. When decoding, the algorithm reconstructs the image based on these features. Compared with CNN-based algorithms, GAN-based compression algorithms can produce higher-quality images by eliminating adversarial losses.

Summary

Compression algorithms can help you optimize file size. Different algorithms have different results. This article briefly describes 6 static lossless compression algorithms and 4 deep learning-based compression algorithms. Of course, if none of these algorithms apply to your scenario, you can check out this article to find an algorithm that suits your scenario. There are many algorithms, there is always one suitable for you!

The above is the detailed content of What are the commonly used lossless compression algorithms?. For more information, please follow other related articles on the PHP Chinese website!