Page 2 of 2 FirstFirst 12
Results 31 to 35 of 35

Thread: Move-to-Front Implementation

  1. #31
    Member
    Join Date
    Apr 2010
    Location
    CZ
    Posts
    81
    Thanks
    5
    Thanked 7 Times in 5 Posts
    well there seems to be a small room for improvements, by using just one pivot point in a linked list I managed to lower the worst case MTF complexity even with small alphabet size like with the only one byte input. The Improvement should be about -x to +25% for both encoder and decoder.

    I am appending new MTF code in C++ because the Java has several performance bugs with arrays & allocations thus it's making a worst case penalties for newly added code bigger. Anyway Java has been tuned more, it has bit different algorithm so it's performance with pure MTF (if RLE not included) is "quite" close to the C++ code

    Also here is a new release of the Java version, rle0.10.jar.

    No code has to be inserted here.


    MTF 0.11, C++ style, encode
    Code:
    int b[uint8Max + 2], rank, c, i, p0, p1, treshold = 0, pivot = -1;
    long inputFileOffst = 0, pOffset = 0, t[uint8Max + 1];
    
      // initialise
      for (i = 0; i <= uint8Max; t[i++] = 0);
      for (i = 1; i <= uint8Max; b[i - 1] = i++);
      b[uint8Max] = b[uint8Max + 1] = 0;
    
      // read data
      // input  = c; output = rank
    
      rank = 0;
      if ((p1 = b[uint8Max + 1]) != (c = data[input])) {
          if (t[c] < pOffset) {
             rank += treshold++;
             t[c] = inputFileOffst;
             p1 = pivot;
          } else if (t[c] == pOffset) {
             pivot = c;
             t[c] = pOffset = inputFileOffst;
             treshold = 0;
          }
          while (true) {  // passing the list
            if ((p0 = b[p1]) == c) {rank++;  b[p1] = b[c]; break;}
            if ((p1 = b[p0]) == c) {rank+=2; b[p0] = b[c]; break;}
            if ((p0 = b[p1]) == c) {rank+=3; b[p1] = b[c]; break;}
            if ((p1 = b[p0]) == c) {rank+=4; b[p0] = b[c]; break;}
            rank += 4;
          }
          b[c] = b[uint8Max + 1];
          b[uint8Max + 1] = c;
      }
    C++ style decode
    Code:
    int b[uint8Max + 2], rank, treshold = 0, c, offset, pivot =-1;
    
      // initialise
      for (int i = 1; i <= uint8Max; b[i - 1] = i++); 
      b[uint8Max] = b[uint8Max + 1] = 0;
    
      // read data
      // input = c; output = rank
    
      if ((c = data[input]) > 0) {
        offset = b[uint8Max + 1];
    
        if (pivot < 0) {
           pivot = offset;
        } else if (c > treshold)
          if (++treshold == c) {
            pivot = -1;
            treshold = 0;
          } else  {
              offset = pivot;
              c -= treshold;
            }
         while (c-- > 1) offset = b[offset];
         b[offset] = b[rank = b[offset]];
         b[rank] = b[uint8Max + 1];
         b[uint8Max + 1] = rank;
      } else rank =  b[uint8Max + 1];
    Attached Files Attached Files
    Last edited by quadro; 31st July 2010 at 13:45. Reason: version 0.11 added, encoder code deleted

  2. #32
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,912
    Thanks
    291
    Thanked 1,272 Times in 719 Posts
    What about at least adding enwik8.bwt?
    Eg. download openbwt from http://encode.su/threads/104-libBWT?p=8675
    FInd bwt.exe in \build_win32\samples
    Then produce enwik8.bwt by running bwt.exe 100 enwik8 enwik8.bwt

  3. #33
    Member
    Join Date
    Apr 2010
    Location
    CZ
    Posts
    81
    Thanks
    5
    Thanked 7 Times in 5 Posts
    100 MB chunks seems to be out of my hardware, I will add some max. possible though

  4. #34
    Member
    Join Date
    Apr 2010
    Location
    CZ
    Posts
    81
    Thanks
    5
    Thanked 7 Times in 5 Posts
    Results are added. I managed to make up this 100 MB chunk after some 40 min of swapping.

    Also a new version MTF 0.11 update is added, some needless code has been cleaned from encoder
    Last edited by quadro; 31st July 2010 at 14:18. Reason: + new version

  5. #35
    Member
    Join Date
    Apr 2010
    Location
    CZ
    Posts
    81
    Thanks
    5
    Thanked 7 Times in 5 Posts
    Hello everyone,

    I was playing with MTF output encoding and here is some update ( it could apply for RLE-Bit with MTF or WFC and all similar things).

    I am Suspecting that two first(most random) output bits are coded separetly and first bit contains rle0 .

    Here I go and mutually swap every 5+(n*4) and 6+(n*4) ranks. This will increase the overall Zero counts in output 1st bit, if smaller rank is more frequent.

    Overall result is quite minor, about 1009065 Zeros Gained for Enwik8's output, cca 80kB in compression, however transform is fast O(1) and simmilar process works for RLE0, and here is a transform for general case increase of RLE0 zero counts before encoding.

    Code:
    int rle0Trans[] = new int[] {1,2,3,4,5,6,7,8,9,11,10,13,12,14,15,16,17,19,23,18,21,27,20,25,24,28,26,29,22,30,
    				31,32,33,35,39,47,34,37,43,55,36,41,51,40,49,48,38,45,59,42,53,57,44,50,56,52,54,60,58,46,61,62,
    				63,64,65,67,71,79,95,66,69,75,87,111,68,73,83,103,72,81,99,80,97,96,70,77,91,119,74,85,107,76,89,115,82,101,88,
    				113,104,100,98,112,84,105,123,120,114,102,78,121,116,106,86,117,90,93,108,109,92,125,124,122,118,110,94,126}; 
    
    if(rleSequenceLength <= 126) rleSequenceLength = rle0Trans[(int)rleSequenceLength - 1];
    Last edited by quadro; 8th August 2010 at 01:35. Reason: typo

Page 2 of 2 FirstFirst 12

Similar Threads

  1. Implementation of JPEG2000 LLC based on LZMA
    By Raymond_NGhM in forum Data Compression
    Replies: 0
    Last Post: 19th March 2010, 01:14
  2. Statistical implementation of Ziv-Lempel
    By thomas in forum Data Compression
    Replies: 3
    Last Post: 10th February 2009, 19:13
  3. New move-to-front variant?
    By Lasse Reinhold in forum Forum Archive
    Replies: 7
    Last Post: 17th September 2007, 16:05

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
  •