home *** CD-ROM | disk | FTP | other *** search
/ PC Welt 1996 Counselor / COMPUSERVE.ISO / mailbox / packer / acb123b / techniq.txt < prev   
Encoding:
Text File  |  1996-05-12  |  18.3 KB  |  395 lines
  1.             ACB, DMC, PPM, LZ - CLASSIFICATION, IDEA, COMPARISON
  2.  
  3.                                                          George Buyanovsky
  4.  
  5.                    1.  Introduction
  6.  
  7.  This article provides a brief overview of the existing technologies for
  8. compression of information and describes the place taken by ACB compression.
  9. The overview discusses only the technologies for building compression
  10. models: LZ, PPM, DMC, ACB; coding is not discussed.
  11.  
  12. LZ has two basic modifications, LZ77 and LZ78 along with a large number of
  13.    variations. At present LZ models are widely used (zip,rar,arj,lzh,lzw...).
  14.    The theoretical approach for LZ models was suggested in 1977 by
  15.    Lempel A. Ziv J. (LZ), with software realization in the early eighties.
  16.  
  17. PPM, or context modelling, is based on theoretical work conducted from 1986-95
  18.     (T.C.Bell, J.G.Cleary, I.H.Witten, W.J.Teahan, A.Moffat ....).
  19.     Software realization came about in the early nineties (HA, X1, ....).
  20.  
  21. DMC - Several DMC, or Dynamic Markov Coding, are known, in particular,
  22.       Ross Williams'DHPC algorithm, as well as the DMC algorithm of
  23.       Cormack & Horspool, which uses many heuristics methods (as well as PPM).
  24.       I am not aware of industrial archivators using the DMC-technology.
  25.  
  26.  
  27.                    2.  LZ, PPM, ACB<-->DMC
  28.  
  29.  
  30.   When two persons speak with one another, they have to formulate their
  31. ideas in detail at the beginning of their conversation, but the longer
  32. their conversation lasts, less detail is required. Why does this happen?
  33. Many ideas have been expressed and are understood by conversants without
  34. detail.
  35.  
  36.                    2.1  LZ-compression
  37.  
  38. LZ-compression substitutes the initial text with references to a dictionary;
  39. it seems that this scheme resembles the methodology used by two interlocutors.
  40.  
  41. However, with the growth of the dictionary, the number of bits
  42. necessary for formulating the reference grows proportionally by a binary
  43. logarithm to the size of the dictionary. The length of the phrases
  44. in the dictionary (in the simplest case, a binary tree) at the beginning
  45. considerably surpasses the growth of the length of the references, but after
  46. some saturation, the speed of their growth asymptotically tends to
  47. logarithmic dependence.
  48. The optimal size of the dictionary varies for different types of data;
  49. the more variable are the data, the smaller the optimal size of the
  50. dictionary.
  51.  
  52.                    2.2 PPM - algorithms (context modelling)
  53.  
  54. The idea of context modeling is based on the fact that distribution of
  55. possibilities in the alphabet depends on the nearest context, in other
  56. words, letters are more likely to appear in a particular pattern, that
  57. is, next to or near other particular letters. For this technology, there
  58. also exist principal restrictions for the increase of a sliding frame,
  59. or a moving processor of data or letters, for which a context model is
  60. built. A small sliding frame with a corresponding meagre context model
  61. is optimal on variable data, for which the problem of zero frequency is
  62. especially acute. In the course of increasing the size of a sliding frame,
  63. more and more various information is processed (e.g., a text in French,
  64. then a text in German and then a text in Russian enters this frame),
  65. with the result that the distribution of possibilities widens and the
  66. effectiveness of context modelling (with short context) decreases quickly.
  67. With the increase of the context length, costs also increase exponentially.
  68. The transition to context-mixed models has improved the situation to some
  69. extent; however, the absence of theoretically substantiated schemes of
  70. intermingling probabilities is compensated by a large number of heuristics,
  71. which takes us back to the times of alchemy.
  72.  
  73.                    2.3  ACB-compression
  74.  
  75. However, the brain of interlocutors in a mysterious fashion can overcome
  76. this barrier and can use all accumulated information through a mechanism
  77. called associative memory.
  78.  
  79. The general principle of ACB-compression is very simple: the ACB-algorithm
  80. puts on glasses with an associative filter and looking at the past, it sees
  81. not the whole frame but rather only fragments, which are close by context
  82. to the nearest context. Fragments or phrases of the received picture differ
  83. much by quality; phrases close by context are distinct in their relation to
  84. other phrases, less close phrases are less distinct or are not distinct at
  85. all. In this case, the ACB-algorithm has ideal conditions for work, in that
  86. it works more quickly by considering larger units, moreover, it can
  87. distinguish the value of phrases, through consideration of the probability
  88. of the appearance or use. In the case of an unlimited increase of a frame,
  89. ACB-compression always ensures an optimal size of a context dictionary.
  90.  
  91. Some ditailes about ACB-compression see APPENDIX_A & APPENDIX_B
  92.  
  93.                    2.4  DMC - Dynamic Markov Coding
  94.  
  95. Probabilistic models with a finite number of states can be described by a
  96. finite automate. A set of states S(i) and a set of probabilities of
  97. transition P(i,j) from the state i into the state J are called Markov's
  98. models. Markov's Dynamic Coding (DMC) is of practical interest, in that
  99. it works adaptively, starting from a simple initial model and adding,
  100. if necessary, new states. PPM technology is a particular case of the DMC
  101. approach. DMC allows the construction of context models not only for
  102. single symbols (as with PPM and consideration of letters of the alphabet),
  103. but also for phrases or lines. In this sense, ACB-compression can be
  104. classified as a variety of the DMC approach. I am not aware of software
  105. realizations of DMC algorithms; I would appreciate receiving any
  106. information on this issue (especially software realizations for the IBM_PC).
  107.  
  108.                    3. Comparison: ACB, PPM, LZ
  109.  
  110. ACB.EXE v1.14a & v1.23b works only in a "solid" mode, in which all files being
  111. packed are lined in a solid stream; this allows the most effective use the
  112. advantages of a large frame. The least favourable data for this solid-mode
  113. test data. As a rule, various information is taken into the catalogue to
  114. conduct tests. However, the high adaptivity of ACB-compression reduces to a
  115. minimum the possible loss, and on real data, the solid mode gives gain in
  116. compression in 99% cases. Below please find a comparative table (as test
  117. files, I have selected those transmitted by modem):
  118.  
  119. Compared: ACB v1.14a, X1 v0.93e, RAR v1.54b, ZIP v2.04g
  120. DATA -    Borland_C++_v_3.1 and GS_system_(convertor for *.ps)
  121. (exe,asm,c,cpp,h,hpp,obj,rtf,hlp,txt,doc,rc,res,bmp,lib,dll,wav,prj,ps,....)
  122.  
  123.        Regim (Options):
  124.  ACB - default ( "TAUGHT CHANNEL"-mode is not used)
  125.  X1  - select mode with max compression (m1/m3/m4/m1-Solid/m3-Solid/m4-Solid)
  126.  RAR - all Solid, max compression
  127.  ZIP - max compression
  128.  
  129.       ACB        PPM        LZ          LZ
  130.       *.ACB     *.X        *.RAR    *.ZIP
  131. TLIB  78,232      124,950    197,383     219,503 
  132. LIB   551,153      798,122    1,020,380     1,157,399 
  133. BGI   80,441      91,310     88,763     111,801 
  134. DOC   145,801     157,010    193,922     209,196 
  135. OWL   813,594      1,306,961  1,306,723     1,569,437 
  136. EXMPL 413,790      568,216    565,897     837,843 
  137. GS    605,931      653,809    671,410     725,455 
  138.       2,688,942     3,700,378  4,044,478    4,830,634
  139.  
  140. Time on OWL     Pentium-100  (486SX-33)
  141. ACB -           232 sec.     1057 sec.
  142. X1  -(m4-Solid) 190 sec.     710  sec.
  143. RAR -            101 sec.     341  sec.
  144. ZIP -             77  sec.     170  sec.
  145.  
  146. The non-linear nature of the gain in speed in switching to a Pentium processor
  147. is explained by three reasons:
  148. 1) Time costs for disk operations in switching over to Pentium are not
  149.    substantially decreased; their share for ACB is very small.
  150. 2) Optimization of the code for Pentium.
  151. 3) More effective caching of RAM, which is very critical for ACB.
  152.  
  153. The advantage of ACB-compression can be increased if ACB is tuned to some type
  154. of data, using the "TAUGHT CHANNEL" mode, having created in advance the
  155. context from relative information. Such a possibility is only a side effect of
  156. this mode. Something similar occurs in choosing options in order to obtain the
  157. maximum compression coefficient (external information about the data type).
  158. This approach is good if one wants to set the world records, but is of little
  159. practical application.
  160.  
  161. In the APPENDIX_B see the comparative table between the best research
  162. algorithms and ACB (on "Calgary Corpus" ).
  163.  
  164. In the APPENDIX_C see the comparative table between ACB_1.23b and ACB_1.14a.
  165.  
  166.  
  167.                    4. "TAUGHT CHANNEL"
  168.  
  169. The idea: in compressing information transmitted by a channel of
  170.           communications, all of ALL!!! the information earlier transmitted by
  171.           this channel is tranmitted, so that any repetitions of the data
  172.           transmitted in the past through the channel will be used in
  173.           establishing the algorithm for compression.
  174.  
  175. Realization: The ACB-compression algorithm was implemented in the
  176.              archivator ACB.EXE for Dos-WIN95 (ACB_1.23b- the latest version);
  177.              it was fully written on Assembler (32_Protection-mode) and
  178.              optimized for the Pentium processor.
  179.              It supports the TAUGHT CHANNEL mode.
  180.  
  181. Innovations: The ACB-compression algorithm is the only algorithm of
  182.              compression, the compression coefficient of which asymptotically
  183.              increases with the growth of the sliding frame. Other algorithms
  184.              can track not more than 8-65 Kb of the channel's background,
  185.              depending on the types of the data, as compared with
  186.              822 Kb in ACB_1.14a & 1671 Kb in ACB_1.23b.
  187.  
  188.                    4.1 Testing with "taught channel" - mode
  189.  
  190. Stream of data consists of two types of data:
  191. - ARCHIVE COMPARISON TEST (A.C.T.) Author: JEFF GILCHRIST
  192.   for June, July, August, September, October;
  193. - and *.exe files these are different version ACB.EXE:
  194.  
  195.        Regim (Options):
  196.  ACB - "TAUGHT CHANNEL"-mode
  197.  X1  - aem#
  198.  RAR - all Solid, max compression
  199.  ZIP - max compression
  200.  
  201. Stream: TXT --> EXE --> TXT --> EXE .... TXT --> EXE
  202.  
  203.              ACB        PPM      LZ       LZ
  204. Stream       *.ACB      *.X     *.RAR    *.ZIP
  205. of data       size      size     size     size
  206. A.C.T_6.95   10323     10314    12201    12199
  207. ACB_1.10     35605     36713    37150    37605
  208. A.C.T_7.95    3976     11039    13118    13121
  209. ACB_1.11      7903     36751    37172    37620
  210. A.C.T_8.95    2120     10847    12855    12849
  211. ACB_1.12      6963     36977    37381    37853
  212. A.C.T_9.95    1905     11004    12962    12949
  213. ACB_1.13      6123     37036    37402    37886
  214. A.C.T_10.95   1847     11381    13465    13480
  215. ACB_1.14      6873     36201    36410    36978
  216.              83638    238263   250116   252540
  217. Time (sec.)    20        28       7        5
  218.  
  219. Testing was conducted on Pentium-75.
  220.  
  221.                    5.  Conclusion
  222.  
  223. Pentium-100 encourages the creation of new algorithms, one of which is
  224. ACB-compression. 
  225.  
  226. If you are working on the problem of data compression for communications
  227. channels, ACB-compression is the most effective algorithm for compressing
  228. the stream of various information.
  229.  
  230. ---------------------------------------------------------------------------
  231. APPENDIX_A:
  232.                       Complexity of ACB-compression
  233.  
  234. Time:   T(n) = n/k * ( S + Log2( n/(2*k) ) ) + o(1)
  235. Memory: M(n) = n + n/8 + n*(Log2(n)+1)/4 + 11000
  236.  
  237. n - sliding frame size (for ACB v1.14 n=822000 bytes & v1.23b n=1671000 bytes),
  238. S - context dictionary size
  239. for ACB_1.14 : S=53, for ACB_1.23b : S=100 (MAX.), S=55 (NORMAL), S=16 (FAST)
  240. k - I/C  I - data size, C - code size,
  241. T(n)code=T(n)decode,
  242. M(n)code=M(n)decode.
  243.  
  244. Note:
  245. - memory requirements decrease proportionally to an ratio.
  246.   However, the latter possibility in ACB.EXE is not used 
  247.   to simplify memory manager.
  248.   M'(n) = n + n/8 + n*(Log2(n)+1)/(4*k) + 11000
  249.  
  250. - If S=1, the compression rate will be approximately the same as LZ-schemes
  251.   have on small files (32-64 Kb). However, with the inrease of their size,
  252.   the advantage of the ACB-compression increases (S=1). And all its valuable
  253.   properties (on_the_fly, unrestricted growth of a sliding frame ...) remain.
  254.  
  255. - Log2(n)+1 is the size of the pointer (bits), necessary for addressing
  256.   each byte of the sliding frame 
  257.  
  258. For n=4096 bytes   M(n)=28920 bytes
  259.     n=32768        M(n)=178936
  260.     n=65536        M(n)=363256
  261.     n=1048576      M(n)=6695672
  262.  
  263. Property:
  264.        _____        _____
  265. Data  |     | Cod  |     |  Data
  266. ----->| ACB |----->| ACB |-------->
  267. Time1 |_____|      |_____| Time2
  268.  
  269. Time1=Time2
  270.  
  271. The first compressed byte generates the code sufficient for
  272. restoration of this byte (on_the_fly).
  273.  
  274. On Pentium_100 the speed of the code is 40000 bits/sec, if the transmition
  275. speed in the communication line is <= than 40000 b/s, then time work
  276. of the ACB does not influence on the total transmition time.
  277. ---------------------------------------------------------------------------
  278. APPENDIX_B:
  279.  
  280. This overview shows the results obtained by the best universal compression
  281. algorithms (research implementations) on the test "Calgary Compression Corpus".
  282.  
  283. The columns are --
  284. LZB             Bell [1987] one of the best in the family LZ77
  285. order-0         BWT with a simple order-0 arithmetic final stage
  286. Shann           BWT with a "Shannon coder"
  287. Struct model    BWT with a "structured model" ( ditto)
  288. PPM*+, PPMD+    two recent PPM compressors
  289. BW95 6/2 arith  The best of David Wheeler's BWT compressors.
  290. LZP4            Author is Charles Bloom
  291. ACB             Buyanovsky's Associativety coding (ACB.EXE DOS/ver.1.23a)
  292. BEST            Combination of the best results from the
  293.         algorithms being considered
  294.  
  295. The results on all BWTs & PPMD+ were kindly provided
  296. by Dr Peter Fenwick <p_fenwick@cs.auckland.ac.nz>.
  297.  
  298. The results on PPM*+ were kindly provided
  299. by Dr Bill Teahan <wjt@kauri.cs.waikato.ac.nz>
  300.  
  301. The results on LZP4 were kindly provided by the author of this
  302. algorithm Charles Bloom <cbloom@mail.utexas.edu>.
  303.  
  304. The results on ACB (ACB.EXE v.1.23a for DOS) were kindly provided
  305. by Leonid Broukhis <leob@mailcom.com>
  306.  
  307.  
  308.       order-0 Shann  Struct BW94  PPM*+ PPMD+ BW95  LZP4   ACB   LZB    BEST
  309.                      model
  310. Bib    2.13   1.97   1.95   2.07 +1.86 +1.86  2.02  1.915  1.95  3.17 | 1.86
  311. Book1  2.52   2.40   2.39   2.49  2.41 +2.30  2.48  2.350  2.34  3.86 | 2.30
  312. Book2  2.19   2.06   2.04   2.13  2.00 +1.96  2.10  2.011 +1.96  3.28 | 1.96
  313. Geo    4.81   4.55  +4.50   4.45  4.78  4.73  4.73  4.740  4.69  6.17 | 4.50
  314. News   2.67   2.53   2.50   2.59  2.37  2.35  2.56  2.350 +2.34  3.55 | 2.34
  315. Obj1   4.20   3.93   3.87   3.98  3.83  3.73  3.88  3.744 +3.54  4.26 | 3.54
  316. Obj2   2.70   2.49   2.46   2.64  2.31  2.38  2.53  2.388 +2.24  3.14 | 2.24
  317. Paper1 2.60   2.48   2.46   2.55 +2.33 +2.33  2.52  2.378  2.37  3.22 | 2.33
  318. Paper2 2.57   2.44   2.42   2.51  2.34 +2.32  2.50  2.389  2.37  3.43 | 2.32
  319. Pic    0.83   0.77   0.77   0.83  0.84  0.80  0.79  0.814 +0.75  1.01 | 0.75
  320. ProgC  2.68   2.52   2.50   2.58 +2.34  2.36  2.54  2.392  2.35  3.08 | 2.34
  321. ProgL  1.85   1.73   1.72   1.80  1.61  1.68  1.75  1.589 +1.53  2.11 | 1.53
  322. ProgP  1.83   1.72   1.70   1.79  1.55  1.70  1.74  1.585 +1.52  2.08 | 1.52
  323. Trans  1.61   1.50   1.50   1.57  1.39  1.47  1.52  1.343 +1.31  2.12 | 1.31
  324. ----------------------------------------------------------------------|-----
  325. AVG    2.52   2.36   2.34   2.43  2.28  2.28  2.40  2.291 +2.23  3.18 | 2.20
  326.  
  327. ------ ACB_1.23a -----
  328. Computer: (Intel - P90/RAM 16M/MS-DOS)
  329.  
  330.                     -----FAST-------     ------NORM-----     ------MAX------
  331.              Size    Code /bpc /time     Code /bpc /time     Code /bpc /time
  332.                                  sec.                sec.                sec.
  333. bib.acb    111261   29215  2.10    7    27410  1.97   13    27178  1.95   20
  334. book1.acb  768771  241257  2.51   92   226612  2.36  199   224529  2.34  319
  335. book2.acb  610856  159132  2.08   55   150598  1.97  115   149753  1.96  193
  336. geo.acb    102400   61052  4.77   11    60189  4.70   24    60047  4.69   34
  337. news.acb   377109  116998  2.48   30   111149  2.36   64   110131  2.34  100
  338. obj1.acb    21504    9652  3.59    1     9535  3.55    2     9527  3.54    3
  339. obj2.acb   246814   72692  2.36   15    69781  2.26   29    69228  2.24   42
  340. paper1.acb  53161   16418  2.47    3    15797  2.38    6    15773  2.37    9
  341. paper2.acb  82199   25473  2.48    6    24391  2.37   12    24313  2.37   17
  342. pic.acb    513216   52604  0.82   16    49372  0.77   30    48272  0.75   45
  343. progc.acb   39611   12056  2.43    2    11673  2.36    4    11647  2.35    6
  344. progl.acb   71646   14284  1.59    3    13740  1.53    6    13686  1.53    8
  345. progp.acb   49379    9690  1.57    1     9379  1.52    3     9358  1.52    4
  346. trans.acb   93695   16062  1.37    3    15411  1.32    6    15308  1.31    8
  347.   Total:  3141622  836585        245   795037        513   788750        808
  348. ------------------------------------------------------------------------------
  349. AVR.                       2.33                2.24                2.23
  350. --------------------------------------------------------------------------
  351.  
  352. APPENDIX_C:
  353.  
  354. Here are the results comparing ACB v1.23b against ACB v1.14a:
  355.  
  356. i486DX-75  16 RAM  (256 Kb cache)
  357.  
  358. ///////////////// TXT ////////////////////////
  359.  
  360. Non-formatted text 8 files of parts of fiction  - 2359210 bytes
  361.  
  362. ................
  363. .            <DIR>         13.02.96   21:43
  364. ..           <DIR>         13.02.96   21:43
  365. JELYAZ02 TXT       485 162 09.09.91   17:35
  366. LKNKPLNT TXT       357 680 25.11.95   14:17
  367. VAGNER01 TXT       312 153 10.03.94   22:25
  368. STARWIND TXT       206 486 05.05.93   16:50
  369. ELEPHANT TXT       112 611 24.11.93    8:19
  370. ANDERS07 TXT       560 582 21.11.93    2:04
  371. BSELIKS  TXT        86 491 02.04.91   15:13
  372. WARRIOR  TXT       237 851 16.01.94   23:41
  373.        10 file(s)      2 359 016 bytes
  374. ................
  375.  
  376.                    Size (bytes)  Time (sec.)
  377. ACB_1.14a           724821       473
  378. ACB_1.23b(NORMAL)   710498       427
  379. ACB_1.23b(MAX)      702851       646
  380. ACB_1.23b(FAST)     758146       229
  381. PKZIP_2.04g (-ex)  1005277        35
  382.  
  383. ///////////////// EXE ////////////////////////
  384.  
  385. WINWORD.EXE (MS_WINWORD v.6.0_rus) - 3483156 bytes
  386.  
  387.                    Size (bytes)  Time (sec.)
  388. ACB_1.14a          1753719        715
  389. ACB_1.23b(NORMAL)  1701156        704
  390. ACB_1.23b(MAX)     1680749       1064
  391. ACB_1.23b(FAST)    1780426        369
  392. PKZIP_2.04g (-ex)  2031837         50
  393.  
  394. //////////////////////////////////////////////
  395.