Results 1 to 22 of 22

Thread: TC 5.0dev4 released!

  1. #1
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,954
    Thanks
    359
    Thanked 332 Times in 131 Posts
    What's new:
    + Improved range coder. Now it is a smaller and a little bit faster.

    In addition, compared to LZPX's source code, source of TC is much clear and well structured - now I use the full power of C++ and also terminology was changed (instead of cstate - TCounter, cmodel - TCodec, etc.)

    Note: This version is fully compatible with previous one.

    Link:
    tc-5.0dev4.zip (22 KB)

  2. #2
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,954
    Thanks
    359
    Thanked 332 Times in 131 Posts
    Comparison (ENWIK9, 1,000,000,000 bytes):
    <u>
    TC 5.0dev4</u>
    comp. time: 224 sec.
    decomp. time: 206 sec.
    <u>
    TC 5.0dev2</u>
    comp. time: 270 sec.
    decomp. time: 244 sec.

    Compression ratio is the same.

    <u>PC</u>
    P4 3.0 GHz, 1 GB RAM, Windows XP SP2

  3. #3
    Guest
    Its getting faster. One day it may be faster than Thor?

  4. #4
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,954
    Thanks
    359
    Thanked 332 Times in 131 Posts
    Just a few notes. According to the benchmark at www.maximumcompression.com, this new version is a little bit slower compared to dev2. Well, it is possible, since new index table uses different mechanism and in some cases can be slower due to a cache misses (we need a fast access to 16 MB of memory). Also note, speed of TC cannot be significantly increased - since here we use arithmetic compression. In addition, current arithmetic coder (or range encoder - i.e. modern arithmetic coder) is one of the fastest arithmetic coders ever (another possible variant - carryless range encoder is a little bit faster, but with a little bit poorer compression). Another thing, TC works with a large alphabet (alpabet power of 512 symbols), and arithmetic compression is slowest on large alphabets. Anyway, it is possible, in future and if needed, to change this feature. So, I'll try to keep current speed of TC, improving the compression. IMHO, THOR is too fast, with poor compression. I think, current TC is fast enough - according to my tests, and in practice, TC compresses faster than Deflate (ZIP).

    Basic planned features:
    + Compression is about the same or higher than BZIP2
    + Speed is about the same as TC 5.0dev4
    + Takes no options or switches
    + OpenSource (GPL) and multi-platform

    Expected improvements:
    + Ring buffer (Sliding window), planned in dev5. Also this improvement can give noticeable difference on large files (MFC).
    + Better literal compression. Probably order-2/order-2-0 literal coder instead of order-1.


  5. #5
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,954
    Thanks
    359
    Thanked 332 Times in 131 Posts
    Some testing results. TC 5.0dev4 and buffer size.

    Test file: ENWIK9, 1,000,000,000 bytes

    Layout:
    <buffer size>: <compressed size>

    Results:
    512 MB: 280,851,530 bytes
    256 MB: 281,049,101 bytes
    128 MB: 281,343,404 bytes
    64 MB: 281,721,853 bytes
    32 MB: 282,289,236 bytes
    16 MB: 283,039,249 bytes [current]
    8 MB: 284,066,482 bytes
    4 MB: 285,410,098 bytes
    2 MB: 287,205,215 bytes
    1 MB: 289,585,428 bytes

    Like you see, even with super-large buffer, compression is not too much improved.

  6. #6
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,954
    Thanks
    359
    Thanked 332 Times in 131 Posts
    Another one. TC 5.0dev4 and hash size.

    Test file: ENWIK9, 1,000,000,000 bytes

    Layout:
    <hash size>: <compressed size>

    Results:
    22-bit: 282,714,293 bytes
    21-bit: 282,903,438 bytes
    20-bit: 283,039,249 bytes [current]
    19-bit: 283,950,026 bytes
    18-bit: 285,201,261 bytes
    17-bit: 292,371,911 bytes
    16-bit: 296,999,896 bytes

    I guess, hash size of 20 bits is enough.

  7. #7
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,954
    Thanks
    359
    Thanked 332 Times in 131 Posts
    For comparison, check results of TC 5.0dev4x with 21-bit hash and 64 MB buffer.

    Test file: ENWIK9, 1,000,000,000 bytes

    Layout:
    <program>: <compressed size>

    Results:
    TC 5.0dev4: 283,039,249 bytes
    TC 5.0dev4x: 281,460,640 bytes
    BZIP2 1.0.2: 253,977,839 bytes

    It's clear, to kick-out BZIP2, I must improve compression. And enlarging hash or buffer, as a ring buffer, not helps. Furthermore, my current implementation of ring buffer significantly reduce execution speed of TC, and, in fact, gives just a little compression improvement. So, I'll try to implement some kind of PPM-literal coder. Maybe create PIMPLE-like engine? Let's wait and see...


  8. #8
    Guest
    It's clear, to kick-out BZIP2, I must improve compression. And enlarging hash or buffer, as a ring buffer, not helps. Furthermore, my current implementation of ring buffer significantly reduce execution speed of TC, and, in fact, gives just a little compression improvement. So, I'll try to implement some kind of PPM-literal coder. Maybe create PIMPLE-like engine? Let's wait and see...

    I'm sure you will improve TC and it WILL "kick-out BZIP2".

  9. #9
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,954
    Thanks
    359
    Thanked 332 Times in 131 Posts
    Actually, it's really hard to keep the same speed. But I know a few variants of simple and fast PPM coders. Also note, the success of LZPXJ is due to kind-of PPM - i.e. higher order literal coder.


  10. #10
    Guest
    ppms (small ppmd) + lzp

  11. #11
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,954
    Thanks
    359
    Thanked 332 Times in 131 Posts
    Well, in my plans add just a simple and my own PPM coder (order-2). Furthermore, I have additional idea for improvement - recent match handling.


  12. #12
    Guest
    I think order-4 ppm (8 mb memory) and lzp nearby qazar or lzpxj it was better,
    As idle time lzp works with concurrence hash + minimal length, that about 4-5 bytes, and consequently
    ppm 4 orders quite stably work and yields good results

  13. #13
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,954
    Thanks
    359
    Thanked 332 Times in 131 Posts
    Yes, that's perfectly implemented in PIMPLE.

    I think order-4 PPM (PPMC/PPMD) is a complete and fully-featured PPM coder - i.e. it's not so easy to implement and adopt to our LZP-hybrid, and the most important thing - we break the main feature of TC - simplicity. Anyway, examples and/or source code of simple PPM coders are also welcomed!


  14. #14
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,954
    Thanks
    359
    Thanked 332 Times in 131 Posts
    I think, this new TC file compressor represents a new class of LZP coders. I simply compare current TC with LZPX 1.5b - In fact, TC outperforms LZPX... But TC is much smaller and simpler! (I think, it's due to my new theory and method for literals and match lengths coding)


  15. #15
    Guest
    But pimple it is more cm, than lzp. And as about good lzp parts. It is necessary to find balance between lzp and cm.Besides speed of coding at mine order-1 coders somewhere 3-5 mb on PIII133 Simply for definition Frequencies it is possible to use something like binary tree in static array.Encode, lay out separately the order-1 coder. And it is possible to look aridemo on compression.ru

  16. #16
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,954
    Thanks
    359
    Thanked 332 Times in 131 Posts
    Look at this:
    http://www.cs.fit.edu/~mmahoney/comp...text.html#6373
    Acording to this benchmark, we cannot significantly improve speed of range encoding.

    About, aridemo - I know about this sources - excellent work!

    Anyway, you can send me your variants via email. My email account: mailto:encode@narod.ru


  17. #17
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,954
    Thanks
    359
    Thanked 332 Times in 131 Posts
    Some testing results. TC 5.0dev4 with full order-2 arithmetic compression (instead of order-1).

    Test file: ENWIK9, 1,000,000,000 bytes

    Compressed size: 252,887,329 bytes


  18. #18
    Guest
    What speed on the static alphabet?

  19. #19
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,954
    Thanks
    359
    Thanked 332 Times in 131 Posts
    I didn't perform any speed-tests for this version yet. Furthermore, I always test my programs only on REAL data.

    Intersting results:

    ENWIK9 (1,000,000,000 bytes):
    TC 5.0dev4: 283,039,249 bytes
    TC 5.0dev4-blend: 295,049,882 bytes


    MPTRACK.EXE (1,159,172 bytes):
    TC 5.0dev4: 572,933 bytes
    TC 5.0dev4-blend: 550,717 bytes


    PAK0.PAK (183,997,730 bytes):
    TC 5.0dev4: 99,630,471 bytes
    TC 5.0dev4-blend: 93,076,568 bytes


    TC 5.0dev4-blend uses order-1-0 PPM with full blending. Formula: P = P-o1 + P-o0. Like you see, performance on binary files is significantly improved, but compression on text files is affected. Now I'm experimenting with different formulas and variants...


  20. #20
    Guest
    Real data can be different, and estimate speed block-adaptive coding costs! In fact it can give the big gain of speed with small loss in compression, or even a prize, here so that!

  21. #21
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,954
    Thanks
    359
    Thanked 332 Times in 131 Posts
    Well, I'll keep this idea. Also note, now I'm working on simple PPM or CM algorithm - making those things is not so easy, and making simple things, like linear search for "cumFreq", more complex is not welcomed.


  22. #22
    Guest
    Idle time, does not mean slow. Use of the fixed weights on the byte alphabet with model 4 of the order is 4*256 operations of reading, record, multiplication, or division, and addition. This huge number will give falling speed up to 100kb at the best. Here PAQ even will be faster. And with linear search and simple structures of data.... It is little bit more complex with huge speed, than with turtle so more shortly, better.
    p.s You CTW would realize (10 hours on 100kb text)

Posting Permissions

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