Balisage Paper: XML Entropy Study

Size

The size of the XML document is the size in bytes of its serialization (textual or binary). However, to have a coherent measurement for all XML documents in the testing corpus, we computed the size by serializing the parsed XML document. This enabled to remove some variations such as the presence or absence of the XML declaration, the presence or absence of DTD, the presence of superfluous white-spaces, and the use of DTD to include external content in the document. In the rest of this document, we will call this process ‘normalization’.

The size of the XML documents in our testing corpus varies from 133 bytes to 62,750,078 bytes, with an average of 364,620 bytes and a standard deviation of 2,790,290 bytes.

To use the size as a criterion, three classes of document were considered. Small documents have a size smaller than or equal to 1,000 bytes. Medium documents have a size between 1,000 bytes and 10,000 bytes. Large documents have a size greater than 10,000 bytes.

Information density

The second measurement used is information density: information density represents the part of content in the XML document relative to the part of structure in the XML document. The content size of an XML document is computed by summing the size of all character data (the “value” of elements) and attribute values present in the XML document, in bytes. The information density is computed as the ratio between the content size and the size, in bytes, of the XML document.

A low information density means that the document contains mainly structural information, while a high value means that the document contains mainly actual contents (non-element and non-value definition contents).

The information density of the XML documents in the testing corpus varies from 0 to 1, with an average of 0.39 and a standard deviation of 0.23.

While there is a variety of XML documents with low information density values in our corpus, XML documents with large information density values are mainly SVG (Scalable Vector Graphics), with some X3D (Extensible 3D) documents and scientific information documents.

The limit between structure-rich XML documents and information-rich XML documents was chosen to be the value of 0.33 for the information density parameter. This means that a document is considered as structure-rich when the part of content in it is less than one third of the total document.

Structure regularity

The third measurement represents the regularity of the structure of the XML document. We chose the following simple definition: the structure regularity is computed as one minus the ratio of the total number of distinct elements over the total number of elements in the XML document.

High structure regularity means that the document is very regular, using only a few number of distinct elements, while low structure regularity means that the document is irregular, using many different elements.

The structure regularity of the XML documents in our testing corpus varies from 0 to 1, with an average of 0.56 and a standard deviation of 0.36.

We chose 0.9 as the limit to separate regular from irregular XML documents. XML documents with a higher regularity are considered as regulars, while XML documents with a lower regularity are considered as irregulars.

This limit means that for a regular XML document, each element, in average, is repeated at least 10 times. Ten times may be considered large, but is indeed small compared to typical large regular documents, which can contain hundreds or thousands of repetitions (e.g., an address book).

Naïve evaluation

A naïve evaluation of the quantity of information contained in an XML document is to use the first-order entropy of this document considered as a set of characters.

Figure 1 displays this first-order entropy value, in the form of the cost in bytes of the whole document, and compares it to several values. The first comparison value is the size of the XML document. The two other comparison values are the size of the XML document compressed with gzip or bzip2.

Figure 1: XML Document Sizes

Comparison of four size-related measures for the documents from the testing corpus: the base document size, the compressed size using gzip, the compressed size using bzip2, and the first-order entropy cost.

In addition, the results are sorted by increasing document size to enable a more meaningful comparison.

The results show that for all documents, the first-order entropy, as expected, is lower than the document’s size. However, in most cases, the compressed size (both with gzip and bzip2) is lower than this first-order entropy. These apparently surprising results are due to the fact that the hypothesis of independence between the symbols used to compute the first-order entropy does not hold. This entropy value does not represent accurately the quantity of information contained in an XML document.

For example, for someone quite knowledgeable of the XML specification, the name of an element contained in a closing-tag carries no informative value.

For it to become be useful, the quantity of information contained in an XML document must be evaluated by also taking into account the structure of this document. This evaluation is presented in the remaining of this section. It was realized by splitting the different sources of information comprised in an XML document, and evaluating the quantity of information for each source using its first-order entropy measure.

XML structure

An XML document is a tree-like structure mostly composed of elements, attributes (definition and values) and textual data. For the purpose of this study, it is useful to represent an XML document as a sequence of events, in a manner similar to SAX (Simple API for XML) or StAX (Streaming API for XML).

In such a representation, an XML document is represented by a list of events, each event being described by its type and content. For example, the start-tag of an element is described by an event of type start-element, whose value is the name of the element. Table I lists all the types of events used to represent an XML document, and succinctly describes each of them.

Structure-based evaluation

Using the event representation of an XML document, a fine-grained evaluation of the entropy of XML documents can be computed. It is a general principle to split a piece of data to be compressed, such as a picture, a movie, or a textual document, into several independent sources of information. Each source of information can then be compressed more efficiently. Similarly, an XML document is split into several sources of information. First, a list of event types describes the type of each event contained in the representation of the XML document. Then several other sources of information are used to describe the content of these events: the list of element names, the list of attributes, the list of character contents, the list of comments and the list of processing instructions. The list of attributes is further divided into a list of attribute names and a list of attribute values, or considered as a whole.

