Results 1 to 6 of 6

Thread: What is best compression method for permutations

  1. #1
    Member
    Join Date
    Jun 2008
    Location
    G
    Posts
    377
    Thanks
    26
    Thanked 23 Times in 16 Posts

    What is best compression method for permutations

    Hi,

    What is the best compression method for permutations (1,....,n) when there are only a few elements fullfill the condition e[i] > e[i+1] were 1 <= e[i] <= n?

    thanks

  2. #2
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,976
    Thanks
    296
    Thanked 1,303 Times in 740 Posts
    Well, an obvious answer is enumeration.
    But to count these specific permutations, we need a precise description of their structure, not in terms of "only a few elements".
    For example, we can start with only one out-of-order element, etc.

  3. #3
    Member
    Join Date
    Nov 2013
    Location
    Kraków, Poland
    Posts
    803
    Thanks
    244
    Thanked 255 Times in 159 Posts
    For a general permutation you need lg(n!) bits (assuming uniform probability distribution among them), what can be easily get with enumerative coding, e.g. with rANS-style renormalization to avoid large number arithmetics.
    https://en.wikipedia.org/wiki/Lehmer_code

    However, the condition suggests that you want to encode some special permutations.
    Probably the simplest way is going to nonuniform probabilities in this standard enumerative coding way - somehow model them (Pr(0) should increase I think) and then e.g. analogously use rANS.

  4. #4
    Member
    Join Date
    Jun 2008
    Location
    G
    Posts
    377
    Thanks
    26
    Thanked 23 Times in 16 Posts
    Quote Originally Posted by Shelwien View Post
    Well, an obvious answer is enumeration.
    But to count these specific permutations, we need a precise description of their structure, not in terms of "only a few elements".
    For example, we can start with only one out-of-order element, etc.
    Ok here some more information of the struchture of the permutations.

    - the permutation has just 1 cycle
    - the permutation length is 10000 <= n <= 50000
    - there are just 255 turning points were e[i-1] > e[i]

    with ranking (enumerative coding) i just get (n-1%) bytes for a permutation of length n, but i need to get about 10% savings

  5. #5
    Member
    Join Date
    Nov 2013
    Location
    Kraków, Poland
    Posts
    803
    Thanks
    244
    Thanked 255 Times in 159 Posts
    If turning points are just ~1%, maybe just encode them - transformation from identity permutation to yours.
    If order of such transformations is not important, try to sort them and encode differences.

    If I properly understand, e[i] - e[i-1] is:
    a) usually 1 or
    b) a small natural number, or
    c) negative only in 255 cases.
    If so, maybe use entropy coder to choose one of these 3 cases, in a) you can additionally use RLE to directly write lengths of such blocks, in b) maybe some entropy coding, and in c) probably directly write the negative distance.

  6. #6
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,976
    Thanks
    296
    Thanked 1,303 Times in 740 Posts
    I'd also suggest detecting and encoding "turning points" separately.
    For example, you can create a bitmap of locations (n-bit string with 255 1s in it),
    then encode e[i] values for bitmap[i]=1, with the bounds of (e[i+1]..n]...
    or just one of 255 remaining values, if e[i] are all unique.

Similar Threads

  1. NEW compression method: FUDGEpAQ!
    By Math Mahoney in forum Data Compression
    Replies: 5
    Last Post: 19th January 2019, 10:09
  2. Steganography based on dictionary permutations
    By Shelwien in forum Data Compression
    Replies: 15
    Last Post: 6th September 2016, 18:44
  3. New compression method
    By no404error in forum Data Compression
    Replies: 5
    Last Post: 21st September 2015, 23:00
  4. Identifying compression method
    By ngc.kor in forum Data Compression
    Replies: 5
    Last Post: 15th November 2014, 05:03
  5. Does this compression method already exist?
    By Lasse Reinhold in forum Forum Archive
    Replies: 4
    Last Post: 24th August 2007, 13:59

Posting Permissions

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