Results 1 to 8 of 8

Thread: Faster compression or faster decompression

  1. #1
    Member
    Join Date
    Sep 2016
    Location
    China
    Posts
    9
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Question Faster compression or faster decompression

    What is in general, and without any particular requirement about speed, the most desirable behavior if one has to choose between faster compression or faster decompression?

  2. #2
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,974
    Thanks
    296
    Thanked 1,302 Times in 739 Posts
    Normally people choose faster decompression.
    For example, there exist CM and PPM coders which compress both better and faster than lzma etc, but nobody uses them.

    However, in theory, there're some tasks (like backups) where compression speed is more important.

  3. #3
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,572
    Thanks
    780
    Thanked 687 Times in 372 Posts
    [sodtware] distribution - decompression
    backup - compression

    btw, i know only one family of compression methods where compression is faster than decompression - those employing Shindler Sort, unfortunately they are not very efficient for binary data
    Last edited by Bulat Ziganshin; 26th September 2016 at 19:30.

  4. #4
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,974
    Thanks
    296
    Thanked 1,302 Times in 739 Posts
    Its also possible to use hashing instead of entropy coding.
    Alternatively, rANS can be tweaked to improve encoding speed.
    Also in PPM/CM various prefetch-based speed optimizations are possible during encoding, but not for decoding.

  5. #5
    Member
    Join Date
    Dec 2011
    Location
    Cambridge, UK
    Posts
    506
    Thanks
    187
    Thanked 177 Times in 120 Posts
    Quote Originally Posted by Bulat Ziganshin View Post
    [sodtware] distribution - decompression
    backup - compression

    btw, i know only one family of compression methods where compression is faster than decompression - those employing Shindler Sort, unfortunately they are not very efficient for binary data
    It's also true for non-binary arithmetic coding. The encoder has multiplier while the decoder has a division. rANS more or less reverses this behaviour.

    I'd add a use case for the middle ground too where compression and decompression should be matched - for data transport. Eg foo | compress | <network transfer> | decompress | bar.

  6. #6
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,974
    Thanks
    296
    Thanked 1,302 Times in 739 Posts
    Yeah, but symmetric codecs are easily available, and thus boring.
    And slower encoding is very easy to set up - just add some parameter optimization, even if there're no decoding-specific speed optimizations.
    But there're no well-known codecs with fast encoding / slow decoding, so its more interesting.

  7. #7
    Member
    Join Date
    Nov 2013
    Location
    Kraków, Poland
    Posts
    803
    Thanks
    244
    Thanked 255 Times in 159 Posts
    Quote Originally Posted by Shelwien View Post
    But there're no well-known codecs with fast encoding / slow decoding, so its more interesting.
    I have written about examples of such situations: entropy coding where encoder doesn't know probabilities (decoder knows) or a priori knowledge of receiver - still approaching the same capacity as he would know it. It for example allows to remove statistical modeling from encoder to make it cheaper:
    http://encode.su/threads/2282-Applic...rom-compressor

    There are also various distributed source coding ( https://en.wikipedia.org/wiki/Distributed_source_coding ) situations:
    - imagine you have array of sensors, which reads are correlated (e.g. due to being close) - if communicating, they could encode only differences. It turns out that without communication they can approach similar capacity,
    - multiview video coding ( https://en.wikipedia.org/wiki/Multiview_Video_Coding ) - you encode full spherical angle, but only need to decode part where the viewer is currently watching.

    In above situations, usually encoder just writes sparse checksums - e.g. 1bit per byte of data, this 1bit is pseudorandom depending on already processed file - encoding is cheap.
    Decoder searches the space of possible messages until getting given sequence of checksums - its expensive.
    He uses some additional information while such search to reduce the space of possibilities: modeled statistics, own a priori information, correlations between signals of neighboring sensors, already decoded part of the scene, etc.

  8. Thanks:

    Cyan (27th September 2016)

  9. #8
    Member
    Join Date
    Nov 2015
    Location
    ?l?nsk, PL
    Posts
    81
    Thanks
    9
    Thanked 13 Times in 11 Posts
    Quote Originally Posted by Bulat Ziganshin View Post
    backup - compression
    For personal users, maybe. For business, restoration often involves downtime and related losses, so decompression too.

    And pretty much always, the most important question is "if I spend x seconds extra, how many bytes does it save me?", whether it's compression and decompression time.

Similar Threads

  1. LzTurbo: The fastest now more faster
    By dnd in forum Data Compression
    Replies: 41
    Last Post: 21st January 2020, 13:05
  2. How to make umac even faster
    By calthax in forum Data Compression
    Replies: 2
    Last Post: 26th March 2015, 00:38
  3. Computing the BWTS faster
    By nburns in forum Data Compression
    Replies: 4
    Last Post: 20th July 2013, 20:17
  4. GCC 4.6 faster than previous GCC, faster than LLVM
    By willvarfar in forum The Off-Topic Lounge
    Replies: 2
    Last Post: 15th November 2010, 15:09
  5. Faster PAQ7/8
    By LovePimple in forum Forum Archive
    Replies: 6
    Last Post: 8th February 2007, 13:04

Posting Permissions

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