The rest of this section contains the evaluation of each of these sources of information using several representations. Indeed, each source of information can be structured or further divided with several methods. For each source of information, the main methods used by binary XML encodings and variations thereof have been studied.

The documents of the testing corpus contain only few occurrences of comments or processing instructions. Therefore, the results obtained for those pieces of information were not deemed significant and are not presented here.

Example XML Document

For a better understanding of the different types of representations described afterwards, the following XML document will be used as an example.

<article xmlns="http://docbook.org/ns/docbook">
	<section>
		<title>Introduction</title>
		<para>XML...</para>
	</section>
	<section>
		<title>Testing Corpus</title>
		<section>
			<title>XML document sources</title>
			<para>To provide...</para>
		</section>
	</section>
</article>

Introduction

Event types form the backbone of the XML document representation: by describing the type of each event, they describe the base structure of the XML document, and point at the source of information to use for completing this structure for each event.

The set of events used here is close to those used in SAX or StAX. Compared to those APIs, we kept only the main events, removed events related to the document’s start and end (which, in themselves, provide no meaningful information), and events related to DTD and entities. In addition, we chose to be closer to the StAX model by separating attributes from their owning element.

Representations

Two different methods for representing the list of event types have been studied from the entropy point of view. It should be noted that the set of all possible event types is defined by the XML specification. Therefore, event types can be represented by tokens defined beforehand and no indexing mechanism is needed for them.

First, the list of event types can be considered as a sequential list (list representation). This is a representation used by most binary XML technologies.

Using this representation, for the example document, the event types to be encoded are represented by the following list. In this list, // is used for delimiting comments.

SE // article
SE // section
SE // title
CH
EE // title
SE // para
CH
EE // para
EE // section
SE // section
SE // title
CH
EE // title
SE // section
SE // title
CH
EE // title
SE // para
CH
EE // para
EE // section
EE // section
EE // article

Second, the list of event types can be partitioned according to the name of their containing element (part representation). That means that the list of event types is split into sub-lists corresponding to the content of each element. Then, those sub-lists are grouped according to their element names. Such a representation further splits the list of event types into several sources of information. There is no cost associated to this separation, as for each event type its containing element can be reconstructed from the list of event types and of element names: it is the latest element for which a “Start-tag” event was encountered without a matching “End-tag” event. Such a representation is used by the EXI format.

In this representation, the same event types are to be coded, but they are spread over five different partitions, depending on their enclosing element: document, article, section, title, and para. The document partition is used for the root element. In the following description, the partition for each event is given in curly brackets. There is no need to encode this partition, as the current element can be retrieved from what was previously parsed.

{document} SE // article
{article}  SE // section
{section}  SE // title
{title}    CH
{title}    EE // title
{section}  SE // para
{para}     CH
{para}     EE // para
{section}  EE // section
{article}  SE // section
{section}  SE // title
{title}    CH
{title}    EE // title
{section}  SE // section
{section}  SE // title
{title}    CH
{title}    EE // title
{section}  SE // para
{para}     CH
{para}     EE // para
{section}  EE // section
{section}  EE // section
{article}  EE // article

Results

For each document, the entropy associated to encoding event types was computed using as unit the number of bytes to represent an event type.

As there are 7 different types of events (see Table I), the entropy for representing them as a list corresponding to a uniform distribution can be computed by the formula:

Figure 2 represents the repartition of the entropy values for both the list representation and the partitioned representation.

Figure 2: Event Type Histogram

Distribution of the entropy for event types, computed in byte per event type, for the list representation and the partitioned representation.

For the list representation, the average entropy is 0.23 byte per event, with a standard deviation of 0.03. For the partitioned representation, the average entropy is 0.12 byte per event, with a standard deviation of 0.03.

It can be noted that the partitioned representation has lower entropy values than the list representation, which is what we expected.

Figure 3 shows the ratio between the entropy for the partitioned representation and for the list representation for the different categories of XML documents. On average, this ratio is 0.50, with a standard deviation of 0.10. The differences amongst the categories of documents remain small. The only exception is for the small document category for which the ratio is greater than for the other representations. This comes from the fact that small documents contain only a limited number of elements and therefore provide fewer opportunities for partitioning to be efficient.

Figure 3: Event Type Entropy Ratio

Ratio of the event type entropy between the partitioned representation and the list representation for the different categories of documents.

As a conclusion, the partitioned representation has much lower entropy than the basic list representation, with an average entropy cost of half the average entropy cost of the list representation.

Introduction

Start element events are described by their type and the name of the element. There is no name associated to the description of end element events, as this name can be determined by finding the corresponding start element event. Therefore, the name contained in the end-tag construct of the XML markup is redundant information.

The useful information about an element’s name is the URI of its namespace and its local name. However, this information can be represented in several ways. Indeed, it was foreseen during the writing of the Namespaces in XML 1.0 [XML Namespaces] specification that using the URI in each element’s name would be too verbose for XML documents. Therefore, a shortcut mechanism was designed from the start to represent an element’s name using a prefix associated to its namespace.

