Skip to content

Latest commit

 

History

History
521 lines (409 loc) · 60.9 KB

SACA_Benchmarks.md

File metadata and controls

521 lines (409 loc) · 60.9 KB
Raw

Specifications

  • Processor: 2.66 GHz Intel Core 2 Duo E6750
  • L1 Cache: (32 Kb + 32 Kb) x 2
  • L2 Cache: 4 Mb
  • RAM: 2 Gb main memory
  • Operating system: Windows XP Home SP 3 (with Cygwin)
  • Compiler: GCC version 4.3.1 All programs were compiled with gcc/g++ using '-O3 -fomit-frame-pointer -DNDEBUG' optimization options. The times are the average of five runs, in seconds, and were measured using the standard Unix/Cygwin 'time' command. (user + system) The spaces were measured using the 'memusage' command.

Implementations

Archon4r0 kvark's sorting algorithm http://forum.compression.ru/viewtopic.php?t=352
BPR Bucket-Pointer Refinement algorithm http://bibiserv.techfak.uni-bielefeld.de/bpr/
DC Difference-Cover algorithm (v = 32) http://www.cs.helsinki.fi/juha.karkkainen/publications/cpm03.tar.gz
DS Deep-Shallow sorting algorithm http://www.mfn.unipmn.it/~manzini/lightweight/
divsufsort1 libdivsufsort version 1.2.3 http://libdivsufsort.googlecode.com/
divsufsort2 libdivsufsort version 2.0.0 http://libdivsufsort.googlecode.com/
KA Ko-Aluru algorithm http://ko.pang.cn.googlepages.com/software2
KS Kärkkäinen-Sanders algorithm http://www.mpi-inf.mpg.de/~sanders/programs/suffix/
MSufSort3 MSufSort version 3.1.1 beta http://www.michael-maniscalco.com/msufsort.htm
qsufsort Larsson-Sadakane algorithm http://www.larsson.dogma.net/research.html
sais Induced Sorting algorithm http://yuta.256.googlepages.com/sais

Testfiles

ACT - Test files http://compression.ca/act/act-files.html
Artificial Corpus http://corpus.canterbury.ac.nz/descriptions/#artificl
Calgary Corpus http://corpus.canterbury.ac.nz/descriptions/#calgary
Canterbury Corpus http://corpus.canterbury.ac.nz/descriptions/#cantrbry
Large Canterbury Corpus http://corpus.canterbury.ac.nz/descriptions/#large
Manzini's Large Corpus http://www.mfn.unipmn.it/~manzini/lightweight/corpus/
Maximum Compression - Test files http://www.maximumcompression.com/data/files/index.html
Miscellaneous Corpus http://corpus.canterbury.ac.nz/descriptions/#misc
Protein Corpus http://www.data-compression.info/Corpora/ProteinCorpus/
Silesia Corpus http://sun.aei.polsl.pl/~sdeor/silesia.html
Testfiles http://homepage3.nifty.com/wpage/junk/generator2.c.bz2
The Gauntlet http://www.michael-maniscalco.com/testset/gauntlet/

Running times

ACT-Executable

Files Size Archon4r0 BPR DC DS divsufsort1 divsufsort2 KA KS MSufSort3 qsufsort sais
101.EXE 438144 0.044 0.202 0.176 0.060 0.062 0.050 0.130 0.130 0.072 0.074 0.076
netscape.exe 2934336 0.176 0.542 1.102 0.246 0.232 0.236 0.836 2.230 0.322 0.660 0.460
pine.bin 1566200 0.104 0.336 0.572 0.150 0.120 0.124 0.378 0.704 0.178 0.320 0.206
totals 4938680 0.324 1.080 1.850 0.456 0.414 0.410 1.344 3.064 0.572 1.054 0.742

ACT-Graphics

Files Size Archon4r0 BPR DC DS divsufsort1 divsufsort2 KA KS MSufSort3 qsufsort sais
clegg.tif 2149096 0.506 0.436 0.852 0.456 0.202 0.210 0.674 0.900 0.264 0.656 0.242
frymire.tif 3706306 0.202 0.450 1.626 0.264 0.160 0.150 0.672 1.272 0.276 0.836 0.288
lena.tif 786568 0.062 0.252 0.296 0.080 0.064 0.064 0.244 0.242 0.100 0.106 0.116
monarch.tif 1179784 0.078 0.296 0.414 0.110 0.082 0.084 0.306 0.342 0.130 0.184 0.148
peppers.tif 786568 0.056 0.252 0.286 0.074 0.068 0.064 0.226 0.244 0.098 0.102 0.106
sail.tif 1179784 0.072 0.298 0.422 0.108 0.094 0.086 0.312 0.428 0.138 0.186 0.154
serrano.tif 1498414 0.142 0.460 0.606 0.202 0.088 0.094 0.264 0.330 0.170 0.298 0.118
tulips.tif 1179784 0.074 0.308 0.418 0.104 0.086 0.086 0.330 0.408 0.140 0.164 0.156
totals 12466304 1.192 2.752 4.920 1.398 0.844 0.838 3.028 4.166 1.316 2.532 1.328

ACT-Sound

Files Size Archon4r0 BPR DC DS divsufsort1 divsufsort2 KA KS MSufSort3 qsufsort sais
every.wav 6994092 0.630 1.870 3.630 0.738 0.794 0.760 4.480 11.492 0.984 1.614 2.708
mike.wav 1708300 0.142 0.398 0.610 0.174 0.174 0.180 0.442 0.680 0.206 0.324 0.278
totals 8702392 0.772 2.268 4.240 0.912 0.968 0.940 4.922 12.172 1.190 1.938 2.986

