%=============================================================================== % % This document contains the paper: % % "An Extremely Fast Ziv-Lempel Data Compression Algorithm", % IEEE Computer Society Data Compression Conference, % 8-11 April 1991, Snowbird, Utah, % Edited by James A. Storer and John H. Reif. % % Reprints can be obtained from the IEEE from whom the entire conference % proceedings are also available. % % IEEE Computer Society % PO Box 3014 % 10662 Los Vaqueros Circle % Los Alamitos CA 90720-1264 % USA % Ph: +1 (714) 821-8380 % % The funny IEEE digits appearing in the proceedings beneath my paper % are: TH0373-1/91/0000/0362/$01.00 (c) 1991 IEEE % % The paper is in LaTeX format. The entire text is here but the diagrams were % created using a drawing program, printed and stuck in separately, so here % there are just blank spaces where the diagrams are supposed to be. % % To typeset this document you need to give the "latex" command, not the % "tex" command. Latex will generate a ".dvi" file which can then be printed % using a special printing command (such as "lpr - d"). See your local % typesetting Guru for more information. % %=============================================================================== \documentstyle[12pt]{article} \pagestyle{empty} % Turn off page numbering. \topmargin=0.5cm \textheight=23cm \textwidth=15cm \title{An Extremely Fast Ziv-Lempel\\Data Compression Algorithm} \author{{\bf Ross N. Williams}\\ \\ Renaissance Software\\ GPO Box 171\\ Adelaide 5001, Australia\\ \\ {\tt ross@spam.ua.oz.au}} \date{} \begin{document} \pagestyle{empty} \maketitle \parskip=8pt \def\bold#1{{\bf #1}} \def\b#1{{\bf #1}} \def\i#1{{\it #1}} \def\paper#1{\bold{[#1]}\allowbreak{}} \def\dq#1{``{#1}''} \def\checked#1{} %\def\fix#1{\errmessage{FIX IT UP NOTE!!!}} %\def\fix#1{\footnote{$\bullet$ #1}} \def\fix#1{} \def\talkabout#1{\noindent {\bf #1}} \def\talkaboutfirstpar#1{{\bf #1}} \def\comment#1{{(\it Comment: #1)}} %\def\citefigure#1{{\bf Figure~\ref{fig:#1}}} \def\citefigure#1{{\bf Figure~#1}} \def\p#1{{\tt #1}} \def\startsmall{\begingroup{}\footnotesize} \def\endsmall{\endgroup{}} \def\opt#1{\noindent\bold{#1}} \def\startsmall{\begingroup{}\footnotesize} \def\endsmall{\endgroup{}} \def\mycaption#1{\begin{quotation}\footnotesize\noindent #1\end{quotation}} \def\mytitle#1#2{\caption{#2}\label{fig:#1}} \def\eg#1{e.g.~} \def\ie#1{i.e.~} \long\def\bigcaption#1#2#3{% \begin{quotation} \normalsize\noindent #3 \end{quotation} \centerline{\b{Figure~#1: #2}} } \long\def\bigcaptionnodesc#1#2{% \medskip \centerline{\b{Figure~#1: #2}} } % E.g. \bigcaption{zivdiag}{Compressed data format.}{This diagram %shows...} \sloppy \begin{abstract} % \noindent\normalsize A new, simple, extremely fast, locally adaptive data compression algorithm of the LZ77 class is presented. The algorithm, called LZRW1, almost halves the size of text files, uses 16K of memory, and requires about 13~machine instructions to compress and about 4~machine instructions to decompress each byte. This results in speeds of about 77K and 250K bytes per second on a one MIPS machine. The algorithm runs in linear time and has a good worst case running time. It adapts quickly and has a negligible initialization overhead, making it fast and efficient for small blocks of data as well as large ones. % \end{abstract} \section{Introduction} Text data compression techniques can be partitioned into ad hoc techniques, dictionary techniques, and statistical techniques (see reviews in \paper{Williams90}\paper{Bell90a}\paper{Storer88}). Of these, the class of adaptive dictionary algorithms pioneered by Ziv and Lempel\paper{Ziv77}\paper{Ziv78} provides the most practical trade off between flexibility, compression, and speed. Most modern text data compression programs, including the popular Unix \i{compress} utility (derived from \paper{Welch84}), use Ziv and Lempel (LZ) algorithms. Although current LZ algorithms are generally fast, they are not always fast enough for embedded real-time systems with tight throughput requirements. In such systems time is the important constraint and designers of compression algorithms must concentrate primarily on speed, with compression taking second place. This paper presents a new LZ variant called LZRW1 that was designed with speed as the primary objective. The algorithm takes only a few instructions to process each byte, but still yields useful compression. LZRW1 is based on the A1 algorithm by Fiala and Greene\paper{Fiala88} which itself is a member of the class of LZ77 algorithms\paper{Ziv77}. \section{The LZRW1 Algorithm} LZRW1 uses the single pass literal/copy mechanism of \paper{LZ77}. At each step, the next few bytes of input are transmitted either directly as a string or as a pointer to the text already transmitted (the \b{history}). \citefigure{1} shows how a particular message would be divided into \b{literal items} and \b{copy items} if the minimum length of an uncompressed copy item were three bytes. Compression is achieved by representing as much of the message using copy items, resorting to literal items only when a match of three or more bytes cannot be found. \begin{figure}[ht] \vspace{4.5cm} \bigcaption{1}{The literal/copy compression technique.}{% % LZ77 class algorithms (of which LZRW1 is a member) achieve compression by converting the text into a sequence of items, each of which can be either a literal item or a copy item. Literal items consist of the text they represent. Copy items consist of an offset and a pointer that together point to a substring of the text already transmitted. % } \end{figure} \citefigure{2} shows how LZRW1 arranges the items into compressed data. A literal item contains a single byte that is coded directly. A copy item contains two bytes that specify the length[3,16] and offset[1,4095] of a string appearing in the most recent 4095 bytes of the history (the \b{Lempel}). Control bits indicate whether items are literal or copy items, and are clustered into groups of 16 to preserve byte alignment. \begin{figure}[ht] \vspace{9cm} \bigcaption{2}{LZRW1's compressed data format.}{% % This figure gives LZRW1's compressed data format. LZRW1 uses a single bit to determine whether each item is a literal item or a copy item. To preserve byte alignment, items are clustered into 16-item groups preceded by a 16-bit control word. % } \end{figure} \citefigure{3} gives a snapshot of the LZRW1 compression algorithm in execution. The algorithm's data structures, which form its source model, consist of a few scalar variables, the input block, and a hash table of 4096 pointers. The hash table maps any three byte key to a single pointer that can point anywhere in memory, but which is likely to point to a matching key somewhere in the Lempel. At each step the hash table is used to try to find a match in the Lempel for the first three or more bytes of the \b{Ziv} (the next 16 bytes to be coded) with a match resulting in the generation of a copy item. Because the algorithm checks all pointers that it fetches from the hash table, the hash table does not need to be initialized. LZRW1 updates its hash table after every item rather than every byte, making the hash table update rate inversely proportional to compression. This policy also exploits the phrase structure\paper{Langdon84} present in most data. Decompression is extremely simple and fast. The decompressor processes one item at a time, translating it into one or more bytes which are appended to the end of the output. If the item is a literal item, its single literal byte is appended. If the item is a copy item, the length and offset fields are used to locate and copy a string already in the output block. Control bits must be buffered. LZRW1's hash function is constructed in accordance with the advice in \paper{Knuth81} and seems to be near optimal. A recently published hash function that used a lookup table\paper{Pearson90} was tried, but yielded identical performance. LZRW1's hash table provides at most the most recent Lempel match of a key. Bell\paper{Bell90b} discusses other LZ77 search techniques. A precise specification of the LZRW1 text data compression algorithm is given in \b{Figures~4--6} which provide a turnkey implementation in the~C programming language\paper{Kernighan88}. \section{Experiments} To test its performance, LZRW1 was implemented in high and low level languages and applied to the standard corpus of test files described in Appendix~B of \paper{Bell90a}. \citefigure{7} gives the results of running the C~implementation of LZRW1 of \b{Figures~4--6} against a similar implementation of the A1 algorithm and against the Unix \i{compress} utility (LZC) on a Pyramid~9820 computer running Unix. LZRW1 compresses about 10\% worse than LZC, but runs four times faster. LZRW1 compresses about 4.3\% worse than the A1 algorithm, but runs ten times faster. This indicates that A1's exhaustive search of the Lempel and its use of a two-byte minimum copy length does not greatly improve its compression. \citefigure{8} gives the performance of an hand-optimized 68000 assembly language implementation of LZRW1 running it on an 8MHz Macintosh-SE computer. LZRW1 achieves reasonable compression while requiring an average of just thirteen machine instructions to compress and four machine instructions to decompress each byte. The performance of LZRW1 on the files \i{zeros} and \i{noise} demonstrates the stability of the algorithm. For the 68000 runs, each file was divided into 16K blocks each of which was compressed independently. This impaired compression by at most 2\% absolute. This fact coupled with LZRW1's negligible initialization cost makes LZRW1 ideal for small blocks of data. \section{Conclusion} Use of a simple hash table mechanism along with ruthless elimination of housekeeping has led to the extremely fast LZRW1 text compression algorithm that requires about 13 machine instructions to compress each byte and about 4 machine instructions to decompress each byte. This results in speeds of about 77K and 250K per second on a one MIP machine. LZRW1 compresses ten percent worse than the popular Unix \i{compress} utility, but runs four times faster, making it possibly the fastest adaptive text compression algorithm yet. \section{References} \paper{Bell90a} Bell T.C., Cleary J.G., Witten I.H., \dq{Text Compression}, Prentice Hall, Englewood Cliffs, New Jersey, 1990. \noindent\paper{Bell90b} Bell T.C., \dq{Longest Match String Searching For Ziv-Lempel Compression}, Department of Computer Science, University of Canterbury, Christchurch, New Zealand. \noindent\paper{Fiala88} Fiala~E.R., Greene~D.H., \dq{Data Compression with Finite Windows}, \i{Communications of the ACM}, Vol.~32, No.~4, pp.~490--505. \noindent\paper{Kernighan88} Kernighan~B.W., Ritchie~D.M., \dq{The C Programming Language}, Prentice Hall, Englewood Cliffs, New Jersey, 1988. \noindent\paper{Knuth81} Knuth~D.E., \dq{Sorting and Searching}, The Art of Computer Programming, Vol.~23, Addison-Wesley Publishing Company, Reading, Massachusetts, 1973. \noindent\paper{Langdon84} Langdon~G.G, \dq{On Parsing Versus Mixed-Order Model Structures for Data Compression}, IBM Research Report RJ-4163 (46091) 1/18/84, IBM Research Laboratory, San Jose, CA 95193, 1984. \noindent\paper{Pearson90} Pearson~P.K., \dq{Fast Hashing of Variable-Length Text Strings}, \i{Communications of the ACM}, Vol.~33, No.~6, June~1990, pp.~677--680. \noindent\paper{Storer88} Storer~J.A., \dq{Data Compression: Methods and Theory}, Computer Science Press, 1803 Research Boulvard, Rockville, Maryland 20850, 1988. \noindent\paper{Welch84} Welch T.A., \dq{A Technique for High-Performance Data Compression}, \i{IEEE Computer}, Vol.~17, No.~6, pp.~8--19. \noindent\paper{Williams90} Williams R.N., \dq{Adaptive Data Compression}, Kluwer Academic Publishers, 1990. \noindent\paper{Ziv77} Ziv J., Lempel A., \dq{A Universal Algorithm for Sequential Data Compression}, \i{IEEE Transactions on Information Theory}, Vol.~23, No.~3, pp.~337--343. \noindent\paper{Ziv78} Ziv J., Lempel A., \dq{Compression of Individual Sequences via Variable-Rate Coding}, \i{IEEE Transactions on Information Theory}, Vol.~24, No.~5, pp.~530--536. \begin{figure} \vspace{12cm} \bigcaption{3}{The LZRW1 algorithm in execution.}{% % This figure gives a snapshot of the LZRW1 compression algorithm in execution. The horizontal bar represents the input block (in memory) which is used directly as a read-only data structure. The hash table maps three-byte keys to pointers that can point anywhere in memory, but which are likely to point to a recent occurrence of the key in the input already scanned (the history). At each step the hash table is used to map the first three bytes of the Ziv (defined to be the first sixteen bytes of the remaining part of message) to such a pointer. To keep the hash table up to date, the hash table entry from which the pointer was just fetched is replaced by a pointer to the Ziv. If the pointer fetched points to one of the most recent 4095 bytes of the history (the Lempel) and points to a match with the Ziv of at least three bytes, a copy item is constructed representing the bytes matched, otherwise a literal item is constructed representing the first byte in the Ziv. Because the algorithm checks the pointers that it obtains from the hash table, the hash table need not be initialized. % } \end{figure} \begin{figure} \startsmall \begin{verbatim} void lzrw1_compress(p_src_first,src_len,p_dst_first,p_dst_len) /* Input : Specify input block using p_src_first and src_len. */ /* Input : Point p_dst_first to the start of the output zone (OZ). */ /* Input : Point p_dst_len to a ULONG to receive the output length. */ /* Input : Input block and output zone must not overlap. */ /* Output : Length of output block written to *p_dst_len. */ /* Output : Output block in Mem[p_dst_first..p_dst_first+*p_dst_len-1]. */ /* Output : May write in OZ=Mem[p_dst_first..p_dst_first+src_len+256-1].*/ /* Output : Upon completion guaranteed *p_dst_len<=src_len+FLAG_BYTES. */ UBYTE *p_src_first,*p_dst_first; ULONG src_len,*p_dst_len; #define PS *p++!=*s++ /* Body of inner unrolled matching loop. */ #define ITEMMAX 16 /* Maximum number of bytes in an expanded item. */ {UBYTE *p_src=p_src_first,*p_dst=p_dst_first; UBYTE *p_src_post=p_src_first+src_len,*p_dst_post=p_dst_first+src_len; UBYTE *p_src_max1=p_src_post-ITEMMAX,*p_src_max16=p_src_post-16*ITEMMAX; UBYTE *hash[4096],*p_control; UWORD control=0,control_bits=0; *p_dst=FLAG_COMPRESS; p_dst+=FLAG_BYTES; p_control=p_dst; p_dst+=2; while (TRUE) {UBYTE *p,*s; UWORD unroll=16,len,index; ULONG offset; if (p_dst>p_dst_post) goto overrun; if (p_src>p_src_max16) {unroll=1; if (p_src>p_src_max1) {if (p_src==p_src_post) break; goto literal;}} begin_unrolled_loop: index=((40543*((((p_src[0]<<4)^p_src[1])<<4)^p_src[2]))>>4) & 0xFFF; p=hash[index]; hash[index]=s=p_src; offset=s-p; if (offset>4095 || p>=1; control_bits++;} else {PS || PS || PS || PS || PS || PS || PS || PS || PS || PS || PS || PS || PS || s++; len=s-p_src-1; *p_dst++=((offset&0xF00)>>4)+(len-1); *p_dst++=offset&0xFF; p_src+=len; control=(control>>1)|0x8000; control_bits++;} end_unrolled_loop: if (--unroll) goto begin_unrolled_loop; if (control_bits==16) {*p_control=control&0xFF; *(p_control+1)=control>>8; p_control=p_dst; p_dst+=2; control=control_bits=0;} } control>>=16-control_bits; *p_control++=control&0xFF; *p_control++=control>>8; if (p_control==p_dst) p_dst-=2; *p_dst_len=p_dst-p_dst_first; return; overrun: fast_copy(p_src_first,p_dst_first+FLAG_BYTES,src_len); *p_dst_first=FLAG_COPY; *p_dst_len=src_len+FLAG_BYTES; } \end{verbatim} \endsmall \bigcaptionnodesc{4}{The LZRW1 compression algorithm.} \end{figure} \begin{figure} \startsmall \begin{verbatim} #define UBYTE unsigned char /* Unsigned byte (1 byte ) */ #define UWORD unsigned int /* Unsigned word (2 bytes) */ #define ULONG unsigned long /* Unsigned longword (4 bytes) */ #define FLAG_BYTES 4 /* Number of bytes used by copy flag. */ #define FLAG_COMPRESS 0 /* Signals that compression occurred. */ #define FLAG_COPY 1 /* Signals that a copyover occurred. */ void fast_copy(p_src,p_dst,len) /* Fast copy routine. */ UBYTE *p_src,*p_dst; {while (len--) *p_dst++=*p_src++;} \end{verbatim} \endsmall \bigcaptionnodesc{5}{Definitions used by LZRW1 code.} \end{figure} \begin{figure} \startsmall \begin{verbatim} void lzrw1_decompress(p_src_first,src_len,p_dst_first,p_dst_len) /* Input : Specify input block using p_src_first and src_len. */ /* Input : Point p_dst_first to the start of the output zone. */ /* Input : Point p_dst_len to a ULONG to receive the output length. */ /* Input : Input block and output zone must not overlap. User knows */ /* Input : upperbound on output block length from earlier compression. */ /* Input : In any case, maximum expansion possible is eight times. */ /* Output : Length of output block written to *p_dst_len. */ /* Output : Output block in Mem[p_dst_first..p_dst_first+*p_dst_len-1]. */ /* Output : Writes only in Mem[p_dst_first..p_dst_first+*p_dst_len-1]. */ UBYTE *p_src_first, *p_dst_first; ULONG src_len, *p_dst_len; {UWORD controlbits=0, control; UBYTE *p_src=p_src_first+FLAG_BYTES, *p_dst=p_dst_first, *p_src_post=p_src_first+src_len; if (*p_src_first==FLAG_COPY) {fast_copy(p_src_first+FLAG_BYTES,p_dst_first,src_len-FLAG_BYTES); *p_dst_len=src_len-FLAG_BYTES; return;} while (p_src!=p_src_post) {if (controlbits==0) {control=*p_src++; control|=(*p_src++)<<8; controlbits=16;} if (control&1) {UWORD offset,len; UBYTE *p; offset=(*p_src&0xF0)<<4; len=1+(*p_src++&0xF); offset+=*p_src++&0xFF; p=p_dst-offset; while (len--) *p_dst++=*p++;} else *p_dst++=*p_src++; control>>=1; controlbits--; } *p_dst_len=p_dst-p_dst_first; } \end{verbatim} \endsmall \bigcaptionnodesc{6}{The LZRW1 decompression algorithm.} \end{figure} \begin{figure} \begin{center} \begin{tabular}{|lr|rrr||r|r|r|} \cline{3-8} \multicolumn{2}{l|}{\hbox{}} & \multicolumn{3}{c||}{\%Rem} & \multicolumn{3}{c|}{K/Sec} \\ \hline File & K & A1 & LZC & RW1 & \multicolumn{1}{c}{A1} & \multicolumn{1}{c}{LZC} & \multicolumn{1}{c|}{RW1} \\ \hline bib & 109 & 53.8 & 41.8 & 59.4 & 27~~435 & 58~~~94 & 213~~388 \\ book1 & 751 & 61.6 & 43.2 & 67.9 & 21~~419 & 46~~~90 & 186~~368 \\ book2 & 597 & 52.5 & 41.1 & 59.0 & 24~~435 & 49~~~92 & 215~~375 \\ geo & 100 & 94.0 & 76.0 & 84.4 & 13~~270 & 48~~~74 & 167~~313 \\ news & 368 & 56.8 & 48.3 & 61.3 & 27~~433 & 44~~~87 & 210~~392 \\ obj1 & 21 & 60.8 & 65.3 & 61.7 & 4~~350 & 53~~~75 & 191~~420 \\ obj2 & 241 & 47.0 & 52.1 & 51.3 & 23~~482 & 41~~~86 & 225~~423 \\ paper1 & 52 & 51.5 & 47.2 & 57.8 & 26~~433 & 58~~~91 & 226~~371 \\ paper2 & 80 & 54.0 & 44.0 & 61.0 & 23~~401 & 64~~~94 & 206~~382 \\ pic & 501 &*23.3 & 12.1 & 25.6 & 37~~604 & 108~~148 & 346~~506 \\ progc & 39 & 49.1 & 48.3 & 54.6 & 29~~387 & 55~~~90 & 242~~387 \\ progl & 70 & 35.5 & 37.9 & 43.7 & 20~~466 & 65~~103 & 241~~412 \\ progp & 48 & 35.4 & 38.9 & 42.8 & 19~~438 & 63~~~98 & 241~~344 \\ trans & 91 & 40.8 & 40.8 & 46.1 & 25~~457 & 61~~~96 & 241~~436 \\ \hline Average& 219 & 51.2 & 45.5 & 55.5 & 22~~429 & 58~~~94 & 224~~394 \\ \hline \end{tabular} \end{center} \bigcaption{7}% {Performance of algorithms on a Pyramid~9820.}{% % This table compares the performance of the A1 (a simple LZ77 class algorithm by Fiala and Greene), LZC (Unix \i{compress} which is based on the LZW algorithm), and LZRW1 (the topic of this paper) algorithms coded in~C and running on a Pyramid~9820 computer. The implementation of A1 used a hash table indexing into a bounded buffer array holding linked lists of hash matches. A standard corpus of files was used for the test. The \%Rem columns give compression as a percentage remaining. The K/Sec columns give the compression and decompression speeds in kilobytes (1024) per second. Decompression speeds are given relative to \i{output} (uncompressed) bytes. Speeds were calculated from the \i{user} time field given by an application of the unix \i{time} command to a block of ten consecutive compression runs. (*Note: The A1 algorithm took so long to run on the file \i{pic} that it was terminated and re-run, for the file \i{pic} only, with an upperbound of ten on its search). A comparison of LZRW1 to its ancestor algorithm A1 shows that, while LZRW1 compresses about 4.3\% worse than the A1 algorithm, LZRW1 runs ten times faster. LZRW1 compresses about 10\% absolute worse than LZW, but runs four times faster. LZRW1 compresses relatively poorly on English text files (e.g. book1), but compresses relatively well on non-English text files such as program texts and object files for which it betters LZW on both compression and speed. % } \end{figure} \begin{figure} \begin{center} \begin{tabular}{|lrr|r|r|r|} \hline %Note: KBytes are rounded to the nearest K. %Note: 16K blocks column direct from test harness. %Note: K/Sec rounded to the nearest K. %Note: Instr/byte rounded to the nearest 0.1 of an instruction. %Note: 05-Feb-91: I have checked all the data in this table and it is OK. File & K & /16K & \%Rem & K/Sec & Ins/Byte \\ \hline bib & 109 & 7 & 61.0 & 43~~147 & 13.4~~4.1 \\ book1 & 751 & 47 & 69.5 & 40~~132 & 14.7~~4.6 \\ book2 & 597 & 38 & 60.5 & 44~~142 & 13.1~~4.3 \\ geo & 100 & 7 & 85.6 & 31~~131 & 18.5~~4.7 \\ news & 368 & 24 & 63.0 & 41~~150 & 14.0~~4.0 \\ obj1 & 21 & 2 & 61.9 & 41~~161 & 14.2~~3.7 \\ obj2 & 241 & 16 & 52.5 & 49~~156 & 11.8~~3.8 \\ paper1 & 52 & 4 & 59.5 & 45~~143 & 12.9~~4.2 \\ paper2 & 80 & 6 & 62.4 & 44~~138 & 13.3~~4.4 \\ pic & 501 & 32 & 25.8 & 87~~187 & 6.5~~3.1 \\ progc & 39 & 3 & 55.7 & 47~~149 & 12.3~~4.0 \\ progl & 70 & 5 & 44.7 & 58~~157 & 10.0~~3.8 \\ progp & 48 & 4 & 44.2 & 58~~158 & 9.9~~3.7 \\ trans & 91 & 6 & 47.9 & 53~~162 & 10.9~~3.7 \\ \hline Average& 219 & 14 & 56.7 & 49~~151 & 12.5~~4.0 \\ \hline \multicolumn{6}{c}{\hbox{}}\\ \hline zeros & 78 & 5 & 13.4 & 136~~205 & 4.1~~2.7 \\ noise & 78 & 5 & 100.0 & 23~~1178 & 24.4~0.25 \\ \hline \end{tabular} \end{center} \bigcaption{8}{Performance of optimized 68000 LZRW1.}{% % This table gives the performance of an hand-optimized 68000 assembly language implementation of LZRW1 running on an 8MHz, 24-bit bus, Macintosh-SE computer. The input files were divided into 16K blocks which were compressed independently. The \%Rem column gives the compression as a percentage remaining. The K/Sec column gives the compression and decompression speeds in kilobytes (1024) per second. Decompression speeds are given relative to \i{output} (uncompressed) bytes. The speeds are for execution only and do not include IO. The Ins/Byte column gives the average number of 68000 instructions required to process each byte during compression and decompression and was obtained by inserting counting instructions into the code and performing a separate run. All results were rounded to the given accuracy. A comparison of these results to those of \citefigure{7} shows that the division of the input file into 16K blocks worsened compression by an average of only 1.2\% absolute with the maximum impact being 1.8\% absolute. The results for the files \i{zeros} (zero bytes) and \i{noise} (uniformly and independently random bytes) suggest that LZRW1's best running time is about one third of its average running time, and that its worst running time is about twice its average running time. For ordinary text data, LZRW1 requires about 13~instructions to compress and about 4~instructions to decompress each byte. % } \end{figure} %Standard deviation for 16K change=0.51 \end{document}