While in XML the usage of the prefix is important for reducing the size of the XML document (and also for syntactic reasons), in many cases the prefix in itself has no other usage and can be discarded by binary XML formats. Therefore, this study ignores in most cases the cost associated to encoding prefixes. In any event, this cost is often very low compared to the rest of the XML document.

Representations

Several representations can be used to encode element names.

First, element names can be encoded as null-terminated strings. There are two options for specifying the namespace of the element: either using the URI of the namespace (lst-URI representation), or using a prefix (lst-pr representation) associated to this URI.

Using the lst-pr representation, the element names of the example document would be represented as follows.

// Prefix binding
=http://docbook.org/ns/docbook // Binds the default prefix
// Element names
:article
:section
:title
:para
:section
:title
:section
:title
:para

A second possibility is to use indexes for the namespace and the local name. For evaluating the entropy cost, the cost of the definition of those indexes must be taken into account. An index definition can be represented by an ordered list of its values. For local names, the index can be either global (idx representation), or it can be partitioned by namespace (idx-part representation).

For the example document, the idx representation would be the following.

// Namespace list
http://docbook.org/ns/docbook
// Local name list
article
section
title
para
// Element names
1,1 // article
1,2 // section
1,3 // title
1,4 // para
1,2 // section
1,3 // title
1,2 // section
1,3 // title
1,4 // para

The idx-part representation would be very similar for the example document, as it uses only one namespace. In the general case, there is one Local name list for each namespace. Here, there would be only one Local name list for the http://docbook.org/ns/docbook namespace.

A third possibility is to use surrogates to represent the element names. A surrogate is an index representing a whole element name, that is both its namespace and its local name. A surrogate can be defined in several ways. The namespace corresponding to a surrogate is best specified using an index. The local name corresponding to a surrogate can be specified as a string (sur-lst representation), as an index (sur-idx representation), or as an index partitioned by URI (sur-idx-part representation).

For example document, the sur-idx surrogate representation would be the following.

// Namespace list
http://docbook.org/ns/docbook
// Surrogate list
1,article
1,section
1,title
1,para
// Element names
1 // article
2 // section
3 // title
4 // para
2 // section
3 // title
2 // section
3 // title
4 // para

A last possibility is to partition the representation of element names according to their enclosing element. Inside a partition, an element name can be represented as a set of strings, using either a URI or a prefix for the namespace (part-lst-URI and part-lst-pr representations), as a set of indexes (part-idx and part-idx-part representations), or as a surrogate, the surrogate being either defined locally for each partition (part-sur-lst, part-sur-idx, and part-sur-idx-part representations) or globally for all the partitions (part-sur-glob-lst, part-sur-glob-idx, and part-sur-glob-idx-part representations).

For the part-idx representation, the element names of the example document would be encoded as follows. The partitions are given in curly brackets for clarity, but don't need to be encoded.

// Namespace list
http://docbook.org/ns/docbook
// Element name lists
// Document partition
article
// article element partition
section
// section element partition
title
para
section
// Element names
{document} 1 // article
{article}  1 // section
{section}  1 // title
{section}  2 // para
{article}  1 // section
{section}  1 // title
{section}  3 // section
{section}  1 // title
{section}  2 // para

Results

For each document, the entropy associated to encoding element names was computed using as unit the number of bytes needed to represent an element name.

Figure 4 shows a summary of those results by displaying, for each representation, the average entropy associated to element names, and the standard deviation.

Figure 4: Element Name Summary

Average entropies, computed in bytes per name, of the different representations for element names. The lst-URI and the part-lst-URI columns have been willingly cut as their values are far above the other values.

The first result is that representations using strings for representing the namespace’s URI have entropies much higher than all the other representations (the vertical scale of Figure 4 was willingly chosen to cut those numbers in order to better show the differences between the other values). The lst-URI representation has an average of 18.64 bytes per element name, with a standard deviation of 6.76, and the part-lst-URI representation has an average of 17.41 bytes per element name, with a standard deviation of 7.02.

Figure 5 and Figure 6 show the distribution of entropy values for a selection of representations. Some features of these distributions can be linked to documents with specific characteristics.

Figure 5: Element Name Histogram - Lists

Distribution of entropies for selected representations of element names based on list of strings or on indexes. The lst-URI histogram has been willingly cut.

Figure 6: Element Name Histogram - Surrogates

Distribution of entropies for selected representations of element names based on surrogates.

The documents with high entropy (around 45 bytes per element name, not displayed on the histogram) for the URI-based representations correspond to medium-sized documents containing several different URIs (from 5 to 7).

The few documents with high entropy (greater than 20 bytes per element name) for the prefix-based representations correspond to documents with very long element names (40 or 50 characters).

For all index-based representations, the documents with a high entropy value (around 25 bytes per element name) are documents containing only one element.

On a more global level, Figure 4 showed that prefix-based representations are much closer to index-based representations than to URI-based representations in terms of entropy values. However, Figure 5 shows that the distributions of those entropy values are very different for prefix-based and index-based representations. Whereas for prefix-based representations, the entropy values roughly follow a normal distribution, for index-based representations, the entropy values roughly follow a geometric distribution. Those differences are directly linked to the kind of representation used.