ACT-Text

Files Size Archon4r0 BPR DC DS divsufsort1 divsufsort2 KA KS MSufSort3 qsufsort sais
1musk10.txt 1344739 0.100 0.206 0.486 0.152 0.128 0.124 0.316 0.620 0.148 0.336 0.188
anne11.txt 586969 0.058 0.088 0.214 0.076 0.070 0.068 0.146 0.170 0.072 0.126 0.094
world95.txt 2988578 0.234 0.462 1.234 0.366 0.270 0.278 0.852 2.308 0.356 0.850 0.470
totals 4920286 0.392 0.756 1.934 0.594 0.468 0.470 1.314 3.098 0.576 1.312 0.752

Artificial Corpus

Files Size Archon4r0 BPR DC DS divsufsort1 divsufsort2 KA KS MSufSort3 qsufsort sais
a.txt 1 0.032 0.036 0.036 0.036 0.034 0.034 0.036 0.036 0.036 0.036 0.034
aaa.txt 100000 0.038 0.036 0.070 0.036 0.034 0.032 0.036 0.038 0.036 0.044 0.042
alphabet.txt 100000 0.034 0.040 0.072 0.368 0.038 0.036 0.036 0.044 0.042 0.046 0.040
random.txt 100000 0.036 0.036 0.062 0.040 0.044 0.040 0.046 0.040 0.046 0.040 0.046
totals 300001 0.140 0.148 0.240 0.480 0.150 0.142 0.154 0.158 0.160 0.166 0.162

Calgary Corpus

Files Size Archon4r0 BPR DC DS divsufsort1 divsufsort2 KA KS MSufSort3 qsufsort sais
bib 111261 0.036 0.044 0.064 0.040 0.034 0.042 0.046 0.052 0.042 0.048 0.040
book1 768771 0.070 0.108 0.280 0.096 0.084 0.078 0.172 0.234 0.092 0.160 0.110
book2 610856 0.060 0.096 0.236 0.088 0.070 0.072 0.150 0.180 0.076 0.126 0.098
geo 102400 0.034 0.162 0.066 0.038 0.038 0.042 0.048 0.044 0.042 0.042 0.040
news 377109 0.046 0.070 0.156 0.062 0.054 0.060 0.102 0.110 0.060 0.080 0.070
obj1 21504 0.034 0.148 0.040 0.036 0.036 0.034 0.036 0.036 0.042 0.038 0.038
obj2 246814 0.040 0.168 0.104 0.052 0.040 0.044 0.078 0.072 0.052 0.064 0.056
paper1 53161 0.036 0.040 0.042 0.038 0.036 0.034 0.044 0.040 0.042 0.034 0.040
paper2 82199 0.034 0.044 0.050 0.036 0.038 0.040 0.046 0.044 0.042 0.046 0.044
pic 513216 0.042 0.084 0.264 0.042 0.044 0.044 0.102 0.106 0.046 0.112 0.060
progc 39611 0.038 0.042 0.040 0.040 0.038 0.036 0.052 0.042 0.040 0.040 0.036
progl 71646 0.034 0.046 0.050 0.038 0.036 0.036 0.044 0.042 0.036 0.042 0.044
progp 49379 0.034 0.040 0.042 0.042 0.034 0.036 0.040 0.038 0.038 0.044 0.036
trans 93695 0.040 0.046 0.068 0.040 0.036 0.038 0.046 0.044 0.040 0.044 0.038
totals 3141622 0.578 1.138 1.502 0.688 0.618 0.636 1.006 1.084 0.690 0.920 0.750

Canterbury Corpus

Files Size Archon4r0 BPR DC DS divsufsort1 divsufsort2 KA KS MSufSort3 qsufsort sais
alice29.txt 152089 0.038 0.044 0.076 0.046 0.038 0.040 0.062 0.058 0.040 0.050 0.046
asyoulik.txt 125179 0.036 0.044 0.072 0.040 0.040 0.038 0.048 0.056 0.048 0.044 0.040
cp.html 24603 0.038 0.040 0.044 0.036 0.032 0.030 0.038 0.036 0.038 0.038 0.036
fields.c 11150 0.034 0.036 0.042 0.034 0.036 0.038 0.038 0.034 0.038 0.036 0.034
grammar.lsp 3721 0.038 0.036 0.034 0.034 0.036 0.032 0.036 0.036 0.040 0.036 0.034
kennedy.xls 1029744 0.076 0.244 0.320 0.188 0.070 0.078 0.186 0.192 0.142 0.170 0.096
lcet10.txt 426754 0.048 0.070 0.174 0.066 0.060 0.060 0.112 0.122 0.070 0.098 0.074
plrabn12.txt 481861 0.066 0.082 0.186 0.074 0.056 0.064 0.126 0.144 0.064 0.104 0.078
ptt5 513216 0.040 0.078 0.254 0.044 0.042 0.040 0.098 0.102 0.050 0.110 0.052
sum 38240 0.036 0.150 0.038 0.036 0.040 0.036 0.046 0.038 0.046 0.038 0.038
xargs.1 4227 0.036 0.038 0.038 0.036 0.034 0.032 0.036 0.036 0.040 0.034 0.036
totals 2810784 0.486 0.862 1.278 0.634 0.484 0.488 0.826 0.854 0.616 0.758 0.564

Large Canterbury Corpus

