eln1

Beside Huffman coding, there is also arithmetic/range coding and now is becoming widely used ANS coding - e.g. LZFSE (Apple), ZSTD (Facebook), VP10 (Google): http://encode.ru/threads/2078-List-of-Asymmetric-Numeral-Sys...

Apple tANS implementation was suboptimal - both from the quantization and symbol spread point of view: http://encode.ru/threads/2221-LZFSE-New-Apple-Data-Compressi... The author of this post (Eric Biggers) has made corrections and one of them was already merged in lzfse github (the second would make it incompatible).

There is a paper about FPGA implementation of tANS encoder ( ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=7306068 ), but it uses branch which is removed in more recent implementations (bottom of the first post of http://encode.ru/threads/2078-List-of-Asymmetric-Numeral-Sys... ).

It is worth to mention that rANS variant - using one multiplication per symbol (e.g. in Google VP10), has recently exceeded the speed of tANS/FSE: https://github.com/jkbonfield/rans_static

Google VP10 and WebP are also planned to be ANS-based: https://chromium.googlesource.com/webm/libvpx/+/fb9186d68d49... https://chromium-review.googlesource.com/#/c/338781/

Also lzturbo is very interesting, closed source but you one can download exec: https://sites.google.com/site/powturbo/ https://github.com/powturbo/TurboBench

Let's look at the most interesting there:

fastest encoding:

210,194,996 bytes, 0.333 sec., 0.371 sec., lz4 -1

fastest decoding:

169,476,113 bytes, 2.072 sec., 0.352 sec., lz4 -9

149,642,742 bytes, 2.069 sec., 0.646 sec., zhuff_beta -c0 -t1

gzip-alternative:

135,723,691 bytes, 8.318 sec., 1.677 sec., bro -q 3

114,602,026 bytes, 8.403 sec., 1.218 sec., lzturbo -32 -p1 -b800

prepacked:

104,094,380 bytes, 2313.780 sec., 1.693 sec., bro -q 10

90,239,627 bytes, 680.976 sec., 1.170 sec., lzturbo -39 -p1 -b800

best compression:

82,891,405 bytes, 882.513 sec., 4.597 sec., lzturbo -49 -p1 -b800

77,286,010 bytes, 6497.059 sec., 7.715 sec., glza

there are missing e.g. density, zpaq, and comments there suggest that brotli doesn't look that good for other than text data ...

Here are some benchmarks and discussion of data compression specialists: http://encode.ru/threads/2313-Brotli?p=44970&viewfull=1#post...

"Input: 812,392,384 bytes, HTML top 10k Alexa crawled (8,998 with HTML response)

Output: 219,591,148 bytes, 1.799 sec., 1.355 sec., tor-small -1

218,018,012 bytes, 1.951 sec., 1.464 sec., tor-small -1 -b800mb

210,647,258 bytes, 1.736 sec., 1.328 sec., qpress64 -L1T1

210,194,996 bytes, 0.333 sec., 0.371 sec., lz4 -1

194,233,793 bytes, 2.818 sec., 1.348 sec., qpress64 -L2T1

187,766,706 bytes, 7.966 sec., 1.059 sec., qpress64 -L3T1

173,904,470 bytes, 2.995 sec., 2.721 sec., tor-small -2

173,418,150 bytes, 3.132 sec., 2.843 sec., tor-small -2 -b800mb

169,476,113 bytes, 2.072 sec., 0.352 sec., lz4 -9

165,571,040 bytes, 2.931 sec., 2.820 sec., NanoZip - f

158,213,503 bytes, 1.855 sec., 0.980 sec., zstd

154,673,082 bytes, 3.213 sec., 2.445 sec., tor-small -3

154,166,902 bytes, 3.364 sec., 2.555 sec., tor-small -3 -b800mb

152,477,067 bytes, 2.128 sec., 0.973 sec., lzturbo -30 -p1

152,477,067 bytes, 2.132 sec., 0.971 sec., lzturbo -30 -p1 -b4

150,773,269 bytes, 2.151 sec., 1.047 sec., lzturbo -30 -p1 -b16

150,219,553 bytes, 2.332 sec., 1.204 sec., lzturbo -30 -p1 -b800

149,670,044 bytes, 7.825 sec., 2.567 sec., WinRAR - 1

149,642,742 bytes, 2.069 sec., 0.646 sec., zhuff_beta -c0 -t1 145,770,266 bytes, 4.586 sec., 2.285 sec., tor-small -4

141,951,602 bytes, 4.484 sec., 2.360 sec., tor-small -4 -b800mb

141,215,050 bytes, 2,751 sec., 0.938 sec., lzturbo -31 -p1 -b4

140,657,806 bytes, 5.037 sec., 2.544 sec., FreeArc - 1

140,211,060 bytes, 6,970 sec., 1.775 sec., bro -q 1

138,103,483 bytes, 118.023 sec., 2.394 sec., cabarc -m LZX:15

138,051,401 bytes, 2.761 sec., 1.001 sec., lzturbo -31 -p1 -b16

137,564,310 bytes, 18.762 sec., 4.299 sec., NanoZip - dp

137,211,547 bytes, 7.808 sec., 1.712 sec., bro -q 2

137,000,208 bytes, 3.763 sec., 3.852 sec., NanoZip - F

136,523,335 bytes, 2.830 sec., 1.094 sec., lzturbo -31 -p1

136,445,854 bytes, 50.932 sec., 2.344 sec., lzhamtest_x64 -m0 -d24 -t0 -b

136,337,495 bytes, 14.823 sec., 4.259 sec., NanoZip - d

135,723,691 bytes, 8.318 sec., 1.677 sec., bro -q 3

135,656,476 bytes, 2.972 sec., 1.153 sec., lzturbo -31 -p1 -b800

135,315,388 bytes, 51.436 sec., 2.371 sec., lzhamtest_x64 -m0 -t0 -b

135,287,357 bytes, 51.937 sec., 2.418 sec., lzhamtest_x64 -m0 -d29 -t0 -b

135,071,576 bytes, 21.650 sec., 4.251 sec., NanoZip - dP

132,819,515 bytes, 20.102 sec., 6.278 sec., 7-Zip - 1

131,871,664 bytes, 14.052 sec., 0.899 sec., lzturbo -32 -p1 -b4

131,401,865 bytes, 9,917 sec., 1.677 sec., bro -q 4

129,184,341 bytes, 8.305 sec., 2.692 sec., tor-small -5

127,355,215 bytes, 20.866 sec., 5.825 sec., 7-Zip - 2

127,045,472 bytes, 9.549 sec., 0.957 sec., lzturbo -32 -p1 -b16

126,139,033 bytes, 8.025 sec., 2.751 sec., tor-small -5 -b800mb

125,732,647 bytes, 10.642 sec., 2.618 sec., tor-small -6

125,454,769 bytes, 140.513 sec., 2.281 sec., cabarc -m LZX:18

123,169,077 bytes, 8.472 sec., 1.090 sec., lzturbo -32 -p1

123,093,411 bytes, 22.468 sec., 5.508 sec., 7-Zip - 3

122,564,329 bytes, 10.074 sec., 2.680 sec., tor-small -6 -b800mb

122,480,456 bytes, 19.411 sec., 1.645 sec., bro -q 5

121,068,548 bytes, 14.536 sec., 3.289 sec., FreeArc - 2

120,653,755 bytes, 16.107 sec., 2.552 sec., tor-small -7

119,969,489 bytes, 27.663 sec., 1.602 sec., bro -q 6

119,740,393 bytes, 27.370 sec., 5.259 sec., 7-Zip - 4

118,343,545 bytes, 24.112 sec., 2.123 sec., WinRAR - 2

118,139,032 bytes, 35.361 sec., 4.371 sec., NanoZip - Dp

117,500,327 bytes, 15.517 sec., 2.594 sec., tor-small -7 -b800mb

117,388,039 bytes, 23.546 sec., 2.524 sec., tor-small -8

116,526,595 bytes, 37.847 sec., 4.383 sec., NanoZip - DP

116,454,906 bytes, 35.232 sec., 4.351 sec., NanoZip - D

116,269,246 bytes, 25.888 sec., 6.589 sec., FreeArc - 3

116,217,001 bytes, 40.748 sec., 1.630 sec., bro -q 7

115,993,125 bytes, 192.929 sec., 2.199 sec., cabarc -m LZX:21

115,985,847 bytes, 386.192 sec., 0.850 sec., lzturbo -39 -p1 -b4

115,729,606 bytes, 35.504 sec., 2.095 sec., WinRAR - 3

115,163,486 bytes, 55.523 sec., 1.614 sec., bro -q 8

115,022,074 bytes, 49.863 sec., 2.084 sec., WinRAR - 5

114,602,026 bytes, 8.403 sec., 1.218 sec., lzturbo -32 -p1 -b800

114,345,025 bytes, 78,418 sec., 1.594 sec., bro -q 9

114,281,170 bytes, 22.925 sec., 2.575 sec., tor-small -8 -b800mb

113,354,128 bytes, 29.519 sec., 2.474 sec., tor-small -9

112,376,531 bytes, 177.077 sec., 1.923 sec., lzhamtest_x64 -m1 -d24 -t0 -b

111,848,802 bytes, 29.046 sec., 2.515 sec., tor-small -9 -b800mb

110,532,234 bytes, 40.580 sec., 2.496 sec., tor-small -10

110,177,215 bytes, 54.632 sec., 6.398 sec., FreeArc - 4

109,908,468 bytes, 40.292 sec., 2.501 sec., tor-small -10 -b800mb

109,522,695 bytes, 208.748 sec., 1.898 sec., lzhamtest_x64 -m2 -d24 -t0 -b

109,425,530 bytes, 436.824 sec., 0.893 sec., lzturbo -39 -p1 -b16

108,520,934 bytes, 58.227 sec., 2.521 sec., tor-small -11

108,520,934 bytes, 58.329 sec., 2.518 sec., tor-small -11 -b800mb

107,850,398 bytes, 266.166 sec., 2.562 sec., tor-small -12

107,842,909 bytes, 267.559 sec., 2.550 sec., tor-small -12 -b800mb

106,128,420 bytes, 271.607 sec., 1.850 sec., lzhamtest_x64 -m3 -d24 -t0 -b

105,933,030 bytes, 571,280 sec., 5.168 sec., lzturbo -49 -p1 -b4

105,692,791 bytes, 193.962 sec., 1.919 sec., lzhamtest_x64 -m1 -t0 -b

104,539,771 bytes, 316.307 sec., 1.833 sec., lzhamtest_x64 -m4 -d24 -t0 -b

104,094,380 bytes, 2313.780 sec., 1.693 sec., bro -q 10

104,053,219 bytes, 195.503 sec., 1.977 sec., lzhamtest_x64 -m1 -d29 -t0 -b

102,895,078 bytes, 148.997 sec., 4.850 sec., 7-Zip - 5

101,941,653 bytes, 237.364 sec., 1.889 sec., lzhamtest_x64 -m2 -t0 -b

100,898,120 bytes, 534.627 sec., 1.097 sec., lzturbo -39 -p1

100,159,922 bytes, 239.813 sec., 1.933 sec., lzhamtest_x64 -m2 -d29 -t0 -b

99,699,129 bytes, 625.001 sec., 4.902 sec., lzturbo -49 -p1 -b16

96,239,572 bytes, 347.011 sec., 1.893 sec., lzhamtest_x64 -m3 -t0 -b

95,197,295 bytes, 236.139 sec., 4.587 sec., 7-Zip - 9

94,133,011 bytes, 356.440 sec., 1.933 sec., lzhamtest_x64 -m3 -d29 -t0 -b

93,601,386 bytes, 431.884 sec., 1.899 sec., lzhamtest_x64 -m4 -t0 -b

92,303,359 bytes, 727.475 sec., 4.729 sec., lzturbo -49 -p1

91,310,894 bytes, 449.102 sec., 1.923 sec., lzhamtest_x64 -m4 -d29 -t0 -b

90,239,627 bytes, 680.976 sec., 1.170 sec., lzturbo -39 -p1 -b800

87,715,022 bytes, 314.169 sec., 5.428 sec., FreeArc - 9

82,891,405 bytes, 882.513 sec., 4.597 sec., lzturbo -49 -p1 -b800

77,286,010 bytes, 6497.059 sec., 7.715 sec., glza

Used: 7z 15.07 beta - Sep 17, 2015 (one thread)

rar 5.40 beta 4 - Sep 21, 2015 (one thread)

arc 0.67 - Mar 15, 2014 (one thread)

nz 0.09 - Nov 4, 2011 (one thread)

zhuff_beta 0.99 - Aug 11, 2014

cabarc 6.2.9200.16521 - Feb 23, 2013

lz4 1.4 - Sep 17, 2013

qpress64 1.1 - Sep 23, 2010

zstd 0.0.1 - Jan 25, 2015

tor-small 0.4a - Jun 2, 2008

lzturbo 1.2 - Aug 11, 2014

lzhamtest_x64 1.x dev - Sept 25, 2015 (own VS2015 compile)

glza 0.3a - Jul 15, 2015 "

lzturbo seems essentially better, a few other happen to be better.

FSE is implementation of this new ANS entropy coding, also used e.g. in lzturbo 1.2. It's surprising that even still using huffman, brotli is slowly approaching its performance:

http://encode.ru/threads/2313-Brotli?p=44970&viewfull=1#post...