Several conclusions can be drawn from the results obtained. First, using local-name indexes partitioned according to the namespace decrease the entropy.

Second, partitioning the representation according to the parent element also decrease the entropy.

Third, while using surrogates, the best representation for a surrogate definition is to use an index for the URI, but a string for the local name. Indexing the URI is efficient, as a URI is reused for several surrogate definitions. But indexing a local name is usually not efficient, as a local name is often only used for one surrogate definition.

In addition, the best surrogate-based representation usually has a slightly lower entropy value than the corresponding index-based representation. This is the case for sur-lst compared to idx and for part-sur-lst compared to part-idx. This is however not the case for part-sur-g-lst compared to part-idx.

Lastly, for representations using surrogates partitioned according to the parent element, those using a global surrogate definition have higher entropy than those using a local surrogate definition.

Figure 7 compares the entropies for some selected representations for the different categories of documents. The main result is that while the lst-pr representation has only small entropy variations across the different categories, the four other representations, all index-based representations, have much more important variations. But the relations between those four representations stay similar across all categories.

Figure 7: Element Name Categories

Comparison of average entropies depending on the category of documents for some selected representations of element names.

This figure shows expected results: for index-based representation, the entropy is lower for larger documents. It is also lower for regular documents.

The conclusion for element names is that the lowest entropy results are obtained by the combination of indexing, partitioning and surrogate usage. On average, the best combination is to use partitioned surrogates, where surrogate definitions use indexes for the URIs and strings for the local names. However, for some document categories, a simple listing of the prefix and local name has lower entropy values.

Introduction

Attributes can be considered either as a whole, or by separating names and values. However, in most cases when an attribute is used several times in a document, it will have different values. Therefore, a join representation of element names and values is not an attractive option and we selected to study only independent representations. In this section, we consider the representations of attribute names. The representations of attribute values are studied in a later section.

Representations

As attribute names and element names are very similar, the same representations were used for attribute names as for element names.

Results

Similarly to element names, for each document, the entropy associated to attribute names was computed using as unit the number of bytes needed to represent an attribute name.

Figure 8 shows a summary of those results by displaying, for each representation, the average entropy associated to attribute names and the standard deviation.

Figure 8: Attribute Name Summary

Average entropies, computed in bytes per name, of the different representations for attribute names.

A first result is that the representations for attribute names have lower entropies than the corresponding representations for element names. This is due to the fact that in many cases, attribute names have no namespace. This is especially true for URI-based representations.

However, for most representations, the standard deviation is higher than for element names. This comes from the fact that in a few cases the attribute names have a namespace, and therefore higher entropy cost.

Figure 9 and Figure 10 show the distributions of entropy values for a selection of representations.

Figure 9: Attribute Name Histogram - Lists

Distribution of entropies for selected representations of attribute names based on list of strings or on indexes. The lst-URI histogram has been willingly cut.

Figure 10: Attribute Name Histogram - Surrogates

Distribution of entropies for selected representations of attribute names based on surrogates.

For most representations, the distribution of entropy values contains a group of documents with entropy values higher than the main group of documents. This group contains the documents containing attributes with a defined namespace.

Apart from this point, the results are quite similar to those obtained for the representations of element names. The last difference is that using a surrogate increases the entropy. This is also due to the fact that many attributes have no specific namespace.

Figure 11 compares the entropies for some selected representations for the different categories of documents. The results are similar to those obtained for element names apart for the differences already noted.

Figure 11: Attribute Name Categories

Comparison of average entropies depending on the category of documents for some selected representations of attribute names.

As a conclusion, for attribute names, the lowest entropy values are obtained by combining indexing and partitioning. Here, surrogate usage does not decrease the entropy values. On average, the best combination is to use partitioned indexing, with local names indexes being partitioned according to their URI. However, as for element names, for some document categories, a simple listing of the prefix and local name has a lower entropy value.

Introduction

While the two previous sections considered element and attribute names separately, they can also be considered jointly. In particular, element and attribute names may share the same namespace, even if many attributes have no namespace value.

Representations

Several representations can be used to encode jointly element and attribute names. Those representations are similar to those used for element names or attribute names, but can vary in the degree of separation used between element names and attribute names.

First, the names can be encoded as null-terminated strings, specifying the namespace either through its URI (lst-URI representation) or through its prefix (lst-pr representation).

A second possibility is to use indexes for the namespaces and the local names. When using an index, two components can be shared: the definition of the indexes from the string values, and the list of items, expressed as index values. Element names and attribute names can be indexed jointly, sharing both the index definitions and the listing of indexed values (idx-j representation). They can share a common index for namespaces and local names, but with separated lists of indexes (idx-cc representation). Last, they can have a common index for namespaces with separated lists of indexes, and separated indexes and lists for local-names (idx-cs representation). As an option, the indexing of local names can be partitioned according to their namespace (idx-j-part, idx-cc-part, and idx-cs-part representations).

For the idx-j representation, the structure of the representation would be the following.

// Namespace list
...
// Local name list
...
// Element and attribute names
...

For the idx-cc representation, the structure would be as follows.