Files Size Archon4r0 BPR DC DS divsufsort1 divsufsort2 KA KS MSufSort3 qsufsort sais
bible.txt 4047392 0.338 0.672 1.740 0.506 0.422 0.426 1.262 3.910 0.528 1.248 0.756
E.coli 4638690 0.482 0.562 2.004 0.614 0.542 0.546 1.476 4.548 0.716 1.126 1.000
world192.txt 2473400 0.180 0.368 0.994 0.290 0.212 0.212 0.650 1.698 0.274 0.684 0.358
totals 11159482 1.000 1.602 4.738 1.410 1.176 1.184 3.388 10.156 1.518 3.058 2.114

Manzini's Corpus

Files Size Archon4r0 BPR DC DS divsufsort1 divsufsort2 KA KS MSufSort3 qsufsort sais
chr22.dna 34553758 6.030 6.196 22.694 7.514 5.404 5.362 16.980 50.006 7.132 10.642 10.796
etext99 105277340 22.160 32.582 79.872 34.264 18.758 18.064 73.236 202.684 24.106 56.612 38.748
gcc-3.0.tar 86630400 13.856 20.692 61.690 35.822 10.382 10.084 40.908 135.174 14.952 40.766 20.990
howto 39422105 5.806 8.326 25.432 8.288 5.472 5.320 20.694 64.834 5.672 16.366 11.388
jdk13c 69728899 18.106 22.252 61.234 32.182 9.260 9.010 34.172 101.096 11.314 39.792 16.396
linux-2.4.5.tar 116254720 18.174 26.226 82.830 25.912 14.672 14.290 58.586 194.412 19.890 54.054 29.614
rctail96 114711151 32.490 55.826 119.026 62.502 18.500 17.914 70.072 190.562 21.060 70.456 33.248
rfc 116421901 20.736 35.404 91.284 29.666 16.116 15.658 64.390 196.500 17.936 61.436 32.224
sprot34.dat 109617186 22.832 36.720 93.122 32.096 17.894 17.404 68.084 187.594 23.352 56.946 34.092
w3c2 104201579 27.264 29.384 89.352 54.682 13.866 13.486 52.660 162.582 17.090 77.804 25.498
totals 896819039 187.454 273.608 726.536 322.928 130.324 126.592 499.782 1485.444 162.504 484.874 252.994

Maximum Compression Testfiles

Files Size Archon4r0 BPR DC DS divsufsort1 divsufsort2 KA KS MSufSort3 qsufsort sais
A10.jpg 842468 0.068 0.322 0.328 0.076 0.076 0.072 0.220 0.408 0.104 0.110 0.146
acrord32.exe 3870784 0.232 0.650 1.508 0.324 0.292 0.288 1.156 3.036 0.400 0.864 0.606
english.dic 4067439 0.284 0.460 1.462 0.974 0.318 0.322 0.982 2.550 0.364 0.768 0.548
FlashMX.pdf 4526946 0.338 1.074 1.996 0.428 0.404 0.412 2.020 5.746 0.610 0.990 1.258
fp.log 20617071 4.472 6.766 19.104 5.284 2.540 2.504 8.912 23.010 3.176 9.108 4.370
mso97.dll 3782416 0.238 0.738 1.484 0.354 0.314 0.322 1.330 3.584 0.422 0.882 0.710
ohs.doc 4168192 0.736 0.790 2.072 1.788 0.336 0.346 1.120 2.884 0.536 1.626 0.598
rafale.bmp 4149414 0.256 0.598 1.508 0.432 0.292 0.290 0.830 1.604 0.410 0.750 0.450
vcfiu.hlp 4121418 0.326 0.648 1.696 0.554 0.304 0.298 0.984 2.606 0.422 1.152 0.534
world95.txt 2988578 0.230 0.462 1.240 0.364 0.266 0.278 0.858 2.314 0.354 0.852 0.462
totals 53134726 7.180 12.508 32.398 10.578 5.142 5.132 18.412 47.742 6.798 17.102 9.682

Miscellaneous Corpus

Files Size Archon4r0 BPR DC DS divsufsort1 divsufsort2 KA KS MSufSort3 qsufsort sais
pi.txt 1000000 0.086 0.156 0.346 0.124 0.110 0.106 0.224 0.320 0.126 0.140 0.154
totals 1000000 0.086 0.156 0.346 0.124 0.110 0.106 0.224 0.320 0.126 0.140 0.154

Protein Corpus

Files Size Archon4r0 BPR DC DS divsufsort1 divsufsort2 KA KS MSufSort3 qsufsort sais
hi 509519 0.050 0.116 0.192 0.072 0.068 0.068 0.132 0.162 0.070 0.080 0.096
hs 3295751 0.272 0.680 1.268 0.400 0.398 0.396 1.190 3.304 0.368 0.672 0.722
mj 448779 0.052 0.110 0.174 0.074 0.066 0.064 0.120 0.138 0.072 0.080 0.080
sc 2900352 0.244 0.608 1.092 0.352 0.334 0.336 1.002 2.710 0.360 0.586 0.602
totals 7154401 0.618 1.514 2.726 0.898 0.866 0.864 2.444 6.314 0.870 1.418 1.500

Silesia Corpus

