Results 1 to 15 of 15

Thread: Compression Ideas

  1. #1
    Member
    Join Date
    Apr 2018
    Location
    World
    Posts
    3
    Thanks
    3
    Thanked 0 Times in 0 Posts

    Question Compression Ideas

    Hello,
    I am new to this forum, and I hope you will bear with me! What I am asking about is if anyone has any ideas for implementation projects in the data compression field. It's actually a project for school, and I really wish I could do it on data compression because it is so interesting! I have researched quite a bit, and it almost seems that everything has been done, though I know that cannot be true. So, if anyone has any suggestions on areas of the field where I could improve upon existing work or create new methods, that you are unopposed to sharing, I would greatly appreciate hearing them! My two ideas right now are encoding JPEGs with ANS and using a neural network as the model for an adaptive rANS compressor. Are these viable projects? Any and all feedback is greatly appreciated!

    Thanks
    (Sorry if this type of post is frowned upon, but this seems like one of the only places to ask!)

  2. #2
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,471
    Thanks
    26
    Thanked 120 Times in 94 Posts
    Compression ratio is often strongly influenced by proper detection of data type and preprocessing and/ or modelling it appropriately. Usual detectors/ parsers are crude and brittle so they often miss opportunity for easy gains. There's a project that aims to change that and you can join it. It's here: https://encode.ru/threads/2927-Fairytale

    encoding JPEGs with ANS
    That looks compelling at first, but if you aim to have (at least theoretically) widespread hardware support then you need to factor in the size of circuitry to achieve the desired functionality. Hardware implementations of tabled ANS are costly because the LUTs (look up tables) need a lot of transistors. There's a talk about new AV1 format here https://www.youtube.com/watch?v=lzPaldsmJbk - at around 23:00 there's a slide that mentions ANS.

    using a neural network as the model for an adaptive rANS compressor
    Hmm, you can always change entropy coder in PAQ to rANS, but that wouldn't make a significant difference. Neural networks are usually so slow that the speed of entropy coding is not important. ANS was implemented in lpaq1a.

  3. The Following User Says Thank You to Piotr Tarsa For This Useful Post:

    jman294 (29th April 2018)

  4. #3
    Member
    Join Date
    Feb 2015
    Location
    United Kingdom
    Posts
    154
    Thanks
    20
    Thanked 66 Times in 37 Posts
    If you want a quick and fairly simple project for school you can do context symbol ranking with rANS. Matt Mahoney's SR2 is a great source of information on how to implement it, but it used binary arithmetic so it didn't run as fast as it could be. In my experience you can usually get 150MB/s with the symbol ranking model, and 120MB/s to 400MB/s with rans. In theory you can make a compressor out of this which encodes and decodes at +70MB/s with ratios between bzip2 and gzip. I feel like using a neural network with rANS would be a missed opportunity to fill in the gaps in high throughput compression, but that's just my opinion, you can do whatever is within your ability

  5. The Following User Says Thank You to Lucas For This Useful Post:

    jman294 (29th April 2018)

  6. #4
    Member
    Join Date
    Jun 2015
    Location
    Switzerland
    Posts
    667
    Thanks
    204
    Thanked 241 Times in 146 Posts
    Quote Originally Posted by Piotr Tarsa View Post
    There's a talk about new AV1 format here https://www.youtube.com/watch?v=lzPaldsmJbk - at around 23:00 there's a slide that mentions ANS.
    I think they decided against ANS in the end.

  7. #5
    Member
    Join Date
    Apr 2018
    Location
    World
    Posts
    3
    Thanks
    3
    Thanked 0 Times in 0 Posts
    Fairytale looks very cool, thanks for the info. I have one question about neural networks: Yes they are very slow, but if I design a system that involves slow neural network compression but speedy decompression, would that be worth it? I'm thinking the decoder would not use the neural network as its model, but a quicker solution. If I could make it compress enough and decode fast enough, is there any potential in this route? Or is it just a dead end, already exhausted by the PAQ series? Anyway, thanks for the help.

  8. #6
    Member
    Join Date
    Jan 2017
    Location
    Germany
    Posts
    48
    Thanks
    25
    Thanked 10 Times in 7 Posts
    Quote Originally Posted by Jyrki Alakuijala View Post
    I think they decided against ANS in the end.
    Yes, the developers decided for the Daala entropy coder, which is an multi-symbol range coder, afaik.
    The developers have a strong focus on an implementation of AV1 decoder in hardware. The Daala entropy coder is more hardware friendly, they say. Higher data throughput per MHz clock speed.

  9. #7
    Member
    Join Date
    Nov 2013
    Location
    Kraków, Poland
    Posts
    645
    Thanks
    205
    Thanked 196 Times in 119 Posts
    Using neural network for prediction (CM) will be rather also very slow on decompression.
    The intermediate world seem a bit unexplored - e.g. SIMD adaptation on 16 size alphabet + SIMD rANS like in LZNA: https://github.com/powzix/kraken/blob/master/lzna.cpp
    https://fgiesen.wordpress.com/2015/0...hmetic-coding/

    Quote Originally Posted by Jyrki Alakuijala View Post
    I think they decided against ANS in the end.
    Indeed, G gave here really impressive presentation of how not to do stuff - while everybody else successfully use advances of ANS (e.g. Apple team looking new in compression), they have proven that some could also fail at it - not only in AV1, but also earlier in Brotli (now ~twice slower than zstd) ... additionally claiming authorship, wanting monopoly for (failing at) using ANS.

    Here is example of how to do image compression with ANS: http://gamma.cs.unc.edu/GST/

    The Daala entropy coder is more hardware friendly, they say.
    I have looked closer at it (before finding the patent...) and while rANS uses one multiplication to decode a symbol ... DAALA EC has used up to 16 multiplications to decode the same single symbol:

    do {
    u = v;
    v = cdf[++ret] * (uint32_t)r >> ftb;
    } while (v <= c);

  10. #8
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,471
    Thanks
    26
    Thanked 120 Times in 94 Posts
    Quote Originally Posted by jman294 View Post
    I have one question about neural networks: Yes they are very slow, but if I design a system that involves slow neural network compression but speedy decompression, would that be worth it? I'm thinking the decoder would not use the neural network as its model, but a quicker solution. If I could make it compress enough and decode fast enough, is there any potential in this route? Or is it just a dead end, already exhausted by the PAQ series? Anyway, thanks for the help.
    PAQ is a symmetric algorithm - compression and decompression is almost the same thing from computational complexity perspective. In PAQ you have a lot of machinery that outputs a single prediction per bit. That prediction is used to encode the bit during compression and to decode a bit during decompression. Entropy coding consumes very tiny fraction of time in PAQ so that's why it doesn't really affect the total time, which is dominated by computing the prediction.

    Asymmetric algorithms, like LZ77 (Deflate, LZMA, ZSTD, etc) have usually slow compression and fast decompression. In case of LZ77 the compressor is working hard to find matches - i.e. it finds repetitions in input and encodes (offset, match length) pairs. Decompression is much faster because decompressor doesn't have to do the same work as compressor - decompressor just copies the data that is pointed by (offset, match length) pair.

    If you want to have asymmetric compressor then decompressor must do simpler work than the compressor, but the decompression must be a reverse process compared to compression. You can't e.g. predict probablities during compression using precise model and then somehow decode it using imprecise probabities. The result of hard work must be encoded in a simple way, like in LZ77. Therefore, if you really want to use neural networks in asymmetric compressor, then you can probably e.g. use them for data type detection and then encode the result of detection in the compressed stream. After that you would use a fast transforms and other algorithms specialized to detected data types. That's just one idea.

  11. The Following User Says Thank You to Piotr Tarsa For This Useful Post:

    jman294 (30th April 2018)

  12. #9
    Member
    Join Date
    Apr 2018
    Location
    World
    Posts
    3
    Thanks
    3
    Thanked 0 Times in 0 Posts
    If I were to, say, convert the neural network's topology to a simple lookup table of context input/probability output, and add this to the compressed data, could the decompressor use this table as its model (it would be the same model the encoder got)? The benefit would come from the fact that the table would be generated by a neural network, and would (hopefully) have very accurate probabilities. Otherwise, I really like your suggestion about data type detection with neural networks. You all have been very, very helpful!

  13. #10
    Member
    Join Date
    Apr 2018
    Location
    GUANGZHOU
    Posts
    5
    Thanks
    1
    Thanked 0 Times in 0 Posts
    I had the same thought before, man! How can I craft something with great originality? I am gonna say it is really hard! If you look at the IEEE DCC(Data Compression Conference), there are quite a lot PhDs/Profs who are currently researching. WoW. This is amazing! However, in truth, we are still using LZ-based methods invented 30-40 years ago. I don't mean that you should abandon this idea. I just tell you it could be tough.

    AI is a new topic for data compression. Seriously, coming up something new is hard, but you are surely in the right direction. I don't think AI could be used for adaptive entropy encoder. The optimal freq table can always be obtained by stat. What is the point of applying neural network?

    I would say AI should be used in the well-known NP-hard problem "what is optimal grammar/dictionary for a certain source?". In theory, we should pick "words" with low information entropy as many as possible util there is no "profit". The sad fact is picking 1 word into dictionary will affect many other words' information entropy.

    AI(NLP) may deal with this problem(hopefully). If AI could understand "some " is not a good word, then pick "some". That would be really good, because "space" appears quite often in English, but it is meaningless to be a word like("some[space]"), just let entropy encoder handle space. I tried to build a global dictionary/grammar before, there were too many junk words like("some"|"some "|" some"), which is harmful for entropy coder.

    Look at this paper, you will understand what I said.
    https://ieeexplore.ieee.org/document/7921913/ Those guys are trying to use **
    heuristical** way to select words for "Re-Pair" algorithm. The paper is on DCC 2017. If you can use AI to beat the paper. WOW. GO TO DCC! Actually, you can choose NLP for your master degree if you are really interested in Lossless Text Data Compression.
    Last edited by JIMLYN; 30th April 2018 at 14:23.

  14. #11
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,471
    Thanks
    26
    Thanked 120 Times in 94 Posts
    Quote Originally Posted by jman294 View Post
    If I were to, say, convert the neural network's topology to a simple lookup table of context input/probability output, and add this to the compressed data, could the decompressor use this table as its model (it would be the same model the encoder got)? The benefit would come from the fact that the table would be generated by a neural network, and would (hopefully) have very accurate probabilities.
    I'm not sure what you mean. If you want to use neural network to compute static probabilities for fixed contexts then that doesn't make sense. To compute single static probability you only need to count 0's and 1's. Probability of 0 is count0 / (count0 + count1). Probability of 1 is count1 / (count0 + count1). Simple as that. Neural network attractiveness lies in its predictive power, not in doing arithmetics.
    If OTOH you mean that neural network should be used to find useful contexts then you need to provide more detail on how it could work. I don't have any idea right now how it could work. Usually in PAQ models you have plenty of simple functions that compute contexts, those contexts are then hashed and used to index a table. Every stored context has a priority so low priority contexts are deleted to make space for ones with higher priority. This way the useful contexts are emerging automatically.
    But there's another way to employ smart algorithms. Christopher Mattern's M1 (and M1x2) discussed here: https://encode.ru/threads/159-M1-Opt...highlight=m1x2 employ genetic algorithms to iteratively select context masks that lead to better compression on a particular file.

    I think one area that is relatively unexplored is data structures. Improvements to PAQ series mostly narrow down to adding new contexts, tuning parameters and detecting and modelling custom data types. I am developing my own CM compressor on https://github.com/tarsa/demixer which replaces hash tables with suffix tree. This allows to reduce memory usage and improve speed (because of less cache misses) for high context lengths. I also have an idea on how to improve (potentially, because not all ideas lead to improvements) PAQ's state tables. Instead of having 8-bit state and using it directly as a context for modelling we can e.g. have 16-bit states (used in FSMs) that then are mapped to a few 8-bit reduced states (used as contexts for modelling).

  15. #12
    Member
    Join Date
    Nov 2013
    Location
    Kraków, Poland
    Posts
    645
    Thanks
    205
    Thanked 196 Times in 119 Posts
    Quote Originally Posted by Jyrki Alakuijala View Post
    I think they decided against ANS in the end.
    Just noticed that Hamid has added AV1 range coder to https://sites.google.com/site/powturbo/entropy-coder :
    621704996 62.2 74.89 100.77 TurboANXN (nibble) o0 *NEW*
    622002650 62.2 17.94 14.34 AOMedia AV1 nibble o0 *NEW*
    +BWT:
    194954146 19.5 88.84 100.37 TurboANXN (nibble) o0 *NEW*
    196471059 19.6 22.57 18.58 AOMedia AV1 nibble o0 *NEW*

  16. #13
    Member
    Join Date
    Mar 2013
    Location
    Worldwide
    Posts
    456
    Thanks
    46
    Thanked 164 Times in 118 Posts
    Quote Originally Posted by Jarek View Post
    DAALA EC has used up to 16 multiplications to decode the same single symbol:

    do {
    u = v;
    v = cdf[++ret] * (uint32_t)r >> ftb;
    } while (v <= c);
    This is the CDF update and not the entropy coder part.

  17. #14
    Member
    Join Date
    Nov 2013
    Location
    Kraków, Poland
    Posts
    645
    Thanks
    205
    Thanked 196 Times in 119 Posts
    Quote Originally Posted by dnd View Post
    This is the CDF update and not the entropy coder part.
    Hmm nibble update should work for entire CDF (e.g. CDF[s] = (1-lam) CDF[s] + lam * mixCDF[s]), while here we clearly search for symbol/range [u,v] corresponding to position c ... in rANS we just do symbol[x & mask], while range coding requires rescaling earlier ranges until finding the proper one like here (?) ... anyway, I see the file has change since then.

  18. #15
    Member
    Join Date
    Mar 2013
    Location
    Worldwide
    Posts
    456
    Thanks
    46
    Thanked 164 Times in 118 Posts
    Yes, two functions are used for the nibble decoding od_ec_decode_cdf_q15 and update_cdf (in prob.h).
    In contrast to block based ANS, you need also both parts for the adaptive nibble rANS.
    The CDF seems more complex here and is part of the nibble model used, but it is not part of the entropy coder.
    I think, it is possible to use the same CDF part for both entropy coders, Daala and rANS.

Similar Threads

  1. Need some ideas to implement in a compressor
    By Chirantan in forum Data Compression
    Replies: 1
    Last Post: 18th December 2017, 23:41
  2. Ultimate one-click compressor ideas
    By SoraK05 in forum Data Compression
    Replies: 45
    Last Post: 23rd November 2014, 19:03
  3. CM on GPU - I need ideas for parallelization
    By namibj in forum Data Compression
    Replies: 5
    Last Post: 16th August 2013, 17:22
  4. More ideas for LZ matchfinding
    By Shelwien in forum Data Compression
    Replies: 1
    Last Post: 2nd October 2011, 23:39
  5. Ideas for PIM
    By Mapi in forum Forum Archive
    Replies: 1
    Last Post: 18th June 2007, 22:24

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •