Results 1 to 8 of 8

Thread: New move-to-front variant?

  1. #1
    Programmer
    Join Date
    May 2008
    Location
    denmark
    Posts
    94
    Thanks
    0
    Thanked 2 Times in 2 Posts
    I have recently described a move-to-front variant. Here's an improvement that doesn't have dublicated values in its queue:

    In normal move-to-front you have a symbol queue where the head is the most recent input symbol and the tail is the oldest.

    When an input byte is read, you find it in the queue, move it out and make it the new head. Moving it out creates a gap in the list which you close my moving left and right parts together.

    In my variant, the gap is closed by moving the tail into it. This will of course disturb the property of being sorted by local frequency (I do not know how significant the disturbtion is), but here's the scoop: It is possible to execute this move-to-front variant in O(n) time.

    Does anybody know if this method exists already and if the resulting output is any good?

    Explanation and sample code will follow if it turns out to be unknown

  2. #2
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,474
    Thanks
    26
    Thanked 121 Times in 95 Posts
    it will be much worser than regular mtf. better use short normal mtf queue, eg. 32 symbols and the 224 remaining symbols code using flat distibution.

  3. #3
    Programmer
    Join Date
    May 2008
    Location
    denmark
    Posts
    94
    Thanks
    0
    Thanked 2 Times in 2 Posts
    Hi donkey7,

    That would also be pretty slow. This idea runs faster.

    There's a little discussion on comp.compression now

    Lasse

  4. #4
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,474
    Thanks
    26
    Thanked 121 Times in 95 Posts
    what code do you use?

    my idea can be implemented in assembler using shrd intructions for better speed.

  5. #5
    Programmer
    Join Date
    May 2008
    Location
    denmark
    Posts
    94
    Thanks
    0
    Thanked 2 Times in 2 Posts
    I've created some sample code here: http://rafb.net/p/x7FhiZ87.html

    Would be cool if somebody could test it with BW or similiar, and tell if the mtf transformation is good enough.

    Lasse

  6. #6
    Member
    Join Date
    Dec 2006
    Posts
    611
    Thanks
    0
    Thanked 1 Time in 1 Post
    kvark could test it in his dark archiver

  7. #7
    Expert
    Matt Mahoney's Avatar
    Join Date
    May 2008
    Location
    Melbourne, Florida, USA
    Posts
    3,255
    Thanks
    306
    Thanked 779 Times in 486 Posts
    SRANK uses a variant of your MTF that doesn't hurt compression as much. When it finds a match, it is moved about half way to the front with some random dithering and swapped with the byte at that location. This takes O(1). Search is also O(1) because it maintains an index and can just look up the location of each byte.
    ftp://ftp.cs.auckland.ac.nz/pub/staff/peter-f/sran k.c

  8. #8
    Programmer
    Join Date
    May 2008
    Location
    denmark
    Posts
    94
    Thanks
    0
    Thanked 2 Times in 2 Posts
    Hi Matt,

    Great, thanks for the info

    Lasse

Similar Threads

  1. Move-to-Front Implementation
    By Cyan in forum Data Compression
    Replies: 34
    Last Post: 8th August 2010, 02:11
  2. New LZW variant
    By encode in forum Forum Archive
    Replies: 14
    Last Post: 28th January 2008, 22:33

Posting Permissions

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