Files Size Archon4r0 BPR DC DS divsufsort1 divsufsort2 KA KS MSufSort3 qsufsort sais
dickens 10192446 1.212 1.970 5.626 1.834 1.406 1.366 4.750 14.522 1.668 3.418 2.886
mozilla 51220480 4.958 10.154 30.956 7.256 5.504 5.404 25.214 76.192 6.796 18.620 13.056
mr 9970564 1.122 1.752 5.580 1.298 1.204 1.162 3.398 10.198 1.600 3.500 1.938
nci 33553445 8.234 90.800 30.330 11.494 3.768 3.746 10.038 37.842 5.464 19.098 5.454
ooffice 6152192 0.462 1.114 2.722 0.668 0.580 0.574 2.322 7.146 0.712 1.662 1.306
osdb 10085684 1.176 2.400 5.990 1.538 1.320 1.264 5.134 12.550 1.540 3.464 2.890
reymont 6627202 0.686 1.358 3.412 0.938 0.808 0.796 2.406 7.210 1.042 2.438 1.512
samba 21606400 2.466 3.586 12.050 3.376 2.094 2.042 8.106 26.348 3.424 8.298 4.324
sao 7251944 0.662 1.666 3.666 0.860 0.872 0.854 3.924 7.646 1.084 1.958 2.414
webster 41458703 6.618 15.578 30.480 9.156 6.244 6.034 22.956 67.140 6.606 16.774 12.454
x-ray 8474240 0.710 1.704 3.616 0.980 1.008 0.978 3.864 7.468 1.170 2.050 1.816
xml 5345280 0.604 0.822 2.510 0.924 0.436 0.450 1.370 4.006 0.648 1.918 0.756
totals 211938580 28.910 132.904 136.938 40.322 25.244 24.670 93.482 278.268 31.754 83.198 50.806

Testfiles

Files Size Archon4r0 BPR DC DS divsufsort1 divsufsort2 KA KS MSufSort3 qsufsort sais
test4 2097152 1.700 0.786 1.160 2.028 0.152 0.152 0.404 1.080 33.472 3.244 0.248
test5 2097152 0.932 33.542 0.988 1.308 0.190 0.194 0.304 0.712 3.274 2.856 0.196
totals 4194304 2.632 34.328 2.148 3.336 0.342 0.346 0.708 1.792 36.746 6.100 0.444

The Gauntlet

Files Size Archon4r0 BPR DC DS divsufsort1 divsufsort2 KA KS MSufSort3 qsufsort sais
abac 200000 0.044 0.064 0.104 27.914 0.042 0.036 0.058 0.048 0.050 0.062 0.044
abba 10500600 3.270 5.124 10.766 30.702 1.714 1.602 2.570 7.952 3.514 15.272 1.460
book1x20 15375420 4.392 3.530 13.872 97.468 2.312 2.154 7.442 15.756 3.542 22.376 3.912
fib_s14930352 14930352 12.728 10.830 18.524 179.040 3.638 3.588 3.544 10.232 6.700 18.224 2.542
fss10 12078908 11.390 8.974 15.130 85.328 2.828 2.824 3.344 8.646 4.618 14.754 2.076
fss9 2851443 1.002 1.210 1.644 5.256 0.410 0.416 0.618 1.290 0.554 2.836 0.336
houston 3840000 0.344 0.708 2.226 118.960 0.118 0.128 0.520 0.744 0.242 1.230 0.238
paper5x80 981924 0.110 0.154 0.454 0.806 0.092 0.090 0.210 0.256 0.144 0.448 0.110
test1 2097152 0.332 2.132 1.108 8.680 0.268 0.280 0.376 1.066 1.302 2.762 0.202
test2 2097152 0.710 0.616 1.110 8.682 0.180 0.176 0.374 1.076 3.354 2.768 0.206
test3 2097152 0.488 213.154 1.164 1.772 0.220 0.226 0.388 1.082 0.922 3.246 0.212
totals 67050103 34.810 246.496 66.102 564.608 11.822 11.520 19.444 48.148 24.942 83.978 11.338

totals

Corpus Size Archon4r0 BPR DC DS divsufsort1 divsufsort2 KA KS MSufSort3 qsufsort sais
ACT-Executable 4938680 0.324 1.080 1.850 0.456 0.414 0.410 1.344 3.064 0.572 1.054 0.742
ACT-Graphics 12466304 1.192 2.752 4.920 1.398 0.844 0.838 3.028 4.166 1.316 2.532 1.328
ACT-Sound 8702392 0.772 2.268 4.240 0.912 0.968 0.940 4.922 12.172 1.190 1.938 2.986
ACT-Text 4920286 0.392 0.756 1.934 0.594 0.468 0.470 1.314 3.098 0.576 1.312 0.752
Artificial Corpus 300001 0.140 0.148 0.240 0.480 0.150 0.142 0.154 0.158 0.160 0.166 0.162
Calgary Corpus 3141622 0.578 1.138 1.502 0.688 0.618 0.636 1.006 1.084 0.690 0.920 0.750
Canterbury Corpus 2810784 0.486 0.862 1.278 0.634 0.484 0.488 0.826 0.854 0.616 0.758 0.564
Large Canterbury Corpus 11159482 1.000 1.602 4.738 1.410 1.176 1.184 3.388 10.156 1.518 3.058 2.114
Manzini's Corpus 896819039 187.454 273.608 726.536 322.928 130.324 126.592 499.782 1485.444 162.504 484.874 252.994
Maximum Compression Testfiles 53134726 7.180 12.508 32.398 10.578 5.142 5.132 18.412 47.742 6.798 17.102 9.682
Miscellaneous Corpus 1000000 0.086 0.156 0.346 0.124 0.110 0.106 0.224 0.320 0.126 0.140 0.154
Protein Corpus 7154401 0.618 1.514 2.726 0.898 0.866 0.864 2.444 6.314 0.870 1.418 1.500
Silesia Corpus 211938580 28.910 132.904 136.938 40.322 25.244 24.670 93.482 278.268 31.754 83.198 50.806
Testfiles 4194304 2.632 34.328 2.148 3.336 0.342 0.346 0.708 1.792 36.746 6.100 0.444
The Gauntlet 67050103 34.810 246.496 66.102 564.608 11.822 11.520 19.444 48.148 24.942 83.978 11.338
totals 1289730704 266.574 712.120 987.896 949.366 178.972 174.338 650.478 1902.780 270.378 688.548 336.316

