Syllable-based compression achieves sufficiently good results on text documents of a medium size. Since the majority of XML documents are of that size, we suppose that the syllable-based method can give good results on XML documents, especially on documents that have a simple structure (small amount of elements and attributes) and relatively long character data content.
In this paper we propose two syllable-based compression methods for XML documents. The first method, XMLSyl, replaces XML tokens (element tags and attributes) by special codes in input document and then compresses this document using a syllable-based method. The second method, XMillSyl, incorporates syllable-based compression into the existing method for XML compression XMill. XMLSyl and XMillSyl are compared with a non-XML syllable-based method and with other existing method for XML compression.
The Extensible Markup Language (XML) [5] is a simple text format for structured text documents. XML provides flexibility in storing, processing and exchanging data on the Web. However, due to their verbosity, XML documents are usually larger in size than other exchange formats containing the same data content. One solution to this problem consists of compressing XML documents. Because XML is a text format, it is possible to compress XML documents with existing text compression methods. These methods are more effective, when XML documents have simple structure and long character data content. There are different types of text compression: text compression by characters and text compression by words. There is also a novel method: text compression by symbols [12]. In our work an application of this method to XML documents was developed. Since single text compression is not able to discover and utilize the redundancy in the structure of XML, we modify syllable-based compression method for XML.
At the beginning we supposed that XML syllable-based compression will be suitable for middle-sized textual XML documents. There are many XML documents that meet these conditions, for example any documentation written in DocBook [16] format or news in RSS format [18]. Moreover we suppose that our compression would be more suitable for documents in languages with rich morphology (for example Czech or German [12]).
Syllable-based compression [12] is the method where compression is performed at the syllable level. There are two syllable-based compressors. The first one is syllable-based LZW, and the second one is syllable-based Huffman.
Algorithm LZW [11] is a dictionary compression character-based method. The syllable-based version is called LZWL. In the initialization step, the syllable dictionary is filled with empty syllable and syllables from a database of frequent syllables. The following steps are similar with character-based version of LZW, but LZWL works over an alphabet of syllables.
The second syllable-based compression method is called HuffSyllable. It is a statistical compression method based on the adaptive Huffman coding. For our purposes, we use only LZWL syllable-based compression method. Adaptation of HuffSyllable for XML compression gave worse results than LZWL.
Our goal was to modify the syllable-compression method to compress XML documents efficiently. We attempted to modify existing syllable-based compressor so, that it treats XML tokens (element tags and attributes) as single syllables instead of decomposing them into many syllables. There were two possibilities to compel the syllable-based compressor to treat XML tokens as syllables:
1. Modify parser used in the syllable-based tool and combine it with an XML parser, so that it can recognize XML tokens and treat them as a single syllable. 2. Replace XML tokens with bytes in the input document and then compress such a document with an existing syllable-based tool.
We decided to implement the second way because this implementation allows us to make some future improvements easily. For example, we may compel the syllable-based compressor to assign codes with minimal length to XML tokens by adding this single bytes to the syllable dictionary [12]. This improvement is impossible in the first variant. The encoding of XML tokens is inspired by existing XML compression methods like XMLPPM [3], XGrind [6], XPress [9], XMill [8].
The architecture of XMLSyl is shown in Figure 1. It has four major modules: the SAX Parser, the Structure Encoder, the Containers and the Syllable Compressor. First, the XML document is sent to the SAX Parser. Next the parser decomposes document into SAX events (start-tags, end-tags, data items, comments and etc.) and forwards them to the Structure Encoder. The Structure Encoder encodes the SAX events and routes them to the different Containers. There are three containers in our implementation: When a document is parsed and separated into the containers completely, the contents of the containers are sent to the Syllable Compressor. It compresses the content of each container separately using syllable-based compression and sends the result to the output.
We have not written the SAX parser by ourselves, rather we have used the Expat parser [10] which is an open-source SAX parser written in C.
The structure of XML document is encoded in XMLSyl as follows. Whenever a new element or attribute is encountered, its name is sent to the dictionary and the index of the element is sent to the Data and Structure Container. Two different dictionaries are used for attributes and elements: the Element Dictionary and the Attribute Dictionary. The Attribute Container operates as the Attribute Dictionary and the Element Container as the Element Dictionary. Whenever an end tag is encountered a token END_TAG is sent to the Data and Structure container. Whenever a character sequence is encountered, it is sent to the Data and Structure Container without changes. Start and end of character sequences are indicated by special tokens. We distinguish four different character sequences: value of attribute, value of element, comment, and white spaces between tags, if white spaces are preserved.
To illustrate the encoding process, consider the encoding of the following small XML document: <book> <title lang="en">XML</title> <author>Brown</author> <author>Smith</author> <price currency="EURO">49</price> </book> <!--Comment--> First, the XML document is converted into a corresponding stream of SAX events: startElement("book") startElement("title",("lang","en")) characters("XML") endElement("title") startElement("author") characters("Smith") endElement("author") startElement("author") characters("Brown") endElement("author") startElement("price","currency","EURO") characters("49") endElement("price") endElement("book") comment("Comment")
The tokens in the SAX event stream are sent to the Structure Encoder. It encodes them and sends them to their corresponding containers. When the book start element token is encountered, the string book is sent to the Element Container since this element name was not encountered before. An index E0 is assigned to this entry. This index is sent to the Data and Structure Container. The same operation is executed for title start element. String title is sent to The Element Container and an index E1 is assigned to it. The index E1 is sent to the Data and Structure Container. The element title has the attribute lang. The attribute name is sent to the Attribute Container and the index A0 is assigned to it. The index A0 is sent to the Data and Structure Container. Then attribute value "en" is sent without modification to the Data and Structure Container. The "en" attribute is followed by the token END_ATT, that signals the end of the attribute value. When an element value such as "XML" is encountered, the token CHAR, signaling the beginning of character sequence, the data value and then the token END_CHAR are all sent to the Data and Structure Container. Finally, all the end tags are replaced by the token END_TAG. When a comment event is encountered, the code CMNT is put into the Data and Structure Container. The comment is also sent to the container and is enclosed by END_CMNT code. The final state of all containers is shown in Figure 2. In this example we have ignored white spaces between tags, e.g. <book> and <title>, so the decompressor then produces a standard indentation. Optionally, XMLSyl can preserve the white spaces. In that case, it stores the white spaces as the sequence of characters in the Data and Structure Container between tokens WS and END_WS.
The containers are the basic units for grouping XML data. The Attribute Container holds attribute names and the Element Container holds element names. As long as the number of all element and attribute names in any XML document is not high, this two containers are kept in main memory. During parsing, the containers size increases as the container is filled with entries. Each entry in the Element container is assigned a byte in the range 00-A9. These bytes are used for encoding the element names. Each entry in the Attribute container is assigned a byte in the range AA-F9. These bytes are used for encoding the attribute names. The residual 6 bytes are reserved for special codes like CHAR, END_TAG etc. In most cases, 170 (or 80) bytes are enough to encode element (or attribute) names. If the number of elements (or attributes) are greater than 170 (or 80), entries are encoded with two bytes, then tree and so on.
There is another situation with The Data and Structure Container. We do not know the size of the input XML document. The size of XML document can be so big, that document will not fit into memory, and it is not possible to increase the size of container endlessly. Therefore, the container consists of two memory block of constant size. The content of the first memory block is compressed, as soon as the container is filled. We don't compress two blocks at once, because the context of the second memory block is used for compression of the first one. After the compression, the compressed content of the first block is sent to the output and the first block swaps its purpose with the second one. Now the first block is filled with data. When it is full, the second block is compressed, and so on.
The Syllable Compressor compresses the Structure and Data Container first and sends the output to the output file. Then the Attribute Containers are compressed and sent to the output file and finally the same happens with the Element Container. LZWL is used for the compression of data. HuffSyll could be also chosen, but the performance is worse, so we decided to use only LZWL.
This chapter introduces our second syllable-based XML compressor, XMillSyl. This second method incorporates syllable-based compression with the existing method for XML compression of XMill [8]. XMill has two main principles in order to optimize XML compression:
separating structure from data content, and grouping Data values with related semantics in the same "container".
Each data container is then compressed individually with gzip [21]. In XMillSyl, containers are compressed with LZWL.
We do not suppose that XMillSyl method gives better results than XMill because gzip compression performs better than LZWL. We have implemented XMillSyl in order to compare the power of XMLSyl with the power of two main principles of XMill.
We did not write XMill compressor. We decided to use existing sources of XMill.
XMill operates as follows: a SAX parser parses the XML file and the SAX events are sent to the core module of the XMill called the path processor. It determines how to map tokens to containers: element tag names and attribute names are encoded and sent to the structure container, while the data values are sent to various data containers, according to their semantic. Finally, the containers are gzipped independently and stored on disk.
We have modified compression and decompression functions (operating on containers) in the way they compress and decompress the data containers with the syllable-based method (see Figure 3). Moreover we have modified the syllablebased method so that it can work with the containers of XMill implementation instead of a file stream. XMillSyl discerns the difference between small and large containers. Since LZWL is not suitable for extremely small data, the small containers are compressed with gzip. The structure container is also gzipped in XMillSyl. The large containers are compressed with LZWL.
To show the effectiveness of XMLSyll and XMillSyl, we compared the performance of this two compressors with one representative of XML compressors XMill and the syllable-based compressor LZWL [12].
XMLSyl and XMillSyl were tested on two data sets that cover a wide range of XML data formats and structures. The first data set is shown in Table 1.
It contains English XML documents with different inner structure. It includes regular data that has regular markup and short character data content (elts, stats, weblog, tpc). It also includes irregular data, that has irregular markup (pcc, tall).
The second data set is shown in Table 2. It contains textual XML documents of simple structure with long character data content. It contains five stage plays marked up as XML, four in English and one in Czech. It also contains data in DocBook format in Czech and in English.
Some data was distributed with the XMLPPM [3] and the Exalt [4] compressors while others were found on Internet [15], [16]. All Czech documents use Windows-1250 encoding. V set2 Murkup menshe chem 50% I harakter dannych tekstovyj=> pokazyvajet horoshije rezultaty.
The compression ratio is defined as follows:
We compare XMillSyl and XMLSyl compression ratios with those of XMill. The compression ratio factor shows normalization of the compression ratio of XMillSyll or XMLSyl with respect to XMill. The compression ratio factor is defined as follows: CRF XSyl = CR XSyl CR XM ill .
The compression ratio statistics of two sets of XML documents are shown in Table 3 and Table 4.
The syllable-based method performed worse on documents from the first data set. On the other hand, both XMLSyl and XMillSyl shows great improvement comparing to LZWL. They compressed the input to 50-60% of the size of the compressed file with LZWL.
On XML documents of the second data set, LZWL provides a reasonably good compression ratio -on the average, about two-thirds that of XMill. This confirms our prediction, that syllable-based compression is effective for textual XML documents. Moreover our compression methods show even greater improvement.
On the document of the second data set, XMillSyl achieves about 15% and XMLSyl is about 20% better compression ratio than LZWL. Compared to XMill, both methods perform slightly worse. XMillSyl compresses about 13% and XML-Syl about 7% worse than XMill.
Figure 4 shows the variation of the compression ratio as a function of XML data size for "DocBook: The Definitive Guide".The compression was run on several subsets. On small files XMillSyl performs better than XMLSyl. The explanation is, that the data are split into many small containers in XMillSyl, which are compressed with gzip (gzip outperforms LZWL, especially on small data). On middle-sized and large files XMLSyl outperforms XMillSyl. We can observe that the bigger size also implies a better compression.
In this work we introduced syllable-based compression tools for XML documents called XMLSyl and XMillSyl. We presented the architecture and implementation of our tools and tested their performance on a variety of XML documents. In our experiments, XMLSyl and XMillSyl were compared with LZWL and XMill. Both methods are more suitable for textual XML documents. XMill outperformed our methods only marginally. XMLSyl performs better than XMillSyl. It implies that in our case encoding of XML structure is more efficient than separating a structure from data and grouping data values with related meaning. XMillSyl and XMLSyl show better results for Czech language.
In the future, we want implement some modifications to enhance the compression ratio. For example, the information in the DTD section can be extracted and utilized to create a special syllable dictionary for elements and attributes.