1 Introduction
Text compression for Chinese characters is problematical because of its large alphabet size. Today, few Chinese texts are translated into electronic form. It is estimated that almost 70% of Chinese paper-based information is urgently required to be transformed into electronic form (Vines and Zobel Reference Vines and Zobel1998). However, very little work has been done in the area of Chinese text compression. Of the results that have been published, the researchers have chosen to experiment with a small number of files they have collected themselves. They have also used different compression measures to compare results. For example, Lua (Reference Lua1994) in his article reported on an n-gram scheme to encode Chinese characters and achieved the compression rate of 6.44 bits per Chinese character (bpCc) on 14-bit Chinese characters. Gu (Reference Gu1995; Reference Gu2005) describe a Prediction by Partial Match (PPM)-like predictive scheme for Big5 encoded Chinese text, which reduces a text file's size to 5.424 bpCc. Vines and Zobel (Reference Vines and Zobel1998) modified the PPM model for Chinese characters by changing the unit of encoding from 8 to 16 bits, and achieved 6.2 bpCc. Cheng et al. (Reference Cheng, Young and Wong1999) introduce a word-based dictionary coding algorithm that use both the LZW and Huffman coding schemes. It is reported that the compression results are comparable to that of the traditional PPM-based schemes. Most recently, Ong and Ng (Reference Ong and Ng2005) announced the compression rate of 7.925 bpCc for Dynamic Markov Compression. However, these results cannot be directly compared because they have been obtained under entirely different experimental conditions (such as testing corpus). A primary purpose of this article is to provide a standardized framework under which such experiments can be done (see Section 5).
Text compression is a useful vehicle for comparison of different language models for natural language processing (NLP) applications. Text mining is one application that can make use of text compression models to achieve better NLP performance by using the Viterbi algorithm and variations to annotate the text (Witten et al. Reference Witten, Bray, Mahoui and Teahan1999). On the other hand, we have found that understanding gained from applying text compression models to NLP applications can lead to further improvements in text compression itself (Teahan and Harper Reference Teahan and Harper2001). The work described here, although focussed on the problem of text compression, is an important precursor future work we wish to perform in the area of NLP for Chinese and other Asian languages.
In this article, we examine the characteristics of Chinese language text in Section 2, then introduce the traditional PPM model in Section 3. Section 4 discusses our new adaptive PPM variant, dubbed PPMO (for PPM with order stream). Section 5 discusses the Bangor Mandarin Chinese Corpus (BMCC), which we have used in our experimental analysis. Section 6 reports the significant experimental results we have obtained with our corpus. A summary and discussion of the implications of the results is provided in Section 7.
2 Chinese text
The modern Chinese dictionary lists about 8,000 Chinese characters. Unlike English, which is usually encoded in the computer by the ASCII character set, Chinese is usually encoded by using a more specific character set such as GB2312-80 and GB13000.
For example, the table for the GB2312-80 character set has 94 rows (sections) and 94 columns (positions), which contains 682 symbols, 6,763 Chinese characters, and some user-defined characters (Figure 1). Both row and columns are encoded as an ASCII character. The whole table is divided into four parts.
Chinese GB2312-80 coding table.
As the above figure shows, every Chinese character can be encoded by using the GB2312-80 character set, which uses a two-dimensional table. Because the GB Chinese code is a two-byte encoding scheme, the high byte is encoded by a row, or ‘section code’, and the low byte is encoded by a column, or ‘position code’.
Unlike English words, which are separated by spaces, Chinese text is not naturally segmented by space or any other symbol. Therefore, it is not clear which is the most appropriate symbol to use for encoding in Chinese. In English experiments, for example, it has been found that word-based symbols are significantly better than character-based ones (Teahan Reference Teahan1998), but it is not clear whether the same would occur with Chinese text.
3 Prediction by Partial Match
PPM is a finite-context model because the predictions are based on a finite number of preceding symbols. It predicts upcoming symbols by employing a suite of context models of different orders, from some pre-defined maximum down to a default −1 model (Cleary and Witten Reference Cleary and Witten1984; Bell et al. Reference Bell, Cleary and Witten1990). If a novel symbol occurs in the context, an escape probability will be assigned. PPM achieves excellent compression rates, although this model seems expensive both in terms of memory and execution speed. There are several variations for PPM, such as PPMA, PPMB, PPMC, PPMD, PPM* (Cleary and Witten Reference Cleary and Witten1984; Moffat Reference Moffat1989; Cleary and Teahan Reference Cleary and Teahan1997; Shkarin Reference Shkarin2002), which are mainly named according to the escape method they employ. Moffat's PPMC, a well-crafted implementation that uses the update exclusion mechanism (Moffat Reference Moffat1990), has become the benchmark version (Cleary and Teahan Reference Cleary and Teahan1997). In a recent article, Dmitry Shkarin introduced PPMII, which stands for PPM with Information Inheritance. It takes advantage of the similarity of distribution functions in parent and child contexts and sets the initial value of the generalized symbol frequency in the child context with regard to information about this symbol gathered in the parent context (Shkarin Reference Shkarin2002). PPMII achieves a good compression rate as well as excellent compression speed. PPM-Ch, introduced by Wu and Teahan (Reference Wu and Teahan2005), adapts the PPM model especially for Chinese text by using pre-processing prior to encoding and uses 16 bits symbol schemes, plus frequency sorting techniques, as well as achieves excellent compression results.
To illustrate the traditional PPM model, we use PPMC as an example. Let A be a discrete alphabet consisting of |A| > 2 symbols and D be the maximum order of the model, where d ≤ D be the current coding order of a model. The probability of an upcoming symbol x n+1 = ϕ, ϕ A depends on the current context s d = x n, . . ., x n−d+1. Let c d(ϕ) denote the number of times that the symbol ϕ occurs in the context s d. Let t d be the total number of unique symbols that occur after the context s d. Let T d = Σc d(ϕ), which denotes the total number of times that the context s d has been. Then, the probability of a symbol ϕ occurring in the context s d is:
![\[ p_d(\verphi) = \frac{c_d(\verphi)}{t_d+T_d}, c_d(\verphi)>0. \]](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20151022065200001-0233:S1351324907004597_eqnU1.gif?pub-status=live){kind=small}
The probability of an escape occurring in the context s d is:
![\[ p_d({\it esc}) = \frac{t_d}{t_d+T_d}. \]](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20151022065200001-0233:S1351324907004597_eqnU2.gif?pub-status=live){kind=small}
The overall conditional probability for any symbol ϕ is:
![$
\[ P_{PPMC}(\verphi) = \left [ \prod^{D}_{i= d+1} p_d({\it esc}|s_i)\right ] * p_d(\verphi|s_d).$](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20151022065200001-0233:S1351324907004597_eqnU3.gif?pub-status=live)
To illustrate the operation of PPM, Table 1 shows the state of seventeen conditioning classes with d = 2, 1, 0 and −1 after the input string 
has been processed. Note that for PPM algorithms, each symbol is usually directly encoded using arithmetic coding (Moffat Reference Moffat1990; Moffat et al. Reference Moffat, Neal and Witten1998) based on the probability suggested by the model. The PPM encoding algorithm proceeds from the highest order model d=2; if the context successfully predicts the next character ϕ, the associated probability p d(ϕ) is used to encode it. For example, if 
followed the input string 
, the probability of 
would be used because a successful prediction 
has been made in the order 2 model.
PPMC model after processing the string
Suppose that the character following the input string is 
, which is not predicted by the current context 
. Consequently, an escape probability would be encoded by using the arithmetic coding algorithm and the encoding process downgrades from order 2 to order 1 model, d=1 context 
is used. Then the desired prediction → is selected with probability 
. The total probability to encode the character is × = 
, which is 4 bits. We can improve this further if we use the ‘exclusion’ mechanism, since → 
cannot be encountered because if it did, it would have been encoded at the order 2 context model. The probability 
can be used in the current order 1 model for the character , which saves coding space in comparison with probabilities encoded without exclusions.
If a novel character 
follows the input string, the encoding process would escape right down to the base level d= −1. In this level, all characters would be encoded as a probability of 
, where |A| is the alphabet size of the non-encoded symbols. For Chinese, |A| ≈ 8,000.
4 PPMO: A new PPM variant for Chinese text
As mentioned above, for Chinese characters, the size of each character requires a two-byte scheme, or 16 bits, to encode it. The main problem of using the traditional PPM algorithm for Chinese text is that the proportion of escape probabilities that need to be encoded is much higher than for English text, which leads to wasted code space. In addition, because of the large alphabet and the large proportion of escapes, performing full exclusions can significantly reduce execution speeds. Lower order models also tend to perform better. Experiments show that on average Chinese text gets its best compression results by using an order 2 PPM model as its maximum order. This compares to order 5 for English (Teahan Reference Teahan1998).
To overcome the disadvantages of the traditional PPM algorithm, we separate the coding process into two parts, namely, order stream and symbol stream. The order stream outputs a coding order for each coding symbol, whereas the symbol stream outputs the coding symbol itself on the baris of the context for the particular order. To illustrate this algorithm, we use the same definitions that we mentioned in the previous section.
• If a symbol ϕ has been found in the context s d, the current maximum order d from the order stream is encoded first, followed by the symbol itself from the symbol stream, which is encoded using the following probability:
![\[\P_s(\varphi) = \frac{c_d(\varphi)}{T}, \quad\quad c_d(\varphi)>0.\]](data:image/gif;base64,R0lGODlhAQABAIAAAMLCwgAAACH5BAAAAAAALAAAAAABAAEAAAICRAEAOw==)
• If a symbol ϕ has not been found in the context s d, it will downgrade to the lower order, ultimately backing off to the default order −1 model if needed. To make sure a symbol can be found in the order −1 model, we allocate one count to each symbol in the alphabet. Once the model that will be used to encode the symbol has been selected, the order of the model is encoded first, then the model is used to encode the symbol.
![\[\P_s(\varphi) = \frac{c_d(\varphi)}{T}, \quad\quad c_d(\varphi)>0.\]](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20151022065200001-0233:S1351324907004597_eqnU4.gif?pub-status=live){kind=small}
Table 2 shows the order and symbol probabilities used when processing the string 
.
PPMO model when processing the string
Table 3 illustrates PPMO model after processing the same string 
. Suppose 
followed the input string, the encoding process outputs 2 in the order stream because would be encoded in the order 2 model, then outputs a probability of since a successful prediction 
has been made in the order 2 model.
PPMO model after processing the string
Suppose instead that the character following the input string 
is 
, which is not predicted by the current context 
. Rather than output an escape probability, the encoding process downgrades from order 2 to the order 1 model and the d=1 context 
is used. Then a 1 is output in the order stream because the desired prediction → is selected with probability .
If a novel character 
follows in the input string, the encoding process would back off to the default order d = −1. A −1 would be output in the order stream and all characters would be encoded as a probability of 
.
As Table 3 shows, all the coding probabilities in the order 2 context model and mostly in the order 1 model are 1, P s(ϕ) = 1. This compares with the probability distributions in Table 1, where all probabilities must be smaller than 1 (p d(ϕ) < 1) by the nature of the traditional PPM encoding scheme.
Moveover, if the total number of unique symbols that occur after the context is 1 (t d=1), the encoding probability would be 1, which implies the symbol stream need not output anything when encoding. In the above example, 
follows the input string, the encoding process only outputs 2 in the order stream and nothing in the symbol stream because in the order 2 context model, the encoding context 
only has one unique symbol that occurs after it.
Obviously, there is the additional expense of encoding the order stream. The trade-off between our new method and the traditional PPM method is between encoding the order stream separately versus additional code space from encoding escapes and backing off to lower orders. Interestingly, at least for Chinese text, we have found the new method outperforms the traditional approach, but understandably, it is dependent on how efficiently the order stream can be encoded. We now discuss one approach on how this can be done.
Figure 2 shows a sample file of the order stream for encoding the Chinese Bible in Section 5 SBMCC.
Sample output of the order stream for encoding the Chinese Bible.
It is clear that the order stream is highly predictable because of its small alphabet size and repetitive nature. For example, if the maximum coding order of the symbol stream is 2 for a model, there are only four possibilities in the order stream, which are {−1, 0, 1, 2}. (In Figure 2, we rescale the order stream to {0, 1, 2, 3} by adding 1 to each order.) We can regard the order d as separate entities to be encoded and use the traditional PPM algorithm to code the order.
The conditional probability for order d is:
![\[
P_o(d) = \left [ \prod^{D^{*}}_{i= d^{*}+1} p_{d^*}({\it esc}|s^{*}_i)\right ] \times p_{d^*}(d|s_d^{*}),\]](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20151022065200001-0233:S1351324907004597_eqnU5.gif?pub-status=live)
where D* denotes the maximum coding order of the order stream; d* ≤ D denotes the current coding order; and s*i denotes the current order stream coding context.
The overall coding probability for a symbol ϕ is:
![\[P_{PPMO}(\varphi) = P_o(d) \times P_s(\varphi).\]](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20151022065200001-0233:S1351324907004597_eqnU6.gif?pub-status=live){kind=small}
When decoding, we first decode the order stream to find out which order the symbol has been encoded with, and then decode the symbol stream on the basis of the order of the model.
Although PPMO is a two-step encoding method, it is still possible to take advantage of the exclusion mechanism that is so effective for the standard PPM algorithm. For example, if follows the input string in Table 2, we can exclude the symbol 
in the order 1 context model since has not been encoded in the order 2 
context model. The probability of 
would be used in comparison with the probability of 
when no exclusion mechanism is used.
PPMO requires a two-step encoding for each symbol, but the traditional PPM algorithm may require many escapes for each symbol, and if the alphabet is large and escaping is frequent, as the case with Chinese text, it is not clear which approach will have better speed performance.
5 Bangor Mandarin Chinese Corpus
To standardize future experimental results, we have set up a corpus named BMCC for experimental usage. It can be downloaded from the following Internet site: http://www.informatics.bangor.ac.uk/~wjt/AIIA/BMCC/BMCC.htm.
According to the file size, the whole corpus is divided into two subcorpora. One is called the Small Bangor Mandarin Chinese Corpus, or SBMCC, the other is the Large Bangor Mandarin Chinese Corpus, or LBMCC.
SBMCC contains all files smaller than 800 KB. We select some news, novels, and fictional articles. We also include a balanced Mandarin Chinese Corpus named Lancaster Corpus of Mandarin Chinese (LCMC) (McEnery and xiao Reference McEnery and Xiao2004), which is constructed by the Linguistics Department of Lancaster University and can be obtained from http://bowland-files.lancs.ac.uk/corplang/lcmc/. It contains fifteen different text categories. The corpus comprises Mandarin Chinese text published in Mainland China, including newspapers, books, as well as text from the Xinhua News Agency. All the text is segmented by space according to the Chinese word as judged by a native speaker, but for the purposes of our experimental corpus, we have removed these spaces. We have also removed the XML tags that accompany the LCMC files.
LBMCC contains all files larger than 800 KB. We select the Chinese Bible, and include some TREC Mandarin Corpus (2000) files and the PH Corpus (Jin Reference Jin1992). All TREC files come from the Xinhua News Agency and were collected for the Text Retrieval Conference. We have concatenated all the TREC files into one big file, removed all the XML tags, and selected five partitions from the head of that file (these are split according to story boundaries).
6 Experimental results
We use some other compression tools for comparison. gzip and bzip2 are the two popular compressors under Unix/Linux environment. WinRAR and ABC2.4 are two compressors under the Microsoft Windows environment. ABC2.4 uses the Burrows-Wheeler Compression Algorithm (Burrows and Wheeler Reference Burrows and Wheeler1994). PPMC, PPMD (Moffat Reference Moffat1990), and PPMII (Shkarin Reference Shkarin2002) are several variations of the PPM model. PPM-Ch is ‘PPM Chinese model’ (Wu and Teahan Reference Wu and Teahan2005) and PPMO is our experimental model. We use an order 2 model as the maximum encoding order for both the symbol stream and the order stream.
The source code of our implementation is available at http://www.informatics.bangor.ac.uk/~wjt/AIIA/BMCC/PPMO.tar.gz. The arithmetic coder for our implementation was obtained from RWTH Aachen University (Bodden et al. Reference Bodden, Clasen and Kneis2004). The configuration of our test machine is Intel Pentium M 1.7 GHz, with 512 MB internal memory. We also use the measure bits per Chinese character byte (bpCc) to compare results, as the notion of a Chinese character is problematical and is dependent on the coding scheme used.
Table 4 shows the results for the SBMCC when using different compressors. It is clear that our variant PPMO achieves the best compression rate in all cases. On average, it is about 3% to 4% better than the second-place compressor PPM-Ch and about 5% to 6% better than the third-place compressor PPMII.
Chinese text compression for Small Bangor Mandarin Chinese Corpus using different compressors (the best result for each file is shown in bold)
Table 5 shows the compression results for the LBMCC. PPMO still performs best on average. It is approximately 1% better than the second place compressor PPMII. Experimental results show that if we use an order 3 context model as a maximum order for the order stream, we achieve further improvements, with the average compression rate reducing to 5.860 bpCc.
Chinese text compression for Large Bangor Mandarin Chinese Corpus using different compressors (best result is shown in bold)
Table 6 shows the compression results by using different orders for the order stream in the PPMO model. For example, PPMO 2+4 shows the compression result by using an order 2 model for the symbol stream and order 4 model for the order stream. We select one small file and one big file to illustrate thus; results are similar for other files in the corpus. It is clear that the compression results are comparable across orders 1–5 for the order stream.
Chinese text compression for selected files from the Bangor Mandarin Chinese Corpus using different orders for the order stream
Table 7 shows the encode and decode execution times for PPMD, PPMII, and PPMO by using exclusions and no exclusions. It is clear that PPMII is much faster than any other PPM-based compressors. However, this well-crafted implementation has been heavily optimized for speed, whereas the focus for our implementation has been on compression performance. Nevertheless, the coding speed of PPMO with no exclusions is approximately seven times faster than that of PPMO with exclusions, and approximately three to four times faster than the traditional PPMD model. Moreover, experimental results of PPMO with no exclusions indicate a 2% to 3% drop in compression rate, but this is still much better than most of the other compressors with better execution speed.
Execution times for PPMD, PPMII, and PPMO encode and decode by using exclusions and no exclusion
Figure 3 shows how the size of the compressed text increases as the input text grows for PPMO, PPMII, and PPMD on the Chinese Bible. In the beginning, the compression rate of PPMO is 7% better than that of PPMII and almost 12% better than that of the PPMD, which shows that the PPMO model adapts more quickly. As the text grows, PPMII's compression rate improves quickly until finally it is slightly better than that of PPMO. Similar results occur for other files in the BMCC, although in most cases, PPMO ends up with the best overall compression (see Tables 4 and 5) unlike for the Bible text file that we have chosen for illustration purposes here.
Size of the output compressed file for PPMO, PPMII, and PPMD as the text grows.
Table 8 shows the separate percentage costs of encoding the symbol and order streams for the Bible file. It can be seen that the cost of encoding the symbol stream is approximately 
of the total cost, whereas that of the order streams is 
.
Percentage of the symbol and order stream in the PPMO output compressed file
Figure 4 illustrates the size of the compressed symbol and order streams as the text grows. Again this is illustrated for the Chinese Bible text (and similar results are evident for the other files). As we have discussed in Section 4, the output size of the order stream increases much slower than that of the symbol stream because of its small alphabet size and repetitive nature. The graph shows a noticeable dip in the order stream compressed output with larger input text, whereas the symbol stream output and combined overall output has reached a plateau.
The size of the symbol and order stream in the PPMO output compressed file asthe text grows.
7 Discussion
We have described a new variant of the PPM compression algorithm designed especially for the Chinese language. The method uses a two-step encoding process. First, we encode the order of the model directly, then we encode the symbol itself. To our knowledge, this is the first empirical PPM algorithm that does not use the traditional PPM escape probabilities blending algorithm. No other study has successfully used a second-order encoding process to process the text.
We have also created a compression corpus that contains a sampling of GB encoded Chinese text documents. The purpose of the corpus is to standardize future experiments with Chinese text compression. As the experiments show in Section 6, PPMO outperforms other approaches on compressing the text in the corpus. This algorithm gained an excellent compression rate of 7.350 bpCc for the small files and 5.938 bpCc for the large files.
Some other language models such as the Interpolated Language Model (Jelinek Reference Jelinek1985) are widely used in the speech recognition area. These models assign a weight to each order model, and then calculate the weighted sum of the probabilities. Different interpolation algorithms such as held-out interpolation (Jelinek Reference Jelinek1985) and word clustering interpolation (Bassiou and Kotropoulos Reference Bassiou and Kotropoulos2005) have been devised on the basis of this idea. Our new PPMO blending mechanism could be used in this area as well. Hence, it is not only of interest to the PPM text compression and language modeling community but also of interest to the wider language modeling community where the adaptive mechanism for encoding the orders may be applicable. The advantage of the coding method that PPMO uses is that it is adaptive—in other words, the ‘weights’ are computed on the fly and so a streaming process is possible rather than an off-line process being required to compute the weights via some optimization method.
In addition, this algorithm should achieve similar improvements in other large alphabet- size languages such as Japanese, Korean, and Thai.
Further work in this area will include an optimization of the coding scheme. It is not clear how the improvements we have detailed here would affect other PPM-based implementations. But it does highlight that there are alternatives to the traditional PPM coding algorithm that may be more appropriate for text (such as Chinese text) that has different properties in the standard text (i.e, English) usually reserved for experimental evaluation.
