The birth of a new algorithm called Broo and comparison with Brotli and the rest

Good day to habravchane and guests of the site, we will focus on the lossless compression algorithm, which is a joint "child." In this article, the intermediate results of which could be achieved in the form of comparison tables with popular algorithms will be presented.

Briefly about the algorithm

The main ideology for the algorithm was compiled in several characteristics:

• Not bound to file types
• Good compression ratio
• Fast unpacking speed

The packing (compression) speed was not included here initially, but will gradually improve as the whole algorithm as a whole. Entropy compression and vocabulary methods are not used.

Training

For cleanliness and ease of measurement, the algorithm was integrated into the lzbench utility (link to GitHub ), since it already has a sufficient number of other algorithms and it is easy to integrate your own.
')
Next, the files were selected from a ready-made package for testing algorithms called Silesia. Brief description of the files:

File name	Description	Type of	Size, Byte
dickens	The collection of works by Charles Dickens	txt (eng)	10 192 446
mozilla	tar archive with Mozilla 1.0 executables	exe	51 220 480
mr	MRI image	image	9,970,564
nci	Base of chemical structures	database	33,553,445
ooffice	Dll files from Open Office.org 1.01	exe	6,152,192
osdb	Sample MySQL database format from	database	10,085,684
reymont	Text book	Polish, pdf	6,627,202
samba	source tar archive	src	21,606,400
sao	Star Catalog of the Smithsonian Astrophysical Observatory	bin data	7,251,944
webster	Webster's American English Dictionary	html	41,458,703
xml	Collection of xml files	xml	5 345 280
X-ray	X-ray image	image	8,474,240

→ Source

List of algorithms that participate in comparisons

• Brotli
• Broo
• Csc
• Gipfeli
• Libdeflate
• Lz4
• Lz5
• Lzlib
• Lzma
• Lzsse
• Quicklz
• Snappy
• Xpack
• Yalz77
• Yappy
• Zlib
• Zstd

The list is saturated with algorithms that solve different problems, but everything is known in comparison.

A short description of some of them.

Brotli - is based on the modern version of the LZ77 algorithm, the entropy Huffman coding and the modeling of the 2nd order context.
Designed to speed up the loading of web pages, supported in Chrome browsers based on Chromium and Firefox.

Deflate is a lossless compression algorithm using a combination of LZ77 and Huffman algorithms.

Zstandard (Zstd) is a lossless data compression algorithm developed from 2015 Yann Collet with the support of Facebook. Combines the vocabulary data compression algorithm of the LZ77 type and the effective entropy coding of the tANS type (FSE - Finite State Entropy), a modification of the Huffman code that implements a non-integer number of bits for storing characters.

LZMA - used in the 7-Zip archiver to create compressed archives in 7z format. The algorithm is based on a dictionary data compression scheme similar to that used in the LZ77, and provides a high compression ratio (usually higher than that obtained with bzip2 compression), and also allows the use of dictionaries of various sizes (up to 4 GB).

Snappy - another google lossless compression algorithm is designed to achieve high speeds without achieving maximum compression levels.

PC specifications

DualCore Intel Core i3 550, 3200 MHz processor
Memory GoodRam 8119 Mb DDR3-1333 DDR3 SDRAM
Ubuntu OS 16.10 x64

results

memcpy - a function that copies the data, taken as a reference for the speed of packing and unpacking.

The tables are sorted by compression ratio (“% of the original”, this way lzbench displays, did not convert) from small to large.

“Afterword”

It should be noted that it is still damp and there is still enough work to improve, but it already gives a positive effect. There are still hours of generating and testing hypotheses, writing tests and optimizing code.

Thanks for attention.