home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / compress / 3177 < prev    next >
Encoding:
Internet Message Format  |  1992-09-03  |  14.0 KB
  1. Path: sparky!uunet!gatech!destroyer!sol.ctr.columbia.edu!eff!snorkelwacker.mit.edu!bloom-beacon!eru.mt.luth.se!lunic!sunic!news.funet.fi!funic!nntp.hut.fi!nntp!eye
  2. From: eye@lesti.hut.fi (Petri M Kuittinen)
  3. Newsgroups: comp.compression
  4. Subject: Re: Best compression technique & ratio for (ascii) text
  5. Message-ID: <EYE.92Sep3163746@lesti.hut.fi>
  6. Date: 3 Sep 92 14:37:46 GMT
  7. References: <BtztDo.3oB@casper.cs.uct.ac.za>
  8. Sender: usenet@nntp.hut.fi (Usenet pseudouser id)
  9. Organization: Helsinki University of Technology, Finland
  10. Lines: 345
  11. In-Reply-To: roland@sun-2.cs.uct.ac.za's message of Thu, 3 Sep 1992 08:10:35 GMT
  12. Nntp-Posting-Host: lesti.hut.fi
  13.  
  14. In article <BtztDo.3oB@casper.cs.uct.ac.za> roland@sun-2.cs.uct.ac.za (Roland Paterson-Jones) writes:
  15.  
  16.    Sorry if this is a FAQ, but I am interested in knowing what compression ratios
  17.    are possible for English text in ascii. Unix's compress (adaptive Lev-Zimpil)
  18.    claims 50-60% for such files. Is this as good as can be done? Quick
  19.    decompression would be essential.
  20.  
  21.    Thanks for any responses...
  22.  
  23.  
  24.     Hmm, I recently made myself a UNIX-compress alike program which uses
  25. my own compression algorithm (yet another LZSS-variant). It is slightly better
  26. than UNIX compress at compression, about 3x slower at compression and
  27. very fast at decompression (about 2x faster).
  28.  
  29. ---------------------Here are few test results------------------------------
  30.  
  31.                    Compression test results
  32.  
  33.         In the above charts I have compared Bcpack-3 with other widely
  34. used compressor and archiver programs for UNIX-systems. The test files
  35. are from "Calcary Text Compression Corpus", files paper3-6 are excluded
  36. from the comparison. (It's common to leave them out in data compression
  37. comparisons). These files ca be obtained via anonymous ftp from:
  38. fsa.cpsc.ucalgary.ca:/pub/text.compression.corpus.tar.Z
  39.  
  40.         Most of the files are text files, few of them are binary files
  41. (geo,obj1,obj2) and one is a picture file (pic). Most of the files are
  42. relatively large, so this comparison favours compressors which are good
  43. at compressing large text files.
  44.     
  45.         All the comparisons are done on a Sony NEWS NWS-1510
  46. work station (CPU Motorola 68030, 25 MHz). All the times in the
  47. charts are CPU-times not real times, which are slightly bigger.
  48. The file lengths also include file headers in the compressor files
  49. (Compress, Bcpack3). The total length of the archive is about 0.1%
  50. larger than the one reported here.
  51.  
  52. program   size      arc       bcpack3   compress  lha   
  53. version             5.00      3.00      4.0       1.00
  54. options                       -om       
  55.  
  56. bib       111261    53537     43132     46528     40740
  57. book1     768771    390356    389156    332056    339074
  58. book2     610856    326083    254142    250759    228442
  59. geo       102400    73884     74792     77777     68574
  60. news      377109    227938    167678    182121    155084
  61. obj1      21504     14269     10754     14048     10310
  62. obj2      246814    141583    89032     128659    84981
  63. paper1    53161     28936     21516     25077     19676
  64. paper2    82199     41318     36114     36161     32096
  65. pic       513216    67658     85164     62215     52221
  66. progc     39611     22810     14936     19143     13941
  67. progl     71646     30851     18658     27148     16914
  68. progp     49379     23117     12642     19209     11507
  69. trans     93695     50234     22728     38240     22578
  70. ------------------------------------------------------------------
  71. total     3141622   1492574   1240444   1259141   1096138    
  72. time      -         234,6     460,0     67,4      731,8
  73.           -         155,2     15,5      36,7      71,8
  74.  
  75.  
  76. program   size      lharc     zip       zoo   
  77. version             1.02      1.0       2.1
  78. options                       -9        -ah       
  79.  
  80. bib       111261    46502     40717     40742
  81. book1     768771    369479    339932    339076              
  82. book2     610856    252540    229419    228444
  83. geo       102400    70955     69837     68576
  84. news      377109    166048    154865    155086
  85. obj1      21504     10748     10522     10312
  86. obj2      246814    90848     86661     84983
  87. paper1    53161     21748     19761     19678
  88. paper2    82199     32275     32296     32098
  89. pic       513216    61394     56828     52221
  90. progc     39611     15399     13995     13943
  91. progl     71646     18760     16954     16916
  92. progp     49379     12792     11558     11509
  93. trans     93695     28092     22737     22580
  94. ------------------------------------------------------------------
  95. total     3141622   1200580   1106013   1096166    
  96. time      -         496,03    254,0     503,0
  97.           -         85,56     75,7      43,9
  98.          
  99. Compression result
  100. 1. lha *            34,9%
  101. 2. zoo *            34,9%
  102. 3. zip              35,2%
  103. 4. lharc            38,2%
  104. 5. bcpack           39,5%           
  105. 6. compress         40,1%
  106. 7. arc              47,5%
  107.  
  108. * A file compressed with zoo is always 2 bytes longer than a one
  109. compressed with lha. The both programs use the same compression
  110. algorithm (AR002), but the implementation and the file structure
  111. differs. That explains the slight speed and size differences.
  112.  
  113. Compression speed
  114. 1. compress     45,5 kb/s          
  115. 2. arc          13,1 kb/s                     
  116. 3. zip          12,1 kb/s
  117. 4. bcpack3      6,7 kb/s
  118. 5. lharc        6,1 kb/s
  119. 6. zoo          6,1 kb/s
  120. 7. lha          4,2 kb/s
  121.  
  122. Decompression speed
  123. 1. bcpack3      197,9 kb/s     
  124. 2. compress     83,6 kb/s
  125. 3. zoo          69,9 kb/s
  126. 4. lha          42,7 kb/s
  127. 5. zip          40,5 kb/s 
  128. 6. lharc        35,9 kb/s
  129. 7. arc          19,8 Kb/s                  
  130.  
  131. File compression speeds per file don't appear in the charts. The other
  132. compressors spent nearly the average compression time per file, but
  133. Bcpack3 used most of its time to compress pic-file. (CPU-time elapsed
  134. 251,92 s). The search method used in Bcpack3 probably failed miserably
  135. with this file. The average compression speed of Bcpack3 is 12,3 kb/s
  136. if file pic is left out from the calculations.
  137.  
  138.         In the below is another comparison done with small file found
  139. from: nic.funet.fi:pub/msdos/utilities/txtutlo/
  140.  
  141. program         size    arc     bcpack3 compresslha   
  142. version                 5.00    3.00    4.0     1.00
  143. options                         -om       
  144.  
  145. readme          1704    1118    1110    1120    923     
  146. shell.com       12616   11880   9820    11970   9278
  147. shell.pas       3101    1358    1080    1392    928
  148. sort.c          5909    1800    1246    1838    1108
  149. sort.exe        9807    8117    6538    8130    6224
  150. sortdemo.doc    2944    1763    1678    1774    1447
  151. sortf.com       3235    2774    2438    2794    2321
  152. sortf.doc       12753   5378    4668    5420    4170
  153. sortf.obj       4056    3789    3244    3799    3153
  154. ------------------------------------------------------------------
  155. total           56125   37977   31882   38237   29552
  156. time    -       5,52    4,38    2,22    10,86
  157.                 -       3,50    0,92    1,75    2,59
  158.         
  159. program         size    lharc   zip     zoo   
  160. version                 1.02    1.0     2.1
  161. options                         -9      -ah       
  162.  
  163. readme          1704    1007    993     925     
  164. shell.com       12616   9426    9595    9280
  165. shell.pas       3101    997     1023    930
  166. sort.c          5909    1141    1188    1109
  167. sort.exe        9807    6389    6420    6226
  168. sortdemo.doc    2944    1533    1544    1449
  169. sortf.com       3235    2330    2385    2323
  170. sortf.doc       12753   4555    4235    4172
  171. sortf.obj       4056    3153    3244    3155
  172. ------------------------------------------------------------------
  173. total           56125   30531   30627   29569
  174. time            -       9,02    6,55    6,91
  175.                 -       3,53    2,09    1,36
  176.  
  177. compression result
  178. 1. lha          52,7% 
  179. 2. zoo          52,7%
  180. 3. lharc        54,4%
  181. 4. zip          54,6%
  182. 5. bcpack3      56,8%
  183. 6. arc          67,7%
  184. 7. compress     68,1%
  185.  
  186. compression speed:
  187. 1. compress     24,7 kb/s
  188. 2. bcpack       12,5 kb/s
  189. 3. arc          9,9 kb/s
  190. 4. zip          8,4 kb/s
  191. 5. zoo          7,9 kb/s
  192. 6. lharc        6,1 kb/s
  193. 7. lha          5,0 kb/s
  194.  
  195. decompression speed:
  196. 1. bcpack       59,6 kb/s
  197. 2. zoo          40,3 kb/s
  198. 3. compress     31,3 kb/s
  199. 4. zip          26,2 kb/s
  200. 5. lha          21,2 kb/s
  201. 6. arc          15,7 kb/s
  202. 7. lharc        15,5 kb/s
  203.  
  204.         Test done on the small files favour the archiver prg:s even more
  205. The archives are about 2-3% bigger than the total length shown here.
  206. In addition the archiver prg:s are now proportionally faster at
  207. uncompression than compressors, because archiver programs need only
  208. to read one bigger file instead of reading many small ones as the
  209. compression prg:s must do.
  210.  
  211.                 Variable parameters effects in Bcpack3
  212.  
  213.         There are two variable parameters in Bcpack3, which affect
  214. the compression. The first one is offset range (you can set it by
  215. option -oN, where N is offset range. If N=m then maximum offset
  216. range is used). Offset range tells the ring buffer size. Here is
  217. a table which shows it's effect on a finnish text file.
  218.  
  219. decom2.txt, original length 97044 bytes
  220.  
  221. offset    size      compression  decompression
  222.           (bytes)   time (s)     time (s)
  223. 300       68356     3,6            0,8
  224. 1000      60698     4,2            0,7     
  225. 3000      56046     5,1            0,7
  226. 5000      54102     5,7            0,6
  227. 7000      53096     6,3            0,6
  228. 9000      52552     6,8            0,6
  229. 11000     51954     7,3            0,6
  230. 13000     51512     7,8            0,7
  231. 15000     50780     8,6            0,6
  232. 17000     50694     9,0            0,6
  233. 19000     50604     9,4            0,6
  234. 21000     50008     10,2           0,6
  235.  
  236.         As you can see from the table, compression results get better
  237. with bigger offset. Compression time is also gets bigger with bigger
  238. offset sizes. Decompression time is slightly smaller with files which
  239. are compressed using bigger offset.
  240.  
  241.         Bcpack3 features are also another variable parameter. It is
  242. called relative-mode (Option '-r'). With relative mode on the program
  243. first delta codes the files before compression. Delta coding means
  244. transforming the data, to a form in which each byte is a signed value
  245. which tells the difference to previous byte.
  246.  
  247. program size    bcpack3 bcpack3     
  248. version         3.00    3.00
  249. options         -om     -rom       
  250.  
  251. bib     111261  43132   48924
  252. book1   768771  389156  440106
  253. book2   610856  254142  286102
  254. geo     102400  74792   95064
  255. news    377109  167678  195392
  256. obj1    21504   10754   12674
  257. obj2    246814  89032   107898
  258. paper1  53161   21516   24738
  259. paper2  82199   36114   39956
  260. pic     513216  85164   96180
  261. progc   39611   14936   17678
  262. progl   71646   18658   21678
  263. progp   49379   12642   15220
  264. trans   93695   22728   26842
  265. -------------------------------------
  266. total   3141622 1240444 1428452    
  267. time            460,0   425,8
  268.                 15,5    18,0
  269.  
  270.         From the above chart you might make a conclusion that relative
  271. mode is non-useful. It's not meant for compressing ordinary files.
  272. It's meant for compressing files, which mostly consist of continuous
  273. periodical data. Eg. sound files are such files. On the below
  274. Here are few test results done on few sound/music files found from
  275. nic.funet.fi:pub/amiga/audio.
  276.  
  277. program         size    arc     bcpack3 bcpack3 compress        
  278. version                 5.00    3.00    3.00    4.00
  279. options                         -om     -rom
  280.  
  281. beethoven.snd   96360   59296   53612   56088   53608
  282. explosion2.snd  24312   19728   19218   15392   19166
  283. illbeback.snd   11716   11239   10792   9590    11716 * 
  284. mod.BeyondMusic 402166  338422  332032  305242  343905
  285. mod.spectral_in 109152  87824   77662   74508   91001
  286. --------------------------------------------------------
  287. total           643706  516509  493316  460820  519396
  288. time            -       92,81   71,77   120,53  28,14
  289.                 -       38,61   5,84    6,05    12,73
  290.  
  291. program         size    lha     lharc   zip     zoo     
  292. version                 1.00    1.02    1.0     2.1
  293. options                         -9      -ah
  294.  
  295. beethoven.snd   96360   48820   51246   50392   48822
  296. explosion2.snd  24312   17489   18096   18265   17491
  297. illbeback.snd   11716   9977    10086   10466   9979    
  298. mod.BeyondMusic 402166  307261  314144  321918  307263
  299. mod.spectral_in 109152  72578   77012   75820   72580
  300. --------------------------------------------------------
  301. total           643706  456125  470548  476861  456135
  302. time            -       164,22  101,64  77,06   106,97
  303.                 -       25,78   39,16   25,58   14,66
  304.  
  305. compression result:
  306. 1. lha          70,9%
  307. 2. zoo          70,9%
  308. 3. bcpack3 -r   71,6%
  309. 4. lharc        73,1%
  310. 5. zip          74,1%
  311. 6. bcpack3      76,6%
  312. 7. arc          80,2%
  313. 8. compress     80,7% *
  314.  
  315. * compress wasn't able to compress file illbeback.snd at all.
  316.  
  317. compression speed:
  318. 1. compress     22,3 kb/s
  319. 2. bcpack3      8,8 kb/s
  320. 3. zip          8,2 kb/s
  321. 4. arc          6,8 kb/s
  322. 5. lharc        6,2 kb/s
  323. 6. zoo          5,9 kb/s        
  324. 7. bcpack -r    5,2 kb/s
  325. 8. lha          3,8 kb/s
  326.  
  327. decompression speed:
  328. 1. bcpack3      107,6 kb/s
  329. 2. bcpack3 -r   103,9 kb/s
  330. 3. compress     49,4 kb/s
  331. 4. zoo          42,9 kb/s 
  332. 5. zip          24,6 kb/s
  333. 6. lha          24,4 kb/s
  334. 7. lharc        16,1 kb/s
  335. 8. arc          16,3 kb/s               
  336.  
  337.         As you see delta-coding improves compression results by
  338. average of 5%, increases compression time and doesn't affect much the
  339. decompression speed. It's usually useful to use relative mode on
  340. files which consist mostly of 8-bit sound data.
  341. ---------------------------end of results stuff------------------------------
  342.     
  343.     The text compression results above could have been improved by about
  344. 5% if there would be a special ASCII mode, which would code bytes to just
  345. 7 bits.
  346.     The Bcpack3 program, C-source code & the algorithm are copyrighted
  347. at this moment, but if enough interest comes from the field, I will publish
  348. them and make them Public Domain (PD). If nobody is interested about my
  349. program, I won't continue improving it.
  350.  
  351.         Petri -The Eye- Kuittinen
  352.  
  353.  
  354. --
  355. | The Eye of Brainwash Company    |    LEA    POINT(PC),A3    ;Don't try  |
  356. | E-mail:eye@niksula.hut.fi    |     ADD.L     #$465707B7,(A3)    ;this M68000|
  357. | S-mail:Timpurinkuja 1 C 39    |     LEA    $8000,A4    ;assembler  |
  358. |     02600 Espoo, Finland    |POINT:    ORI.W    #$5945,D5    ;program!!  |
  359.