// Namespace list
...
// Local name list
...
// Element names
...
// Attribute names
...

For the idx-cs representation, it would be the following.

// Namespace list
...
// Element local name list
...
// Attribute local name list
...
// Element names
...
// Attribute names
...

A third possibility is to use a partitioned representation according to the enclosing element. All the possibilities of the previous index-based representations were reused with partitioned representations (part-idx-j, part-idx-cc, part-idx-cs, part-idx-j-part, part-idx-cc-part, and part-idx-cs-part representations).

The possibility of using surrogates was not studied here, as the previous results showed that they were very close to the simple index-based representations.

Results

As for the analysis of separate representations of element and attribute names, the entropy associated to combined representations of element and attribute names was computed using as unit the number of bytes needed to represent one of those names.

In addition to all the representations combining element and attribute names, some representations separating element and attribute names were included for comparison purpose. Those references are using string representations (lst-URI-ref and lst-pr-ref representation), index-based representations (idx-ref and idx-ref-part representations), and partitioned representations (part-idx-ref and part-idx-ref-part representations). The entropy values for those reference representations were computed by combining the values of the corresponding independent representations.

Figure 12 shows a summary of those results, displaying the average entropy and the standard deviation for each representation. As for element names, the chosen scale has been willingly selected to cut the values of the string-based representations using URIs as they were far greater than the other values. For lst-URI-ref representation, the average entropy is of 15.00 bytes per name, with a standard deviation of 7.41, while for the lst-URI representation, the average entropy is of 15.40 bytes per name, with a standard deviation of 7.41.

Figure 12: Name Summary

Average entropies, computed in bytes per name, of the different representations for element and attribute names. The lst-URI-ref and the lst-URI columns have been willingly cut as their values are far above the other values.

The main result is that while a join representation increases the entropy for string-based representations, it decreases the entropy for index-based representations.

Figure 13 and Figure 14 show the distributions of entropy values for selected string-based and simple index-based representations.

Figure 13: Name Histogram - List

Distribution of entropies for selected representations of element and attribute names based on list of strings.

Figure 14: Name Histogram - Index

Distribution of entropies for selected representations of element and attribute names based on indexes.

The main result is that for simple index-based representations, the lowest entropy values are obtained for the idx-cs representation. This corresponds to the fact that element and attribute names generally share the same set of URIs, but with different usages, while they have different sets of local names.

This result mostly holds for more complex index-based representation. The exception is for representations partitioned according to the containing element and with local name indexes partitioned by namespace. For these representations, the lowest entropy values are obtained for the part-idx-j-part representation.

Figure 15 compares the entropies for some selected representations for the different categories of documents. The main results from this figure is that the relationships found between the index-based representations are maintained for all categories, and that the relationships found previously between string-based and index-based representations depending on the category of documents are also maintained.

Figure 15: Name Categories

Comparison of average entropies depending on the categories of documents for some selected representations of element and attribute names.

The conclusion that can be drawn from these results is that for index-based representations, the lowest entropy is obtained by a partial joining of the representations of element names and attribute names.

Introduction

Namespace declarations are used to associate a prefix to a URI representing a namespace. As previously stated in the section for element names, in many cases the prefixes can be discarded by binary XML formats. However, in some cases, prefixes are used in attribute values for specifying a qualified name (for example, in XML Schema to associate a type to an element or to an attribute). In such cases, the namespace declarations must be preserved.

A namespace declaration is constituted of two components: the URI of the namespace and the prefix associated to it.

Representations

Several representations can be used to encode a namespace declaration.

First, both the URI and the prefix can be encoded as null-terminated strings (lst representation).

A second possibility is to use indexes. As URI are long and can be used in several declarations, while prefix tend to be short and not reused, a first option is to index the URIs and simply list the prefixes (idx-lst representation). A second option is to index both the URIs and the prefixes (idx representation).

A third possibility is to partition the prefix definition according to their URIs. The URIs are indexed, and in each partition, the prefixes can either be represented with a string (part-lst representation) or as an indexed value (part-idx representation).

Results

For the documents of the testing corpus, the entropy associated to namespace declaration is computed using as unit the number of bytes needed to represent a namespace declaration.

Figure 16 displays the distribution of the entropy values for the different representations.

Figure 16: Namespace Histogram

Distribution of entropies for the representation of namespace declarations.

These results show that using indexing reduces the entropy. However, indexing only the URI is slightly better than indexing both the URI and the prefix. This is explained by the fact that prefixes are usually short and not repeated.

Partitioning has a somewhat stronger effect than indexing. For the prefix definition in partitioned representations, both direct string and indexed representation have the same entropy values.

It should be noted that in most cases, a document contains only a few or no namespace declarations. However, a few sample documents from the testing corpus contained a lot of namespace declarations (from 150 to 3000). Those documents are automatically generated documents with repetition of namespace declarations for each separately generated element. For such documents, indexing reduces significantly the entropy value.

As a conclusion, in most cases, where only a few namespace declarations are used and no redundancies are present in those declarations, all the representations have almost the same entropy. However, when taking into account all the cases, using a partitioned representation gives the best results.