Space (in MiB)

ACT-Executable

Files Size Archon4r0 BPR DC DS divsufsort1 divsufsort2 KA KS MSufSort3 qsufsort sais
101.EXE 438144 2.71 67.76 2.46 2.12 2.34 2.34 3.75 5.43 4.80 3.34 2.09
netscape.exe 2934336 15.29 89.19 16.44 14.05 14.24 14.24 25.11 36.38 19.33 22.39 13.99
pine.bin 1566200 8.39 77.45 8.78 7.51 7.72 7.72 13.59 19.42 11.24 11.95 7.47
totals 4938680 26.39 234.40 27.68 23.68 24.30 24.30 42.45 61.23 35.37 37.68 23.55
mean - 5.60 49.77 5.88 5.03 5.16 5.16 9.01 13.00 7.51 8.00 5.00

ACT-Graphics

Files Size Archon4r0 BPR DC DS divsufsort1 divsufsort2 KA KS MSufSort3 qsufsort sais
clegg.tif 2149096 11.33 82.45 12.04 10.30 10.50 10.50 17.51 26.64 14.90 16.40 10.25
frymire.tif 3706306 19.18 55.97 20.77 17.74 17.92 17.92 31.22 45.95 23.27 28.28 17.67
lena.tif 786568 4.46 70.75 4.41 3.78 4.00 4.00 6.86 9.75 6.83 6.00 3.75
monarch.tif 1179784 6.45 71.91 6.61 5.64 5.88 5.88 9.49 14.63 9.17 9.00 5.63
peppers.tif 786568 4.46 70.01 4.41 3.76 4.00 4.00 6.75 9.75 6.91 6.00 3.75
sail.tif 1179784 6.45 70.45 6.61 5.64 5.88 5.88 9.14 14.63 9.07 9.00 5.63
serrano.tif 1498414 8.05 63.65 8.40 7.21 7.40 7.40 13.07 18.57 10.62 11.43 7.15
tulips.tif 1179784 6.45 71.91 6.61 5.64 5.88 5.88 10.04 14.63 9.25 9.00 5.63
totals 12466304 66.83 557.10 69.86 59.71 61.46 61.46 104.08 154.55 90.02 95.11 59.46
mean - 5.62 46.86 5.88 5.02 5.17 5.17 8.75 13.00 7.57 8.00 5.00

ACT-Sound

Files Size Archon4r0 BPR DC DS divsufsort1 divsufsort2 KA KS MSufSort3 qsufsort sais
every.wav 6994092 35.75 124.03 39.19 33.45 33.60 33.60 61.89 86.71 42.62 53.36 33.35
mike.wav 1708300 9.11 78.67 9.57 8.17 8.40 8.40 15.16 21.17 11.96 13.03 8.15
totals 8702392 44.86 202.70 48.76 41.62 42.00 42.00 77.05 107.88 54.58 66.39 41.50
mean - 5.41 24.42 5.88 5.01 5.06 5.06 9.28 13.00 6.58 8.00 5.00

ACT-Text

Files Size Archon4r0 BPR DC DS divsufsort1 divsufsort2 KA KS MSufSort3 qsufsort sais
1musk10.txt 1344739 7.28 14.42 7.53 6.43 6.66 6.66 11.55 16.67 9.71 10.26 6.41
anne11.txt 586969 3.46 7.47 3.29 2.81 3.05 3.05 5.05 7.28 5.37 4.48 2.80
world95.txt 2988578 15.56 29.14 16.74 14.31 14.50 14.50 26.12 37.05 19.13 22.80 14.25
totals 4920286 26.30 51.03 27.56 23.55 24.21 24.21 42.72 61.00 34.21 37.54 23.46
mean - 5.60 10.88 5.87 5.02 5.16 5.16 9.10 13.00 7.29 8.00 5.00

Artificial Corpus

Files Size Archon4r0 BPR DC DS divsufsort1 divsufsort2 KA KS MSufSort3 qsufsort sais
a.txt 1 0.50 0.00 0.00 0.00 0.00 0.00 0.00 0.00 2.00 0.00 0.00
aaa.txt 100000 1.00 0.86 0.56 0.48 0.73 0.73 0.49 1.24 2.57 0.76 0.48
alphabet.txt 100000 1.00 2.60 0.56 0.50 0.73 0.73 0.52 1.24 2.57 0.76 0.48
random.txt 100000 1.00 1.86 0.56 0.48 0.73 0.73 0.88 1.21 2.61 0.76 0.48
totals 300001 3.50 5.32 1.68 1.46 2.19 2.19 1.89 3.69 9.75 2.28 1.44
mean - 12.23 18.59 5.87 5.10 7.65 7.65 6.61 12.90 34.08 7.97 5.03

Calgary Corpus

