Some text compression methods take advantage from using more complex compression units than characters. The synchronization between coder and decoder then can be done by transferring the unit dictionary together with the compressed message. We propose to use a dictionary compression method based on a proper ordering of nodes of the tree-organized dictionary. This reordering allows achieving of better compression ratio. The proposed dictionary compression method has been tested to compress dictionaries for word-and syllable-based compression methods. It seems to be effective for compressing dictionaries of syllables, and promising for larger dictionaries of words.
Dictionary is used in many applications. Sometimes the space occupied by a dictionary is important and should be taken into account. Then it is reasonable to consider storing the dictionary in a compressed form. We propose here a method for the compression of dictionaries. We have focused on dictionaries used for text compression -or even more precisely: on a compression of dictionaries used by word-or syllable-based document compression methods. The comparisons with other methods are therefore oriented to this topic.
The paper is structured as follows: At first (in part two) we describe the dictionaries and give some formal definitions. Then, in part three, we remember some existing methods used to store the dictionaries. Part four is dedicated to the newly proposed methods. The comparisons of the tested methods are presented in part five. Last part (sixth) is dedicated to the summary.
We suppose that a dictionary is a set of ordered pairs (string, number), where the string is a string over an alphabet Σ and the number is an integer of the range 1-n where n is the number of the ordered pairs in the dictionary.
It is sometimes useful to partition the set of all strings (dictionary items) into several disjoint categories. It is possible that the join of the categories does not cover the set of all possible strings over Σ. In this case it is necessary to ensure that the input strings always fit in the given categories.
For the text compression purposes this requirement can be met e.g. by a proper input string selection (partition of the input message into properly formed subparts). Words and syllables are special types of such strings.
It is quite common for the papers on word-and syllable-based compression methods that their authors give no big importance to the compression of the dictionary as the dictionary often makes only a small part of the resulting compressed message. It is probably true for very large documents but for middle-sized documents the importance of a dictionary size grows as the dictionary takes larger part of the compressed message.
The following two approaches are the most widely used: The first approach is based on coding of a succession of strings (words or syllables) contained in it. In the second approach the dictionary is compressed as a whole. All the strings are concatenated using special separators. The resulting file is then compressed using some general method.
There is described a method in [1] for the encoding of strings using a partitioning of the strings into five categories, similarly to the method TD3 described below. Every string is encoded as a succession of string type codes followed by encoded string length and by the codes for individual symbols. String type is encoded using binary phase coding (c1), string length is encoded by adaptive Huffman code (c2), and individual symbols are coded also using adaptive Huffman code (letters by c3, numbers by c4, and other characters by c5). Lower and upper case letters use the same code value c3, they are distinguished by the syllable type. All adaptive Huffman trees are initialized according language specification. Examples are given in Fig. 1.
code("to") = c1(mixed), c2(2), c3('t'), c3('o') code("153") = c1(numeric), c2(3), c4('1'), c4('5'), c4('3') code(". ") = c1(other), c2(2), c5('.'), c5('0') Fig. 1. An example of a coding a string by the CD method It is not necessary to know the whole dictionary at the beginning. It is possible to compress individual items on the fly. It is then possible to encode new items whenever they are encountered. Other methods discussed in this paper need to compress the whole dictionary at once.
Let us have a separator being not part of the used alphabet. Let all the strings forming the dictionary are concatenated to a single string using this separator. The resulting string is then encoded using an arbitrary compression method. In [2] the authors tried to encode the dictionary of word using gzip, PPM, and bzip2 methods and recognized as best for this purpose bzip2. We tried to encode the dictionary using bzip2 [3] (in the tables denoted as BzipD -bzip compressed dictionary) and LZW [4] (denoted in the tables as LZWD -LZW compressed dictionary).
When designing here introduced methods TD1, TD2, and TD3 we decided to represent the dictionary by a data structure trie [5, Section 6.3: Digital Searching, pp. 492-512]. Trie T is a tree of maximal degree n, where n is the size of the alphabet of symbols Σ and satisfies following conditions: The root represents an empty element. Let the string α be represented by the node A, the string β represented by the node B. If the node A is father of the node B, then the string β is created by concatenation of the string α by one symbol from Σ. For all nodes A and B exists a node C, that represents common prefix of strings α and β and this node is on both paths (including border points) from the root to B and from the root to A.
The dictionary trie is created from the strings appearing in the text. Then the trie is encoded. Duriung this encoding there is a unique number assigned to each string using depth-first traversal of the trie.
Trie compression of a dictionary (TD) is based on coding structure of a trie representing the dictionary. For each node in the trie we know the following: whether the node represents a string (represents), the number of sons (count), the array of sons (son), and the first symbol of an extension for each son (extension). Basic version of such encoding (TD1) is given by a recursive procedure EncodeNode1 in Fig. 2 which traverse the trie by a depth first search (DFS) method. For encoding the whole dictionary we call this procedure on the root of the trie representing the dictionary.
In procedure EncodeNode1 we code only a number of sons and the distances between the extensions of sons. For non-leaf nodes we must encode in one bit whether that node represents a dictionary item (e.g. syllable or word) or not. Leafs represent dictionary items always, it is not necessary to code it. Differences between extensions of the sons are given as distances of binary values of the extending characters. For coding of a number of sons and the distances between them we use gamma and delta Elias codes [6]. We have tested other Elias codes too, but we achieved the best results for the gamma and delta codes. The numbers of sons and the distances between them can reach the value 0, but standard versions of gamma and delta codes starts from 1 what means that these codings do not support this value. We therefore use slight modifications of Elias gamma and delta codes: gamma 0 (x) = gamma(x + 1) and delta 0 (x) = delta(x + 1). An example is given in Fig. 3. The example dictionary contains the strings ".\n", "ACM", "AC", "to", and "the". Let us introduce the TD1 method by coding the root of the trie representing our example dictionary:
In the node we must first encode the number of its sons. Root has 3 sons, hence we say that gamma 0 -code of the 3 (sons) is a string of bits '00001' and we write gamma 0 (3) = 00001.
Then we state that the already represented word (an empty string) is not part of the dictionary by writing a bit 0.
Value of the the first son is encoded as a distance between its value and zero by delta 0 (46 − 0) = 0100101111.
Then the first subtrie is encoded by a recursive call of the encoding procedure on the first son of the actual node.
When the first subtrie is fully encoded, we should specify what the second son is. The difference between the first and the second son is 65 − 46, hence we write delta 0 (65 − 46) = 000110011.
Then we encode the second subtrie and the third son and the subtrie rooted in it. Now the whole node and all it subtries are encoded. As our example node is the root, we have encoded the whole trie representing the dictionary.
In TD1 version the distances between sons according binary values of the extending symbols are coded. These distances are encoded by Elias delta coding representing smaller numbers by shorter codes and larger numbers by longer codes. In version TD2 we reorder the symbols in the alphabet according the types of the symbols and their frequencies typical for given language. In our exmaple the symbols 0-27 are reserved for lower-case letters, 28-53 for uppercase letters, 54-63 for digits and 64-255 for other symbols. There are some examples in table 1. Table 1. An example of new ordering of the symbols symbol 'e' 't' 'a' 'I' 'T' 'A' '0' '1' '2' ' ' ',' '.' ord(symbol) 0 1 2 28 29 30 54 55 56 64 65 66
Improving procedure TD1 by a replacement of the expression "son[i] → extension" by the expression "ord(son[i] → extension)" in the lines 08 and 11 we get procedure TD2 (Fig. 4).
Let us demonstrate this method on an example (Fig. 5). The example dictionary contains again the strings ".\n", "ACM", "AC", "to" and "the". We will describe the work of the coding procedure EncodeNode2 on the node labelled by 't'.
In a node we must first encode the number of its sons. Our node has two sons, hence we write gamma 0 (2) = 011.
Then we state that the already represented word (the string "t") is not part of the dictionary by writing a bit 0. ?
. 66 ) P P P P P P q ) Fig. 5. Example of a dictionary for TD2 and TD3
In the new ordering described in version TD2 it is given for each symbol type some interval of the new orders. Function first returns for each type of symbols the lowest orders available for given symbol type. Function first is described in Tab. 2. We are counting (Fig. 6, line 10) and coding (Fig. 6, line 11) the distances between the sons. For the first sons of some nodes of a known type, we can use function first and decrease the value of the distance and shorten the code. We modify version TD2 by a modifying of the line 06 and inserting the lines 07 and 08 getting version TD3.
Let us show the differences between TD3 and TD2 on our example (Fig. 5).
Let us go directly to the node 't'. Here we must first encode the number of the sons of this node (2), we write gamma 0 (2) = 011.
Then we state that the already represented word (string "t") is not part of the dictionary by writing a bit 0.
Value of the the first son of our node is encoded as a distance between its value (3) and and zero (it is the first son) decreased by value of function f irst for a lower-case letter (0). Encoded value is delta 0 (3−0−0) = 01100. It is possible to restrict the shift interval by f irst of the encoded character type as we know this type -in a subtrie of the node 't' occur only lower-case letters. The encoded value is the same as in TD2 but there is a diference is in the calculation.
Other codings are made accordingly. German language has a lot of different and long word forms, the trie representing such dictionary is quite sparse and therefore the TD3 method outperformed other methods only for dictionary of very large documents.
English typically uses less word forms than Czech and German. These word forms are often shorter than the ones used in Czech and German. The trie is then for smaller documents quite sparse and therefore our compression method outperforms the other ones only for larger documents.
In Czech the documents are typically made form lots of middle-sized word forms and the dictionary tries are therefore quite dense. It is the reason why the method has been so successful for the dictionaries of Czech documents.
We have proposed three methods for compression of dictionaries based on the representation of the dictionary by a trie data structure. One of them (TD3) has compressed the dictionary of syllables for given files better than all other tested methods have. It has been also the most successful method for compression of dictionaries of words of large documents.
Such dictionaries are used by many word-and syllable-based compression algorithms. Improving compression ratio of the dictionary improves (although with smaller impact) the overall compression ratio of these methods.
Value of the the first son of 't' is encoded as a distance between its value 3 and zero by delta 0 (3 − 0) = 01100.
Then the first subtrie of node 't' is encoded by a recursive call of the encoding procedure on the first son of the actual node.
When the subtrie of node 't' is fully encoded, we should specify what the second son of the root is. The difference between first and second son is 6 − 3, hence we write delta 0 (6 − 3) = 01100.
Then we encode second subtrie. Now the whole node and all it subtries are encoded.
Words and syllables are special types of strings. We recognize these five types of words (and syllables): lower-words (from lower-case letters), upper-words (from upper-case letters), mixed-words (having the first letter upper-case and the following letters lower-case), numeric-words (from digits) a other-words (from special characters). We know the type of a coded string for some nodes in the trie (in Fig. 6 IsKnownTypeOfSons) and we can use this information.
If a string begins with a lower-case letter (lower-word or lower-syllable), the following letters must be lower-case too. In a trie each son of a lower-case letter can be only a lower-case letter too. Similar situation is for other-words and numeric-words. If a string begins with an upper-case letter, we must look at the second symbol to recognize the type of the string (mixed or upper). In our example (Fig. 5) we know for the nodes 't', 'o', 'h' and 'e' that all their sons are lower-case letters.
We have tested three versions of the method compressing the dictionary using the trie data structure (TD -variants TD1, TD2, TD3), one method compressing the dictionary character-by-character (CD), and two methods using an external compressing tool for the concatenated directory items (LZWD, BzipD).
We have tested the dictionaries of words and syllables for variously sized documents written in following three languages: English (EN), German (GE), and Czech (CZ).
The best for the dictionaries of syllables it appears to be the method TD3 that outperfomed all other tested methods on all tested document sizes. For example, when compressing a 10KB document, TD3-compressed dictionary takes about 770 bytes whereas the second best method (CD) takes about 1450 bytes. In the case of the compression of dictionaries of words the best-performing method has been for small documents (up to 10kB) CD, for middle-sized documents BzipD, and for large documents TD3. The boundary between 'middle-sized' and 'large' documents is in this case dependent on the used language: for Czech it was about 50kB, for English about 200kB and for German about 2MB.
It seems that the success of the TD methods (TD3 inclusive) grows with the average arity of the trie nodes. The syllables are short and the trie representing a dictionary of syllables is typically dense, hence the TD3 method has been always the best.