Introduction

In addition to their name, attributes are also defined by their value. In this section, we consider the representation of attribute values independently of their names.

Representations

A few different representations can be used for attribute values.

First, the attribute values can be represented as null-terminated strings (lst representation).

Second, the attribute values can be indexed (idx representation). As for the element names, the cost of the index definition must be taken into account.

Third, the attribute value representation can be partitioned according to the attribute name. This can be done either for a string-based representation (part-lst representation) or for an index-based representation (part-idx representation).

Last, in a partitioned representation, the attribute values can be represented by using a global index instead of local ones (part-idx-glob representation).

Results

The results for attribute values were obtained by measuring the entropy associated to them, using as unit the number of bytes needed to represent an attribute value.

The first thing of note is that there is a huge variation in the results obtained depending on the document. While most documents have entropies ranging from 0 to 100 bytes per attribute value, there are a few documents with much greater entropies (up to about 12,000 bytes per attribute value).

Those documents with very high entropies for attribute values are either SVG or X3D documents containing large graphical information in one (or more) attribute values.

Taking into account those documents skew the results and do not provide many insights on the different representations. In particular, the average entropy value is almost the same for all the representations.

Therefore, to enable a better analysis of the attribute value representations, those documents were removed from the testing corpus. Specifically, all documents for which the average attribute value entropy was greater than 100 bytes per attribute value for the lst representation were discarded. There were 33 such documents.

Figure 17 shows the distributions of entropies for the reduced testing corpus. These distributions show that indexing and partitioning reduce the entropy. Indexing has a somewhat stronger effect. In addition, indexing and partitioning can be combined, enabling their respective entropy reductions to partly combine. Using a global index and a partitioned list of value is slightly less efficient than using a partitioned index.

Figure 17: Attribute Value Histogram

Distribution of entropies for the representations of attribute values, on the reduced testing corpus (i.e., without documents with entropy values greater than 100 bytes).

A more detailed analysis was conducted by analyzing the results for each category of documents on this reduced testing corpus. It should be noted that the removed documents mostly belong to the large, information-rich, and irregular categories.

The main result obtained is that partitioning is more effective than indexing for small documents. On the other hand, indexing is more effective than partitioning, for large documents, for information-rich documents, and for regular documents.

In all case the combination of indexing and partitioning leads to lower entropy results than using only one of those mechanisms. Joining the two mechanisms has a greater impact for the medium, structure-rich and irregular documents.

In addition, in most cases, using a global index gives slightly higher entropy values than using partitioned indexes. The main exceptions are the information-rich and irregular documents.

As a conclusion, the representation with the lowest entropy for attribute values is the one using partitioning according to the attribute name and locally indexed values.

Introduction

Character contents representation is very similar to attribute values representation. Both represent textual information contained in an XML document. Where an attribute value is related to an attribute, a character content item is related to an element.

However, character contents and attribute values have different natures and therefore, it is expected that some differences will appear in the results.

Representations

For character contents, the same representations were used as for attribute values (lst, idx, part-lst, part-idx, and part-idx-glob representations)

Results

The results for character contents were obtained from the testing corpus and are expressed using for unit the number of bytes needed to represent a character content item.

It should be noted that the documents from the testing corpus were pruned of any whitespace character content, and that all contiguous character contents were joined together (i.e., removing newlines).

A second thing to note is that, as for attribute values, there are a few documents with much larger entropy values than the others (up to about 500,000 bytes per character content). These documents with very high entropy values are either SVG documents containing application specific additions, or some scientific data files.

To enable a better analysis of the character content representations, documents with average character content entropy greater than 100 bytes per character content item for the lst representation were pruned from the testing corpus. There were 25 such documents.

Figure 18 shows the distribution of the entropy values for the reduced testing corpus. Those results show that both indexing and partitioning reduce the entropy. On average, indexing enables a somewhat more important reduction than partitioning. Combining indexing with partitioning enables combining part of their respective reductions of entropy. Last, using a global index with partitioned list of values representation leads to greater entropy values than a fully partitioned indexed representation.

Figure 18: Character Histogram

Distribution of entropies for the representations of character contents on the reduced testing corpus (i.e., without documents with entropy values larger than 100 bytes).

A more detailed analysis was conducted on the different categories of documents. The removed documents mostly belong to the large, information-rich and irregular categories.

The first result is that indexing is more effective than partitioning for large documents, for information-rich documents, and for regular documents. On the contrary, partitioning is more effective than indexing for small documents, for medium documents, for structure-rich documents, and for irregular documents.

Secondly, the combination of indexing and partitioning has lower entropy values than using only one of those mechanisms.

Last, using a global index leads in all cases to higher entropy values than using partitioned indexes.

As a conclusion, the general observations found for the attribute values are also relevant for the character contents. However, the difference of usage between attribute values and character contents is reflected in the details of the results.

XML

Textual XML is the default format for XML document. We considered here XML documents as defined by the XML 1.0 [XML] and the Namespaces in XML 1.0 [XML Namespaces] specifications (XML 1.1 introduces only marginal changes and the results of our study mostly apply).

