Page 1 of 2 12 LastLast
Results 1 to 30 of 35

Thread: Demixer - new tree-based bitwise CM codec is in development

  1. #1
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,497
    Thanks
    26
    Thanked 132 Times in 102 Posts

    Demixer - new tree-based bitwise CM codec is in development

    I want to announce that I've started working on tree-based bitwise CM compressor. Currently I have made (but not throroughly tested) an algorithm that builds and prints the tree - no compression is currently done. Sources are in attachment.

    Description of the tree:
    - tree is binary, thus number of internal nodes is one less than number of leaves,
    - leaves are stored in nodes (ie instead of making separate node for leaf and storing a pointer to that node in internal node, I'm saving a position in buffer only), thus total number of nodes is roughly equal to input length in bytes,
    - each node takes 16 bytes of space; when adding an input buffer and some other auxIlyary structures, total memory consumption should be less than 20x block size,
    - depth is limited, currently to 255 bits, ie equivalent to order-31 (last 7 bits are for the bits in processed byte),
    - total number of nodes can be noticeably lower than input length in bytes if there are lots of repetitions of length N, where N is the chosen order limit,
    - all paths are compressed, so if the tree has more than one node, then it is always a proper (full) binary tree, no degeneration to lists,

    I want to make a cascade of mixers, ie something like: mix(mix(mix(order-(-1), order-0), order-1), order-2). Trees have no hash collisions and order gaps ie. if I have a prediction of order-X where X > 0, then I have prediction of order-(X-1). No gaps means easy casading mixing I think. I need yet to think about how to exploit all that information that bitwise tree provides and how to manage states in nodes.



    PS:
    Note for Shelwien: License is there for a reason. Don't strip it completely.
    Attached Files Attached Files
    Last edited by Piotr Tarsa; 3rd February 2013 at 15:40.

  2. #2
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,985
    Thanks
    298
    Thanked 1,311 Times in 747 Posts
    Binary tree with pointers doesn't seem like a good idea at all though.

  3. #3
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,497
    Thanks
    26
    Thanked 132 Times in 102 Posts
    What do you mean? They aren't really pointers, but indexes in node array. Positive "pointer" means it is an index for input buffer and negative "pointer" means it is an index in node array. The current limit is about 2^31 of nodes (and correspondingly - bytes in input buffer). That amounts to over 32 GiB of RAM.

    I've checked PPMd and with order-16 it uses more than 20x the input size on files like enwik8. With order-32 the situation with PPMd is even worse. I don't know how to easily measure overhead in hash-tables-based codecs but I suspect they aren't more compact than PPMd structures. OTOH I'm predicting my coder to have memory consumption of less than 20x the input size, assuming an maximum order of 31 bytes. I could even increase that order limit to something like 127 bytes without increasing memory overhead, but I think that such high orders aren't really needed.


    BTW:
    Congratulations for your 2^11'th post
    Last edited by Piotr Tarsa; 3rd February 2013 at 15:41.

  4. #4
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,985
    Thanks
    298
    Thanked 1,311 Times in 747 Posts
    > What do you mean?

    I mean that binary trees with direct indexing (like (256+c)>>i) can be ok.

    > I've checked PPMd and with order-16 it uses more than 20x the input
    > size on files like enwik8.

    ppmd's tree is a little redundant as a speed optimization,
    ppms uses a more compact version.
    In ppmd tree, there're suffix pointers, and context nodes
    are allocated separately from symbol tables.
    Thanks to that, ppmd doesn't have to maintain a pointer
    table for orders, and doesn't have to visit all contexts
    either, if a higher-order context has the right symbol.

    And I don't see how you can have a fixed 20N tree size there.
    Order-32 model is supposed to have at least 32 different
    probability estimations per symbol, all stored somewhere, ie >32N.

    I suppose the tree itself can be linear, but for that it
    has to be a string tree, like lzma's bt4.
    And in that case it can't provide a separate probability
    estimation per each order.

    > I don't know how to easily measure overhead in hash-tables-based
    > codecs but I suspect they aren't more compact than PPMd structures.

    Actually they are, because they can afford to be lossy.

    > Congratulations for your 2^11'th post

    Thanks :)

  5. #5
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,497
    Thanks
    26
    Thanked 132 Times in 102 Posts
    Actually they are, because they can afford to be lossy.
    Trees also can be lossy - it its enough to prune some nodes along the way. I was particularly interested about the unused space vs lossiness and other factors.

    And I don't see how you can have a fixed 20N tree size there.
    Order-32 model is supposed to have at least 32 different
    probability estimations per symbol, all stored somewhere, ie >32N.
    Do you know a structure called a suffix tree? Suffix tree has linear size but it stores n strings with average length equal to n / 2 (actually they are all suffixes of one string, so it's not really n different strings).

    As to statistics: do we really need to store all statistics on a compressed path? The answer is no, because statistics for all nodes on compressed path are the same, so they also can be compressed.
    Last edited by Piotr Tarsa; 3rd February 2013 at 18:29.

  6. #6
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,985
    Thanks
    298
    Thanked 1,311 Times in 747 Posts
    > Trees also can be lossy - it its enough to prune some nodes along the way.

    Yes, in theory, but a proper sliding window implementation is more
    than 2x slower and requires a lot of additional memory.
    And "garbage collection" approach in ppmd seems to be noticeably
    inferior, compression-wise.

    > I was particularly interested about the unused space vs lossiness and other factors.

    Well, LTCB seems to imply that paq hashtable can be 8x smaller than
    a ppmd tree, while providing similar compression.

    Also actually a lossy hashtable frequently provides better
    statistics than a precise tree - apparently collision stats are
    still better than newly initialized (kinda like secondary modelling).

    So I don't think that a structure which can be implemented with a hashtable
    (eg. a binary tree) would make sense as a real linked tree.
    Imho the whole point of a tree is about things that are not compatible
    with a hashtable - like getting the whole symbol table for a context,
    or tweaking the memory layout for more cache friendliness (and prefetches).

    > The answer is no, because statistics for all nodes on compressed
    > path are the same, so they also can be compressed.

    Well, I guess I'm thinking in terms of a bytewise tree, where we'd
    have to expand symbol tables for all suffixes when a new symbol appears.

    But are there any benefits in a binary tree vs a hashtable?

  7. #7
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,497
    Thanks
    26
    Thanked 132 Times in 102 Posts
    In ppmd tree, there're suffix pointers
    PPMonstr uses the same memory structure, judging by memory occupance, so it implies that both PPMd and PPMonstr avoid mixing of all orders, maybe none of them do any mixing and rely strictly on the so called "Information Inheritance". What do you think?

    Well, LTCB seems to imply that paq hashtable can be 8x smaller than
    a ppmd tree, while providing similar compression.

    Also actually a lossy hashtable frequently provides better
    statistics than a precise tree - apparently collision stats are
    still better than newly initialized (kinda like secondary modelling).
    I think PAQ like codecs are better than PPMonstr strictly because CM is better than Information Inheritance. And there are plenty of models in PAQ, not only usual order-X models. What would be the result of PAQ without the unusual or specialized modelling, only with straight order-X models?

    So I don't think that a structure which can be implemented with a hashtable
    (eg. a binary tree) would make sense as a real linked tree.
    Nobody did path compression with hashtables and used that in CM, AFAIK. And it's the path compression that gives tremendous savings at high orders.

    Well, I guess I'm thinking in terms of a bytewise tree, where we'd
    have to expand symbol tables for all suffixes when a new symbol appears.
    I encourage you to read about suffix trees and count how many nodes they have. Compressed path is a path that doesn't branch. Every branch has its own node in suffix tree. I will thus have full statistics for all branches.

    But are there any benefits in a binary tree vs a hashtable?
    Ability to collect statistics of tens of orders with reasonable speed and completely without collisions.



    We'll see. I haven't yet done the quantized state management (firstly I'll do simple recent bits histories). I'm not yet 100% sure that the whole idea will work. I'll probably insert some debugging code that print the full collected statistics to compare the algorithm with different one and you'll have a chance to compare it yourself.

  8. #8
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,985
    Thanks
    298
    Thanked 1,311 Times in 747 Posts
    > maybe none of them do any mixing and rely strictly on the so called
    > "Information Inheritance". What do you think?

    Yes, but II can be considered a speed optimization of linear mixing.
    Probabilities of new symbols are initialized in such a way that
    overall probability distribution (over all orders) remains the same.

    Plus, ppmonstr is based on unary SSE coder, with lots of useful
    flags in contexts, including predictions of a sparse submodel.

    > I think PAQ like codecs are better than PPMonstr strictly because CM
    > is better than Information Inheritance.

    First, they're not as different as you think.
    Sure, logistic mixing is better than linear mixing, but with SSE in
    the picture there's no real difference.

    Also a model with a byte alphabet provides better results for
    stationary data (like text). A bitwise model can be too adaptive
    sometimes.

    > And there are plenty of models in PAQ, not only usual order-X
    > models.

    Yes, but in that case its not so important.
    Both paq8hp and durilca use wrt-like preprocessing,
    and after wrt paq's word model is not that helpful I think.
    And most of others don't have much effect on enwik anyway.

    > What would be the result of PAQ without the unusual or specialized
    > modelling, only with straight order-X models?

    Afair the last time when I tried making a paq rip with order-X submodel only,
    I've got 202xxx on book1 for paq (ppmonstr result is 203245).

    Of course, paq is much better on binaries though - ppmonstr doesn't
    have a record submodel etc.

    > Nobody did path compression with hashtables and used that in CM, AFAIK.
    > And it's the path compression that gives tremendous savings at high orders.

    Yes, but its possible. Why store pointers if you can have the same thing
    without them?

    > I encourage you to read about suffix trees and count how many nodes
    > they have.

    Trees with stats are still different from just finding substrings though.
    Sure, it works with a binary tree, but a base-256 linear tree would be
    a little bloated, or not linear.
    And being able to access whole symbol tables at once is one of the main
    benefits of a tree imho.

    > Ability to collect statistics of tens of orders with reasonable
    > speed and completely without collisions.

    As I said, collisions are actually good in a bitwise model, they
    improve compression.

    As to speed, I don't think that its really fast, but just in case,
    can you tell how much time it takes to process enwik8?

    > I'm not yet 100% sure that the whole idea will work.

    I don't see why it won't work, and it might have its own benefits.
    But how a binary tree can compete with hashtables?..

  9. #9
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,497
    Thanks
    26
    Thanked 132 Times in 102 Posts
    Development is slowly but steadily progressing. Right now I need some reference point to check if the tree gives correct results. I've made simple program that continually rescans the whole input block multiple times on each input bit to gather statistics. It's slow as hell but hopefully it's at least correct. Please look at it and check if it's correct.

    I don't recommend running it on inputs over 10 kB as it takes huge amount of time. I've checked the program using that command line (Linux):
    piotrek@p5q-pro:/tmp/cm$ echo -n aaabrakadabram | ~/NetBeansProjects/SlowAlternative/dist/Debug/GNU-Linux-x86/slowalternative
    And it seems to give correct results for me.

    Program only prints bit histories, it doesn't do any compression by itself. I'm aiming to extract the same information from the tree, without that excessive rescanning.

    Program reads from standard input and writes to standard output. It can have problems with binary data under Windows.
    Attached Files Attached Files

  10. #10
    Programmer toffer's Avatar
    Join Date
    May 2008
    Location
    Erfurt, Germany
    Posts
    587
    Thanks
    0
    Thanked 0 Times in 0 Posts
    If you want to enumerate all order-N context histories (byte sequences or bit sequences) you can use the following program (which is reasonably fast - although far from optimal), i've written it for viewing context histories:

    Code:
    ctxdump.cpp:
    
    #include<cassert>
    #include<cstdio>
    #include<cctype>
    #include<cstring>
    #include<cmath>
    #include<vector>
    #include<algorithm>
    
    
    ////////////////////////////////////////////////////////////////////////////////
    
    // Compute the file size of the (seekable stream) f.
    size_t FileSize( FILE* f )
    {
      assert(f!=NULL);
      const long pos=ftell(f);
      fseek(f, 0, SEEK_END);
      const long end=ftell(f);
      fseek(f, pos, SEEK_SET);
      return end;
    }
    
    enum iomode {
      READ,
      WRITE
    };
    
    // Open a file in the given IO mode; bail out on an error.
    FILE* OpenFile( const char* name, const iomode mode )
    {
      const bool reading = mode==READ;
      FILE* file=fopen(name, reading ? "rb" : "wb");
      if (file==NULL) {
        fprintf(stderr,
          "Couldn't open '%s' for %sing.\n", name, reading ? "read" : "write");
        exit(1);
      }
      return file;
    }
    
    // Write a character in a human-readable form.
    void Putc( const int c, FILE* to )
    {
      if (isprint(c)) {
        putc(' ', to);
        putc(' ', to);
        putc(c, to);
        putc(' ', to);
      } else {
        printf("<%2x>", c);
      }
    }
    
    
    ////////////////////////////////////////////////////////////////////////////////
    
    class processor
    {
    protected:
      typedef unsigned char uint8;
      uint8* buffer;
      std::vector<int> index;
      int order;
    
      // Comapre two contexts
      struct compare {
        compare( uint8* buf, int ord ):
          buffer(buf),
          order(ord)
        {}
    
        uint8* buffer;
        int order;
    
        // Compare two contexts located at buffer[i-1..i-order], buffer[j-1..j-order].
        bool operator()(int i, int j)
        {
          int n=order;
          while (i>0 && j>0 && buffer[i-1]==buffer[j-1] && n-->1) {
            --i; --j;
          }
          return i==0 || j==0 ? i==0 : buffer[i-1]<buffer[j-1];
        }
      };
    
      /// Some helper functions ///
      // Does the context of the i-th and i+1-th differ?
      bool EndOfContext( int i ) const
      {
        if (i+1>=index.size()) {
          return true;
        }
    
        int n=order;
        int j=index[i+1];
        i=index[i];
        while (i>0 && j>0 && buffer[i-1]==buffer[j-1] && n>0) {
          --i; --j; --n;
        }
        return n>0;
      }
    
      // Print the i-th context
      void PutContext( const int i, FILE* to=stdout ) const
      {
        for (int j=index[i]-order; j<index[i]; ++j) {
          if (j<0) {
            fputs(" -- ", to);
          } else {
            Putc(buffer[j], to);
          }
        }
      }
    
      /// Worker functions ///
      // Start to process contexts, index of first is passed.
      virtual void Begin( int i ) = 0;
      // Finished processing contexts.
      virtual void End() = 0;
      // Process next context, located at buffer[i]
      virtual void Next( int i ) = 0;
      // Process next character of current context
      virtual void Char( int c ) = 0;
    
    public:
      processor():
        buffer(NULL),
        order(-1)
      {}
    
      virtual ~processor()
      { delete[] buffer; }
    
      void LoadFile( const char* name, const int n )
      {
        if (buffer!=NULL) {
          delete[] buffer;
        }
    
        // Open and read the file
        FILE* file = OpenFile(name, READ);
        int count = FileSize(file);
        buffer = new uint8[count];
        count = fread(buffer, 1, count, file);
        fclose(file);
        index.resize(count);
        order = n;
    
        // No sorting required for order 0
        if (order==0) {
          for (int i=0; i<count; ++i) {
            index[i]=i;
          }
          return;
        }
    
        // Try to read the stored sorted pointers
        char* str = new char[strlen(name)+4+2+1];
        assert(order<99);
        sprintf(str, "%s.idx%02u", name, order);
        file = fopen(str, "rb");
    
        bool cached = file!=NULL;
        // We could successfully recover the indices
        if (cached) {
          cached = fread(&index[0], sizeof(index[0]), count, file)==count;
          fclose(file);
        }
        if (!cached) {
          for (int i=0; i<count; ++i) {
            index[i]=i;
          }
          std::stable_sort(index.begin(), index.end(), compare(buffer,order));
    
          file = OpenFile(str, WRITE);
          if (fwrite(&index[0], sizeof(index[0]), count, file)!=count) {
            fprintf(stderr, "Error writing to '%s'.\n", str);
          }
          fclose(file);
        }
    
        delete[] str;
      }
    
      virtual void Run()
      {
        if (buffer==NULL || order<0) {
          return;
        }
    
        Begin(index[0]);
        for (int i=0; i<index.size();) {
          Char(buffer[index[i]]); // process character
          if (EndOfContext(i++)) {
            Next(i);  // index of next context
          }
        }
        End();
      }
    };
    
    
    ////////////////////////////////////////////////////////////////////////////////
    
    class proc_print: public processor
    {
    protected:
      void Begin( int i )
      { PutContext(i, stdout); printf(" | "); }
    
      void End()
      {}
    
      void Char( int c )
      { Putc(c, stdout); }
    
      void Next( int i )
      { putchar('\n'); PutContext(i, stdout); printf(" | "); }
    };
    
    class proc_binprint: public processor
    {
    protected:
      const int symBits;
      int begin;
      int end;
    
      void Begin( int )
      { begin=end=0; }
    
      void End()
      {}
    
      void Char( int )
      { ++end; }
    
      void Next( int )
      {
        // Enumerate all context lengths
        for (int i=symBits, ctx=1; i>=1; --i) {
          // Enumerate all contexts of length i
          while (ctx < (2<<(symBits-i))) {
            bool empty=true;
            // Enumerate the data and check for a match with the
            // current context.
            for (int k=begin; k<end; ++k) {
              const int c=256|buffer[index[k]];
              if ((c>>i)==ctx) {
                empty=false;
                putchar('0' + ((c>>(i-1))&1));
              }
            }
            ++ctx;
            if (!empty) {
              putchar('\n');
            }
          }
        }
        begin=end;
      }
    
    public:
      proc_binprint( const int bits ):
        symBits(bits)
      {}
    };
    
    processor* ParseArgs( int argc, char* argv[] )
    {
      if (!(argc==2 || argc==3)) {
        return NULL;
      }
    
      const char* arg=argv[1];
      char mode='\0';
      int order=-1;
    
      while (*arg!='\0') {
        switch (*arg) {
          // order
          case 'o':
            if (!isdigit(*++arg)) {
              return NULL;
            }
            order = *arg++ - '0';
            if (isdigit(*arg)) {
              order = 10*order + *arg++-'0';
            }
            break;
          // operation modes
          case 'p':
          case 'q':
            mode=*arg++;
            break;
          default:
            return NULL;
        }
      }
    
      // either one required option is missing
      if (order<0 || mode=='\0') {
        return NULL;
      }
    
      processor* proc;
      switch (mode) {
        case 'p': proc = new proc_print(); break;
        case 'q': proc = new proc_binprint(8); break;
        default:
          fprintf(stderr, "Mode '%c' unimplemented.\n", mode);
          return NULL;
      }
    
      proc->LoadFile(argv[2], order);
      return proc;
    }
    
    int main( int argc, char* argv[] )
    {
      processor* proc=ParseArgs(argc,argv);
      if (proc==NULL) {
        fprintf(stderr,
          "usage:   ctxdump [options] file\n"
          "options:\n"
          "  o# - 0 to 99, specify order of contexts\n"
          "  p  - print context histories (bytewise)\n"
          "  q  - print context histories (bitwise)\n");
        return 1;
      }
    
      proc->Run();
      delete proc;
    
      return 0;
    }
    For instance "ctxdump o1p some_file" prints a two column output: The first column tells you the name of the context, "--" means no order-1 context. The second column list the context history. Unprintable characters are output as <hex-value>, characters without . Example:

    Code:
    I:\temp>echo AAAABABAB > 1.txt
    
    I:\temp>ctxdump o1p 1.txt
     --  |   A
    < d> | < a>
         | < d>
      A  |   A   A   A   B   B   B
      B  |   A   A
    The context history of order-1 context "A" is "AAABBB". The context history of order-1 context "B" is "AA". "< d>" and "< a>" are CR and LF characters.

    The program prints binary context histories too. However it doesn't include the context name in its output, it just outputs context histories of successiev contexts separated by newlines.

    Maybe anyone find this useful.

    Cheers
    M1, CMM and other resources - http://sites.google.com/site/toffer86/ or toffer.tk

  11. #11
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,497
    Thanks
    26
    Thanked 132 Times in 102 Posts
    Thanks toffer, but your program does completely different thing from what I wanted :P

    I think that I've succeded to make a *correct* algorithm that extracts bit histories from the tree. I've changed the SlowAlternative a bit so I'm attaching the changed version. Demixer and SlowAlternative must output the same data. If not, then there's a bug (or maybe wrong printf's are commented out). I've tested them on few files from Calgary Corpus and the output is identical.

    I've tested Demixer on enwik8 and it took about 400 seconds to process it. That amounts to about 250 kB/s on Core 2 Duo E8400. Surprisingly slow, but bear in mind that it's not optimized for speed in any way. Also it does gather a really huge amount of statistics.


    Edit:
    I've discovered a bug in Demixer - it shows up when beginning of the file is a symbol run longer than about 60. Please don't test on files with such long runs at the beginning
    Attached Files Attached Files
    Last edited by Piotr Tarsa; 9th February 2013 at 23:59.

  12. #12
    Programmer toffer's Avatar
    Join Date
    May 2008
    Location
    Erfurt, Germany
    Posts
    587
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Maybe i got you wrong. I thought you want to output the context histories of each order-N context in some file? Since your compressor works bitwise you output the binary context histories of partial context (every order-N context has at most 255 partial contexts).
    This is what my program does:
    With options "oNp" it outputs the context history (bytewise) for every appearing order-N context c.
    With options "oNq" it outputs the context history (bitwise) for every appearing partial order-N context. Again, an order-N context c has up to 255 partial contexts namely "c", "c,0", "c,1", "c,00", "c,01", ..., "c,11", "c,000", ... , "c,00000000", "c,11111111" if you use a flat decomposition.
    If you want all binary context histories from order N=0..D run the program with options "o0q", ..., "oNq"
    M1, CMM and other resources - http://sites.google.com/site/toffer86/ or toffer.tk

  13. #13
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,497
    Thanks
    26
    Thanked 132 Times in 102 Posts
    My program does basically that:

    Code:
    ...python like formatting...
    for every `byteIndex` in the input:
      for every `bitIndex` in the byte:
        for every `order` from 0 to maxOrder:
          check if a prefix of (order * 8 + 7 - bitIndex) bits has appeared before
          if not then skip
          else search for all such occurences and gather `bitHistory`, ie for each context occurence gather the bit that immediately follows that context
          print that `bitHistory` (trimmed to last 10 bits at most, with leading `1` bit prepended to indicate where the history bits in `bitHistory` starts)
        go to next line (only if anything was written in the inner loop)
      print empty line (indicating going to next byte from input)
    While, AFAIU, your code does something like that:
    Code:
    for every possible order-N context in a file:
      find all occurences of that context
      for each occurence print the immediately following byte
    Which is different as you are collecting histoires for whole file at once, while I'm printing statistics that were computed at every processed input bit and progressively updated.

  14. #14
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,497
    Thanks
    26
    Thanked 132 Times in 102 Posts
    I'm refactoring the code and thinking about a clean text model and XML model which I'm going to insert into Demixer ASAP, so next release will be somewhat delayed. I need to review the various text modelling tricks that text oriented compressors use.

    Anyway, just out of curiosity:
    As I said, collisions are actually good in a bitwise model, they
    improve compression.
    If collisions are so good, then we should use as small hashtables as possible. But using smaller hashtables decreases compression ratio. And smaller hashtables means more collisions. PAQ has checksums to prevent most of (but not all) collisions and even when I was developing TarsaLZP then adding collision detection improved compression ratio.

    And I don't see how you can have a fixed 20N tree size there.
    Order-32 model is supposed to have at least 32 different
    probability estimations per symbol, all stored somewhere, ie >32N.
    I proved that you can have fixed 16N tree size + 1N for input buffer and probably around 1.1N for rescaling purposes (rescaling isn't implemented yet), while having a history of last 10 bits for every context. If you spot any error in the program (other than the error with long run at the beginning), let me know.

    In the last posted version of Demixer I've increased the maximum order to 63 while retaining the 16-byte size of single node. State is 11 bits in size (I can extend it to 12 bits because the highest bit of text pointer is unused). It stores bit histories directly, but can be easily replaced with a more sophisticated FSM describing bit histories of up to 31 (ie 2^5 - 1) bits in size, because I store 5 bit clamped counters that are used to initialize new nodes.



    As to clean Latin ASCII text model:
    Firstly I want to do a permutation that swaps all the printable characters with codes 64-127 that are not letters with symbols from 0-31 range (except TAB, CR, LF). I assume that those non-printable characters are seldom used and thus they won't affect compression ratio much. I would preserve the property that lower letters have the same lower five bits as the corresponding upper letters.

    Next there would be a clean Latin ASCII text model, which would be used to predict (ie participate in prediction of) the lower five bits of letters and would be enabled only if the input symbol code (after permutation) is in the range 64-127. Every character outside of the range 64-127 (after permutation) would be treated as whitespace and all whitespace runs would be contracted to one fixed symbol.

    What do you think about it? Any suggestions?

  15. #15
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,497
    Thanks
    26
    Thanked 132 Times in 102 Posts
    Development progress is steady but somewhat slow. I've done some refactorings but the program doesn't compress yet. The whole magic has to be included in file predictor.h, but for now function predict() returns fixed prediction. But maybe someone will find it interesing as it is in the current form. I need to integrate logistic mixing, counters, etc yet

    Currently, function predict() is provided with a vector of collected bit histories, where collectedStates->array[x].bitHistory corresponds to a bit history for context of length x. Bit histories are limited to 11 bits. There is leading 1 bit, which marks the length of the bit history, so total length of state is 12 bits. Function __predictor__ (and other functions in the form __xxx__) is used as a constructor.

    Input is taken from stdin, output is written to stdout, messages and debug info go to stderr.
    Attached Files Attached Files
    Last edited by Piotr Tarsa; 17th February 2013 at 14:43.

  16. #16
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,497
    Thanks
    26
    Thanked 132 Times in 102 Posts
    I've just made a version that actually compress. There's a chain of 2-input unrestricted mixers, which is rather unstable if the chain gets long (eg order 50). I had to lower the initial adaptation speed of high order counters to reduce the instability.

    I've copied the logic blindlessly from LPAQ1 but I don't know if I've introduced any errors.

    Maximum and default order is 63 but there are some bugs so that order can give errors. It's currently better to use lower orders.

    Buffer size is currently hardcoded in function __engine__ in engine.h. There's no check for buffer overflows.

    Assertions are enabled unless you pass -DNDEBUG to compiler.

    enwik8 with order=12 gives 21505413 bytes and decompresses correctly.
    enwik8 with order=60 gives 26919295 bytes and I haven't tested decompression yet (edit: I've verified it now and it is OK).

    One problem with high order mixing is that if we are on position where maximum order is high, say 60, then there's high probability that there are runs of orders that have identical statistics. That effectively applies too much weight for predictions for that repeated statistics.

    PS:
    I'm trying mixing in reverse order. Results:

    enwik8 with order=12 gives 22462259 bytes and decompression is OK
    enwik8 with order=60 gives 22460881 bytes and decompression is OK

    As I've said earlier, there may be some bugs and it may be the case than one of them is ruining compression ratio.
    Attached Files Attached Files
    Last edited by Piotr Tarsa; 23rd February 2013 at 15:45.

  17. #17
    Programmer toffer's Avatar
    Join Date
    May 2008
    Location
    Erfurt, Germany
    Posts
    587
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Mixing top-down or bottom-up?
    M1, CMM and other resources - http://sites.google.com/site/toffer86/ or toffer.tk

  18. #18
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,497
    Thanks
    26
    Thanked 132 Times in 102 Posts
    The first two results are for the attached version ie mixing starting on low orders and move to high orders.

    Results after "PS" are for reversed mixing order, ie starting with mixing highest orders and then moving to lowest ones.


    All the mixing and modelling is in predictor.h. Other files are either scaffolding or tree management. Predictor.collectedStates is an array of trimmed bit histories for each context and currently only that is used for modelling so the code should be rather easy to follow.

  19. #19
    Programmer toffer's Avatar
    Join Date
    May 2008
    Location
    Erfurt, Germany
    Posts
    587
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Quote Originally Posted by Piotr Tarsa View Post
    The first two results are for the attached version ie mixing starting on low orders and move to high orders.

    Results after "PS" are for reversed mixing order, ie starting with mixing highest orders and then moving to lowest ones.


    All the mixing and modelling is in predictor.h. Other files are either scaffolding or tree management. Predictor.collectedStates is an array of trimmed bit histories for each context and currently only that is used for modelling so the code should be rather easy to follow.
    Hey - evidence for my math beeing correct. Now you need to tune the parameters.
    M1, CMM and other resources - http://sites.google.com/site/toffer86/ or toffer.tk

  20. #20
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,497
    Thanks
    26
    Thanked 132 Times in 102 Posts
    I feel that the reversed order mixing (ie highest to lowest order) was broken. Highest order prediction was mixed with p=1/2 which is obviously incorrect. I'm redoing tests with topmost order prediction unmixed.

    Edit1:
    OK, I've fixed that and I've changed initialization from:
    predictor->counters[order][context].length = order + 3;
    to:
    predictor->counters[order][context].length = 3;

    Results are:
    order 12 - 21943022 bytes, decompressed OK
    order 60 - 21936741 bytes, decompression not verified

    I'll also retest with "order + 3" modification.

    Edit2:
    With "order + 3" results are as follows:
    order 12 - 21942884 bytes, decompression not verified
    order 60 - 21936613 bytes, decompression not verified
    Last edited by Piotr Tarsa; 23rd February 2013 at 18:46.

  21. #21
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,497
    Thanks
    26
    Thanked 132 Times in 102 Posts
    OK, I had small pause in Demixer development (I've thought a bit on TarsaLZP, but after all I've ceased to develop it further as I have no chance to beat or even come close to Francesco's Rings with my design).


    So what do you suggest to optimize (to get familiar with your framework)? What would make sense to optimize?

    I'll paste your example here:
    Code:
    // problem (NAME)
    // constant (NAME) value ( <numeric value> ) more
    // integer (NAME) range (<min. value>, <max. value>) more
    // natural (NAME) range (<min. value>, <max. value>) more
    // real (NAME) precision (<nr. of bits>) range (<min. value>, <max. value>) more
    // bitmask (NAME) range (<lsb pos.>, <msb pos.>) more
    // ... end
    problem (RASTRIGIN)
    constant (DIM) value (2) more
    real (X) precision (10) range (-5,5) count (DIM) end
    Firstly:
    count(X) isn't present in comments. Are there undocumented features?

    Secondly:
    Suppose that I want to optimize learning rates for mixers in chain and/ or learning rates for indirect SSEs. Each order can have separate mixer and/ or indirect SSE learning rate and I would expect those rates to form a rather smooth sequence (ie low relative difference between learning rates of neighbour orders), so they shouldn't be treated as completely unrelated values. What would you suggest for that? And I would want to optimize for both bottom-up and top-down mixing (separately of course).

  22. #22
    Programmer toffer's Avatar
    Join Date
    May 2008
    Location
    Erfurt, Germany
    Posts
    587
    Thanks
    0
    Thanked 0 Times in 0 Posts
    OK, I had small pause in Demixer development (I've thought a bit on TarsaLZP, but after all I've ceased to develop it further as I have no chance to beat or even come close to Francesco's Rings with my design).


    So what do you suggest to optimize (to get familiar with your framework)? What would make sense to optimize?
    AFAIU you've got a PAQ mixer and use the add-const estimator (p(x|s) = (count of x in s + a)/(length of s + b). So it makes sense to optimize mixer parameters. (As you say below.) You can optimize the constants a and b as well. To avoid overtuning don't use too many paramters. E.g. for estimating the probability of bits just optimize a and set b=2a. I hope you get the idea.

    I'll paste your example here:
    Code:
    // problem (NAME)
    // constant (NAME) value ( <numeric value> ) more
    // integer (NAME) range (<min. value>, <max. value>) more
    // natural (NAME) range (<min. value>, <max. value>) more
    // real (NAME) precision (<nr. of bits>) range (<min. value>, <max. value>) more
    // bitmask (NAME) range (<lsb pos.>, <msb pos.>) more
    // ... end
    problem (RASTRIGIN)
    constant (DIM) value (2) more
    real (X) precision (10) range (-5,5) count (DIM) end
    Firstly:
    count(X) isn't present in comments. Are there undocumented features?
    No, i just forgot to write 'count' down there. Next week i can upload an enhenced version of the optimizer and its interface (which is slightly different now).
    Since this is an in-development-version always compile optimize.cpp with assertions turned on!

    Secondly:
    Suppose that I want to optimize learning rates for mixers in chain and/ or learning rates for indirect SSEs. Each order can have separate mixer and/ or indirect SSE learning rate and I would expect those rates to form a rather smooth sequence (ie low relative difference between learning rates of neighbour orders), so they shouldn't be treated as completely unrelated values. What would you suggest for that?
    1. You can optimize an array of learning rates.
    problem (DEMIXER)
    constant (MAX_ORDER) value ( more // orders i=1..8 use rate MIX_RATE[i]; orders>=8 use rate MIX_RATE[MAX_ORDER]
    constant (MIX_RATE_LOG) value (10) more // 10 bit fixed point
    natural (MIX_RATE) range (0, (1<<MIX_RATE_LOG)-1) count (MAX_ORDER+1) end

    Remark:
    For higher orders (you can try this for lower orders as well, but the gain will be small) i suggest the following: w_i' = w_i + 1/min(k,K) * d_i (d_i is the usual step direction)
    in the k-th update. This has the advantage that it yields redundancy O(log k) w.r.t. the best static weight vector for sequences of length at most K. For sequences of bigger length you can guarantee adaptivity (in theory and practise).
    You need to optimize the parameter K per order.

    2. You can optimize counter parameters analogously. The remark above applies as well.

    3. If you think that mixer parameters should behave like you described, you can opimize the coefficients of a (low-degree, say order 2 to 3) polynomial p(x) with range [0..1]. And set MIX_RATE[i] = p(i).

    And I would want to optimize for both bottom-up and top-down mixing (separately of course).
    Make two implementations and compile-in the optimizer. If the parameters are the same, you don't even need separate definition files as i described previously.
    M1, CMM and other resources - http://sites.google.com/site/toffer86/ or toffer.tk

  23. #23
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,497
    Thanks
    26
    Thanked 132 Times in 102 Posts
    compile-in the optimizer
    That isn't trivial because your optimizer is written in C++, my program is written in plain C and I don't know how to merge them. Doing "#include" in example.cpp produces lots of errors. I also need to plug memory leaks for now.

  24. #24
    Programmer toffer's Avatar
    Join Date
    May 2008
    Location
    Erfurt, Germany
    Posts
    587
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Quote Originally Posted by Piotr Tarsa View Post
    That isn't trivial because your optimizer is written in C++, my program is written in plain C and I don't know how to merge them. Doing "#include" in example.cpp produces lots of errors. I also need to plug memory leaks for now.
    C++ is almost a superset of C. Force your compiler to interepret the input as C++. Compile your files (even if these are "*.c") with option

    -x <language> Specify the language of the following input files
    Permissible languages include: c c++ assembler none
    'none' means revert to the default behavior of
    guessing the language based on the file's extension
    if you use gcc/g++.

    Plug memory leaks? What?!
    M1, CMM and other resources - http://sites.google.com/site/toffer86/ or toffer.tk

  25. #25
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,497
    Thanks
    26
    Thanked 132 Times in 102 Posts
    OK, I've somehow managed to attach the C sources to the Code::Blocks project.

    Plug memory leaks? What?!
    I'm not yet invoking free() on memory allocated by malloc().


    PS:
    That poor result with bottom-up mixing and order-60 was caused by numeric overflow. With that bug fixed the difference between order-12 and order-60 results is rather small.


    PPS:
    Fresh results:
    Code:
    -rw-rw-r--  1 piotrek piotrek 21565901 mar  2 21:38 enwik8.e60
    -rw-rw-r--  1 piotrek piotrek 21936741 mar  2 22:08 enwik8.f60
    The smaller one is for bottom-up mixing. The bigger one is for top-down.

    Right now I'm running optimizer on world95.txt.

    PPPS:
    Some preliminary results with world95.txt and order-60:
    - bottom-up mixing with LPAQ1 fixed update rate - 515831 bytes,
    - results for top-down mixing and toffer's optimizer (rates scaled by 2^5, so LPAQ1's fixed update rate which is 7, after scaling would be 224):
    Code:
    INIT: Using RNG seed 1362258810.
    INIT: Parameter recording disabled.
    INIT: Randomizing 50 individuals with 90 bits each...
    DCGA: Set mutation rate to 0.060000.
    
       0  520512.0000
    DEMIXER:
    MIX_RATE =  {107, 764, 326, 181, 122, 594, 45, 687, 163}
    
    
       1  518456.0000
    DEMIXER:
    MIX_RATE =  {225, 233, 332, 535, 176, 165, 0, 797, 411}
    
    
       2  516730.0000
    DEMIXER:
    MIX_RATE =  {350, 100, 53, 538, 76, 687, 330, 119, 0}
    It takes insane amounts of iterations to produce even one line of output and I'm too tired waiting for results. Unfortunately I haven't enabled dumping optimization state to disk. But it seems that at least for current state of my CM codec bottom-up mixing is better than top-down mixing.




    How did you optimize the parameters for CMM? Ie what were the test files, what was the size of them and how long did you run the optimizer? It seems that with default settings it takes thousands of iterations to complete. Single run on enwik8 now takes about 10min, so eg 5000 runs * 10 min / run = 50000 mins which is over 800 hours of optimizing.



    How many iterations it takes to produce final output? How often optimization state is dumped to disk and what it contains (eg does it contain an information whether we are in constructor or in subsequent optimization runs? does it save data after each compression invocation or only between the high level genetic algorithm iterations?)
    Last edited by Piotr Tarsa; 3rd March 2013 at 00:44.

  26. #26
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,497
    Thanks
    26
    Thanked 132 Times in 102 Posts
    I've made a new version, this time I've added clean text model plus a light permutation. The permutation I'm doing is swapping any non-alphabetic character in 64-127 range with unused (in text files) symbols in range 16-31. I'm doing that because the clean text model only predicts alphabetic characters. It seems that doing anything more during permutation eg swapping 32 (ASCII code for space) with 7, 8 or 31 worsens compression. However, I've read that Alexander Rhatushnyak performed such swapping somewhere, but I'm not 100% sure it was in a CM codec. Does anybody have experience in permutations for CM codecs?

    In the long run I'm going to add a dynamically computed mapping that maps from a 12-bit state (from a static, ie non-recomputable state machine) to an eg 7-bit small state, based on statistics and edit distance (ie states that have more similar statistics and lower edit distance are more likely to end up in the same cluster, ie to end up being mapped to the same small state). I plan to use k-means/ k-medians/ k-medoids algorithm. Do you have some recommendations for that task?

    Results from BottomUp mixing and clean text model enabled:
    Code:
    piotrek@p5q-pro:/tmp/cm$ time ~/NetBeansProjects/Demixer/dist/Release/GNU-Linux-x86/demixer encode order=60 nodesNumber=200M < ~/corpora/enwik/enwik8 > enwik8.e60
    Completed!
    Bytes written: 20868712
    
    real	18m38.626s
    user	18m31.581s
    sys	0m2.272s
    piotrek@p5q-pro:/tmp/cm$ time ~/NetBeansProjects/Demixer/dist/Release/GNU-Linux-x86/demixer decode < enwik8.e60 > enwik8.d60 
    Completed!
    Bytes written: 100000000
    
    real	18m27.457s
    user	18m23.509s
    sys	0m2.444s
    piotrek@p5q-pro:/tmp/cm$ time ~/NetBeansProjects/Demixer/dist/Release/GNU-Linux-x86/demixer encode order=12 nodesNumber=200M < ~/corpora/enwik/enwik8 > enwik8.e12
    Completed!
    Bytes written: 20900379
    
    real	14m4.401s
    user	14m1.661s
    sys	0m1.580s
    piotrek@p5q-pro:/tmp/cm$ time ~/NetBeansProjects/Demixer/dist/Release/GNU-Linux-x86/demixer decode < enwik8.e12 > enwik8.d12
    Completed!
    Bytes written: 100000000
    
    real	14m23.967s
    user	14m18.186s
    sys	0m2.068s
    piotrek@p5q-pro:/tmp/cm$ 
    
    
    piotrek@p5q-pro:/tmp/cm$ md5sum enwik8.d12 enwik8.d60 ~/corpora/enwik/enwik8
    a1fa5ffddb56f4953e226637dabbb36a  enwik8.d12
    a1fa5ffddb56f4953e226637dabbb36a  enwik8.d60
    a1fa5ffddb56f4953e226637dabbb36a  /home/piotrek/corpora/enwik/enwik8
    Attached Files Attached Files

  27. #27
    Programmer toffer's Avatar
    Join Date
    May 2008
    Location
    Erfurt, Germany
    Posts
    587
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Quote Originally Posted by Piotr Tarsa View Post
    OK, I've somehow managed to attach the C sources to the Code::Blocks project.


    I'm not yet invoking free() on memory allocated by malloc().


    PS:
    That poor result with bottom-up mixing and order-60 was caused by numeric overflow. With that bug fixed the difference between order-12 and order-60 results is rather small.


    PPS:
    Fresh results:
    Code:
    -rw-rw-r--  1 piotrek piotrek 21565901 mar  2 21:38 enwik8.e60
    -rw-rw-r--  1 piotrek piotrek 21936741 mar  2 22:08 enwik8.f60
    The smaller one is for bottom-up mixing. The bigger one is for top-down.
    Still it confirms theory. And the difference is roughly 2%, which is quite a bit for just a tiny implementation issue.

    Right now I'm running optimizer on world95.txt.

    PPPS:
    Some preliminary results with world95.txt and order-60:
    - bottom-up mixing with LPAQ1 fixed update rate - 515831 bytes,
    - results for top-down mixing and toffer's optimizer (rates scaled by 2^5, so LPAQ1's fixed update rate which is 7, after scaling would be 224):
    Code:
    INIT: Using RNG seed 1362258810.
    INIT: Parameter recording disabled.
    INIT: Randomizing 50 individuals with 90 bits each...
    DCGA: Set mutation rate to 0.060000.
    
       0  520512.0000
    DEMIXER:
    MIX_RATE =  {107, 764, 326, 181, 122, 594, 45, 687, 163}
    
    
       1  518456.0000
    DEMIXER:
    MIX_RATE =  {225, 233, 332, 535, 176, 165, 0, 797, 411}
    
    
       2  516730.0000
    DEMIXER:
    MIX_RATE =  {350, 100, 53, 538, 76, 687, 330, 119, 0}
    It takes insane amounts of iterations to produce even one line of output and I'm too tired waiting for results. Unfortunately I haven't enabled dumping optimization state to disk. But it seems that at least for current state of my CM codec bottom-up mixing is better than top-down mixing.
    You can read-off the parameter array. In your case, for a single iteration, you need to compress the input exactly 50 times (population size). The optimization speed is determined by the speed of your compressor. You can try to use RHC instead and/or set different population/neighbourhood sizes, it might give results faster. I didn't implement multithreading yet, previous experiments with M1(x2) and my old optimizer indicate that you get an almost linear speedup for up to 3 threads (on my old Q6600). I recently bought the FX8350 with 8 cores, so i suspect that this will be a big benefit.

    How did you optimize the parameters for CMM? Ie what were the test files, what was the size of them and how long did you run the optimizer? It seems that with default settings it takes thousands of iterations to complete. Single run on enwik8 now takes about 10min, so eg 5000 runs * 10 min / run = 50000 mins which is over 800 hours of optimizing.
    For CMM i used hand-tuning. Optimizing M1(x2) took roughly 200-300 iterations (DCGA) for good results with a population sizeo of 50. Thus the input is compressed roughly at most 300*50 = 15000 times.

    How many iterations it takes to produce final output? How often optimization state is dumped to disk and what it contains (eg does it contain an information whether we are in constructor or in subsequent optimization runs? does it save data after each compression invocation or only between the high level genetic algorithm iterations?)
    The optimization state is dumped every iteration. It contains all parameter sets of the N "individuals" plus the best solution found so far. Thus in your case (50+1)*90 bits saved as hex strings with some cr/lf characters. If you resume the optimizer it will proceed from the dumped state, just as if you continued optimization previously (OK, the only difference is the RNG seed/state).
    M1, CMM and other resources - http://sites.google.com/site/toffer86/ or toffer.tk

  28. #28
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,497
    Thanks
    26
    Thanked 132 Times in 102 Posts
    Still it confirms theory. And the difference is roughly 2%, which is quite a bit for just a tiny implementation issue.
    Hmm, maybe we got our wires crossed. You firstly told that top-down mixing like in CTW should be superior, but when I compare top-down mixing to bottom-up mixing in my codec, then bottom-up mixing consistently wins.

    Top-down is mixing from highest orders to lowest ones.
    Bottom-up is mixing from lowest orders to highest ones.


    As to multithreading of optimizer:
    Simple multithreading would mean running N separate instances of Demixer, so in turn that would mean keeping N identical sets of trees in memory (assuming that I don't try to optimize state tables and actually I haven't been optimizing that yet). That would be a waste of memory and computing resources. Instead it would be beneficial for me to change the cost-calculating metod so that there would be N sets of parameters passed to that function and N results returned at once.
    Trees are the main memory hogs here and ISSE tables, mixer chains etc occupy little space compared to trees, so having N instances of (ISSE tables, mixer chains, etc) wouldn't dramatically increase memory usage.
    Could you make such modification to your optimizer?

  29. #29
    Programmer toffer's Avatar
    Join Date
    May 2008
    Location
    Erfurt, Germany
    Posts
    587
    Thanks
    0
    Thanked 0 Times in 0 Posts
    OK, let me drop the names and use plain math. The mixing technique that does the following should provide better (worst-case) performance:

    mix(p_0, mix(p_1, mix( p_2, ... mix( p_m, p_(m-1) ) ... )

    where p_i is the PDF predicted by model with order i. I have to say that in the situation i've analysed there's a mixer for *every* context (i've mentioned that previously). But i suspect that there's a similar effect in your case as well.

    As to your request - this will be no problem. I'm currently extending and testing the optimizer. There're now methods to tune permutations (e.g. for aplhabet permutations) and subset as well. In addition there'll be one more parameter type: a vector within the discrete probability simplex, i.e. (x_1, ..., x_n) where x_i>=0 and x_1 + ... + x_n = X, where X is some constant.
    M1, CMM and other resources - http://sites.google.com/site/toffer86/ or toffer.tk

  30. #30
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,497
    Thanks
    26
    Thanked 132 Times in 102 Posts
    OK, let me drop the names and use plain math. The mixing technique that does the following should provide better (worst-case) performance:

    mix(p_0, mix(p_1, mix( p_2, ... mix( p_m, p_(m-1) ) ... )

    where p_i is the PDF predicted by model with order i. I have to say that in the situation i've analysed there's a mixer for *every* context (i've mentioned that previously). But i suspect that there's a similar effect in your case as well.
    I think COPY has best worst-case performance as it never expands :]

    I can always do some refinement after the main mixing though, just like LPAQ1 does order-0 and order-1 APM just before coding.

    Just to recap the bottom-up/ top-down mixing - I understand that:
    - top-down mixing is: mix(p_0, mix(p_1, mix( p_2, ... mix( p_m, p_(m-1) ) ... )
    - bottom-up mixing is: mix(...(mix(mix(p_0, p_1), p_2), p_3), ...), p_m)

    My intuition is that bottom-up mixing should do better on usual files as in bottom-up scheme a mixer does know how many orders were mixed before (it's equal to mixer's position in chain) and also that higher models predictions should have more influence than lower order models ones so they should be mixed-in last.

    As to your request - this will be no problem. I'm currently extending and testing the optimizer. There're now methods to tune permutations (e.g. for aplhabet permutations) and subset as well. In addition there'll be one more parameter type: a vector within the discrete probability simplex, i.e. (x_1, ..., x_n) where x_i>=0 and x_1 + ... + x_n = X, where X is some constant.
    Cool, I'm waiting

    PS:
    A validate function would be also helpful, ie a function that tests if the input parameters are valid. Now I can just return some very high cost for invalid parameters and the effect should be similar, but having a dedicated validating function would be more elegant.
    Last edited by Piotr Tarsa; 10th March 2013 at 19:55.

Page 1 of 2 12 LastLast

Similar Threads

  1. plzma codec
    By Shelwien in forum Data Compression
    Replies: 30
    Last Post: 19th January 2013, 03:34
  2. LZWC - A fast tree based LZW compressor
    By david_werecat in forum Data Compression
    Replies: 6
    Last Post: 16th January 2013, 02:45
  3. Suffix Tree's internal representation
    By Piotr Tarsa in forum Data Compression
    Replies: 4
    Last Post: 18th December 2011, 07:37
  4. lzma's binary tree matchfinder
    By Shelwien in forum Data Compression
    Replies: 7
    Last Post: 13th October 2011, 08:38
  5. New data structure for bitwise CM
    By Shelwien in forum Data Compression
    Replies: 5
    Last Post: 27th November 2010, 16:35

Posting Permissions

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