1 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
\r
4 <META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=iso-8859-1">
\r
5 <META NAME="GENERATOR" CONTENT="Mozilla/4.06 [es] (Win95; I) [Netscape]">
\r
6 <META NAME="KeyWords" CONTENT="model, arithmetic, coding, modeling, symbol, alphabet, size, order, context, contexts, cump, cumulative, probabilities, frequencies, escape, codes, code, redundancy, zero, problem, arturo, campos, compression, ppmc, PPMC, ppm, modeling, hash, table, linked, list, C, source, code, cump, esc, range">
\r
7 <META NAME="Description" CONTENT="Ppmc is implemented with hash tables to access probabilities.">
\r
8 <META NAME="Author" CONTENT="Arturo San Emeterio Campos">
\r
9 <TITLE>Implementing ppmc with hash tables by Arturo Campos</TITLE>
\r
11 <BODY TEXT="#000000" BGCOLOR="#FFFFFF" LINK="#0000FF" VLINK="#800080" ALINK="#3366FF">
\r
13 <CENTER><FONT SIZE=+2>"Implementing ppmc with hash tables"</FONT>
\r
14 <BR><FONT SIZE=+1>by</FONT>
\r
15 <BR><FONT SIZE=+2>Arturo San Emeterio Campos</FONT></CENTER>
\r
24 <P><FONT SIZE=+2>Disclaimer</FONT>
\r
25 <BR>Copyright (c) Arturo San Emeterio Campos 2000. All rights reserved.
\r
26 Permission is granted to make verbatim copies of this document for private
\r
29 <P><FONT SIZE=+2>Download</FONT>
\r
30 <BR>Download the <A HREF="ac_ppmc_html.zip">whole article</A> zipped. It
\r
31 includes the C source code as well as compiled binaries for Dos.
\r
33 <P><FONT SIZE=+2>Table of contents</FONT>
\r
35 <A HREF="#Introduction">Introduction</A></LI>
\r
38 <A HREF="#Ppmc">Ppmc, history review and data structures used</A></LI>
\r
41 <A HREF="#Some terminology">Some terminology and a brief look to a model</A></LI>
\r
44 <A HREF="#Cumulative probabilities">Cumulative probabilities and how to
\r
45 manage them</A></LI>
\r
48 <A HREF="#Escape method C">Escape method C, how to compute and use it</A></LI>
\r
51 <A HREF="#Linked lists">Linked lists for the counts of the bytes</A></LI>
\r
54 <A HREF="#Coding and decoding with linked lists">Coding and decoding with
\r
55 linked lists</A></LI>
\r
58 <A HREF="#Hash tables">Hash tables for contexts</A></LI>
\r
61 <A HREF="#Global variables">Global variables</A></LI>
\r
64 <A HREF="#Functions for every order">Functions nomenclature and use</A></LI>
\r
67 <A HREF="#The main">The main part</A></LI>
\r
70 <A HREF="#Order-(-1)">Order-(-1)</A></LI>
\r
73 <A HREF="#Order-0">Order-0 and order-1</A></LI>
\r
76 <A HREF="#Order-2">Order-2</A></LI>
\r
79 <A HREF="#Order-3">Order-3 and order-4</A></LI>
\r
82 <A HREF="#Memory requeriments and management">Memory requirements and management</A></LI>
\r
85 <A HREF="#Fast order-3 hashed">How to implement the fast order-3 hashed
\r
89 <A HREF="#Full exclusion">Adding full exclusion to the already done functions</A></LI>
\r
92 <A HREF="#Compression and speed">Compression and speed results of the different
\r
93 implementations</A></LI>
\r
96 <A HREF="#References">References</A></LI>
\r
99 <A HREF="#Closing words">Closing words</A></LI>
\r
102 <A HREF="#Contacting the author">Contacting the author</A></LI>
\r
113 <P><A NAME="Introduction"></A><FONT SIZE=+2>Introduction</FONT>
\r
114 <BR><P ALIGN="JUSTIFY">This article is about ppmc, a lossless compression
\r
115 algorithm which achieves compression higher than some commercial products.
\r
116 This articles shows in deep how to implement ppmc using hash tables and
\r
117 linked lists. Different versions of it are explained, ppmc with lazy exclusions,
\r
118 ppmc with full exclusions (slower than the previous but achieving more compression)
\r
119 and a tricky version of ppmc, <A HREF="#Fast order-3 hashed">ppmc order-3
\r
120 hashed</A>, the only ppm implementation which is practical in the compression/speed/memory
\r
121 tradeoff. Ppmc can be used as an standalone compressor or with other algorithms
\r
122 like lzp for <A HREF="#literals-lzp">coding of the literals</A> <A HREF="#r.[14]">[14]</A>,
\r
123 due to his high compression level. You are encouraged to see the
\r
124 <A HREF="#Compression and speed">results</A>
\r
125 in speed and compression to see if this is the algorithm that you need.
\r
126 Understanding ppmc is the key to understand ppmz, the state of art in text
\r
127 compression <A HREF="#r.[3]">[3]</A>. The explanations follow the code
\r
128 that is released along with the article. This article presupposes a theory
\r
129 which is explained in my article about finite context modeling
\r
130 <A HREF="#r.[6]">[6]</A>.
\r
131 <P><P ALIGN="JUSTIFY">The article is distributed in the following way:
\r
132 Some historical <A HREF="#Ppmc">review</A> is done. After that, some <A HREF="#Some terminology">terminology</A>
\r
133 is explained. First I talk about
\r
134 <A HREF="#Cumulative probabilities">cumulative
\r
135 probabilities</A>, <A HREF="#Linked lists">linked lists</A>, the probability
\r
136 of the <A HREF="#Escape method C">escape code</A>, and <A HREF="#Hash tables">hash
\r
137 tables for contexts</A>. These sections describe all the algorithms and
\r
138 code used for managing the model and encoder which are later needed. Then
\r
139 we see how to put everything together. Some <A HREF="#Global variables">global
\r
140 variables</A> and data structures are discussed, the initialization and
\r
141 some other code is explained too. The next section explains more about
\r
142 the code and the <A HREF="#Functions for every order">functions</A> for
\r
143 coding, decoding and updating. Then the algorithm is commented from the
\r
144 <A HREF="#Order-(-1)">lowest
\r
145 order</A> till <A HREF="#Order-3">order-4</A>, once there it's only a matter
\r
146 of implementing the code explained before. Due to the fact that the data
\r
147 structures and functions from one context don't depend on others, the idea
\r
148 is to have order-(-1) working before starting implementing order-0, and
\r
149 so on. This makes programming very easy, and it helps finding bugs. My
\r
150 implementation uses bytes as symbols as its goal is to compress files.
\r
151 At first all the functions will be explained for lazy exclusion. Then there's
\r
152 a section about how much <A HREF="#Memory requeriments and management">memory</A>
\r
153 needs every data structure and every order, and how it's managed. After
\r
154 this there's a section about <A HREF="#Full exclusion">full exclusion</A>
\r
155 which shows how to make ppmc with full exclusions, from the code already
\r
156 done. Also I talk about a <A HREF="#Fast order-3 hashed">fast order-3 hashed</A>
\r
157 ppmc implementation, which is as fast as order-2 but achieving more compression
\r
158 (not as much as real order-3 of course). At the end of the article you
\r
160 <A HREF="#Compression and speed">results</A> of different
\r
161 ppmc implementations, in both compression and speed. The algorithm is explained
\r
162 in the way I found easier to understand, the basic order-0 is explained,
\r
163 then the concept "context" is used order-1. We make order-2 from order-1
\r
164 using linked lists for probabilities, and a hash table for contexts. Based
\r
165 on order-2 we make both order-3 and order-4, which are a natural extension,
\r
166 using a hash table and linked lists for storing the contexts. Every concept
\r
167 is based on the previous, and thus I don't add difficulties to the already
\r
168 complex process of learning.
\r
170 <P><A NAME="Ppmc"></A><FONT SIZE=+2>Ppmc, history review and data structures
\r
172 <BR><P ALIGN="JUSTIFY">Prediction by Partial Matching is the Markovian
\r
173 model which achieves higher compression. Markovian models are those who
\r
174 have the Markov property: the probability of the current symbol only depends
\r
175 on the symbols which appeared before. Due to the increasing power and memory
\r
176 available in today's machines some ppm implementations are practical. Some
\r
177 others are not like the actual state of art in lossless text compression:
\r
178 ppmz2 by Charles Bloom. Other states of art are CTW <A HREF="#r.[13]">[13]</A>
\r
179 and the switching schemes of Paul Volf (though nowadays they are still
\r
180 hardly know). The main programming difficulty of ppm models is the data
\r
181 structure that holds all the contexts to be used. The first data structure
\r
182 used was the context trie in <A HREF="#r.[3]">[3]</A> or <A HREF="#r.[4]">[4]</A>.
\r
183 The context trie uses a linked list for every order. In every node there's
\r
184 a byte and its count, and pointer to the next element in a linked list
\r
185 containing the rest of the bytes under that context. For traversing the
\r
186 structure there's a pointer to the next higher order, obviously at the
\r
187 root of the tree you can find order-0. Optionally (for higher speed) there's
\r
188 another pointer to the next lower order (used when escaping). This data
\r
189 structure is used for bounded (limited) orders of a length of 5 or so.
\r
190 But for unbounded orders (that is, of non previously chosen length), which
\r
191 are very long, this is not satisfactory due to the high memory usage.
\r
192 <P><P ALIGN="JUSTIFY">The patricia tree and, mainly, the suffix tree are
\r
193 a solution to this problem. The suffix tree is used in ppmd <A HREF="#r.[5]">[5]</A>.
\r
194 However suffix trees are more difficult to implement than other solutions.
\r
195 <P><P ALIGN="JUSTIFY">In <A HREF="#r.[8]">[8]</A> hash tables were used,
\r
196 I've not checked this paper though. Thus I'll explain how to implement
\r
197 ppmc with hash tables without following it. The ideas exposed in this article
\r
198 are based on the implementation of ppmz by Malcolm Taylor. Hash tables are
\r
199 easy to learn, so they fit quite well this article. Moreover they are
\r
200 the appropriate structure structure for ppmz, and another of the goals of
\r
201 this article is to learn the base of ppmz. Just as a little overview of
\r
202 ppmc with hash tables, every context has its own hash table and linked
\r
203 lists where the bytes (or symbols) and counts are stored, then it's only
\r
204 a matter to read the count of a symbol, compute probabilities and code
\r
205 it. All the theory behind ppm was explained in "Finite context modeling"
\r
206 <A HREF="#r.[6]">[6]</A>
\r
207 so it's recommended to read it before this one. Along with this article,
\r
208 I've released my implementation of ppmc in C. I'll not try to focus much
\r
209 on it, because this would cause problems to the reader interested in implementing
\r
210 it in other language, anyway I'll follow it.
\r
211 <P><P ALIGN="JUSTIFY">Ppm was invented by John Cleary and Ian Witten back
\r
212 in 1984. The original paper <A HREF="#r.[9]">[9]</A>, talked about ppma
\r
213 and ppmb. The suffix letter ('a' or 'b') denotes the escape code used in
\r
214 the algorithm, however the rest of the algorithm is roughly the same. In
\r
215 the book "Text compression"
\r
216 <A HREF="#r.[2]">[2]</A> all of them were explained.
\r
217 Ppmc was presented by Alistair Moffat in <A HREF="#r.[7]">[7]</A>. In the
\r
218 paper by Moffat also ppmc' was presented, which is ppmc but using lazy
\r
219 exclusion. Other variants such as ppmd, ppm* or ppmz fall outside
\r
220 the scope of this article, however I'll probably talk about them too in
\r
221 a near future. The difference between ppmc and ppma or ppmb are only the
\r
222 probability computation for the escape code.
\r
223 <P><P ALIGN="JUSTIFY">As we saw in <A HREF="#r.[6]">[6]</A> ppm variants
\r
224 are finite context models. Practical implementations don't use blending.
\r
225 They use escape codes instead. They fallback to lower orders when needed.
\r
226 That is, they start at the highest order initialized, if the byte is present
\r
227 they code it under the current context, otherwise they emit an escape code,
\r
228 fallback to (use) a lower context and try to code the byte under that context.
\r
229 The last context (order-(-1)) contains all the bytes, so we'll surely find
\r
230 it there if it wasn't present in higher orders. We code the probability
\r
231 with arithmetic coding, or any variant (like in the case of the source,
\r
233 <A HREF="#r.[11]">[11]</A>). Once the byte is coded, it's
\r
234 only a matter of updating the probability of the symbol which we have just
\r
235 coded. As we are going to see later, ppmc uses update exclusions, which
\r
236 does not only make it faster but also achieves slightly better compression.
\r
237 How to implement update exclusions is explained in the section <A HREF="#Global variables">Global
\r
239 <P><P ALIGN="JUSTIFY">If we are using escape codes, when we are in a given
\r
240 context we exclude lower orders from probability computing, because we
\r
241 just take in account the probabilities of current one, that's ppmc
\r
242 using lazy exclusions. If we exclude symbols which have appeared in higher
\r
243 orders from the probability computation that's called full exclusion.
\r
244 <P><P ALIGN="JUSTIFY">Once we have the probabilities, we code them optimally
\r
245 (respect to the entropy) with arithmetic coding, which is explained in
\r
246 <A HREF="#r.[10]">[10]</A> and <A HREF="#r.[2]">[2]</A>. The range coder,
\r
247 a variant of it is explained in <A HREF="#r.[11]">[11]</A> and the original
\r
248 source code can be found in <A HREF="#r.[12]">[12]</A>.
\r
250 <P><A NAME="Some terminology"></A><FONT SIZE=+2>Some terminology and a
\r
251 brief look to a model</FONT>
\r
252 <BR><P ALIGN="JUSTIFY">This is only a brief look to some terms which may
\r
253 cause problems, for more theory you are encouraged to read <A HREF="#r.[6]">[6]</A>
\r
254 Context are the symbols or symbol which come before or after current one
\r
255 (in ppmc only before). Order-n refers to n bytes of context. In a given
\r
256 message a symbol can appear k times, this is its frequency. From there
\r
257 the model computes its probability, which in ppmc comes in the form of
\r
258 probability/total_probability, like 1/4. Ppmc rescales the frequencies,
\r
259 so they are called counts instead. If we have the message "bacabac" the
\r
260 ppmc model would look like the following if we don't take the escape code
\r
261 in account (bytes in order of appearance).
\r
263 <TABLE BORDER CELLSPACING=2 CELLPADDING=2 >
\r
266 <BR>Context: "bac" list: 'a'-1
\r
267 <BR>Context: "aca" list: 'b'-1
\r
268 <BR>Context: "cab" list: 'a'-1
\r
269 <BR>Context: "aba" list: 'c'-1</TD>
\r
272 <BR>Context: "ba" list: 'c'-2
\r
273 <BR>Context: "ac" list: 'a'-1
\r
274 <BR>Context: "ca" list: 'b'-1
\r
275 <BR>Context: "ab" list: 'a'-1</TD>
\r
280 <BR>Context: "b" list: 'a'-2
\r
281 <BR>Context: "a" list: 'c'-2 'b'-1
\r
282 <BR>Context: "c" list: 'a'-1</TD>
\r
285 <BR>Context: "" list: 'b'-2 'a'-3 'c'-2</TD>
\r
289 <P>Under order-0 the probabilities are: 'a' 3/7, 'b' 2/7 and 'c' 2/7. For
\r
290 more examples, see <A HREF="#r.[6]">[6]</A>.
\r
292 <P><A NAME="Cumulative probabilities"></A><FONT SIZE=+2>Cumulative probabilities
\r
293 and how to manage them</FONT>
\r
294 <BR><P ALIGN="JUSTIFY">Arithmetic coding optimally encodes a symbol given
\r
295 its probability (optimal compared with the entropy, which has been proven
\r
296 to be the minimum, read <A HREF="#r.[1]">[1]</A>). In arithmetic coding
\r
297 we distribute the symbols in a probability line (between 0 and 1), then
\r
298 to encode a symbol we need to know its cumulative probability and its probability.
\r
299 The cumulative probability of the first symbol in the probability line
\r
300 is 0. For any other symbol its cumulative probability is the sum of all
\r
301 the probabilities of the symbols before it. We do so to assign ranges of
\r
302 this probability line to every symbol, and that thus we can latter know
\r
303 which is the encoder symbol, knowing only its cumulative probability.
\r
305 <TABLE BORDER CELLSPACING=2 CELLPADDING=2 >
\r
307 <TD>Symbol: </TD>
\r
321 <TD>Count: </TD>
\r
335 <TD>Probability:</TD>
\r
349 <TD>Cumulative probability: </TD>
\r
365 <TD>[0 , 0.25) </TD>
\r
367 <TD>[0.25 , 0.625) </TD>
\r
369 <TD>[0.625 , 0.625) </TD>
\r
371 <TD>[0.625 , 0.75) </TD>
\r
373 <TD>[0.75 , 1) </TD>
\r
377 <P><P ALIGN="JUSTIFY">In the example above we have in first file the count
\r
378 of the byte, in some cases that could be the frequency. But as we'll see
\r
379 later ppmc uses renormalization, and thus it's the count instead. The second
\r
380 has the probability of the byte, note that 8 is the total count (the sum
\r
381 of all the counts). Then the cumulative probability is computed for every
\r
382 symbol as explained above. The last file has the theorical range assigned
\r
383 for this symbol. The symbol 'c' has an invalid range, however it's supposed
\r
384 that we'll never try to code it (in a real implementation of ppmc instead
\r
385 we would have coded an escape code). When implementing ppmc you don't need
\r
386 to compute the range for the symbols. Arithmetic coding only needs the
\r
387 count of the symbol, its cumulative probability and the total count (the
\r
388 sum of all the counts).
\r
389 <P><P ALIGN="JUSTIFY">Though in my implementation and some other you can
\r
390 find other terms like probability referring to the count, the terms used
\r
391 above are the correct ones. Probability is used to refer to count just
\r
392 because count/total_count is the probability. The total count is also called
\r
393 maximum cumulative probability. Expect different names and misuses not
\r
394 only in my article but also in others, but don't forget the correct names.
\r
395 <P><P ALIGN="JUSTIFY">In the implementation we'll keep tables (or linked
\r
396 lists for orders higher than 1) with the count of every byte. Based on
\r
397 this we have to compute the cumulative probabilities and maximum cumulative
\r
398 probability. We don't need all the cumulative probabilities, only the cumulative
\r
399 probability for the symbol that we want to code (the symbol that we are
\r
400 modeling now). From the explanation of how to compute the cumulative probabilities
\r
401 we can derive the following pseudo code:
\r
404 Symbol_cumulative_probability = 0 //The cumulative probability
\r
405 of the first symbol is 0</LI>
\r
408 For ( counter = 0 ; counter != byte ; ++counter ) //Till
\r
409 we hit the entry of the byte to code</LI>
\r
413 Symbol_cumulative_probability += counts_table[ counter ] //Add
\r
414 the count of the previous bytes</LI>
\r
417 <P ALIGN="JUSTIFY">This is the code used for order-0 and order-1, where
\r
418 a byte's probability can be found in counts_table[byte]. The complexity
\r
419 of this code is O(K) where K is the position of the byte in the table.
\r
420 It's worth mentioning that this is the greatest overhead of simple a arithmetic
\r
421 coding implementation, and also an important part (in time execution) of
\r
422 ppmc. Once the code above is executed and assuming that we have the maximum
\r
423 cumulative probability (as it will be seen later, that's stored in every
\r
424 context) we can code the symbol. In this example counts_table[] stores
\r
425 the counts of the symbols under the current order (which is assumed for
\r
426 simplicity to be 0).
\r
429 symbol_probability = counts_table[ byte ] //Get its count
\r
430 (here called probability)</LI>
\r
433 Arithmetic_encode ( symbol_probability , symbol_cumulative_probability
\r
434 , maximum_cumulative_probability )</LI>
\r
436 <P ALIGN="JUSTIFY">With this information the arithmetic coder can compute
\r
438 <BR>[ symbol_cumulative_probability / maximum_cumulative_probability ,
\r
439 <BR>( symbol_cumulative_probability + symbol_probability ) / maximum_cumulative_probability
\r
441 <BR>And encode the symbol. This is not the point of this article, however
\r
442 note that arithmetic coding compresses best symbols with higher count because
\r
443 it can use all the range to represent this number, for example in the table
\r
444 above 'b' ( [0.25 , 0.625) ) can be represented with 0.25, 0.3, 0.4, 0.5,
\r
445 0.6, 0.6249999, etc.
\r
446 <P><P ALIGN="JUSTIFY">When decoding you need the maximum cumulative probability
\r
447 (which we have assumed to be already know), and the arithmetic decoder
\r
448 will return a cumulative probability. This cumulative probability distinguishes
\r
449 the symbol coded. We have to search it in our table, and then update the
\r
450 arithmetic coding state. As stated before we only store the counts, so
\r
451 we have to compute the cumulative probability on the fly to search our
\r
452 symbol. Let's say that we have the same table as in the previous example:
\r
454 <TABLE BORDER CELLSPACING=2 CELLPADDING=2 >
\r
456 <TD>Symbol: </TD>
\r
470 <TD>Count: </TD>
\r
484 <TD>Cumulative probability: </TD>
\r
498 <P><P ALIGN="JUSTIFY">We need to read till the next byte of the coded one.
\r
499 For example with a cumulative probability of 4 we know that the encoded
\r
500 byte was 'b' (because 4 lands in its range) however to know so we have
\r
501 to read till the 'c', whose cumulative probability is 5, so we can be sure
\r
502 that the decoded byte is the right one, the previous. We'll compare the
\r
503 decoded cumulative probability with the one computed on the fly, when it's
\r
504 higher we can be sure that the previous byte was the encoded one. But what
\r
505 about if both have the same value? in this case we can't be sure. Let's
\r
506 say we have encoded a 'd', the cumulative probability is 5, but when decoding
\r
507 if we stop comparing when they are the same, we would decode a 'c' which
\r
508 is wrong. If we however stop only when the computed one is greater, we
\r
509 would stop in the 'e' and thus correctly decode a 'd' (the previous symbol).
\r
510 We have to do so because we have to care about both the lower and higher
\r
511 bound. Having all the previous in mind we do the following decoding routine:
\r
514 Decoded_cumulative_probability = arithmetic_decode ( maximum_cumulative_probability
\r
515 ) //Decode it</LI>
\r
518 On_the_fly_cumulative_probability = 0 //First symbol
\r
519 has a cumulative probability of 0</LI>
\r
522 For ( counter = 0 ; counter != 256 ; ++counter ) //Search
\r
523 symbol based on cumulative probability</LI>
\r
527 If ( Decoded_cumulative_probability < on_the_fly_cumulative_probability
\r
528 ) //Check upper bound</LI>
\r
532 break; //We are sure that the encoded byte is the previous</LI>
\r
536 On_the_fly_cumulative_probability += counts_table[ counter ] //Make
\r
537 cumulative probability</LI>
\r
541 Decoded_byte = counter-1 //Once the loop is breaked we
\r
542 know that the decoded byte is the previous one</LI>
\r
544 <P ALIGN="JUSTIFY">In this code we compute the cumulative probability (on_the_fly_cumulative_probability)
\r
545 only for the current symbol in each step, because we don't need the cumulative
\r
546 probability of symbols which are in positions after the byte to decode.
\r
547 Note that this code is the same as for any simple order-0 arithmetic coding
\r
548 implementation. And that they use a table where the entry of a byte is
\r
549 the value of the byte itself (the count of 'byte' is in count_table[byte]).
\r
550 Due to this at the end of this routine we decide that the decoded byte
\r
551 is counter-1, because counter is the current one and counter-1 is the previous,
\r
552 note that the symbols are in order. In linked lists this will be different,
\r
553 but we'll see this later. We already know the decoded byte thus we know
\r
554 its probability and cumulative probability, so we can update the state
\r
555 of the arithmetic coder.
\r
556 <P><P ALIGN="JUSTIFY">To save some space in higher order tables we may
\r
557 want to reduce the size of the count. For lower orders we can use double words
\r
558 (32 bits) but for higher orders is better to use only a byte (8 bits).
\r
559 Every time the count is incremented we have to check that it isn't the
\r
560 maximum, if it is we have to halve all the counts. We divide all of them
\r
561 by a factor of 2. This is called renormalization or rescaling. In the case
\r
562 of linked lists we don't want that the count of a byte is 0, so when this
\r
563 happens, we change its value to 1. Renormalization does not only save space
\r
564 but also increases compression a little bit. That is because the probabilities
\r
565 of text change within a file, thus giving more importance to newer frequencies
\r
566 improve compression, because it reflects the changes in the source (the
\r
567 probabilities of the file).
\r
569 <P><A NAME="Escape method C"></A><FONT SIZE=+2>Escape method C, how to
\r
570 compute and use it</FONT>
\r
571 <BR><P ALIGN="JUSTIFY">The escape method C was already discussed at <A HREF="#r.[6]">[6]</A>
\r
572 and can be also found in <A HREF="#r.[2]">[2]</A>. I'll recall the example
\r
573 table, where a symbol ('c') had a count of 0. In ppmc we'll suppose that
\r
574 all the orders are initially empty (unless the order-(-1)), when we want
\r
575 to code in any order that is totally empty we just don't code anything.
\r
576 But what happens if there's only one symbol or just a few? how can we transmit
\r
577 to the decoder that the byte that we want to finally decode is not present
\r
578 in this table? For doing this we use the escape code. Both compressor and
\r
579 decompressor assign the same probability to the escape code. There are
\r
580 different methods for estimating the escape probability. Ppmc uses the
\r
581 escape method called 'C' (and that's why it's called ppmc) Method C assigns
\r
582 a count to the escape code equal to the number of different symbols that
\r
583 have appeared under this context. For practical issues we assume that
\r
584 the escape code is the last one. We also have to take care of its probability
\r
585 when coding. Let's see the table that we are using for examples, how it
\r
586 is without using escape code and with it:
\r
587 <CENTER><TABLE BORDER=0 CELLSPACING=2 CELLPADDING=2 >
\r
590 <TABLE BORDER CELLSPACING=2 CELLPADDING=2 >
\r
592 <TD>Symbol: </TD>
\r
606 <TD>Count: </TD>
\r
620 <TD>Cumulative probability: </TD>
\r
634 <CENTER>Without escape code (total_cump=8)</CENTER>
\r
640 <TABLE BORDER CELLSPACING=2 CELLPADDING=2 >
\r
642 <TD>Symbol: </TD>
\r
658 <TD>Count: </TD>
\r
674 <TD>Cumulative probability: </TD>
\r
690 <CENTER>With escape code (total_cump=12)</CENTER>
\r
694 <P ALIGN="JUSTIFY">As I have said before, in every context we'll store
\r
695 the maximum cumulative probability. Also we'll store the number of different
\r
696 bytes (which in my implementation is called defined_bytes). Due to this
\r
697 I call the maximum cumulative probability "max_cump", but because
\r
698 we also have to take in account the code space of the escape code,
\r
699 I have another variable called "total_cump", which is the maximum cumulative
\r
700 probability plus the count of the escape code (which for method C is the
\r
701 number of different bytes), this is the value which must be using when
\r
702 calling the decoding functions.
\r
703 <P><P ALIGN="JUSTIFY">But how does the escape code affect to coding and
\r
704 decoding? In encoding before trying to make the cumulative probability
\r
705 of the current byte and coding it, we have to check that it exists or that
\r
706 it has a non zero probability. If everything is ok then we can code it,
\r
707 otherwise the context is present but the byte is not, so we have to code
\r
708 an escape code. We know the probability (which comes from the count) of
\r
709 the escape code, it's simply the number of defined bytes in that context.
\r
710 But what about its cumulative probability? Due to how the cumulative probabilities
\r
711 are computed and also due to the fact that we assume the escape code to
\r
712 be the last symbol, the cumulative probability of the escape code is the
\r
713 maximum cumulative probability.
\r
714 <BR>"max_cump" is the total count before adding it the escape code's count.
\r
715 If you have a look at the table above, you'll see that max_cump is 8, and
\r
716 that the escape code's cumulative probability is also 8. Taking all those
\r
717 facts in account we use the following pseudo code:
\r
720 If ( counts_table[ counter ] != 0 ) //Check if it has
\r
721 a 0 count, in that case we can't code it</LI>
\r
725 Code byte as usual</LI>
\r
729 Else //Otherwise we have to code an escape code</LI>
\r
733 symbol_probability = defined_bytes //The count of the
\r
734 escape code is the number of different bytes</LI>
\r
737 symbol_cumulative_probability = maximum_cumulative_probability</LI>
\r
740 total_cumulative_probability = maximum_cumulative_probability + symbol_probability
\r
741 //The total count</LI>
\r
744 Arithmetic_encode ( symbol_probability , symbol_cumulative_probability
\r
745 , total_cumulative_probability )</LI>
\r
748 <P ALIGN="JUSTIFY">In the case of decoding we have to check if the coded
\r
749 symbol is an escape code, we do so based on its cumulative probability
\r
750 (which is stored) otherwise decode as usual:
\r
753 Decoded_cumulative_probability = arithmetic_decode ( total_cumulative_probability
\r
754 ) //Decode it</LI>
\r
757 If ( Decoded_cumulative_probability > maximum_cumulative_probability )</LI>
\r
761 Fallback to lower order //Escape code, byte not present
\r
762 in current context</LI>
\r
770 Decode byte as usual</LI>
\r
774 <P><BR><A NAME="Linked lists"></A><FONT SIZE=+2>Linked lists for the counts
\r
775 of the bytes</FONT>
\r
776 <BR><P ALIGN="JUSTIFY">All the algorithms used above work only if we have
\r
777 all the symbols in order and in a table where the entry of 'byte' is in
\r
778 count_table[byte]. This is a good idea for order-0 and order-1 where the
\r
779 tables may take up to 1,024 and 262,144 bytes respectively (in case we
\r
780 use double words (32 bits) for the count). But this is not acceptable for
\r
781 order-2 which would need 67,108,864 bytes to hold all the tables (256*256*256*4).
\r
782 For higher orders the amount of memory is not available nowadays. Moreover
\r
783 due to the fact that there are less high context than lower ones, most
\r
784 of the entries are not used. The solution to both problems is using a linked
\r
785 list for storing the counts. A linked list is made of different elements,
\r
786 every element has its own value and a pointer to the next element. We store
\r
787 on it the count, and also the byte. In the case of tables (which in fact
\r
788 were hash tables with direct addressing) we knew the value of a byte by
\r
789 its entry, now we don't, so we have to store the value of the byte too.
\r
790 The last element in the linked list, has a pointer with a value of 0, meaning
\r
791 that it's the last one. Using linked list we can dynamically allocate memory
\r
792 only for the entries that we are going to use. Let's have a look at our
\r
793 table of example, which now is a linked lists:
\r
801 <TABLE BORDER CELLSPACING=2 CELLPADDING=2 >
\r
803 <TD>Byte </TD>
\r
805 <TD>Count </TD>
\r
807 <TD>Pointer </TD>
\r
821 <TABLE BORDER CELLSPACING=2 CELLPADDING=2 >
\r
823 <TD>Byte </TD>
\r
825 <TD>Count </TD>
\r
827 <TD>Pointer </TD>
\r
841 <TABLE BORDER CELLSPACING=2 CELLPADDING=2 >
\r
843 <TD>Byte </TD>
\r
845 <TD>Count </TD>
\r
847 <TD>Pointer </TD>
\r
861 <TABLE BORDER CELLSPACING=2 CELLPADDING=2 >
\r
863 <TD>Byte </TD>
\r
867 <TD>Pointer </TD>
\r
882 <CENTER>Linked list form</CENTER>
\r
893 <TD><P ALIGN="JUSTIFY">As you can see in linked list form, there's no entry
\r
894 for 'c' because it has not appeared, in our example the linked list is
\r
895 sorted, but in the implementation you'll find them in order of appearance,
\r
896 the first that appeared will be the first in the linked list.
\r
897 <P><P ALIGN="JUSTIFY">In my implementation I kept a <A HREF="#Memory requeriments and management">buffer</A>
\r
898 where new nodes were allocated. Once this buffer was full, another one
\r
899 was allocated. The pointers to all the allocated buffers were stored in
\r
900 one array. When compression or decompression is done, all the allocated
\r
901 buffers are freed.</TD>
\r
904 <TABLE BORDER CELLSPACING=2 CELLPADDING=2 >
\r
906 <TD>Symbol: </TD>
\r
920 <TD>Count: </TD>
\r
934 <CENTER>Table form</CENTER>
\r
939 <P>The data structure of a linked list in C is the following:
\r
940 <BR>struct _byte_and_freq
\r
942 <BR>unsigned char byte; //The value of the byte
\r
943 <BR>unsigned char freq; //The count of the byte
\r
944 <BR>struct _byte_and_freq *next; //Pointer to the next
\r
945 node in the linked list
\r
947 <P><P ALIGN="JUSTIFY">In a linked list new nodes are stored at the end.
\r
948 For example if we had to put 'c' in the list, we should read the linked
\r
949 list till the end, once at the end, allocate memory for this new buffer.
\r
950 Then put in the node of 'e' a pointer to this new location. The new element
\r
951 should have the following values: byte 'c', count 1, pointer 0. Its pointer
\r
952 is 0 because now it is the last element in the linked list. In our implementation
\r
953 we don't need to delete nodes of the linked list, so we make it even easier.
\r
955 <P><A NAME="Coding and decoding with linked lists"></A><FONT SIZE=+2>Coding
\r
956 and decoding with linked lists</FONT>
\r
957 <BR><P ALIGN="JUSTIFY">For coding we need to know if a given byte is present
\r
958 in the linked list, if it is we can code it. To check if it's present,
\r
959 we have to read the whole linked list till we find it or reach the end.
\r
960 When implementing this we'll already have a pointer to the first element,
\r
961 so we we'll assume so. Checking all the elements is only a matter of reading
\r
962 current one, if it's not the one we are looking for, get the pointer to
\r
963 the next, and so on, till we hit the end of the linked list. The pseudo
\r
964 code is like the following:
\r
967 Pointer_ll = first_element_in_ll //Initialize pointer
\r
968 to the first node in the linked list</LI>
\r
971 While ( 1 ) //Loop break would be done in the body of
\r
976 If ( pointer_ll->byte = byte ) //If the byte to code
\r
977 and byte are equals</LI>
\r
981 Goto _byte_found //Execute the code which we have to</LI>
\r
985 If ( pointer_ll->next = 0 ) //If this is the last element
\r
986 in the linked list</LI>
\r
990 Goto _byte_not_found //Execute the proper code</LI>
\r
994 <A NAME="Coding and decoding with linked lists.coding"></A><P ALIGN="JUSTIFY">For
\r
995 the readers who don't know the C language, pointer_ll->byte, means accessing
\r
996 the value called 'byte' in the data structure addressed by the pointer
\r
997 'pointer_ll'. We also need to know the cumulative probability of the byte,
\r
998 to do so we need the code explained before. We have to read all the elements
\r
999 till the byte. Both the code needed for searching a symbol and checking
\r
1000 if it's present and the code for making the cumulative probability do the
\r
1001 same. So why not merging them? In the same loop we have to check if the
\r
1002 byte is present or not and compute its cumulative probability, for the
\r
1003 case that it is present. Later we'll have to update the count of this byte,
\r
1004 and because we want to avoid having to read the linked list again, we store
\r
1005 the pointer in a global variable. But if the byte is not present when we
\r
1006 update we'll have to add a new pointer to the end of the linked list, for
\r
1007 that case we store a pointer to the last element.
\r
1010 Symbol_cumulative_probability = 0 //The cumulative probability
\r
1011 of the first symbol is 0</LI>
\r
1014 Pointer_ll = first_element_in_ll //Initialize pointer
\r
1015 to the first node in the linked list</LI>
\r
1020 While ( 1 ) //Loop break would be done in the body of
\r
1025 If ( pointer_ll->byte = byte ) //If the byte to code
\r
1026 and byte are equals</LI>
\r
1030 Goto _byte_found //Execute the code which we have to</LI>
\r
1034 Symbol_cumulative_probability += pointer_ll->byte //Add
\r
1035 to the cump the count of the byte</LI>
\r
1038 If ( pointer_ll->next = 0 ) //If this is the last element
\r
1039 in the linked list</LI>
\r
1043 Goto _byte_not_found //Execute the proper code</LI>
\r
1050 _byte_not_found: //Because it was not found, code an
\r
1054 symbol_probability = defined_bytes //The count of the
\r
1055 escape code is the number of different bytes</LI>
\r
1058 symbol_cumulative_probability = maximum_cumulative_probability</LI>
\r
1061 total_cumulative_probability = maximum_cumulative_probability + symbol_probability
\r
1062 //The total count</LI>
\r
1065 Arithmetic_encode ( symbol_probability , symbol_cumulative_probability
\r
1066 , total_cumulative_probability )</LI>
\r
1069 o2_ll_node = Pointer_ll Save pointer to last element
\r
1070 in linked list for updating.</LI>
\r
1078 _byte_found: //The byte was found in the linked list,
\r
1079 thus we can code it</LI>
\r
1082 symbol_probability = pointer_ll->freq //Get its count,
\r
1083 cump already computed</LI>
\r
1086 Arithmetic_encode ( symbol_probability , symbol_cumulative_probability
\r
1087 , total_cumulative_probability )</LI>
\r
1090 o2_ll_node = Pointer_ll //Save pointer to current element,
\r
1091 when updating its count will be be incremented</LI>
\r
1097 <P><BR><A NAME="Coding and decoding with linked lists.update"></A><P ALIGN="JUSTIFY">Updating
\r
1098 the count of a byte with tables was done just by accessing its entry. For
\r
1099 linked list we don't know its position beforehand, so we have to search
\r
1100 it in the linked list, when found, update its count. But in fact we know
\r
1101 its position: when we code the symbol we need to read the linked list,
\r
1102 so if we keep a pointer to it, we'll not need to read the whole linked
\r
1103 list again. As I've explained before, the linked list nodes are allocated
\r
1104 in a big buffer, to avoid having to call the functions of memory allocation
\r
1105 for every new node. When updating we have to check whatever the encoder
\r
1106 emitted an escape code or a byte. One could think that we could check if
\r
1107 the pointer of the node (o2_ll_node) is 0, in that case this is the last
\r
1108 element and thus the end of the linked list was reached. But this is false.
\r
1109 Imagine that we found the byte but it was in the last position, in that
\r
1110 case the pointer is also 0. The solution is to check if the byte is the
\r
1111 same, that unambiguously distinguishes between the two cases. In all the
\r
1112 examples before we assumed that max_cump and defined_bytes were stored
\r
1113 in the context, now we have to update them aswell. As long as we have coded
\r
1114 the byte (or an escape) with the code above, the following pseudo code
\r
1115 would update the model.
\r
1118 If ( o2_ll_node->byte = byte ) //Check if byte
\r
1123 o2_ll_node->freq ++ //Increment its probability. It was
\r
1127 Context->max_cump ++ //Increment maximum cumulative probability
\r
1128 stored in this context</LI>
\r
1131 If ( o2_ll_node->freq = 255 ) <FONT COLOR="#33CCFF"> </FONT>//Check
\r
1132 if its the maximum that a byte can hold</LI>
\r
1136 Renormalize ( ) <FONT COLOR="#33CCFF"> </FONT>//In that
\r
1137 case renormalize current order. (in the example it's supposed to be order-2)</LI>
\r
1145 Else //Byte was not present, we have to create a new
\r
1146 node in the end of the linked list</LI>
\r
1150 o2_ll_node->pointer = allocate_memory_in_buffer //In my implementation
\r
1151 I use big buffers</LI>
\r
1154 update_pointers_to_buffer ( ) //Update memory management
\r
1158 new_location->byte = byte //'byte' is the new byte to
\r
1162 new_location->freq = 1 //As it is new, its count is 1</LI>
\r
1165 new_location->pointer = 0 //Now this is the last element
\r
1166 in the linked list</LI>
\r
1169 Context->max_cump ++ //Increment maximum cumulative probability
\r
1170 stored in this context</LI>
\r
1173 Context->defined_bytes ++ //A new byte in this context</LI>
\r
1179 <A NAME="Coding and decoding with linked lists.decoding"></A>Let's say
\r
1180 we have again our example, in linked list form, and not in order (as in
\r
1181 a real implementation it would).
\r
1185 <TABLE BORDER CELLSPACING=2 CELLPADDING=2 >
\r
1187 <TD>Byte </TD>
\r
1189 <TD>Count </TD>
\r
1191 <TD>Pointer </TD>
\r
1207 <TABLE BORDER CELLSPACING=2 CELLPADDING=2 >
\r
1209 <TD>Byte </TD>
\r
1211 <TD>Count </TD>
\r
1213 <TD>Pointer </TD>
\r
1229 <TABLE BORDER CELLSPACING=2 CELLPADDING=2 >
\r
1231 <TD>Byte </TD>
\r
1233 <TD>Count </TD>
\r
1235 <TD>Pointer </TD>
\r
1251 <TABLE BORDER CELLSPACING=2 CELLPADDING=2 >
\r
1253 <TD>Byte </TD>
\r
1255 <TD>Count </TD>
\r
1257 <TD>Pointer </TD>
\r
1271 Such a linked list would produce a table like the following:
\r
1272 <TABLE BORDER CELLSPACING=2 CELLPADDING=2 >
\r
1274 <TD>Symbol: </TD>
\r
1298 <TD>Cumulative probability: </TD>
\r
1309 <P ALIGN="JUSTIFY">However as I've explained before we don't need to actually
\r
1310 build this table, only as much as needed. Linked lists are a little bit
\r
1311 more difficult to manage than tables for decoding, mainly in the search
\r
1312 (when we have to get the previous symbol). Also another problem is in updating:
\r
1313 we can't ensure that the pointer (in case of an escape code) points to
\r
1314 the last element, because the decoding routine doesn't need to read the
\r
1315 linked list to identify an escape code. The latter problem has no other
\r
1316 solution that reading the whole linked list when updating and an escape
\r
1317 code was emitted. However the second has two solutions. Remember that we
\r
1318 have to read till the next byte of the one to decode? at first glance one
\r
1319 could think that like we did with the tables we have to read till the next
\r
1320 symbol. But then how do we get the previous? in that case we should have
\r
1321 a variable which always has the last byte in the linked list. Fortunately
\r
1322 there's a better solution. Why do why need to read the next element? because
\r
1323 we need to know the upper bound of the cumulative probability. For tables
\r
1324 the fastest (and thus it was used) way is reading the next element's cumulative
\r
1325 probability. However for linked lists its better to sum to the current
\r
1326 cumulative probability the count of the byte. That way we also have the
\r
1327 upper bound. Then we can check if we have to stop. And the node pointer
\r
1328 will point to the byte that we have to decode.
\r
1331 Decoded_cumulative_probability = arithmetic_decode ( maximum_cumulative_probability
\r
1332 ) //Decode it</LI>
\r
1335 Pointer_ll = first_element_in_ll //Initialize pointer
\r
1336 to the first node in the linked list</LI>
\r
1339 On_the_fly_cumulative_probability = 0 //First symbol
\r
1340 has a cumulative probability of 0</LI>
\r
1343 While ( 1 ) //Break condition in the body of the loop</LI>
\r
1347 on_the_fly_cumulative_probability += Pointer_ll->freq //Cump,
\r
1348 currently upper bound of current byte's range</LI>
\r
1351 If ( Decoded_cumulative_probability < on_the_fly_cumulative_probability
\r
1352 ) //Check upper bound</LI>
\r
1356 break; //We are sure that the encoded byte is the current
\r
1362 Decoded_byte = Pointer_ll->byte //Get current byte</LI>
\r
1365 Symbol_prob = Pointer_ll->freq //The count, probability
\r
1366 for updating the state</LI>
\r
1369 Symbol_cumulative_probability = on_the_fly_cumulative_probability - Symbol_prob
\r
1370 //Lower bound of range</LI>
\r
1373 Arithmetic_decoding_update_state ( )</LI>
\r
1375 <P ALIGN="JUSTIFY">To avoid problems when using linked lists for cumulative
\r
1376 probabilities, we don't allow any count to be 0. When renormalizing we
\r
1377 check if it's 0, in this case we put the value of 1.
\r
1379 <P><A NAME="Hash tables"></A><FONT SIZE=+2>Hash tables for contexts</FONT>
\r
1380 <BR><P ALIGN="JUSTIFY">Hash tables are arrays used to store and find items.
\r
1381 A hash table which allows direct addressing has one entry for every item.
\r
1382 This is obviously very memory consuming if the number of items is big.
\r
1383 In the cases where direct addressing is not possible, we use chaining for
\r
1384 resolving collisions (collisions are two or more contexts sharing the same
\r
1385 hash entry). The item of the hash table instead is a pointer to a linked
\r
1386 list. This linked list contains the different contexts. The value of the
\r
1387 context itself is stored for checking. Also we store a pointer to the linked
\r
1388 list with the bytes and counts. One hash table is used for every order.
\r
1389 Hash tables and linked list for contexts are only used for orders above
\r
1391 <P><P ALIGN="JUSTIFY">Let's say we have a hash table for order-1 which
\r
1392 has only two entries. And we have a hash function which maps the items
\r
1393 in the following way: 'a','b','c' entry 1. 'd', 'e', 'f' entry 2. After
\r
1394 having stored the contexts 'e','b','d','a','c' it would look like the following:
\r
1396 <TABLE BORDER CELLSPACING=2 CELLPADDING=2 >
\r
1398 <TD>Hash entry </TD>
\r
1400 <TD>Value </TD>
\r
1406 <TD>Pointer to linked list, element 'b' </TD>
\r
1412 <TD>Pointer to linked list, element 'e' </TD>
\r
1416 <P>Big memory buffer for linked lists:
\r
1420 <TABLE BORDER CELLSPACING=2 CELLPADDING=2 >
\r
1422 <TD>Byte </TD>
\r
1424 <TD>Pointer </TD>
\r
1438 <TABLE BORDER CELLSPACING=2 CELLPADDING=2 >
\r
1440 <TD>Byte </TD>
\r
1442 <TD>Pointer </TD>
\r
1456 <TABLE BORDER CELLSPACING=2 CELLPADDING=2 >
\r
1458 <TD>Byte </TD>
\r
1460 <TD>Pointer </TD>
\r
1474 <TABLE BORDER CELLSPACING=2 CELLPADDING=2 >
\r
1476 <TD>Byte </TD>
\r
1478 <TD>Pointer </TD>
\r
1492 <TABLE BORDER CELLSPACING=2 CELLPADDING=2 >
\r
1494 <TD>Byte </TD>
\r
1496 <TD>Pointer </TD>
\r
1509 <P><A NAME="Hash tables.context structure"></A>The structure of a context
\r
1510 node in a linked list is:
\r
1511 <BR>struct context
\r
1513 <BR>struct context *next; //Next context in the linked
\r
1514 list (corresponding to this hash entry)
\r
1515 <BR>unsigned long order4321; //Order-4-3-2-1 (or order-3-2-1
\r
1516 for order-3), that's the value of the context
\r
1517 <BR>struct _byte_and_freq *prob; //Pointer to linked
\r
1518 lists containing bytes and counts of this context
\r
1519 <BR>unsigned int max_cump; //Maximum cumulative probability
\r
1521 <BR>unsigned int defined_bytes; //The number of bytes
\r
1524 <P><P ALIGN="JUSTIFY">Note that we could reduce the space needed by using
\r
1525 a byte (unsigned char) instead of a double word (unsigned int or unsigned
\r
1526 long, 32 bits) for the
\r
1527 number of bytes in the context, however then we should add 1 every time
\r
1528 we read this value (to make 0 represent 1 instead, and so on). I decided
\r
1529 to not make the code more difficult to read. Thus this is not implemented
\r
1530 in my ppmc implementation. See the section of<A HREF="#Fast order-3 hashed.hash explanation">
\r
1531 fast order-3 hashed</A> for another example.
\r
1532 <P><P ALIGN="JUSTIFY">The code for managing the linked lists with contexts
\r
1533 is the same as the code for the counts and bytes. For contexts, the value
\r
1534 that makes every element different is "order4321" instead of "byte". When
\r
1535 we want to read the counts of a context, we have to read the pointer in
\r
1536 its hash entry. If this entry is empty, the context was not initialized
\r
1537 yet, so we fallback to the next lower order without emitting escape code.
\r
1538 Then use this pointer to search current context in the linked list of contexts,
\r
1539 if it's not present we also have to fallback without escape code. In case
\r
1540 we found it, we'll read the pointer to the linked list with the bytes and
\r
1541 counts. Because we already know the maximum cumulative probability, and
\r
1542 the number of defined bytes, we can code the byte as explained before.
\r
1543 But let's have a look at the implementation.
\r
1544 <P><P ALIGN="JUSTIFY">The first function called by both encoding and decoding
\r
1545 functions is "ppmc_get_totf_order3". Thus this is the function which is
\r
1546 going to read the linked list with contexts and ensure that the current
\r
1547 one is present. The first thing is to do the hash key. After that we need
\r
1548 to have the context in a variable, in that case because it's order-3, an
\r
1549 unsigned long is ok, if we want higher orders, say 6, we would have order-4-3-2-1
\r
1550 in an unsigned long, and the rest, order-6-5 in another one. We'll use
\r
1551 this variable for comparing while searching for the context.
\r
1554 o3_cntxt=ppmc_order3_hash_key(o1_byte,o2_byte,o3_byte);</LI>
\r
1557 full_o3_cntxt=(o1_byte)+(o2_byte<<8)+(o3_byte<<16);
\r
1560 <P ALIGN="JUSTIFY">The first thing to check is that current entry in the
\r
1561 hash table for this order is initialized. The table is initialized to 0,
\r
1562 so if current entry is 0, it's not initialized, otherwise it would have
\r
1563 a pointer. If it isn't we can be sure that there's no context in this entry,
\r
1564 so we have to abort. "ppmc_get_totf_order3" unlike functions for lower
\r
1565 orders returns a value. I decided to make it return a 0 in case that the
\r
1566 hash entry was not initialized or the context not present, and a 1 in case
\r
1570 if(order3_hasht[o3_cntxt]==0) //if 0 the entry is not initialized</LI>
\r
1574 o3_context=0; //no hash entry</LI>
\r
1577 return 0; //hash entry not initialized</LI>
\r
1580 <P ALIGN="JUSTIFY">Now we get the pointer from the entry to the linked
\r
1581 list with contexts and store it in "cntxt_node". And now we have to read
\r
1582 all the linked list till we find current context, if we reach the end before
\r
1583 we find it, the context is not present and thus we have to return a 0,
\r
1584 so the encoding or decoding functions know that they can't code in this
\r
1588 cntxt_node=order3_hasht[o3_cntxt];</LI>
\r
1595 if(cntxt_node->order4321==full_o3_cntxt) //compare
\r
1600 goto ppmc_gtf_cntxt_found;</LI>
\r
1604 if(cntxt_node->next==0) //end of context's
\r
1613 cntxt_node=cntxt_node->next; //next element</LI>
\r
1617 // Once there the context was not found</LI>
\r
1620 o3_context=cntxt_node; //pointer to last element in the
\r
1624 return 0; //it was not present</LI>
\r
1626 <P ALIGN="JUSTIFY">Once we know that the context is present we have to
\r
1627 return the total cumulative probability. Note that this is different for
\r
1628 <A HREF="#Full exclusion">full exclusions</A>.
\r
1631 // The context is found, so return pointer and cump</LI>
\r
1634 ppmc_gtf_cntxt_found:</LI>
\r
1637 o3_context=cntxt_node;</LI>
\r
1640 // Total cump is current total cump plus the escape for the escape code</LI>
\r
1643 total_cump=o3_context->defined_bytes+o3_context->max_cump;</LI>
\r
1646 return 1; //context found</LI>
\r
1648 <P ALIGN="JUSTIFY">Now encoding and decoding functions would be able to
\r
1649 do their job. After that we have to update the count of current byte. Now
\r
1650 we rely on the fact that "o3_cntxt" and "full_o3_cntxt" are initialized.
\r
1651 While updating four different cases can happen:
\r
1654 Hash entry was not initialized.</LI>
\r
1657 Symbol was coded under current context.</LI>
\r
1660 An escape code was emitted.</LI>
\r
1663 Current context was not present in the linked list.</LI>
\r
1665 <A NAME="Hash tables.new"></A><P ALIGN="JUSTIFY">In the first case we have
\r
1666 to create a new node in the linked list of context in the current hash
\r
1667 entry. The way we allocate memory is explained in the section about <A HREF="#Memory requeriments and management">memory
\r
1668 management</A>. Then we have to initialize this node, and also put pointer
\r
1669 to this new node in the hash table. After that we have to put a new symbol
\r
1670 in the linked list with probabilities, see the section about <A HREF="#Coding and decoding with linked lists.update">linked
\r
1671 lists</A> for that matter. The code is like the following:
\r
1674 order3_hasht[o3_cntxt]=allocate_memory_in_buffer;</LI>
\r
1677 _context_pool->next=0; //this is the
\r
1681 _context_pool->order4321=full_o3_cntxt; //put
\r
1685 _context_pool->prob=allocate_memory_in_buffer;
\r
1686 //pointer to linked list</LI>
\r
1689 _context_pool->max_cump=1;</LI>
\r
1692 _context_pool->defined_bytes=1;</LI>
\r
1695 //Put new byte and count in the linked list</LI>
\r
1697 <P ALIGN="JUSTIFY">If the byte was coded under current context we just
\r
1698 have to update its count. We can assume that "o3_ll_node" and "o3_context"
\r
1699 are initialized, so the code becomes as easy as that:
\r
1702 o3_ll_node->freq++; //increment its frequency</LI>
\r
1705 o3_context->max_cump++; //total cump</LI>
\r
1708 if(o3_ll_node->freq==255) //do we have to renormalize?</LI>
\r
1712 ppmc_renormalize_order3(); //renormalize</LI>
\r
1715 <P ALIGN="JUSTIFY">Once the two first cases have been discarded, it may
\r
1716 happen that an escape occurred or that In the third case an escape code
\r
1717 has to be coded because current context was not present in the linked list
\r
1718 of context. Because the case of an uninitialized hash entry was already
\r
1719 discarded we can be sure that there's at least one context in the linked
\r
1720 list of current hash entry for contexts. The way to know which one of those
\r
1721 cases is to check the context in the pointer, if it's the same as the current
\r
1722 one we can be sure that an escape was coded, because in that case the context
\r
1723 existed, and we already discarded the case that the byte was coded under
\r
1727 if(o3_context->order4321==full_o3_cntxt) //check if that's the last</LI>
\r
1731 do the updating for the case of an escape code</LI>
\r
1739 do the updating for the case that current context didn't exist</LI>
\r
1742 <P ALIGN="JUSTIFY">Otherwise we know that it's pointing to the last element
\r
1743 in the linked list of contexts, because when looking for current context,
\r
1744 it wasn't found so it reached the end of the linked list, and also updated
\r
1745 the variable "o3_context". But however we know that the context was present
\r
1746 (because there was at least 1 symbol). Thus the only thing to do is to
\r
1747 create a new node in the linked list for bytes and probabilities as shown
\r
1748 in the section of <A HREF="#Coding and decoding with linked lists.update">linked
\r
1750 <P><P ALIGN="JUSTIFY">In the fourth case the context was not present in
\r
1751 the linked list corresponding to this hash entry. What we do is reading
\r
1752 till the end of the linked list for context (though I think this is not
\r
1753 really needed) and then put a new node as explained <A HREF="#Hash tables.new">above</A>,
\r
1754 with the only difference that the pointer is stored in the last element
\r
1755 in the linked list instead in the hash entry of the current order.
\r
1757 <P><A NAME="Global variables"></A><FONT SIZE=+2>Global variables</FONT>
\r
1758 <BR><P ALIGN="JUSTIFY">In some cases (unbounded length contexts) we need
\r
1759 to have the whole file loaded in a buffer. However in this implementation
\r
1760 the maximum context that we need is order-4 (but we could very easily extent
\r
1761 this to order-8, at the cost of speed and memory, though). Thus we store
\r
1762 the contexts in another way. Because C has some restrictions, we store
\r
1763 the contexts in unsigned chars. One unsigned char for every byte, order-1
\r
1764 is stored in o1_byte, order-2 is stored in o2_byte and so on. Thus is we
\r
1765 have the context "ther", o1_byte = 'r', o2_byte = 'e', o3_byte =
\r
1766 'h', o4_byte = 't'. If the next byte to code is an 'e', after coding it,
\r
1767 the context would be: o1_byte = 'e', o2_byte = 'r', o3_byte = 'e',
\r
1768 o4_byte = 'h'. In assembly language we could store the whole order-4 in
\r
1769 a double word (32 bits), and then just read a byte for order-1 and so on.
\r
1770 <P><P ALIGN="JUSTIFY">In high orders (3,4) we need to have the hash entry
\r
1771 and also the full context so we can compare it when finding the context
\r
1772 in the linked list. In the case of order-3 we have "o3_cntxt" which contains
\r
1773 the hash key used to index in the order-3 hash table. And "full_o3_cntxt"
\r
1774 which contains all the order-3. In the previous example "o3_cntxt" depends
\r
1775 on the hash function, and "full_o3_cntxt" = "ere". For order-4 only the
\r
1776 number changes, that is "o4_cntxt" instead of "o3_cntxt".
\r
1777 <P><P ALIGN="JUSTIFY">For making the code easier to read, the arithmetic
\r
1778 coding routines (range coder) are called with the same variables. They
\r
1779 are: total_cump with the total cumulative probability, symb_cump symbol
\r
1780 cumulative probability, and symb_prob the probability (count) of the symbol.
\r
1781 <P><P ALIGN="JUSTIFY">Ppmc uses update exclusion. That is we only update
\r
1782 in the order where the byte was coded and higher ones. In my implementation
\r
1783 I use a variable called "coded_in_order" whose value is where the byte
\r
1784 was coded. If the byte was coded under order 3 the value of "coded_in_order"
\r
1785 will be 3. If it was coded in order-(-1) its value will be 0 though. It
\r
1786 has a 0 value to update the right orders. The code in C used for updating
\r
1788 <P>switch(coded_in_order)
\r
1789 <BR> {
\r
1790 <BR> case 0: ppmc_update_order0();
\r
1791 <BR> case 1: ppmc_update_order1();
\r
1792 <BR> case 2: ppmc_update_order2();
\r
1793 <BR> case 3: ppmc_update_order3();
\r
1794 <BR> case 4: ppmc_update_order4();
\r
1795 <BR> default: break;
\r
1796 <BR> };
\r
1797 <P><P ALIGN="JUSTIFY">Which means that if the value of coded_in_order
\r
1798 is 0, all the functions for updating will be called. And if it's 3 then
\r
1799 only the functions for order-3 and order-4 will be called.
\r
1800 <P><P ALIGN="JUSTIFY">For memory usage I use "ppmc_out_of_memory". If it's
\r
1801 0 then there's still memory available. If it's 1 there's not. Every function
\r
1802 which needs to allocate memory aborts in the case its value is 1. Once
\r
1803 we have a problem allocating memory, this variable is set to 1. At the
\r
1804 end of the loop we check this variable, and in case it's 0 we flush the
\r
1805 model. This is explained in the section of <A HREF="#Memory requeriments and management.flushing">memory
\r
1807 <P><P ALIGN="JUSTIFY">Before starting to model and code the input we have
\r
1808 to reinitialize the model. The main job is to allocate the memory needed
\r
1809 for the hash tables and linked lists. Moreover tables from low orders,
\r
1810 like order-0 and order-1 must be cleared, that is all the counts must have
\r
1811 a value of 0. The hash tables of high orders must be cleared too, that
\r
1812 is we must put a value of 0 in the offsets stored. Apart from that we
\r
1813 have to care about initialising the context variables by reading from the
\r
1814 input, updating the variables and writing directly to the output. Once
\r
1815 this is done we can start with the main loop. Have a look at the source
\r
1816 if you have any question about these steps.
\r
1817 <P><P ALIGN="JUSTIFY">Now we'll see how to implement every order, don't
\r
1818 try doing order-0 until order-(-1) doesn't work, and so on. But before
\r
1819 going in that matter we'll see which functions uses every order and what
\r
1821 <P><P ALIGN="JUSTIFY">Note that there are some variables different for
\r
1822 every order which are pointers to linked list of contexts or bytes, and
\r
1823 which are initialized in a function, and then in another function are used.
\r
1824 One example is a pointer to the linked list with bytes of the order-2 which
\r
1826 (to whatever it has to be) in the function of encoding,
\r
1827 and which is used later while updating. So it's not a good idea to modify
\r
1828 these kind of variables between those functions.
\r
1830 <P><A NAME="Functions for every order"></A><FONT SIZE=+2>Functions nomenclature
\r
1832 <BR><P ALIGN="JUSTIFY">Every order uses different functions to manage their
\r
1833 data structures. For increasing readability of the code they follow some
\r
1834 guidelines, all functions that do the same have the same name (the only
\r
1835 difference is in the number of the order). They do the same things, in
\r
1836 the sense that they are called in the same way and achieve the same goals,
\r
1837 though most of them use different code.
\r
1838 <P><P ALIGN="JUSTIFY">When decoding we need to know the maximum cumulative
\r
1839 probability for being able to decode the input, so in this case, and also
\r
1840 while encoding, the first function called is "ppmc_get_totf_order2". Which
\r
1841 stands for: get the total frequency, in fact frequency and probability
\r
1842 are different things, as I explained before, unfortunately I perpetuated
\r
1843 this error, but I suggest you to not do so. However the term maximum cumulative
\r
1844 is already used for referring to the sum of the counts of all the bytes
\r
1845 so not using this term for different things can help to avoid misunderstandings.
\r
1846 The function "ppmc_get_totf_order2" does nothing else than returning in
\r
1847 "total_cump" the maximum cumulative probability of the current context.
\r
1848 As explained in the section about the escape method this can be quickly
\r
1849 done by adding the number of defined bytes in the context (the count of
\r
1850 the escape code) and the maximum cumulative probability. Also remember
\r
1851 that "total_cump", "symb_cump" and "symb_prob" are used as the parameters
\r
1852 for arithmetic coding. (in the case of my source a range coder)
\r
1853 <P><P ALIGN="JUSTIFY">The function "ppmc_code_byte_order2" (the number
\r
1854 '2' should be changed if we want the function for another order) codes
\r
1855 the byte in the current symbol if it's present, in that case it returns
\r
1856 a 1. It may happen that under this order, the current context is not present,
\r
1857 in that case it doesn't code anything, and returns a 0. It could happen
\r
1858 too that in current order the context was present but the byte we have
\r
1859 to code wasn't, so an escape code must be coded and the function will return
\r
1860 a 0. From this you can see that the main loop of the compressor just have
\r
1861 to call the encoding routine for highest order, and call the next lower
\r
1862 one in case it returns a 0, or stop when it returns a 1.
\r
1863 <P><P ALIGN="JUSTIFY">Another job of the ppmc model is to update the count
\r
1864 of the current symbol, this is done by calling "ppmc_update_order2". This
\r
1865 function returns nothing, and the main loop doesn't have to check whatever
\r
1866 it worked or not. At least not till the updating is done. In higher orders
\r
1867 the decoder uses a different function for updating "ppmc_update_dec_order2",
\r
1868 because some care should be taken with the linked lists.
\r
1869 <P><P ALIGN="JUSTIFY">When the count of a byte gets too big for the date
\r
1870 type used for storing it, renormalization (halving counts) must be done.
\r
1871 The function "ppmc_renormalize_order2" does this. It's called from the
\r
1872 routine of updating.
\r
1873 <P><P ALIGN="JUSTIFY">For decompression, "ppmc_decode_order2" is called.
\r
1874 It just returns "-1" if the byte was not decoded (because current context
\r
1875 didn't exist or it was an escape code) otherwise it returns the byte in
\r
1876 the variable "byte". The main loop of the decoder would check if the returned
\r
1877 value is "-1" in that case it would try to decode in a lower order.
\r
1879 <P><A NAME="The main"></A><FONT SIZE=+2>The main part</FONT>
\r
1880 <BR><P ALIGN="JUSTIFY">Every order uses its own functions and the only
\r
1881 work of the main part is calling them, this makes the code easier to read
\r
1882 and to expand. The first thing is writing to the output file the length
\r
1883 of the input file, that way the decoder will know when to stop. After that
\r
1884 we start initializing the model and coder:
\r
1887 ppmc_alloc_memory();</LI>
\r
1890 ppmc_initialize_contexts();</LI>
\r
1893 ppmc_encoder_initialize();</LI>
\r
1896 range_coder_init(&rc_coder,file_output);</LI>
\r
1898 <P ALIGN="JUSTIFY">Once this is done we start the main loop, we read a
\r
1899 byte from the input till there are no more bytes. Then we try to code in
\r
1900 the highest order and if failed, in a lower one. In the worst case we'll
\r
1901 code the byte in order-1. After that we have to do the updating, keeping
\r
1902 in mind that we do update exclusion, that is we only update the same order
\r
1903 as the byte was coded in, and higher ones. Then we update the context variables
\r
1904 and check for memory problems. The code is like the following:
\r
1907 while((byte=fgetc(file_input))!=EOF)</LI>
\r
1911 if(ppmc_code_byte_order4()==0) //If it doesn't work keep
\r
1916 if(ppmc_code_byte_order3()==0)</LI>
\r
1920 if(ppmc_code_byte_order2()==0)</LI>
\r
1924 if(ppmc_code_byte_order1()==0)</LI>
\r
1928 if(ppmc_code_byte_order0()==0)</LI>
\r
1932 ppmc_get_prob_ordern1();</LI>
\r
1935 range_coder_encode(&rc_coder,total_cump,symb_cump,symb_prob);</LI>
\r
1938 coded_in_order=0;</LI>
\r
1948 switch(coded_in_order)</LI>
\r
1952 case 0: ppmc_update_order0(); //update only order-0</LI>
\r
1955 case 1: ppmc_update_order1(); //update order-0 and order-1</LI>
\r
1958 case 2: ppmc_update_order2(); //update order-2 1 and 0...</LI>
\r
1961 case 3: ppmc_update_order3();</LI>
\r
1964 case 4: ppmc_update_order4();</LI>
\r
1967 default: break;</LI>
\r
1973 o4_byte=o3_byte;</LI>
\r
1976 o3_byte=o2_byte;</LI>
\r
1979 o2_byte=o1_byte;</LI>
\r
1982 o1_byte=byte; //current one is next time order-1</LI>
\r
1987 if(ppmc_out_of_memory==1)</LI>
\r
1991 ppmc_flush_mem_enc();</LI>
\r
1994 <A NAME="Order-(-1)"></A><FONT SIZE=+2>Order-(-1)</FONT>
\r
1995 <BR><P ALIGN="JUSTIFY">The order-(-1) in the code is called "ordern1" meaning
\r
1996 negative one. As we saw in the article about <A HREF="#r.[6]">finite context
\r
1997 modeling</A> order-(-1) is the lowest order whose only job is to be able
\r
1998 to code all the symbols that may appear in the input. Order-1 is not used
\r
1999 for achieving compression, so it's never updated. Because it must give a
\r
2000 non-zero count to all the symbols but it's not updated, we use a flat probability
\r
2001 distribution. That is every symbol has the same probability. For matters
\r
2002 of the implementation every symbol has a 1 count. The alphabet has all
\r
2003 the bytes, from 0-255 in the same positions, and an special code, the 256
\r
2004 which is used for flushing the model when running out of memory. Thus we
\r
2005 have that the probability of every symbol in the order-(-1) table is 1/257.
\r
2006 <P><P ALIGN="JUSTIFY">At first we could think about having a table with
\r
2007 the counts and cumulative probabilities of every symbol, but having a look
\r
2008 at those values we realize that this is not needed.
\r
2010 <TABLE BORDER CELLSPACING=2 CELLPADDING=2 >
\r
2012 <TD>Symbol: </TD>
\r
2028 <TD>Count: </TD>
\r
2044 <TD>Cumulative probability: </TD>
\r
2060 <P><P ALIGN="JUSTIFY">We see that the cumulative probability of a given
\r
2061 byte is the value of the byte itself. We can take profit of this fact and
\r
2062 avoid using any table. So the first function to implement "ppmc_get_prob_ordern1"
\r
2063 is quite easy, it just has to assign a 257 for the maximum cumulative probability
\r
2064 (no need of escape code), 1 to the probability, and the value of the byte
\r
2065 to the cumulative probability.
\r
2066 <P><P ALIGN="JUSTIFY">The function for returning the byte of a given cumulative
\r
2067 probability is very easy too, the byte is the value of the cumulative probability.
\r
2068 <P><P ALIGN="JUSTIFY">Because this order has the only job of being able
\r
2069 to code all symbols, it's not update, so we don't need to care about that
\r
2072 <P><A NAME="Order-0"></A><FONT SIZE=+2>Order-0 and order-1</FONT>
\r
2073 <BR><P ALIGN="JUSTIFY">Order-0 and order-1 are not memory hungry, so we
\r
2074 can store them in tables. If you have already implemented any arithmetic
\r
2075 coder, you surely know how does order-0 works. Given this, order-1 is only
\r
2076 a little modification: in order-0 we keep the probabilities in this table
\r
2077 "order0_array[]" and access it directly (that is the probability for "byte"
\r
2078 is in "order0_array[byte]"), order-1 uses instead "order1_array[o1_byte][byte]".
\r
2079 The only difference from an usual implementation is the escape code. Now
\r
2080 it's only a matter of implementing it having in mind the differences pointed
\r
2081 in the section about <A HREF="#Cumulative probabilities">Cumulative probabilities</A>.
\r
2083 <P><A NAME="Order-2"></A><FONT SIZE=+2>Order-2</FONT>
\r
2084 <BR><P ALIGN="JUSTIFY">Order-2 needs more memory than order-1, the probabilities
\r
2085 can't be stored on tables, because it would take too much memory. Thus
\r
2086 the probabilities are stored in linked lists. Order-2 has 2^16 = 65536
\r
2087 contexts, we can afford to put the contexts in a table. Like a hash table
\r
2088 with direct addressing, obviously the hash key is just the order-2, for
\r
2089 the context "there" the hash key would be "re", thus we would find the
\r
2090 context in "order2_array['re']". Due to the fact that in every entry we
\r
2091 only have one context, we don't need to store the context nor use linked
\r
2092 lists for contexts, so the data structure used is similar to the <A HREF="#Hash tables.context structure">one</A>
\r
2093 used for higher orders, but with these differences.
\r
2094 <P>struct o2_context
\r
2096 <BR>struct _byte_and_freq *prob; //Pointer to linked
\r
2097 lists containing bytes and counts of this context
\r
2098 <BR>unsigned int max_cump; //Maximum cumulative probability
\r
2100 <BR>unsigned int defined_bytes; //The number of bytes
\r
2103 <P>Putting all together we have that the maximum cumulative probability
\r
2104 of order-2 with a context like "which" is in:
\r
2106 order2_array['re'].max_cump.</LI>
\r
2108 <BR>Once this is clear we already know how to encode a byte, first we have
\r
2109 to make the hash key.
\r
2111 o2_cntxt = ppmc_order2_hash_key(o1_byte,o2_byte);</LI>
\r
2113 <BR><P ALIGN="JUSTIFY">The hash key as already explained is very simple,
\r
2114 and the only thing it does is putting two bytes, the order-1 and order-2
\r
2115 bytes, in a variable, which will be used to access the array for order-2.
\r
2116 <BR>#define ppmc_order2_hash_key(k,j) ((k)+(j<<8))
\r
2117 <P><P ALIGN="JUSTIFY">Now it could happen that the context hasn't been
\r
2118 created yet, so we have to check it. As explained before once a byte in
\r
2119 a linked list in created, it's never deleted, so just by checking the number
\r
2120 of defined bytes we can see if the context has been already created. If
\r
2121 the count is 0 it hasn't, so we have to return without coding anything.
\r
2123 if(order2_array[o2_cntxt].defined_bytes == 0) //it's empty</LI>
\r
2126 return 0; //byte not coded, nothing done</LI>
\r
2128 <BR><P ALIGN="JUSTIFY">Now we use the code explained in the section of
\r
2129 <A HREF="#Coding and decoding with linked lists.coding">Coding and decoding
\r
2130 with linked lists</A> and code an escape code or the byte depending
\r
2131 on if the byte wasn't present or it was.
\r
2132 <P><P ALIGN="JUSTIFY">The next function to implement is "ppmc_update_order2",
\r
2133 because we saved in "o2_ll_node" the pointer to the linked list, we don't
\r
2134 need to read the linked list again, and thus we can update the order as
\r
2135 explained in <A HREF="#Coding and decoding with linked lists.update">Coding
\r
2136 and decoding with linked lists</A>.
\r
2137 <P><P ALIGN="JUSTIFY">Decoding is not much more difficult just follow the
\r
2139 <A HREF="#Coding and decoding with linked lists.decoding">Coding
\r
2140 and decoding with linked lists</A>, and remember to check first if context
\r
2141 exists. The function for updating while decoding can't rely on the fact
\r
2142 that "o2_ll_node" points to the last element, so it has to read all the
\r
2143 linked lists, till the end and put new nodes there. This happens when the
\r
2144 byte was not coded under order-2. Check the code if you have any question.
\r
2146 <P><A NAME="Order-3"></A><FONT SIZE=+2>Order-3 and order-4</FONT>
\r
2147 <BR><P ALIGN="JUSTIFY">We can't use a table for contexts in order-3 because
\r
2148 it would be too big, it would require 16,777,216 entries and every entry
\r
2149 would take around 12 bytes. We can't afford that, so instead we use linked
\r
2150 lists for storing contexts. Read <A HREF="#Hash tables">Hash tables for
\r
2152 <P><P ALIGN="JUSTIFY">While encoding or decoding the first function called
\r
2153 is "ppmc_get_totf_order3", this one is responsible for checking if current
\r
2154 context is present, and also updates the variable "o3_context" (or
\r
2155 "o4_context" for order-4), it contains a pointer to the entry, and thus
\r
2156 the functions now are as in order-2 but instead of "order2_array[o2_cntxt]"
\r
2157 we use "o3_context". Apart from some special care while updating, all
\r
2158 the functions are the same, so you only have to change that and you already
\r
2159 have order-3 working. Both order-3 and order-4 are managed in the same
\r
2160 way. So do one, and copy the code for the next one.
\r
2162 <P><A NAME="Memory requeriments and management"></A><FONT SIZE=+2>Memory
\r
2163 requirements and management</FONT>
\r
2164 <BR>The basic data structures are the following:
\r
2166 <TABLE BORDER CELLSPACING=3 CELLPADDING=3 >
\r
2168 <TD VALIGN=TOP>struct _byte_and_freq{
\r
2169 <BR>unsigned char byte;
\r
2170 <BR>unsigned char freq;
\r
2171 <BR>struct _byte_and_freq *next; };</TD>
\r
2173 <TD VALIGN=TOP>struct context{
\r
2174 <BR>struct context *next;
\r
2175 <BR>unsigned long order4321;
\r
2176 <BR>struct _byte_and_freq *prob;
\r
2177 <BR>unsigned int max_cump;
\r
2178 <BR>unsigned int defined_bytes; };</TD>
\r
2180 <TD VALIGN=TOP>struct context_o2{
\r
2181 <BR>struct _byte_and_freq *prob;
\r
2182 <BR>unsigned int max_cump;
\r
2183 <BR>unsigned int defined_bytes; };</TD>
\r
2187 <P>Thus they take:
\r
2189 <TABLE BORDER CELLSPACING=3 CELLPADDING=3 >
\r
2191 <TD>Structure </TD>
\r
2193 <TD>Unaligned </TD>
\r
2195 <TD>Aligned </TD>
\r
2199 <TD>_byte_and_freq</TD>
\r
2215 <TD>context_o2</TD>
\r
2223 <P><P ALIGN="JUSTIFY">The static memory of the program, memory which is
\r
2224 not allocated while the program runs takes is the showed in the table.
\r
2225 This is the memory that the programs just need to start.
\r
2227 <TABLE BORDER CELLSPACING=3 CELLPADDING=3 >
\r
2229 <TD>Order-0 </TD>
\r
2231 <TD>256 </TD>
\r
2235 <TD>Order-1 </TD>
\r
2237 <TD>66048 </TD>
\r
2241 <TD>Order-2 </TD>
\r
2247 <TD>Order-3 </TD>
\r
2253 <TD>Order-4 </TD>
\r
2255 <TD>262144 </TD>
\r
2259 <TD>Bytes pool </TD>
\r
2265 <TD>Context pool </TD>
\r
2273 <TD>3377024 </TD>
\r
2277 <P><P ALIGN="JUSTIFY">Order-(-1) doesn't need any array. Order-0 uses an
\r
2278 array with the count (8 bits) for every byte. Order-1 uses the same table
\r
2279 but 256 times, thus 256*256, moreover we need two arrays for every byte
\r
2280 (256 entries thus) for "defined_bytes" and "max_cump". Order-2 has a hash
\r
2281 table with direct addressing, because we'll address two bytes (order-2
\r
2282 context) we need 256*256=65,536 entries. Every entry uses the data structure
\r
2283 context_o2, thus it takes 65536*12=786,432 bytes. Order-3 instead has a
\r
2284 hash table with pointers to contexts, it has 65,536 entries and is a pointer
\r
2285 which (in my implementation) takes 4 bytes, 65536*4=262,144. Order-4 uses
\r
2286 exactly the same. The pool for bytes and contexts take 2,000,000 bytes,
\r
2287 we'll explain now why.
\r
2288 <P><P ALIGN="JUSTIFY">We have to allocate memory for every new element
\r
2289 in the linked list. It wouldn't be a good idea to call the functions for
\r
2290 doing so every time. Also there's another fact that we should be aware of
\r
2291 while thinking about how to allocate memory, an element in the linked list
\r
2292 is never deleted. Due to these facts the solution that I chose for my
\r
2293 implementation was having a big buffer, and put there new nodes there.
\r
2294 Keeping track of the next position and the last one with pointers. Once
\r
2295 this buffer is filled we have to allocate a new one. Given this solution,
\r
2296 there's still two parameters to choose, the length of the buffer, and the
\r
2297 maximum number of buffers to allocate. I decided to give them a value of
\r
2298 1,000,000 and 100 respectively. We can choose to have another value, the
\r
2299 length of new buffers, that way you could allocate a very bug buffer at
\r
2300 the start (suited to your needs) and allocating less memory for the new
\r
2301 buffers, expecting to not need a lot. This could save some memory, but
\r
2302 should be tuned. Though in my implementation I have both definitions, they
\r
2303 have the same value.
\r
2304 <P><P ALIGN="JUSTIFY">Again having code clarity in mind I chose to have
\r
2305 two buffers, one for the linked lists containing bytes and probabilities,
\r
2306 and another for the contexts. The code is the same and only the nomenclature
\r
2307 (names assigned) for the variables is different, thus instead of "_bytes_pool_elements"
\r
2308 there's "_context_pool_elements". The variables used for this code are
\r
2309 the following ones:
\r
2312 struct context *_context_pool, this is a pointer to the current buffer,
\r
2313 exactly in the position where is pointing we can allocate a new element.</LI>
\r
2316 struct context *_context_pool_max, this pointer is used to detect the end
\r
2317 of current buffer.</LI>
\r
2320 unsigned long _context_pool_index, this is a value which says which buffer
\r
2321 are we using.</LI>
\r
2324 struct context *_context_pool_array[_mempool_max_index], this is the table
\r
2325 were we save the pointers to the different buffers, we need to keep it
\r
2326 for freeing them.</LI>
\r
2328 <P ALIGN="JUSTIFY">The defined values follow too. We get the length of
\r
2329 any buffer by multiplying it by its size, so the size of a buffer for contexts
\r
2330 is 50,000*20=1,000,000. I decided to make every buffer one mega long, it
\r
2331 seemed like a reasonable value, because it was big enough to not need to
\r
2332 allocate another buffer soon, and that it was not so big that it couldn't
\r
2333 be allocated it today's computers.
\r
2336 _context_pool_elements (50,000), this is the number of entries which are
\r
2337 allocated for the first buffer (initialized at the very start of the program).</LI>
\r
2340 _context_pool_elements_inc (50,000), this is the number of entries which
\r
2341 would be allocated for the rest of the buffers.</LI>
\r
2344 _bytes_pool_elements (125,000), the same but for the linked list which
\r
2345 holds bytes and probabilities.</LI>
\r
2348 _bytes_pool_elements_inc (125,000), the same but for the linked list which
\r
2349 holds bytes and probabilities.</LI>
\r
2352 _mempool_max_index (1,000), this is the maximum number of buffers, of every
\r
2353 kind, which we can allocate. In my code I choose to use the same value for
\r
2354 both bytes and contexts' tables, but they could be further tuned, though
\r
2355 it's of little importance as long as this number is big enough to not run
\r
2356 out of buffers.</LI>
\r
2358 <P ALIGN="JUSTIFY">If we allocate a new element the steps to follow are
\r
2359 clear: first let the routine use the pointer at "_context_pool" for the
\r
2360 new entry, second increment the pointer and then check that this is not
\r
2361 the last entry, if its we should allocate another buffer. We can do another
\r
2362 paranoid check, that is checking that we still have any entry free in the
\r
2363 table where we store the pointers to the big buffers. We could avoid it
\r
2364 by being sure that we have enough buffers (which probably is the case).
\r
2367 Use the pointer as needed</LI>
\r
2370 ++_context_pool; //increment pointer, next position in
\r
2371 the big buffer</LI>
\r
2374 if(_context_pool==_context_pool_max) //if they are equal,
\r
2375 we reached the maximum</LI>
\r
2379 if(_context_pool_index==_mempool_max_index) // First
\r
2380 check to see that we still have entries in the array</LI>
\r
2384 ppmc_out_of_memory=1; //At the end of the loop in the
\r
2385 main part, flush</LI>
\r
2388 return; //In case we were updating we can't follow, there
\r
2389 are no entries left</LI>
\r
2393 // Allocate memory for new buffer, and return if it's not possible</LI>
\r
2396 if((_context_pool=(struct context *)malloc(sizeof(struct context)*_context_pool_elements_inc))==NULL)</LI>
\r
2400 ppmc_out_of_memory=1; //At the end of the loop in the
\r
2401 main part, flush</LI>
\r
2408 _context_pool_array[_context_pool_index]=_context_pool;</LI>
\r
2411 _context_pool_max=_context_pool+_context_pool_elements_inc;</LI>
\r
2414 _context_pool_index++;</LI>
\r
2417 <P ALIGN="JUSTIFY">After allocating memory for the new buffer, we put its
\r
2418 value in the table, and compute the value of the end of the buffer, obviously
\r
2419 it's the pointer plus the maximum number of entries (in case of assembly
\r
2420 you first should multiply this value by the length of every entry). Then
\r
2421 we increment the index tot the table with pointers to the big buffers,
\r
2422 which will be used when freeing memory.
\r
2423 <P><P ALIGN="JUSTIFY">When the compressing process is done, or when we
\r
2424 have to flush the encoder, we have to free all the buffers. At the start
\r
2425 of the program we cleared all the entries of the table with pointers to
\r
2426 the big buffers, so we have to check if it's non zero, in case it isn't,
\r
2427 then it's a pointer, and we have to free it. In C we only need to know
\r
2428 the pointer of the buffer to free it, in other programming languages you
\r
2429 might need storing additional information.
\r
2430 <P><A NAME="Memory requeriments and management.flushing"></A><P ALIGN="JUSTIFY">The
\r
2431 flushing routine has to ensure that everything (variables, tables and buffers)
\r
2432 is like if it was just initialized. First we have to free all the memory.
\r
2433 Then clear all the tables for all orders, that is all the probabilities
\r
2434 of order-0 and order-1 set to zero, and all the pointers of higher orders
\r
2435 to 0. Then the big buffers must be allocated again. In my implementation
\r
2436 I had to set the count of the current byte in order-0 to 1 too. Next we
\r
2437 have to emit the flush code. We have to visit each context and if there's
\r
2438 any probability, emit an escape code in this order. Once we reach order-(-1)
\r
2439 we can emit the flush code, which in my implementation is done with:
\r
2445 symb_cump=256;</LI>
\r
2448 total_cump=257;</LI>
\r
2451 range_coder_encode(&rc_coder,total_cump,symb_cump,symb_prob);</LI>
\r
2453 <P ALIGN="JUSTIFY">The decoder checks the symbol decoded under order-(-1)
\r
2454 before writing it in the output, in case it's a flush code, it has to flush
\r
2455 its model, no matter if it still has memory (this could happen if the file
\r
2456 was compressed in a computer with more memory). In my code I do even another
\r
2457 check, in case that "ppmc_out_of_memory" = 1, but we didn't decode a flush
\r
2458 code, that means that compressor had more memory than decompressor, in
\r
2459 that case we just can't decompress the rest of the file correctly, because
\r
2460 we can't keep track of changes in the model (new nodes), so we can only
\r
2461 exit. To check this at the end of the loop we check if the variable "expected_flush"=1
\r
2462 (it's initialized to 0) in case it's we exit. After that we check if we
\r
2463 run out of memory. If we do, we set "expected_flush" to 1, and thus if
\r
2464 next time we don't decode a flush code, it means that we have to exit,
\r
2465 which will be done by the check explained before.
\r
2468 <P><A NAME="Fast order-3 hashed"></A><FONT SIZE=+2>How to implement the
\r
2469 fast order-3 hashed version</FONT>
\r
2470 <BR><P ALIGN="JUSTIFY">With hash tables we can do a trick which in most
\r
2471 of the cases is of not use, but in this one resulted in something which
\r
2472 works quite well. The trick is simply not resolving hash collisions. Thus
\r
2473 let different contexts share the same entry. We only need to implement
\r
2474 order-2, once we have it working we change the hash key for order-2 for
\r
2475 the hash key of order-3:
\r
2476 <P>#define ppmc_order2_hash_key(k,j) ((k)+(j<<8))
\r
2477 <BR>#define ppmc_order3_hash_size 65536
\r
2478 <BR>#define ppmc_order3_hash_key(k,j,i) ((k)+(j<<7)+(i<<11))
\r
2479 & ppmc_order4_hash_size-1
\r
2480 <P><P ALIGN="JUSTIFY">If you are not used to C '&' means the AND mask,
\r
2481 in the case of hash keys we use it for erasing the high bits that we don't
\r
2482 use (because we restricted the length of the hash table). The '<<'
\r
2484 <P><P ALIGN="JUSTIFY">Now we just have to change the main part to use order-3
\r
2485 instead of order-2, we only have to use the variable "o3_byte" too. And
\r
2486 it's all done. Now in the same hash entry there will be different contexts
\r
2487 sharing the same probability list. This doesn't produce bad results, instead
\r
2488 it works better than order-2, though of course it works worse than real
\r
2489 order-3. However if we extent the same trick for order-4 the results are
\r
2490 bad. These are the results for book2. (time for compression in kbyps)
\r
2492 <TABLE BORDER CELLSPACING=2 CELLPADDING=2 >
\r
2494 <TD>Order </TD>
\r
2496 <TD>Bpb </TD>
\r
2504 <TD>2.8629 </TD>
\r
2534 <P><P ALIGN="JUSTIFY">It's worth mentioning that order-3h uses almost as
\r
2535 much memory as order-2, because they use the same hash tables. Order-3
\r
2536 can take a little bit more of memory in linked lists for bytes and probabilities.
\r
2537 The difference from order-2 and order-3h in compression is big while in
\r
2538 speed and memory usage is very little! This happens because though different
\r
2539 contexts are sharing the same probability list, they aren't quite different
\r
2540 or because there are just a few contexts in the same entry. In the other
\r
2541 hand in order-4 a lot of contexts share the same entry, with may be different
\r
2542 probabilities, so at the end we get worse compression, because the same
\r
2543 context (hash entry in that case) gives a probability distribution which
\r
2544 doesn't reflect current file.
\r
2545 <P><P ALIGN="JUSTIFY">The differences in speed can be explained too. They
\r
2546 all come from insertion and updating of nodes in the list of bytes and
\r
2547 their counts. 3h or 4h have to create and update more nodes, and while
\r
2548 coding and decoding there are more symbols in the cumulative probabilities,
\r
2549 so the process is slower.
\r
2550 <P><P ALIGN="JUSTIFY">Order-3h is a ppmc implementation well suited for
\r
2551 real world compression because it only takes a little bit more of speed
\r
2552 and memory than order-2, but achieves 0.5bpb more, which ranks it in a
\r
2554 <P><A NAME="Fast order-3 hashed.hash explanation"></A><P ALIGN="JUSTIFY">If
\r
2555 you wonder how this works, let's put an example. Let's say we have a binary
\r
2556 message, that is, the alphabet only contains 1 and 0. And our hash key
\r
2557 looks like the following:
\r
2558 <BR>#define ppmc_order3_hash_key(k,j,i) ((k)+(j<<1)+(i<<1))
\r
2560 <BR>And we have a context like "101". If we apply it the hash key the result
\r
2561 is (all the values are in binary): 1+00+10=11. 11 would be the hash entry
\r
2562 of context "101". But this however is also the hash entry of "011" (using
\r
2563 hash key:) 1+10+00=11. So at the end we have that both contexts "101" and
\r
2564 "011" share the same entry. In their entry there's the probability list
\r
2565 for 0 and 1. And there we would store the probabilities of the two contexts.
\r
2566 In our implementation of ppmc the contexts which share the same entry have
\r
2567 for sure the same order-1 byte, so more or less they have the same probability
\r
2568 distribution, and thus it doesn't suffer much. In fact the error in prediction
\r
2569 in book2 results only in 0.0864 bpb.
\r
2570 <P><P ALIGN="JUSTIFY">If we analyse it, see that we have 2^3 = 8 possible
\r
2571 input values which are mapped to 2^2 = 4 hash entries, thus every entry
\r
2572 is share by 8/4 = context. In our hash key for ppmc we have 2^24 = 16,777,216
\r
2573 contexts which are mapped (that is, we assign them a position in the hash
\r
2574 table) to 2^16 = 65,536 (this is the number of entries in the hash
\r
2575 table). Thus we have that in ppmc order-3h every entry holds 256 different
\r
2576 contexts. 256 different probability distributions in every list, however
\r
2577 the impact in compression is little because due to our hash key the contexts
\r
2578 which share the same entry are similar.
\r
2579 <BR>#define ppmc_order3_hash_key(k,j,i) ((k)+(j<<7)+(i<<11))
\r
2580 & ppmc_order4_hash_size-1
\r
2581 <BR>In our hash key "k" is "o1_byte" and the hash key as worst modify the
\r
2582 highest bit, but the rest remain untouched, so we know for sure that all
\r
2583 the contexts that share the same hash entry have the first seven bits of
\r
2585 <P><P ALIGN="JUSTIFY">Another thing which I had to check was using a classic
\r
2586 hash key (used for example in lzp <A HREF="#r.[14]">[14]</A>) instead of
\r
2587 the current one. Instead of '+' a '^' (xor) <!-- Plain text. File: instead.txt [spaces instead of tabs] -->
\r
2588 <PRE> Using ^ Using +
\r
2589 File Bpb Kbyps c Kbyps d File Bpb Kbyps c Kbyps d
\r
2590 book1 2.5531 218.5143 214.8418 book1 2.5415 236.7239 221.6721
\r
2591 book2 2.3997 237.1344 213.9184 book2 2.3859 241.8208 227.4374
\r
2592 geo 4.8769 86.9565 82.6446 geo 4.9209 90.9091 86.9565
\r
2593 obj2 3.0717 182.5980 162.8576 obj2 3.0635 191.2931 175.9338
\r
2594 progc 2.6109 182.4308 182.4308 progc 2.6010 182.4308 182.4308
\r
2595 news 2.8417 186.2531 167.2981 news 2.8194 203.2762 186.2531
\r
2596 Average 3.0590 182.3145 170.6652 Average 3.0554 191.0756 180.1139</PRE>
\r
2597 <P ALIGN="JUSTIFY">The use of xor instead of adding resulted in worse compression
\r
2598 and speed for all the files except geo, which is a list of floating point
\r
2599 numbers. The hash key for order-3 works better with "+" for text. The test
\r
2601 <A HREF="#r.[15]">[15]</A>.
\r
2603 <P><A NAME="Full exclusion"></A><FONT SIZE=+2>Adding full exclusion to
\r
2604 the already done functions</FONT>
\r
2605 <BR><P ALIGN="JUSTIFY">Full exclusion is when we exclude from probability
\r
2606 computation symbols which appeared in orders which we already used. Obviously
\r
2607 if in an order there's a symbol but we instead emit an escape code, because
\r
2608 it wasn't the symbol to code, it will not be coded, so we shouldn't assign
\r
2609 it any probability. Let's say we have a message with the following probabilities:
\r
2611 <TABLE BORDER CELLSPACING=2 CELLPADDING=2 >
\r
2617 <BR>escape-3 </TD>
\r
2627 <P><P ALIGN="JUSTIFY">And we want to code 'c'. In order-3 we don't find
\r
2628 it, so we emit an escape code with a probability of 3/9. Then in order-2
\r
2629 we find it and emit it with a probability of 1/16 (4 bits). As you see
\r
2630 in order-2 we allocate probability space for 'a' and 'b', though they appeared
\r
2631 in order-3 and we didn't select them, therefore they are not the byte to
\r
2632 code. So we decide to use full exclusion instead of lazy exclusion (which
\r
2633 excludes lower orders) then if we exclude 'a' and 'b', the escape code
\r
2634 has a probability of 1 (the scheme C assigns it a value equal to the number
\r
2635 of defined bytes in the context, which now is only 'c') then we code 'c'
\r
2636 with a probability of 1/2 (1 bit).
\r
2637 <P><P ALIGN="JUSTIFY">For full exclusion we use a table with an entry for
\r
2638 every symbol (in the case bytes this means a table with 256 entries, which
\r
2639 is acceptable), this table is accessed like "excluded[byte]", and has a
\r
2640 value of 0 if it's not excluded, and a value of 1 if it is. At the start
\r
2641 of loop (every itineration, of course) we put all the values to 0, because
\r
2642 no order has been visited yet. If a context emits an escape code, we update
\r
2643 this table, by putting the value of the bytes in that order to 1. That
\r
2644 way they'll be excluded in lower orders. Then when computing probabilities,
\r
2645 we don't take in account bytes excluded. For making the coding easier to
\r
2646 read, I decided to use some new variables: "exc_total_cump", "exc_defined_bytes"
\r
2647 and "exc_max_cump" which are self-explanatory. In the case of order-(-1)
\r
2648 (ordern1 in the code) I chose not to use full exclusions, because order-(-1)
\r
2649 is hardly used. Also if you implement full exclusions, you have to be careful
\r
2650 about a <A HREF="#full.warning">problem</A> that can arise.
\r
2651 <P><P ALIGN="JUSTIFY">The change over previous versions is mainly done
\r
2652 in the function "ppmc_get_totf_order2", which has to exclude from the probability
\r
2653 computation the excluded bytes, comparing its value in the "excluded" table.
\r
2656 node=order2_array[o2_cntxt].prob;</LI>
\r
2659 exc_max_cump=0;</LI>
\r
2662 exc_defined_bytes=0;</LI>
\r
2669 if(excluded[node->byte]==0)</LI>
\r
2673 exc_defined_bytes++;</LI>
\r
2676 exc_max_cump+=node->freq;</LI>
\r
2680 if(node->next==0)</LI>
\r
2688 node=node->next;</LI>
\r
2695 exc_total_cump=exc_max_cump+exc_defined_bytes;</LI>
\r
2697 <P ALIGN="JUSTIFY">We start by clearing both maximum cumulative probability
\r
2698 and defined bytes, then we read till the end of the linked lists,
\r
2699 and check if current byte is excluded, if it isn't we can update the values.
\r
2700 When the end of the linked list is reached (the pointer "next" is 0) we
\r
2701 break the loop, and then we compute the maximum cumulative probability.
\r
2702 <P><P ALIGN="JUSTIFY">The function for coding would first call "ppmc_get_totf_order2",
\r
2703 but now it could happen that due to exclusion there was no byte defined
\r
2704 in the context, thus we have to check it and return a value meaning that
\r
2705 we didn't code the byte.
\r
2708 if(exc_defined_bytes==0) //If there's no byte defined,
\r
2716 <P ALIGN="JUSTIFY">After that we have to compute its probability, the code
\r
2717 used is the modification of the <A HREF="#Coding and decoding with linked lists.coding">code</A>
\r
2718 used with lazy exclusions, in that case we just have to car about excluded
\r
2722 node=order2_array[o2_cntxt].prob;</LI>
\r
2732 if(node->byte==byte)</LI>
\r
2736 goto ppmc_o2_byte_found;</LI>
\r
2740 if(excluded[node->byte]==0)</LI>
\r
2744 symb_cump+=node->freq;</LI>
\r
2748 if(node->next==0)</LI>
\r
2757 node=node->next;</LI>
\r
2762 <P ALIGN="JUSTIFY">Then it's only a matter of coding the byte. But in the
\r
2763 case an escape occurs we do not only have to emit it, but we also have
\r
2764 to update the "excluded" table. As explained before we have to read all
\r
2765 the linked list and then put to 1 the value of the bytes present under
\r
2769 node=order2_array[o2_cntxt].prob;</LI>
\r
2776 excluded[node->byte]=1;</LI>
\r
2779 if(node->next==0)</LI>
\r
2787 node=node->next;</LI>
\r
2793 <A NAME="Full exclusion.optimization"></A><P ALIGN="JUSTIFY">There's room
\r
2794 for optimization. If we code the byte under this context we read the linked
\r
2795 list twice, and if we don't we read it three times, which can be of course
\r
2796 improved. It's possible to make the symbol cumulative probability while
\r
2797 making the maximum cumulative probability, and thus we would avoid reading
\r
2798 the linked list again when coding the symbol. Even we should be able to
\r
2799 not read the linked list again the third time, in that case we should update
\r
2800 the table "excluded" while computing the maximum cumulative probability,
\r
2801 of course we should update the count after having read it. I haven't tested
\r
2802 the idea nor the code, but with both optimizations the code would look
\r
2803 like the following:
\r
2806 node=order2_array[o2_cntxt].prob;</LI>
\r
2812 exc_max_cump=0;</LI>
\r
2815 exc_defined_bytes=0;</LI>
\r
2822 if(excluded[node->byte]==0)</LI>
\r
2826 exc_defined_bytes++;</LI>
\r
2829 exc_max_cump+=node->freq;</LI>
\r
2833 if(node->byte==byte) //If it's the same, we don't have
\r
2834 to update "symb_cump" anymore</LI>
\r
2842 if(byte_seen==0) //If the byte was not seen this itineration
\r
2843 nor the previous ones</LI>
\r
2847 symb_cump+=node->freq;</LI>
\r
2851 excluded[node->byte]=1 //Exclude byte</LI>
\r
2854 if(node->next==0)</LI>
\r
2862 node=node->next;</LI>
\r
2869 exc_total_cump=exc_max_cump+exc_defined_bytes;</LI>
\r
2871 <P ALIGN="JUSTIFY">In this code we exclude all the symbols which appear
\r
2872 in current order, if an escape occurs that was what we had to do, if we
\r
2873 code a byte, it doesn't matter because then we are not going to use "excluded".
\r
2874 Note we can't apply this optimization to the decoding functions, because
\r
2875 we first need to know the maximum cumulative probability for decoding,
\r
2876 then we have to read the linked list for finding the symbol.
\r
2877 <P><P ALIGN="JUSTIFY">The function for decoding starts by doing the same
\r
2878 as the encoding function, that is making "exc_max_cump", and then checking
\r
2879 that there's at least one byte defined in the order. In case an escape
\r
2880 occurs we do the same as when coding. The routine for decoding the symbol
\r
2881 is a modification of the <A HREF="#Coding and decoding with linked lists.decoding">one</A>
\r
2882 used for lazy exclusions, which doesn't take in account excluded bytes.
\r
2885 node=order2_array[o2_cntxt].prob;</LI>
\r
2892 if(excluded[node->byte]==0)</LI>
\r
2896 current_cump+=node->freq;</LI>
\r
2900 if(symb_cump<current_cump)</LI>
\r
2908 node=node->next;</LI>
\r
2912 symb_prob=node->freq;</LI>
\r
2915 byte=node->byte;</LI>
\r
2918 o2_ll_node=node;</LI>
\r
2921 symb_cump=current_cump-symb_prob;</LI>
\r
2924 range_decoder_update(&rc_decoder,exc_total_cump,symb_cump,symb_prob);</LI>
\r
2926 <P ALIGN="JUSTIFY">I leave as an exercise to the reader adapting the functions
\r
2927 for order-0 and order-1, if you find any problem have a look at the source
\r
2929 <P><A NAME="full.warning"></A><P ALIGN="JUSTIFY">Warning: the updating
\r
2930 function assumes that if the byte was not coded under order-2 (or higher)
\r
2931 it didn't exist in the linked list, and that it has the pointer "o2_ll_node"
\r
2932 initialized to the last element in the linked list due to the search done
\r
2933 during the encoding process. This is however not true. It may happen that
\r
2934 all the characters are excluded (due to the fact that they appeared in
\r
2935 higher orders) thus "get_totf" would return a 0 in the variable "exc_defined_bytes".
\r
2936 The encoding function would check it and abort (obviously if there's no
\r
2937 byte in the context we can't code anything). Thus the pointer to the linked
\r
2938 list is not initialized. The solution to this problem is just reading till
\r
2939 the end of the linked list while updating. Note that this is not needed
\r
2940 in the highest order, because none of the symbols is excluded because it's
\r
2941 the higher. Therefore in my code I haven't done this change in the function
\r
2942 for updating of order-4. So be careful if you want to put another higher
\r
2943 order. Use the code for order-3 which takes this in account and has linked
\r
2944 list for probabilities and contexts.
\r
2945 <P><P ALIGN="JUSTIFY">The literature tends to say that full exclusion is
\r
2946 excluding the symbols which appeared in higher orders, but this is not
\r
2947 true for ppmz, which uses LOE (Local Order Estimation) for selecting the
\r
2948 best order for current symbol. I.e: let's say the maximum order is 8, but
\r
2949 LOE chooses to try to encode current symbol in order-5, an escape occurs,
\r
2950 and then LOE selects order-3, now we'll use full exclusion, but we don't
\r
2951 exclude all the bytes of higher orders, because we don't know them (at
\r
2952 encoding time we do, but while decoding we won't), it could even happen
\r
2953 that our byte is present there. We only exclude the orders which we have
\r
2954 seen which in this case is only order-5.
\r
2956 <P><A NAME="Compression and speed"></A><FONT SIZE=+2>Compression and speed
\r
2957 results of the different implementations</FONT>
\r
2958 <BR><P ALIGN="JUSTIFY">A little comparison between different orders and
\r
2959 implementations is shown in the graphics. O-3h is order-3 hashed, and o-4
\r
2960 (exc) is ppmc order-4 with full exclusions. The compression is measured
\r
2961 in bpb and the speed in kbyps.
\r
2965 <BR><IMG SRC="ppmc-bpb.gif" ALT="Bits Per Byte" HEIGHT=234 WIDTH=377>
\r
2966 <CENTER>bpb, Bits Per Byte </CENTER>
\r
2970 <BR><IMG SRC="ppmc-kbyps.gif" ALT="Kylo Bytes Per Second" HEIGHT=234 WIDTH=369>
\r
2971 <CENTER>Kbyps, Kylo BYtes Per Second</CENTER>
\r
2975 <P ALIGN="JUSTIFY">The results which follow correspond to the three different
\r
2976 implementations, ppmc with lazy exclusion, ppmc with full exclusion and
\r
2977 ppmc order-3 hashed. Note that the implementation with full exclusions
\r
2978 could be <A HREF="#Full exclusion.optimization">faster</A>. These are results
\r
2979 for the Calgary Corpus, and at the end you can also see the results
\r
2980 for the large Canterbury corpus
\r
2981 <A HREF="#r.[16]">[16]</A>.<!-- Full results. re_full.txt -->
\r
2982 <PRE>Full results:
\r
2984 Ppmc lazy exclusion, order-4
\r
2985 File Bpb Kbyps c Kbyps d
\r
2986 book1 2.4757 136.9617 118.1796
\r
2987 book2 2.1989 150.3210 126.6680
\r
2988 bib 2.0030 139.9831 123.4259
\r
2989 geo 5.3678 45.6621 42.3729
\r
2990 news 2.8141 107.7190 94.2877
\r
2991 obj1 4.0171 95.4545 77.7778
\r
2992 obj2 2.7300 91.2990 79.8110
\r
2993 paper1 2.5560 139.8309 106.2715
\r
2994 paper2 2.5191 134.3654 113.8373
\r
2995 pic 1.3235 190.5656 146.0821
\r
2996 progc 2.5625 121.6205 105.6178
\r
2997 progl 1.8593 163.9959 131.1967
\r
2998 progp 1.8602 151.9442 128.5682
\r
2999 trans 1.6749 167.7681 139.8068
\r
3000 Average 2.5687 131.2494 109.5645
\r
3003 Ppmc order-3 hashed (lazy exclusion)
\r
3004 File Bpb Kbyps c Kbyps d
\r
3005 book1 2.5415 236.7239 221.6721
\r
3006 book2 2.3859 241.8208 227.4374
\r
3007 bib 2.2053 229.5723 229.5723
\r
3008 geo 4.9209 90.9091 86.9565
\r
3009 news 2.8194 203.2762 186.2531
\r
3010 obj1 4.0532 190.9091 131.2500
\r
3011 obj2 3.0635 191.2931 175.9338
\r
3012 paper1 2.6161 189.7705 189.7705
\r
3013 paper2 2.5515 210.1613 215.6918
\r
3014 pic 1.3430 327.5735 294.8162
\r
3015 progc 2.6010 182.4308 182.4308
\r
3016 progl 1.9551 257.7079 267.2526
\r
3017 progp 1.9208 227.9164 227.9164
\r
3018 trans 1.9003 236.5961 236.5961
\r
3019 Average 2.6341 215.4758 205.2535
\r
3022 Ppmc full exclusion, order-4
\r
3023 File Bpb Kbyps c Kbyps d
\r
3024 book1 2.2723 21.1874 22.5584
\r
3025 book2 1.9947 22.5509 22.9227
\r
3026 bib 1.8522 22.4630 23.2361
\r
3027 geo 4.7744 7.4906 9.0580
\r
3028 news 2.3807 20.8546 17.2488
\r
3029 obj1 3.8140 8.3004 10.6061
\r
3030 obj2 2.5281 16.7498 18.6700
\r
3031 paper1 2.3264 21.0023 21.0856
\r
3032 paper2 2.3028 18.6704 20.6977
\r
3033 pic 1.2678 20.1848 20.0075
\r
3034 progc 2.3511 20.2701 19.7708
\r
3035 progl 1.7235 25.3187 23.4280
\r
3036 progp 1.7267 22.1865 20.3002
\r
3037 trans 1.5737 23.3601 21.8138
\r
3038 Average 2.3492 19.3278 19.3860
\r
3041 Ppmc full exclusion, order-4
\r
3042 File Bpb Kbyps c Kbyps d
\r
3043 bible.txt 1.7062 29.5428 28.9945
\r
3044 e.coli 1.9560 32.8449 31.6604
\r
3045 kjv.guten 1.6801 28.8764 28.3149
\r
3046 world192 1.6892 28.1551 27.9047
\r
3047 Average 1.7579 29.8548 29.2186
\r
3050 <P><BR><A NAME="References"></A><FONT SIZE=+2>References</FONT>
\r
3051 <BR><A NAME="r.[1]"></A>[1] Charles Bloom "Kraft Inequality"<I>,</I> <A HREF="http://www.cbloom.com">http://www.cbloom.com</A>
\r
3052 (Compression : News Postings : Kraft Inequality)
\r
3053 <BR><A NAME="r.[2]"></A>[2] Bell, T.C., Cleary, J.G. and Witten, I.H. (1990)
\r
3054 "Text compression<I>"</I>, Prentice Hall, Englewood Cliffs, NJ.
\r
3055 <BR><A NAME="r.[3]"></A>[3] Charles Bloom "Solving the Problems of Context
\r
3056 Modeling<I>"</I>, <A HREF="http://www.cbloom.com">http://www.cbloom.com</A>
\r
3058 <BR><A NAME="r.[4]"></A>[4] Mark Nelson, Jean-Loup Gaily (1996) "The Data
\r
3059 Compression Book<I>"</I>, M&T Books. Source available at Mark's <A HREF="http://www.dogma.net/markn">page</A>.
\r
3060 <BR><A NAME="r.[5]"></A>[5] Ppmd source code by <A HREF="mailto:dmitry.shkarin@mtu-net.ru">Dmitry
\r
3061 Shkarin</A> available via <A HREF="ftp://ftp.elf.stuba.sk/pub/pc/pack/ppmde.rar">ftp1</A>
\r
3062 or <A HREF="ftp://ftp.simtel.net/pub/simtelnet/win95/compress/ppmde.zip">ftp2</A>.
\r
3063 <BR><A NAME="r.[6]"></A>[6] Arturo Campos (1999) "Finite context modeling"
\r
3064 available at my <A HREF="http://www.arturocampos.com">home page</A>.
\r
3065 <BR><A NAME="r.[7]"></A>[7] Moffat, A. (1988) "A note on the PPM data compression
\r
3066 algorithm," Research Report 88/7, Department of Computer Science, University
\r
3067 of Melbourne, Parkville, Victoria, Australia.
\r
3068 <BR><A NAME="r.[8]"></A>[8] Raita, T. and Teuhola, J. (1987) "Predictive
\r
3069 text compression by hashing." ACM conference on Information Retrieval,
\r
3071 <BR><A NAME="r.[9]"></A>[9] Clearly, J.G. and Witten, I.H. (1984) "Data
\r
3072 compression using adaptative coding and partial string matching" IEEE Trans.
\r
3073 Communications, COM-32 (4), 396-402, April.
\r
3074 <BR><A NAME="r.[10]"></A>[10] Arturo Campos (1999) "Arithmetic coding"
\r
3075 available at my <A HREF="http://www.arturocampos.com">home page</A>.
\r
3076 <BR><A NAME="r.[11]"></A>[11] Arturo Campos (1999) "Range coder" available
\r
3077 at my <A HREF="http://www.arturocampos.com">home page</A>.
\r
3078 <BR><A NAME="r.[12]"></A>[12] Michael Schindler. Source code of the range
\r
3079 coder. Available via <A HREF="http://www.compressconsult.com/rangecoder">html</A>.
\r
3080 <BR><A NAME="r.[13]"></A>[13] The Context-Tree Weighting Project. <A HREF="http://ei0.ei.ele.tue.nl/~frans/ResearchCTW.html">http://ei0.ei.ele.tue.nl/~frans/ResearchCTW.html</A>
\r
3081 <BR><A NAME="r.[14]"></A>[14] Charles Bloom "LZP: a new data compression
\r
3082 algorithm", <A HREF="http://www.cbloom.com">http://www.cbloom.com</A> (lzp.ps)
\r
3083 <BR><A NAME="r.[15]"></A>[15] Calgary corpus set. <A HREF="ftp://ftp.cpsc.ucalgary.ca/pub/projects/text.compression.corpus">ftp://ftp.cpsc.ucalgary.ca/pub/projects/text.compression.corpus</A>
\r
3084 <BR><A NAME="r.[16]"></A>[16] large Canterbury corpus <A HREF="http://corpus.canterbury.ac.nz">http://corpus.canterbury.ac.nz</A>
\r
3086 <P><A NAME="Closing words"></A><FONT SIZE=+2>Closing words</FONT>
\r
3087 <BR><P ALIGN="JUSTIFY">Now you can use your ppmc implementation for an
\r
3088 stand alone compressor of lossless files, or use it for lossless image
\r
3089 compression, or using it for compressing the output of other compression
\r
3090 algorithms (read next paragraph). However those are not the only uses of
\r
3091 ppmc, you can use it for predicting and use it for an operative system
\r
3092 where the reader needs to input text, or as a help for OCR <A HREF="#r.[2]">[2]</A>.
\r
3093 If you want better compression than ppmc you should know that using an
\r
3094 order above 4 with ppmc isn't worth because higher orders produce too much
\r
3095 escape codes. For taking profit of the information that high orders provide
\r
3096 you should have a look at other implementations like ppmd or ppmz. Fortunately
\r
3097 ppmc with hash tables is the perfect base for ppmz <A HREF="#r.[3]">[3]</A>
\r
3098 an state of art. I'll write an article about it, so keep an eye to my <A HREF="http://www.arturocampos.com">home
\r
3100 <P><A NAME="literals-lzp"></A><P ALIGN="JUSTIFY">If you want to use ppmc
\r
3101 for compressing the output of lzp (literals), you have to change update
\r
3102 functions of higher orders, because currently they expect that coding is
\r
3103 always done before updating. However in this case, a lot of literals are
\r
3104 coded with lzp but have to be updated with ppmc too. For orders lowers
\r
3105 than 2 there's no problem, but for order-2 and highers, we have to read
\r
3106 till the end of the linked list of contexts or probabilities when we want
\r
3107 to put a new element, or we have to read till the current one to update
\r
3108 its count (variables like "o2_ll_node" are not initialized because the
\r
3109 coding has not been done). Such changes are easy to do and are left as
\r
3110 homework, in case you have any doubt <A HREF="mailto:arturo@arturocampos.com">email</A>
\r
3112 <P><P ALIGN="JUSTIFY">If when implementing ppmc with full exclusions you
\r
3113 find any bug, read the <A HREF="#full.warning">warning</A> about updating.
\r
3114 If still you can't find the bug, have a look at the code, or <A HREF="mailto:arturo@arturocampos.com">email</A>
\r
3115 me. This article took long to do, and thus I look forward for your comments
\r
3116 about it, so please take the time to tell me what you think of it, just
\r
3117 as I took the (long) time to write it.
\r
3118 <P><P ALIGN="JUSTIFY">I want to thank to Malcolm Taylor for letting me see
\r
3119 his ppmz code which used hash tables, unfortunately later he was too busy
\r
3120 to be able to answer my questions, which at the end I solved myself.
\r
3122 <P><A NAME="Contacting the author"></A><FONT SIZE=+2>Contacting the author</FONT>
\r
3123 <BR><P ALIGN="JUSTIFY">You can reach me via email at: <A HREF="mailto:arturo@arturocampos.com">arturo@arturocampos.com</A>
\r
3124 See you in the next article!
\r
3127 <DIV ALIGN=right>Arturo San Emeterio Campos, Barcelona 21-March-2000</DIV>
\r
3130 <BR><P ALIGN="JUSTIFY">This article comes from Arturo Campos home page
\r
3131 at <A HREF="http://www.arturocampos.com">http://www.arturocampos.com</A>
\r
3132 Visit again soon for new and updated compression articles and software.
\r
projects / z.facultad / 75.06 / jacu.git / blob