We have shown previously some entropy results obtained when considering an XML document as a textual document. However, more precise results can be obtained by splitting the XML document into its different components and considering each of them individually.

In XML, event types are not specified explicitly, but rather implicitly through the XML syntax. However, those event types can be considered as being represented as a list.

Element names are represented as strings, using prefixes to specify their namespaces.

Attribute names are also represented as strings, as well as the attribute values.

Namespace declarations are represented as strings, associating a prefix to a URI.

Character contents are also represented as strings, as well as comments and processing instructions.

Globally, textual XML uses a basic string representation for all the components. The only optimization is to use prefixes as shortcuts for namespace’s URIs.

Fast Infoset

Fast Infoset is a binary XML format, specified by the ITU-T rec. X.891 | ISO/IEC 24824-1 standard [Fast Infoset]. This format drops the textual representation of XML documents to replace it by a binary representation, enabling a more compact encoding of XML documents.

In Fast Infoset, event types are explicitly coded in a binary form, and their representation corresponds to a list.

Element names and attribute names are represented as surrogates, a surrogate being defined from the index of the namespace’s URI and the index of the local name.

Namespace declarations are represented using indexed values for both the URI and the prefix. As prefix preservation has been ignored in this study, namespace declarations have not been taken into account here.

Attribute values, character contents, comments, and processing instructions are represented as indexed strings.

It should be noted that for Fast Infoset, the indexes for attribute values, character contents, comments, and processing instructions are all separated.

The representation used for Fast Infoset was slightly simplified for the purpose of this study. However, these simplifications should have only a minimal impact on the results.

Fast Infoset is a rather straightforward binary XML format, taking advantage of replacing the textual description of the XML structure by a binary description of it, and providing indexes for most items. In addition, Fast Infoset uses various encoding techniques for reducing the size of the encoded documents.

EXI

Efficient XML Interchange (EXI) [EXI] is a binary XML format standardized by the W3C. This format was selected amongst several propositions (one of them was Fast Infoset) and therefore contains some somewhat complex mechanisms for obtaining a compact encoding of XML documents.

In EXI, event types are explicitly coded in a binary form, and are in addition partitioned according to their enclosing element. Therefore their representation is a partitioned list.

Element and attribute names are represented as surrogates, a surrogate being defined from the index of the namespace’s URI and the index of the local name partitioned according to its URI. In addition, surrogates are partitioned according to the parent element. The element and attribute name representations corresponds therefore to partitioned surrogates, with surrogate definition based on URI indexes and local name partitioned indexes.

Namespace declarations are represented as indexed strings for URIs and indexed strings, partitioned according to the URI, for prefixes. As for Fast Infoset, prefix preservation has been ignored here.

Attribute values are represented as indexed strings partitioned according to the attribute name.

In a similar manner, character contents are represented as indexed strings partitioned according to the element name.

Comments and processing instructions are represented as strings.

As for Fast Infoset, the representation used for EXI was slightly simplified for the purpose of this study.

EXI is a binary XML format more complex than Fast Infoset, using partitioning in many places to improve the compactness of the encoding.

Summary

Table II shows a summary of the representations used by each of the three studied formats. This table is representative of the differences between the formats. XML is mostly list-based, Fast Infoset is mostly index-based, and EXI is mostly partitioned-index-based.

Formats overview

The different formats for XML documents can be first compared using their encoding size. Figure 19 shows the distribution of encoded file size for the three formats considered, and also for textual XML compressed with gzip.

Figure 19: Size Summary

Distribution of file sizes for the different formats.

This figure shows that on average, Fast Infoset encoded document size is 39% of the original XML document size, while EXI encoded document size is 34% of the original XML document size. However, gzip achieves much better results, as compressed XML document size is 12% of the original size.

While Fast Infoset and EXI provide better encoding for the XML structure and for repeated content, they leave other aspects of the XML documents uncompressed. On the other hand, gzip compresses the full XML document, both structure and content and is therefore able to achieve better results.

However, gzip has no information on the structure of XML and therefore compressed Fast Infoset or EXI documents are more compact that compressed XML documents.

Entropy values were computed for those three formats and their distributions are shown by Figure 20, alongside with the basic entropy of textual XML documents (that is the entropy of the text constituting the XML documents).

Figure 20: Entropy Summary

Distribution of total entropy values for the different formats.

The relations observed for the encoding sizes still hold for the entropies, meaning that the effective encoding chosen for Fast Infoset and EXI are correct. The average entropy of Fast Infoset documents is 51% of the average entropy of XML documents, and the average entropy of EXI documents is 46% of the average entropy of XML documents. In addition, the average textual entropy of XML documents is 151% of the average XML entropy of XML documents.

The first observation is that the better results obtained by EXI compared to Fast Infoset (as measured by the document sizes) are due to the choice of more efficient representations (as measured by the entropy values).

Second, those results show that the average entropy values for the three formats are closer than the average document sizes for these same formats. This means that the EXI encoding is closer to its theoretical minimum than the Fast Infoset encoding, and that the Fast Infoset encoding is closer to its theoretical minimum than textual XML.

