4 ms·

In other compression news, Apple open sourced their implementation of lzfse yesterday: https://github.com/lzfse/lzfse https://github.com/lzfse/lzfse. It's based

by lpage 10y ago

In other compression news, Apple open sourced their implementation of lzfse yesterday: https://github.com/lzfse/lzfse 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.

mayoff 10y ago
Strange that Apple didn't publish it on https://github.com/apple 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.
- bch 10y ago
  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 ?
  - riffraff 10y ago
    The patent is invalid if prior art exists,so publishing it is enough to avoid it being poached by others
    - derekp7 10y ago
      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.
      - thwarted 10y ago
        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.
        leeoniya 10y ago
        http://patents.stackexchange.com/ http://patents.stackexchange.com/ helps with this
  - andrepd 10y ago
    Offtopic, but I wonder what do you intend to gain by writing "$word" instead of "a word".
    - bch 10y ago
      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.
- eln1 10y ago
  There is an attempt to patent something ANS-related: http://cbloomrants.blogspot.com/2015/05/05-21-15-software-patents-are-fucking.html http://cbloomrants.blogspot.com/2015/05/05-21-15-software-pa...
legulere 10y ago
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.
- js2 10y ago
  WWDC video talking about it: https://developer.apple.com/videos/play/wwdc2015/712/ https://developer.apple.com/videos/play/wwdc2015/712/ Apple's docs: https://developer.apple.com/library/mac/documentation/Performance/Reference/Compression/ https://developer.apple.com/library/mac/documentation/Perfor... Generic info on finite state entropy compression: http://fastcompression.blogspot.com/2013/12/finite-state-entropy-new-breed-of.html http://fastcompression.blogspot.com/2013/12/finite-state-ent... The last link was submitted to HN: https://news.ycombinator.com/item?id=7040951 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.
  - AceJohnny2 10y ago
    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.
twotwotwo 10y ago
More compression news!: https://github.com/Cyan4973/zstd 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 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.)
eln1 10y ago
Apple tANS implementation was suboptimal - both from the quantization and symbol spread point of view: http://encode.ru/threads/2221-LZFSE-New-Apple-Data-Compression?p=48491&viewfull=1#post48491 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-Systems-implementations 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 https://github.com/jkbonfield/rans_static
twitch_checksum 10y ago
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 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-Compression?p=48491&viewfull=1#post48491 http://encode.ru/threads/2221-LZFSE-New-Apple-Data-Compressi...
ralfd 10y ago
Interesting, but it is all spanish to me ... What are "fractional bits"?
- niftich 10y ago
  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/ https://hbfs.wordpress.com/2011/11/01/fractional-bits-part-i... [2] https://hbfs.wordpress.com/2011/05/17/huffman-codes/ https://hbfs.wordpress.com/2011/05/17/huffman-codes/
- eln1 10y ago
  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.

by lpage 10y ago

mayoff 10y ago

Strange that Apple didn't publish it on https://github.com/apple 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.

bch 10y ago
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 ?
- riffraff 10y ago
  The patent is invalid if prior art exists,so publishing it is enough to avoid it being poached by others
  - derekp7 10y ago
    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.
    - thwarted 10y ago
      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.
      - leeoniya 10y ago
        http://patents.stackexchange.com/ http://patents.stackexchange.com/ helps with this
- andrepd 10y ago
  Offtopic, but I wonder what do you intend to gain by writing "$word" instead of "a word".
  - bch 10y ago
    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.
eln1 10y ago
There is an attempt to patent something ANS-related: http://cbloomrants.blogspot.com/2015/05/05-21-15-software-patents-are-fucking.html http://cbloomrants.blogspot.com/2015/05/05-21-15-software-pa...

legulere 10y ago

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.

js2 10y ago
WWDC video talking about it: https://developer.apple.com/videos/play/wwdc2015/712/ https://developer.apple.com/videos/play/wwdc2015/712/ Apple's docs: https://developer.apple.com/library/mac/documentation/Performance/Reference/Compression/ https://developer.apple.com/library/mac/documentation/Perfor... Generic info on finite state entropy compression: http://fastcompression.blogspot.com/2013/12/finite-state-entropy-new-breed-of.html http://fastcompression.blogspot.com/2013/12/finite-state-ent... The last link was submitted to HN: https://news.ycombinator.com/item?id=7040951 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.
- AceJohnny2 10y ago
  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.

twotwotwo 10y ago

More compression news!: https://github.com/Cyan4973/zstd 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 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.)

eln1 10y ago

Apple tANS implementation was suboptimal - both from the quantization and symbol spread point of view: http://encode.ru/threads/2221-LZFSE-New-Apple-Data-Compression?p=48491&viewfull=1#post48491 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-Systems-implementations 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 https://github.com/jkbonfield/rans_static

twitch_checksum 10y ago

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 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-Compression?p=48491&viewfull=1#post48491 http://encode.ru/threads/2221-LZFSE-New-Apple-Data-Compressi...

ralfd 10y ago

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

niftich 10y ago
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/ https://hbfs.wordpress.com/2011/11/01/fractional-bits-part-i... [2] https://hbfs.wordpress.com/2011/05/17/huffman-codes/ https://hbfs.wordpress.com/2011/05/17/huffman-codes/
eln1 10y ago
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.