Files Size Archon4r0 BPR DC DS divsufsort1 divsufsort2 KA KS MSufSort3 qsufsort sais
bib 111261 1.06 2.98 0.62 0.53 0.78 0.78 0.94 1.38 2.65 0.85 0.53
book1 768771 4.37 8.70 4.31 3.68 3.92 3.92 6.62 9.53 6.41 5.87 3.67
book2 610856 3.58 8.62 3.42 2.92 3.16 3.16 5.34 7.57 5.52 4.66 2.91
geo 102400 1.02 64.88 0.57 0.49 0.74 0.74 0.89 1.27 2.75 0.78 0.49
news 377109 2.40 6.83 2.11 1.83 2.05 2.05 3.29 4.68 4.19 2.88 1.80
obj1 21504 0.61 64.19 0.12 0.10 0.35 0.35 0.18 0.27 2.15 0.16 0.10
obj2 246814 1.74 66.12 1.38 1.20 1.43 1.43 2.10 3.06 3.49 1.88 1.18
paper1 53161 0.77 3.73 0.30 0.25 0.50 0.50 0.46 0.66 2.32 0.41 0.25
paper2 82199 0.91 3.58 0.46 0.39 0.64 0.64 0.72 1.02 2.48 0.63 0.39
pic 513216 3.09 19.74 2.88 2.48 2.70 2.70 3.11 6.36 4.96 3.92 2.45
progc 39611 0.70 3.31 0.22 0.19 0.44 0.44 0.33 0.49 2.24 0.30 0.19
progl 71646 0.86 3.13 0.40 0.37 0.59 0.59 0.62 0.89 2.42 0.55 0.34
progp 49379 0.75 3.12 0.28 0.26 0.49 0.49 0.40 0.61 2.29 0.38 0.24
trans 93695 0.97 4.51 0.53 0.47 0.70 0.70 0.80 1.16 2.55 0.72 0.45
totals 3141622 22.83 263.44 17.60 15.16 18.49 18.49 25.80 38.95 46.42 23.99 14.99
mean - 7.62 87.93 5.87 5.06 6.17 6.17 8.61 13.00 15.49 8.01 5.00

Canterbury Corpus

Files Size Archon4r0 BPR DC DS divsufsort1 divsufsort2 KA KS MSufSort3 qsufsort sais
alice29.txt 152089 1.27 2.85 0.85 0.73 0.98 0.98 1.31 1.89 2.88 1.16 0.73
asyoulik.txt 125179 1.13 2.28 0.70 0.60 0.85 0.85 1.08 1.55 2.73 0.96 0.60
cp.html 24603 0.62 2.64 0.14 0.12 0.37 0.37 0.21 0.31 2.15 0.19 0.12
fields.c 11150 0.56 2.88 0.06 0.05 0.30 0.30 0.09 0.14 2.07 0.09 0.05
grammar.lsp 3721 0.52 1.71 0.02 0.02 0.27 0.27 0.03 0.05 2.02 0.03 0.02
kennedy.xls 1029744 5.69 72.84 5.77 4.92 5.16 5.16 8.73 12.02 7.91 7.86 4.91
lcet10.txt 426754 2.65 5.93 2.39 2.04 2.29 2.29 3.69 5.29 4.46 3.26 2.04
plrabn12.txt 481861 2.93 6.17 2.70 2.30 2.55 2.55 4.12 5.97 4.77 3.68 2.30
ptt5 513216 3.09 19.74 2.88 2.48 2.70 2.70 3.11 6.36 4.96 3.92 2.45
sum 38240 0.69 63.58 0.21 0.21 0.43 0.43 0.30 0.47 2.25 0.29 0.18
xargs.1 4227 0.52 1.58 0.02 0.02 0.27 0.27 0.04 0.05 2.03 0.03 0.02
totals 2810784 19.67 182.20 15.74 13.49 16.17 16.17 22.71 34.10 38.23 21.47 13.42
mean - 7.34 67.97 5.87 5.03 6.03 6.03 8.47 12.72 14.26 8.01 5.01

Large Canterbury Corpus

Files Size Archon4r0 BPR DC DS divsufsort1 divsufsort2 KA KS MSufSort3 qsufsort sais
bible.txt 4047392 20.90 35.70 22.68 19.37 19.55 19.55 34.45 50.18 25.17 30.88 19.30
E.coli 4638690 23.88 39.88 25.99 22.20 22.37 22.37 40.01 57.51 28.54 35.39 22.12
world192.txt 2473400 12.97 24.40 13.86 11.85 12.05 12.05 21.24 30.66 16.18 18.87 11.80
totals 11159482 57.75 99.98 62.53 53.42 53.97 53.97 95.70 138.35 69.89 85.14 53.22
mean - 5.43 9.39 5.88 5.02 5.07 5.07 8.99 13.00 6.57 8.00 5.00

Manzini's Corpus

Files Size Archon4r0 BPR DC DS divsufsort1 divsufsort2 KA KS MSufSort3 qsufsort sais
chr22.dna 34553758 174.66 296.88 193.60 165.18 165.02 165.02 289.97 428.39 199.72 263.62 164.77
etext99 105277340 531.13 915.48 589.85 503.23 502.25 502.25 907.34 1305.20 604.45 803.20 502.00
gcc-3.0.tar 86630400 437.14 756.43 485.38 415.87 413.34 413.34 709.50 1074.01 497.79 660.94 413.09
howto 39422105 199.20 367.53 220.88 188.45 188.23 188.23 331.54 488.75 227.67 300.77 187.98
jdk13c 69728899 351.96 603.99 390.68 333.40 332.74 332.74 609.71 864.48 401.04 531.99 332.49
linux-2.4.5.tar 116254720 586.46 1061.83 651.36 555.76 554.60 554.60 977.81 1441.30 667.39 886.95 554.35
rctail96 114711151 578.68 987.64 642.71 548.32 547.24 547.24 1004.98 1422.16 658.43 875.18 546.99
rfc 116421901 587.30 1005.85 652.29 556.53 555.39 555.39 956.52 1443.37 668.26 888.23 555.14
sprot34.dat 109617186 553.01 941.95 614.17 524.03 522.95 522.95 930.06 1359.01 629.26 836.31 522.70
w3c2 104201579 525.71 958.37 583.82 498.09 497.12 497.12 912.00 1291.87 598.82 795.00 496.87
totals 896819039 4525.25 7895.95 5024.74 4288.86 4278.88 4278.88 7629.43 11118.54 5152.83 6842.19 4276.38
mean - 5.29 9.23 5.88 5.01 5.00 5.00 8.92 13.00 6.02 8.00 5.00

