RINGS Fast Bit Compressor.
10 views
Skip to first unread message
Nania Francesco Antonio
Apr 14, 2008, 5:19:00 PM4/14/08
to encode_ru_f...@googlegroups.com
RINGS 1.4c released
- Added 9 commands Min=2 MB - Max=512MB
- ULTRA COMPRESSION!
Warning: Only for testing
Copyright Ž 2007 by Nania Francesco Antonio (Italy).
All rights reserved.
link:
http://www.winturtle.netsons.org/rings.zip
LovePimple
Apr 14, 2008, 5:34:00 PM4/14/08
to encode_ru_f...@googlegroups.com
LovePimple
Apr 15, 2008, 7:00:00 AM4/15/08
to encode_ru_f...@googlegroups.com
Quick test...
RINGS c 1
A10.jpg > 819,150
AcroRd32.exe > 1,564,493
english.dic > 599,707
FlashMX.pdf > 3,777,642
FP.LOG > 799,840
MSO97.DLL > 1,991,174
ohs.doc > 926,673
rafale.bmp > 839,574
vcfiu.hlp > 733,449
world95.txt > 716,408
Total = 12,768,110 bytes
RINGS c 4
A10.jpg > 819,150
AcroRd32.exe > 1,493,652
english.dic > 566,326
FlashMX.pdf > 3,751,205
FP.LOG > 613,832
MSO97.DLL > 1,872,766
ohs.doc > 884,912
rafale.bmp > 799,867
vcfiu.hlp > 716,177
world95.txt > 626,438
Total = 12,144,325 bytes
RINGS c 9
A10.jpg > 819,150
AcroRd32.exe > 1,493,652
english.dic > 566,326
FlashMX.pdf > 3,752,097
FP.LOG > 554,280
MSO97.DLL > 1,872,766
ohs.doc > 884,912
rafale.bmp > 799,867
vcfiu.hlp > 716,177
world95.txt > 626,438
Total = 12,085,665 bytes
LovePimple
Apr 15, 2008, 7:17:00 AM4/15/08
to encode_ru_f...@googlegroups.com
Another quick test...
RINGS c 1
ENWIK8 > 29,038,653 bytes
RINGS c 4
ENWIK8 > 26,442,044 bytes
RINGS c 9
ENWIK8 > 24,591,826 bytes
Nania Francesco Antonio
Apr 15, 2008, 10:53:00 AM4/15/08
to encode_ru_f...@googlegroups.com
Thanks of all tests LovePimple ! Hi !:)
toffer
Apr 15, 2008, 11:41:00 AM4/15/08
to encode_ru_f...@googlegroups.com
The speed with this ratio is really imperssive! I still wonder how you got this context mixer so fast.
Keep improving this! Good work!
nimdamsk
Apr 16, 2008, 7:50:00 AM4/16/08
to encode_ru_f...@googlegroups.com
-1 > 2 MB > BWT+MTF+PRE-HUF+ARI
-2 > 4 MB > ???
-3 > 8 MB > BWT+MTF+PRE-HUF+ARI
-4 > 16 MB > ???
-5 > 32 MB > FCM+LZP+FILTERS
-6 > 64 MB > ???
-7 > 128 MB > ???
-8 > 256 MB > ???
-9 > 512 MB > ???
Are memory requirements right? What algoritms are used instead of ???
Nania Francesco Antonio
Apr 16, 2008, 1:13:00 PM4/16/08
to encode_ru_f...@googlegroups.com
For all profiles
-1
.
.
-9
simply BWT ->MTF -> PRE-HUF -> ARI
Example:
0123012301230123 etc.
BWT -> 0000111122223333 etc.
MTF -> 0000100020003000 etc.
PRE-HUF -> 0=bit 0 1=bits 100 2=101 3=1100 etc.
ARI -> COMPRESSED
toffer
Apr 16, 2008, 1:55:00 PM4/16/08
to encode_ru_f...@googlegroups.com
What about your "fast context mixing" algorithm? Did you always use BWT?
BTW: The dynamic mapping of codes via huffman is a nice idea, which speeds up compression, exspecially after BTW+MTF (low order 0 entropy) and improves it. I had a very beneficial effect after applying just a simpler static mapping of the flat 8 bit codes to 4, 8, 12 bit codes (instead of dynamically built huffman codes).
donkey7
Apr 16, 2008, 3:35:00 PM4/16/08
to encode_ru_f...@googlegroups.com
is it full bwt or schindler transform? grzip uses st4 (shindler transform of order- 4) in its fast modes. do you use pre- bwt stages?
Nania Francesco Antonio
Apr 16, 2008, 4:36:00 PM4/16/08
to encode_ru_f...@googlegroups.com
Old Rings 0.1-0.3 use:
14 MB of buffer -> ARI (Simple FCM + bits mixer ) [2 MB]
Rings 1.0 - 1.4c use:
Fast BWT->MTF->PRE-HUF->ARI
(NEW FCM CORE OPTIMIZED FOR COMPRESSION OF BWT) + ARI [2MB](Simple FCM + bits mixer ) for GIF,JPG,COMPRESSED FILES
donkey7
Apr 17, 2008, 12:17:00 PM4/17/08
to encode_ru_f...@googlegroups.com
what's "fast bwt"? how it differs from "slow" bwt?
Bulat Ziganshin
Apr 17, 2008, 1:27:00 PM4/17/08
to encode_ru_f...@googlegroups.com
i bet that he uses dark sorting engine which is very good
donkey7
Apr 18, 2008, 5:30:00 AM4/18/08
to encode_ru_f...@googlegroups.com
but it can't be that fast. i bet he uses shindler transform. it's super fast - it's a limited order bwt. with limit = 4 (it's called st4 then) you can do the transform using one std::sort call on normal 32 bit uints (not strings).
also bwt with such memory requirements would provide much better compression.
divsufsort is even faster than dark afaik.
Bulat Ziganshin
Apr 18, 2008, 6:02:00 AM4/18/08
to encode_ru_f...@googlegroups.com
btw, in russian compression forum grzip author described idea of extra-fast bwt compression: http://forum.compression.ru/viewtopic.php?t=1948
Black_Fox
Apr 18, 2008, 7:28:00 AM4/18/08
to encode_ru_f...@googlegroups.com
donkey7
Apr 18, 2008, 9:50:00 AM4/18/08
to encode_ru_f...@googlegroups.com
bulat:
that's non deterministic algorithm. the output is usually not valid due to hash collisions. therefore it's not used in practice.
black_fox:
i know about it. afair divsufsort is currently faster than msufsort.
on my system szip -o4 has almost identical speed as rings and szip also uses bwt (of limited order - it's called shindler transform).
rings is more modern so it has better compression (of about 2 - 3 % with same block size).
on 64- bit computers it would be possible to do szip -o8 or -o7 with same speed. it would then have better compression.
Bulat Ziganshin
Apr 18, 2008, 10:10:00 AM4/18/08
to encode_ru_f...@googlegroups.com
donkey7, we know that's ST :)
donkey7
Apr 18, 2008, 2:25:00 PM4/18/08
to encode_ru_f...@googlegroups.com
so why are you pointing to full bwt solutions? st works best with simple one- pass quicksort.
Bulat Ziganshin
Apr 18, 2008, 3:35:00 PM4/18/08
to encode_ru_f...@googlegroups.com
because Nania said about bwt. and i'm not sure that simple sorting may be used for fast ST4 algorithms. afaik, grzip use itw own algorithm
donkey7
Apr 18, 2008, 6:47:00 PM4/18/08
to encode_ru_f...@googlegroups.com
well, i'm partially mistaken. i thought that st4 doesn't need stable sorting algo. but there is a workaround - make uint64 by:
[4 bytes of context] << 32 + [3 bytes of index] << 8 + [1 byte of last column - st4 output]
and then apply simple sort on uint64s.
Bulat Ziganshin
Apr 18, 2008, 6:49:00 PM4/18/08
to encode_ru_f...@googlegroups.com
the problem is that some sorting procedure specialized for ST4 may run faster and definitely will use less amount of memory
Nania Francesco Antonio
Apr 21, 2008, 7:01:00 PM4/21/08
to encode_ru_f...@googlegroups.com
RINGS 1.5 released
- UNREAL COMPRESSION!
LovePimple
Apr 21, 2008, 7:54:00 PM4/21/08
to encode_ru_f...@googlegroups.com
LovePimple
Apr 21, 2008, 10:19:00 PM4/21/08
to encode_ru_f...@googlegroups.com
Quick test...
RINGS c 9
A10.jpg > 819,150
AcroRd32.exe > 1,493,652
english.dic > 566,326
FlashMX.pdf > 3,752,097
MSO97.DLL > 1,872,766
ohs.doc > 884,912
rafale.bmp > 799,867
vcfiu.hlp > 716,177
Total = 11,918,957 bytes
ENWIK8 > 21,848,093 bytes
Compression speed is still quick!
Christian
Apr 22, 2008, 5:09:00 AM4/22/08
to encode_ru_f...@googlegroups.com
Very good results Francesco! Now, text compression is really great - thanks to its BWT nature I think.
Can you confirm that your "fast BWT" is using limited key lengths? Have you extended the length limit with each version?
;)
Nania Francesco Antonio
Apr 22, 2008, 10:23:00 AM4/22/08
to encode_ru_f...@googlegroups.com
Christian
Yes ! but for I apply only now it to some types of file (txt,log,bin) but an a little slower has become!
Nania Francesco Antonio
Apr 22, 2008, 3:05:00 PM4/22/08
to encode_ru_f...@googlegroups.com
RINGS 1.5b released
- More stable !
- Corrected more bugs!
Warning: Only for testing
Copyright ® 2007 by Nania Francesco Antonio (Italy).
Christian
Apr 22, 2008, 4:38:00 PM4/22/08
to encode_ru_f...@googlegroups.com
Quoting: Nania Francesco Antonio
Corrected more bugs!I tested it on a couple of files. What was wrong?
Nania Francesco Antonio
Apr 22, 2008, 5:24:00 PM4/22/08
to encode_ru_f...@googlegroups.com
the prototype of fast bwt coder that use on file of few byte goes to crash!
Nania Francesco Antonio
Apr 22, 2008, 6:19:00 PM4/22/08
to encode_ru_f...@googlegroups.com
LovePimple
Apr 22, 2008, 6:57:00 PM4/22/08
to encode_ru_f...@googlegroups.com
Reply all
Reply to author
Forward
0 new messages