Birth of a new algorithm named Broo and comparison with Brotli and others

Good day to the residents and visitors of the site, we will talk about the lossless compression algorithm , which is a joint “child”. This article will present the intermediate results which were achieved, in the form of comparison tables with popular algorithms.

Briefly about the algorithm

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

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

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

Training

For the purity and simplicity of measurements, 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, files were selected from an existing package for testing algorithms called Silesia. Short file description:

File name	Description	A type	Size Byte
dickens	Collection of 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 chemical structures	database	33 553 445
ooffice	Dll files from Open Office.org 1.01	exe	6 152 192
osdb	Example MySQL database format from	database	10 085 684
reymont	Book text	Polish, pdf	6 627 202
samba	tar source 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	Xml files collection	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 full of algorithms that solve different problems, but everything is known in comparison.

A short description of some of them

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

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

Zstandard (Zstd) is a lossless data compression algorithm developed since 2015 by Yann Collet with the support of Facebook. It combines a vocabulary data compression algorithm of the LZ77 type and efficient 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 LZ77, and provides a high compression ratio (usually higher than the compression ratio obtained using bzip2), and also allows the use of dictionaries of various sizes (up to 4 GB).

Snappy - another google lossless compression algorithm designed to achieve high speeds without reaching maximum compression ratios.

PC specifications

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

results

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

Tables are sorted by compression ratio (“% of the original” 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 is already having a positive effect. There are still hours to generate and test hypotheses, write tests and optimize code.

Thanks for attention.