Maximum Compression Testfiles

Files Size Archon4r0 BPR DC DS divsufsort1 divsufsort2 KA KS MSufSort3 qsufsort sais
A10.jpg 842468 4.75 71.23 4.72 4.03 4.27 4.27 7.38 10.45 7.44 6.43 4.02
acrord32.exe 3870784 20.01 97.23 21.69 18.53 18.71 18.71 33.23 47.99 24.70 29.53 18.46
english.dic 4067439 21.00 45.69 22.79 19.44 19.65 19.65 34.14 50.43 25.28 31.03 19.40
FlashMX.pdf 4526946 23.32 102.86 25.36 21.66 21.84 21.84 39.48 56.12 28.54 34.54 21.59
fp.log 20617071 104.42 181.50 115.51 98.57 98.56 98.56 180.01 255.60 120.00 157.30 98.31
mso97.dll 3782416 19.56 96.47 21.19 18.10 18.29 18.29 32.87 46.89 24.23 28.86 18.04
ohs.doc 4168192 21.51 99.78 23.35 20.01 20.13 20.13 35.24 51.67 26.43 31.80 19.88
rafale.bmp 4149414 21.41 37.10 23.25 19.83 20.04 20.04 33.93 51.44 25.76 31.66 19.79
vcfiu.hlp 4121418 21.27 99.38 23.09 19.72 19.90 19.90 35.58 51.10 25.75 31.44 19.65
world95.txt 2988578 15.56 29.14 16.74 14.31 14.50 14.50 26.12 37.05 19.13 22.80 14.25
totals 53134726 272.81 860.38 297.69 254.20 255.89 255.89 457.98 658.74 327.26 405.39 253.39
mean - 5.38 16.98 5.87 5.02 5.05 5.05 9.04 13.00 6.46 8.00 5.00

Miscellaneous Corpus

Files Size Archon4r0 BPR DC DS divsufsort1 divsufsort2 KA KS MSufSort3 qsufsort sais
pi.txt 1000000 5.54 12.40 5.60 4.78 5.02 5.02 8.76 12.40 7.72 7.63 4.77
totals 1000000 5.54 12.40 5.60 4.78 5.02 5.02 8.76 12.40 7.72 7.63 4.77
mean - 5.81 13.00 5.87 5.01 5.26 5.26 9.19 13.00 8.10 8.00 5.00

Protein Corpus

Files Size Archon4r0 BPR DC DS divsufsort1 divsufsort2 KA KS MSufSort3 qsufsort sais
hi 509519 3.07 16.58 2.86 2.44 2.68 2.68 4.45 6.32 4.92 3.89 2.43
hs 3295751 17.11 37.74 18.47 15.78 15.97 15.97 28.84 40.86 20.86 25.15 15.72
mj 448779 2.76 16.06 2.51 2.15 2.39 2.39 3.92 5.56 4.57 3.42 2.14
sc 2900352 15.12 37.10 16.25 13.89 14.08 14.08 25.40 35.96 18.60 22.13 13.83
totals 7154401 38.06 107.48 40.09 34.26 35.12 35.12 62.61 88.70 48.95 54.59 34.12
mean - 5.58 15.75 5.88 5.02 5.15 5.15 9.18 13.00 7.17 8.00 5.00

Silesia Corpus

Files Size Archon4r0 BPR DC DS divsufsort1 divsufsort2 KA KS MSufSort3 qsufsort sais
dickens 10192446 51.87 91.30 57.11 48.74 48.85 48.85 87.43 126.36 60.34 77.76 48.60
mozilla 51220480 258.67 503.63 286.98 244.93 244.49 244.49 419.50 635.02 295.72 390.78 244.24
mr 9970564 50.75 149.58 55.86 47.68 47.79 47.79 76.38 123.61 59.08 76.07 47.54
nci 33553445 169.62 288.90 187.99 160.40 160.25 160.25 260.07 415.99 194.00 255.99 160.00
ooffice 6152192 31.51 116.81 34.47 29.43 29.59 29.59 53.16 76.27 37.80 46.94 29.34
osdb 10085684 51.34 150.57 56.51 48.21 48.34 48.34 87.76 125.01 60.34 76.95 48.09
reymont 6627202 33.90 120.88 37.13 31.68 31.85 31.85 56.39 82.16 40.15 50.56 31.60
samba 21606400 109.40 249.45 121.06 103.30 103.28 103.28 184.85 267.87 126.26 164.84 103.03
sao 7251944 37.05 126.25 40.63 34.66 34.83 34.83 63.47 88.93 44.13 55.33 34.58
webster 41458703 209.47 359.44 232.29 198.19 197.94 197.94 354.85 513.99 239.26 316.31 197.69
x-ray 8474240 43.21 136.74 47.48 40.51 40.66 40.66 75.43 105.06 50.56 64.65 40.41
xml 5345280 27.44 50.17 29.95 25.57 25.74 25.74 45.88 66.27 32.63 40.78 25.49
totals 211938580 1074.23 2343.72 1187.46 1013.30 1013.61 1013.61 1765.17 2626.54 1240.27 1616.96 1010.61
mean - 5.31 11.60 5.88 5.01 5.01 5.01 8.73 12.99 6.14 8.00 5.00

