algorithm - 前移变换的快速算法

Question

我正在尝试找到最快的算法来进行前端转换。例如与 burrows Wheeler 变换结合使用的那个。

到目前为止，我在 Core i3 2.1GHz 上管理的最好速度约为 15MB/s。但我确信这不是最佳的。这是我迄今为止的最大努力。有什么更快的吗？

class mtf256_x {                                                                            
        typedef unsigned char u8;
        typedef unsigned long long L;
        public:
        L enc[37];
        u8 dec[256];
        mtf256_x() {
                unsigned i;
                for (i=0;i<37;i++) {
                        enc[i]=0;
                }
                for (i=0;i<256;i++) {
                        dec[i]=i;
                        set(i,i);
                }
        }
        u8 decode(u8 in) {
                u8 r = dec[in];                                                             
                if (in) {                                                                   
                        memmove(dec+1,dec,in);                                              
                        dec[0]=r;                                                           
                }                                                                           
                return r;                                                                   
        }                                                                                   
        u8 set(unsigned x, u8 y) {                                                          
                unsigned xl = (x%7)*9;                                                      
                unsigned xh = (x/7);                                                        
                enc[xh] &= ~(0x1FFLLU<<xl);                                                 
                enc[xh] |= ((L)y)<<xl;                                                      
        }                                                                                   
        u8 get(unsigned x) {                                                                
                return enc[x/7] >> (x%7)*9;                                                 
        }                                                                                   
        u8 encode(u8 in) {                                                                  
                u8 r;
                unsigned i;
                r = get(in);
                L m2 = 0x0040201008040201LLU; // 0x01 for each 9 bit int                    
                L m1 = 0x3FDFEFF7FBFDFEFFLLU; // 0xff for each 9 bit int                    
                L Q = (0x100+r)*m2;                                                         
                L a,b,c,d;                                                                  
                L * l= enc;                                                                 
                for (i=0;i<37;i++) {                                                        
                        a=l[i];
                        a+= ((Q-a)>>8)&m2;  // conditional add 1
                        a&=m1;
                        l[i]=a;
                }
                set(in,0);
                return r;
        }
};

Answer 1

也许你可以试试这个 http://kuc406.moxo.cz/projects.php

int b[ uint8Max + 2 ], treshold = 0, pivot = -1;
long inFileOffst = 0, pOffset = 0, t[ uint8Max + 1 ];
int rank, c, i, p0, p1;

  // initialise list

  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

  inFileOffst++;

  rank = 0;
  if( ( p1 = b[uint8Max + 1] ) != ( c = data[input] ) )
  {
     if( t[ c ] < pOffset )
     {
        rank += treshold++;
        t[ c ] = inFileOffst;
        p1 = pivot;
     }
     else if( t[ c ] == pOffset )
     {
        pivot = c;
        t[ c ] = pOffset = inFileOffst;
        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;
  }

但它更像是一个小字母表（例如字节），但对于更大的字母表，我建议尝试 nburns 版本，或者在http://encode.ru论坛上使用更多版本。