Hacker News Reader

Comment by lpage | Hacker News Reader

In other compression news, Apple open sourced their implementation of lzfse yesterday: https://github.com/lzfse/lzfse. It's based on a relatively new type of coding - asymmetric numeral systems. Huffman coding is only optimal if you consider one bit as the smallest unit of information. ANS (and more broadly, arithmetic coding) allows for fractional bits and gets closer to the Shannon limit. It's also simpler to implement than (real world) Huffman.

Unfortunately, most open source implementations of ANS are not highly optimized and quite division heavy, so they lag on speed benchmarks. Apple's implementation looks pretty good (they're using it in OS X, err, macOS, and iOS) and there's some promising academic work being done on better implementations (optimizing Huffman for x86, ARM, and FPGA is a pretty well studied problem). The compression story is still being written.

View on HN

History rewritten once again...

Apple's fse implementation is based on an open-source work from an individual which predates lzfse by about ~20 months.

https://github.com/Cyan4973/FiniteStateEntropy

It's even less optimized than the original one, due to a few errors that slipped through during lzfse conception.

http://encode.ru/threads/2221-LZFSE-New-Apple-Data-Compressi...

More compression news!: https://github.com/Cyan4973/zstd declared its format stable a couple days ago, getting a step towards 1.0. In the example there, it's a little denser than gzip -1 and a lot faster, and includes entropy encoding that uses finite state machines (and that I don't truly understand--maybe there's some similarity to lzfse there). It can look at your data and construct a static dictionary, which sounds cool for tasks like packing a bunch of 4kb database pages.

(https://github.com/google/gipfeli is another compressor aiming at that general space ('fast but not Snappy/LZ4 fast'), but I don't think it caught on much.)

I followed your link which leads me to rant a bit:

LZFSE has been out since one year. Not one mention on wikipedia. The repo lacks a good description what lzfse is. It also contains a LZVN encoder/decoder. The only information I found about it is some blog where someone seems to reverse engineer it for some hackintosh purposes.

I know documenting and presenting the case why people should use your software/file format can be annoying to do, but it's really important.

WWDC video talking about it:

https://developer.apple.com/videos/play/wwdc2015/712/

Apple's docs:

https://developer.apple.com/library/mac/documentation/Perfor...

Generic info on finite state entropy compression:

http://fastcompression.blogspot.com/2013/12/finite-state-ent...

The last link was submitted to HN:

https://news.ycombinator.com/item?id=7040951

The repo's README seems pretty clear. Google provides the rest. Not really sure how much more there is to say about a reference compression algorithm.

Those first two links should ideally have been included in the project's README. From a maintainer's perspective, "Google it" should never be acceptable.

Strange that Apple didn't publish it on https://github.com/apple (which holds all of their open Swift repos).

Also, to clarify, ANS is relatively new (2009) but arithmetic coding has been around for a long time. Historically it was avoided because of patents, many (all?) of which have now expired. Apparently ANS isn't going to be patented.

Question not about ANS, but patenting: Wouldn't it make more sense for Apple (or anybody) to actually patent it, and keep those patents, but make it open via licensing ? If there's patentable material and $developer passes on filing for it, doesn't that leave it open for poaching by $third_party ?

The patent is invalid if prior art exists,so publishing it is enough to avoid it being poached by others

But doesn't the patent office only look at previous patents when searching for prior art? Of course, other sources of prior art can be brought in as a defense, but it still may not stop someone from getting a patent initially and using it to harass financially weak opponents.

Lack of patent examiner familiarity with the industry, history, and the state of the art is traditionally considered a weak point in the system as a whole. Supposedly when writing the patent claims you're supposed to do a search to make sure you're not conflicting with other patents and that there is no prior art, but this is often used to word the patent in such a way to avoid the prior art from invalidating the patent, or use differences with the prior art as support for the uniqueness of the patent being applied for. Unfortunately, patent examiners are traditionally illequipped to accurately make an assessment, and the patent applicant is allowed to make adjustments to address the issues the patent examiner found. I remember there was work on getting patent examiners to be more familiar with the areas the patents they are examining/approving are for (technology, software, or business, for example), but I don't know where that stands today.

However, IANAPL and IANAPE.

http://patents.stackexchange.com/ helps with this

Offtopic, but I wonder what do you intend to gain by writing "$word" instead of "a word".

As it ended up being posted, it really could have been "a <word>". During the course of producing it, it seemed like the entities involved might be confusing, and my first approach was to treat everything like a unique variable.

TLDR, made sense during composition, not w/ final product.

There is an attempt to patent something ANS-related: http://cbloomrants.blogspot.com/2015/05/05-21-15-software-pa...

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

Interesting, but it is all spanish to me ... What are "fractional bits"?

This blog post [1] and its predecessor explaining Huffman Codes [2] was a very helpful guide for me.

[1] https://hbfs.wordpress.com/2011/11/01/fractional-bits-part-i... [2] https://hbfs.wordpress.com/2011/05/17/huffman-codes/

Generally, a symbol of probability p contains lg(1/p) bits of information: 1 bit if p=1/2, 2 bits if p=1/4 etc. In Huffman you directly assign a concrete bit sequence to every symbol - it is perfect if their probabilities are powers of 1/2, but generally is not true: requires approximations, leading to a suboptimal compression ratio.

Accurate entropy coders like arithmetic/range coding or ANS family can directly work on symbols of general probabilities: containing a non-integer number of bits. It has to finally produce complete bits - their fractional number is handled by the state of the coder - kind of a buffer containing a fractional number of bits. Complete bits are produced as soon as they accumulate.

Reply on news.ycombinator.com