Testfiles

Files Size Archon4r0 BPR DC DS divsufsort1 divsufsort2 KA KS MSufSort3 qsufsort sais
test4 2097152 11.07 82.00 11.75 10.05 10.25 10.25 18.34 26.00 14.63 16.00 10.12
test5 2097152 11.07 82.00 11.75 10.05 10.25 10.25 16.04 26.00 14.01 16.00 10.00
totals 4194304 22.14 164.00 23.50 20.10 20.50 20.50 34.38 52.00 28.64 32.00 20.12
mean - 5.54 41.00 5.88 5.03 5.12 5.12 8.60 13.00 7.16 8.00 5.03

The Gauntlet

Files Size Archon4r0 BPR DC DS divsufsort1 divsufsort2 KA KS MSufSort3 qsufsort sais
abac 200000 1.51 1.73 1.12 0.98 1.21 1.20 1.75 2.48 3.15 1.53 0.95
abba 10500600 53.43 90.19 58.83 50.21 50.32 50.32 86.20 130.18 62.09 80.11 50.07
book1x20 15375420 78.00 134.00 86.15 73.52 73.57 73.57 132.42 190.62 89.99 117.31 73.32
fib_s14930352 14930352 75.75 128.15 83.65 71.71 71.44 71.44 117.16 185.10 87.43 113.91 71.19
fss10 12078908 61.38 103.68 67.68 58.05 57.85 57.85 107.05 149.75 71.12 92.16 57.60
fss9 2851443 14.87 24.48 15.98 13.71 13.85 13.85 25.27 35.35 18.32 21.76 13.60
houston 3840000 19.85 36.96 21.52 18.46 18.56 18.56 28.79 47.58 23.98 29.30 18.31
paper5x80 981924 5.45 11.40 5.50 4.72 4.93 4.93 8.59 12.17 7.63 7.49 4.68
test1 2097152 11.07 82.00 11.75 10.10 10.25 10.25 18.34 25.99 14.01 16.00 10.00
test2 2097152 11.07 82.00 11.75 10.10 10.25 10.25 18.34 25.99 14.01 16.00 10.00
test3 2097152 11.07 82.00 11.75 10.05 10.25 10.25 18.34 26.00 14.63 16.00 10.12
totals 67050103 343.45 776.59 375.68 321.61 322.48 322.47 562.25 831.21 406.36 511.57 319.84
mean - 5.37 12.14 5.88 5.03 5.04 5.04 8.79 13.00 6.35 8.00 5.00

totals

Corpus Size Archon4r0 BPR DC DS divsufsort1 divsufsort2 KA KS MSufSort3 qsufsort sais
ACT-Executable 4938680 26.39 234.40 27.68 23.68 24.30 24.30 42.45 61.23 35.37 37.68 23.55
ACT-Graphics 12466304 66.83 557.10 69.86 59.71 61.46 61.46 104.08 154.55 90.02 95.11 59.46
ACT-Sound 8702392 44.86 202.70 48.76 41.62 42.00 42.00 77.05 107.88 54.58 66.39 41.50
ACT-Text 4920286 26.30 51.03 27.56 23.55 24.21 24.21 42.72 61.00 34.21 37.54 23.46
Artificial Corpus 300001 3.50 5.32 1.68 1.46 2.19 2.19 1.89 3.69 9.75 2.28 1.44
Calgary Corpus 3141622 22.83 263.44 17.60 15.16 18.49 18.49 25.80 38.95 46.42 23.99 14.99
Canterbury Corpus 2810784 19.67 182.20 15.74 13.49 16.17 16.17 22.71 34.10 38.23 21.47 13.42
Large Canterbury Corpus 11159482 57.75 99.98 62.53 53.42 53.97 53.97 95.70 138.35 69.89 85.14 53.22
Manzini's Corpus 896819039 4525.25 7895.95 5024.74 4288.86 4278.88 4278.88 7629.43 11118.54 5152.83 6842.19 4276.38
Maximum Compression Testfiles 53134726 272.81 860.38 297.69 254.20 255.89 255.89 457.98 658.74 327.26 405.39 253.39
Miscellaneous Corpus 1000000 5.54 12.40 5.60 4.78 5.02 5.02 8.76 12.40 7.72 7.63 4.77
Protein Corpus 7154401 38.06 107.48 40.09 34.26 35.12 35.12 62.61 88.70 48.95 54.59 34.12
Silesia Corpus 211938580 1074.23 2343.72 1187.46 1013.30 1013.61 1013.61 1765.17 2626.54 1240.27 1616.96 1010.61
Testfiles 4194304 22.14 164.00 23.50 20.10 20.50 20.50 34.38 52.00 28.64 32.00 20.12
The Gauntlet 67050103 343.45 776.59 375.68 321.61 322.48 322.47 562.25 831.21 406.36 511.57 319.84
totals 1289730704 6549.61 13756.69 7226.17 6169.20 6174.29 6174.28 10932.98 15987.88 7590.50 9839.93 6150.27
mean - 5.32 11.18 5.88 5.02 5.02 5.02 8.89 13.00 6.17 8.00 5.00