XML

Figure 21 shows the distribution of the ratio of document size over entropy value for textual XML, using either no compression, gzip compression or bzip2 compression.

Figure 21: XML Results

Distribution of ratio between document size and XML entropy value for textual XML under different compression options.

This figure shows that on average, an XML document size is 2.34 times its entropy value. However, compressed document sizes are lower than the entropy values, being on average 0.73 times the entropy value for gzip, and 0.80 times the entropy value for bzip2.

These results mean that the entropy value we computed is more representative of the quantity of information contained in an XML document than the text-based entropy we computed initially. However, this entropy value is still overestimated. In particular, it should better take into account the possible repetition of element or attribute names.

Figure 22 shows the detailed distribution of entropy costs for XML documents among the different sources of information. This distribution is given for the whole testing corpus and also for the different categories of documents.

Figure 22: XML Cost Repartition

Distribution of entropy costs for XML documents for the different categories of documents.

The entropy cost for each source of information was computed as an average of the entropy cost for this source of information for all documents in the category, and then, for comparison purpose, those entropy costs were normalized so as their total value is one.

First, it should be noted that the cost of the structure (represented by the event list, the element names and the attribute names) is independent of the file size, staying around 40% for the small, medium and large document categories.

However structural cost is higher for structure-rich documents than for information-rich documents. Last, while it is somewhat above the average for regular documents, it is almost negligible for irregular documents (around 2%).

Fast Infoset

Figure 23 shows the distribution of the ratio of document size over entropy value for Fast Infoset documents. A first set of results uses the base Fast Infoset document, while a second set of results uses the Fast Infoset document compressed with gzip.

Figure 23: Fast Infoset Results

Distribution of ratio between document size and Fast Infoset entropy value for Fast Infoset documents with different compression options.

On average, the size of a Fast Infoset document is 1.83 times its entropy, and the size of a compressed Fast Infoset document is 0.94 times its entropy.

Those results first corroborate that on average Fast Infoset documents have a size closer to their entropy values than textual XML documents.

However, as compressed Fast Infoset documents still have on average a size lower than the entropy value, the entropy value computed for Fast Infoset still overestimate the quantity of information contained in an XML document. Nevertheless, the difference is lower for Fast Infoset than for textual XML.

Figure 24 shows the detailed distribution of entropy costs for Fast Infoset documents among the different event types.

Figure 24: Fast Infoset Cost Repartition

Distribution of entropy costs for Fast Infoset documents for the different categories of documents.

These distributions show that the behavior of Fast Infoset is clearly different from the behavior of textual XML.

A first observation is that, globally, the entropy cost of the structure represents a smaller part of the total entropy cost for Fast Infoset documents than for textual XML documents. This means that the representations used by Fast Infoset are more efficient for reducing the entropy of the structure than for reducing the entropy of the content.

Moreover, the part of entropy cost related to the structure decreases as the size of the document increase.

EXI

Figure 25 displays the distribution of the ratio of document size over entropy value for EXI documents.

Figure 25: EXI Results

Distribution of ratio between document size and EXI entropy value for EXI documents with different compression options.

Three types of documents are shown there. First, EXI documents encoded with the options close to the default ones (bit-packed, no schema, no compression, preservation options only for comments and processing instructions), second, EXI documents using the compression mechanism built-in in EXI, third, EXI documents further compressed with gzip (these documents use the pre-compress option as this gives more compact documents than compressing documents encoded with the default options).

On average, the size of an EXI document is 1.66 times its entropy, the size of an EXI document using the compression option is 0.92 times its entropy, and the size of an EXI document compressed with gzip is 0.93 times its entropy.

A first observation is that the built-in compression mechanism of EXI is on par with a generic compression mechanism (with a slight advantage for the built-in mechanism).

These results also corroborate that on average EXI document sizes are closer to their entropy values than Fast Infoset document sizes from their entropy values.

However, compressed EXI document sizes are still smaller than the EXI entropy values, showing that this entropy value is also an overestimation of the quantity of information contained in XML documents.

Figure 26 shows the detailed distribution of entropy costs for EXI documents among the different types of events.

Figure 26: EXI Cost Repartition

Distribution of entropy costs for EXI documents for the different categories of documents.

These distributions are very similar to the ones obtained by Fast Infoset.

In most cases, the entropy cost of the structure is a smaller part of the total cost for EXI than for Fast Infoset. The only exception is for the small document category.

Summary

The results obtained here show that binary XML formats reduce the size of XML documents both theoretically and in practice. Moreover, while indexing mechanisms, as used by Fast Infoset, are efficient for the compactness of the representation, including in addition partitioning mechanisms, as done by EXI, further improves this compactness.

It should also be noted that as EXI is closer to its theoretical minimum than Fast Infoset. This suggests that the practical techniques used by EXI are more efficient than those used by Fast Infoset.

Last, the distribution of the entropy costs among event types show that binary XML formats globally reduce the entropy cost of structure relatively to the entropy cost of content. This means that XML language designers should reflect as much as possible the structure of their data into the XML structure to take a full advantage of these encodings.