Efficient XML Interchange (EXI) Primer

2.1.1 EXI Header

The header communicates encoding properties that are needed to decode the EXI body. The minimal header can be represented in a single byte. This keeps the overhead and complexity to a minimum and does not sacrifice compactness, especially for small documents where a header can introduce a large constant factor.

The structure of an EXI header is depicted in the following figure.

The EXI header starts with an optional four-byte EXI Cookie. The four byte field consists of four characters " $ " , " E ", " X " and " I " in that order, each represented as an ASCII octet, that can be used to distinguish an EXI stream from a broad range of data streams.

The EXI Cookie is followed by a pair of Distinguishing Bits. The two bit-sequence (1 0) can be used to distinguish an EXI document from a textual XML document and is sufficient to distinguish EXI streams from XML streams based on a broad range of character encodings.

The Presence Bit for EXI Options follows the distinguishing bits. The value of this single bit is used to indicate the presence or absence of the EXI Options that appear later in the header.

The EXI Format Version identifies the version of EXI in use and allows future improvements and modifications. A leading 0 (zero) bit indicates that the document is encoded according to the final version of the recommendation, while a leading 1 (one) indicates that it is a preview version. The differentiation is introduced to facilitate early releases of preview versions with less strict interoperability requirements. Only final versions are required to be processed by compliant processors. The leading bit is followed by one or more 4-bit sequences which are collectively interpreted as a format version number starting at 1. For example, the 4-bit sequence 0000 is interpreted as version 1 and the two 4-bit sequences 1111 0001 are interpreted as 15 + 2 or version 17.

The EXI Options specify how the body of an EXI stream is encoded and, as stated earlier, their presence is controlled by the presence bit earlier in the header. The overhead introduced by the EXI options is comparatively small given that they are formally described using an XML schema and are encoded using EXI as well. The following table describes the EXI options that can be specified in the EXI header. When the EXI Options document does not specify a value for a particular option, the default value is assumed.

Most of the options are straightforward and act as boolean values to enable or disable a feature. They are represented using optional XML elements which are also encoded using EXI. For more information on the XML schema that is used to encode these options, the reader is referred to XML Schema for EXI Options Header.

The preserve options shown in the table above are really a family of options that control which XML items are preserved and which XML items are ignored. These are collectively known as fidelity options. These options can be used to eliminate the associated overhead of communicating unused XML items. Certain XML items such as processing instructions or DTDs may never occur (like in SOAP) or are simply unimportant to the use case or application domain. Fidelity options are used to manage filters for certain XML items as shown in the following table.

Naturally, XML items that are discarded at encoding time (due to a particular setting of the fidelity options) cannot be reconstructed exactly at decoding time. The next section deals with the EXI Body and discusses in more detail the effects of enabling and disabling fidelity options.

2.1.2 EXI Body

The body of an EXI document is composed of a sequence of EXI events. The notion of an event in this context is similar to that in the StAX and SAX APIs. XML items are encoded into one or more EXI events; for example, an attribute named foo can be encoded as AT("foo") and an element named bar as the pair of events SE("bar") and EE. EXI events may have additional content associated with them. For example, the attribute event AT("foo") may have an attribute value foo1 associated with it. The following table shows all the possible event types together with their associated information items distinguished by structure and content. In EXI terminology, content denotes attribute and character values while all other information items are considered as belonging to the structure category.

For named XML items, such as elements and attributes, there are three types of events: SE(qname), SE(uri:*) and SE(*) as well as AT(qname), AT(uri:*) and AT(*). These events differ in their associated structure: when SE(qname) or AT(qname) are used, the actual qname of the XML item is not encoded as part of the event while SE(uri:*) and AT(uri:*) events do not encode the uri. The decision to use one type of event over the other will be explained later after introducing the notion of EXI grammars. Additionally, Fidelity Options may allow the preservation of namespace prefixes.

The fidelity options introduced in Section 2.1.1 EXI Header may be used to prune EXI events such as Namespace Declaration (NS), Comment (CM), Processing Instruction (PI), DOCTYPE (DT) or Entity Reference (ER). Grammar pruning simplifies the encoding and decoding process and also improves compactness by filtering out unused event types.

Consider a simple XML document from a notebook application:

<?xml version="1.0" encoding="UTF-8"?> 
<notebook date="2007-09-12">
 <note category="EXI" date="2007-07-23">
  <subject>EXI</subject>
  <body>Do not forget it!</body>
 </note>
 <note date="2007-09-12">
  <subject>Shopping List</subject>
  <body>milk, honey</body>
 </note>
</notebook>

The sequence of EXI events corresponding to the body of this XML document is shown below.

Figure 2-1. EXI Body Stream

This sequence of EXI events can be easily mapped to the structure of the XML document shown above. Every document begins with a Start Document (SD) and ends with an End Document (ED). The order in which attributes are encoded may be different in schema-less and schema-informed EXI streams, as is the exact content associated with each event.

The actual number of bits used to represent each type of event, excluding its content, differs depending on the context. The more event types can occur in a certain context, the larger the number of bits required to represent an event in that context. What constitutes a context in this case is more formally defined by an EXI grammar production in the next section.

2.1.3 EXI Grammars

EXI is a knowledge based encoding that uses a set of grammars to determine which events are most likely to occur at any given point in an EXI stream and encodes the most likely alternatives in fewer bits. It does this by mapping the stream of events to a lower entropy set of representative values and encoding those values using a set of simple variable length codes or an EXI compression algorithm.

EXI grammars are regular grammars in which productions are associated with event codes. An EXI encoder, driven by an XML event stream, matches events to grammar productions and uses their associated event codes to represent an XML document or XML fragment. Since EXI grammars are regular grammars, the sequence of event codes written by an encoder corresponds to a path in the finite automaton that accepts the grammar. In reality, given that XML is not a regular language, a single grammar cannot be used to represent an entire XML event stream. Instead, an EXI encoder uses a stack of grammars, one for each element content model (just like an XML Schema validator might do).

An event code is represented by a sequence of one to three parts, where each part is a non-negative integer. Event codes in an EXI grammar are assigned to productions in such a way that shorter event codes are used to represent productions that are more likely to occur. Conversely, longer event codes are used to represent productions that are less likely to occur. EXI grammars are designed in a way that the average number of bits needed to represent each production is less than that for a grammar in which more likely and less likely productions are not distinguished. The following tables illustrate this principle via an example.

In the first table, where productions are not separated according to their probability, a 4-bit code is needed to represent each entry. In the second table, on the other hand, code lengths vary from 2 bits to 6 bits since productions are grouped based on their likelihood to occur. Assuming the content model for the element being encoded corresponds to the sequence AT(category) AT(date) (i.e., the element declares two attributes) then the encoding of all the event codes will be 4 bits shorter using the second table.

EXI grammars take advantage of a priori knowledge of the kind of data being encoded, namely, XML documents and XML fragments. In particular, EXI grammars can take advantage of the fact that, on any given grammar, certain XML items are more popular than others. For example, by simple inspection of real-world documents, it is easy to verify that attributes occur more frequently than processing instructions and should therefore receive shorter event codes.

Further improvements in grammar design are possible if schema information is available. In this case, we can not only take advantage of generic XML knowledge but also of knowledge that is specific to the type of documents being encoded. For example, as shown in the tables above, we can add specific productions such as AT(category) and AT(date) with shorter event codes than AT(*).

The following two sections describe the differences between the built-in grammars and the schema-informed grammars. Note that an EXI encoder may only have partial schema information in which case it will use a combination of built-in and schema-informed grammars during encoding.

2.1.3.1 Built-In Grammar

EXI uses a set of built-in grammars to encode XML documents and XML fragments when no schema information is available. There are built-in grammars to encode documents, fragments, and elements. Document grammars and fragment grammars describe the top-level structure, while element grammars describe the structure of every element. Fragment grammars are more lenient than document grammars; for example, they allow multiple top-level elements to be encoded as siblings. For more information on these grammars, the reader is referred to Built-in XML Grammars.

The EXI format describes a mechanism by which built-in grammars are dynamically extended using information from the actual instance being encoded. Stated differently, the EXI format describes a learning mechanism to further improve efficiency when no schema information is available statically. Newly learned productions are assigned short event codes, improving compactness for every subsequent use of those productions. In addition, by adding new productions to the grammar, certain data associated with an event only needs to be encoded once. For example, if an element named notebook is matched by SE(*) and subsequently matched by SE(notebook), the actual localName "notebook" is only encoded once as part of the SE(*) event.

As pointed out in the previous section, EXI grammars are always regular and can, therefore, be accepted by finite automata (FA). To provide a more operational view of an EXI processor, we will opt for the use of FA to explain how grammars work. The following figure shows a stack of grammars in which the top-level grammar accepts "note" elements. State transitions in black correspond to the built-in element grammar; state transitions in red have been learned as a result of encoding the element before.

Figure 2-2. Built-In Grammar for SE(note)

The built-in element automaton has two distinguished states: StartTag and Element. The former accepts attribute and namespace events that must occur before any element content; the latter accepts only element content which excludes attribute and namespace events. This separation enables the use of short codes which improves compactness and processing time.

As stated earlier, transitions in red are extensions to the built-in element grammar based on knowledge acquired about the element note. Notice how AT(date), AT(category) and SE(subject) have been added out of the StartTag state while SE(body) has been added out of the Element state. In particular, this suggests that SE(subject) is expected to occur before SE(body), and that both of these SE events are expected to occur after any AT event. In addition, notice that both AT(*) and SE(*) are still available to enable future learning.

2.1.3.2 Schema-informed Grammar

EXI grammars can be further improved if schema information is known statically. Schema information can be interpreted in two different ways or encoding modes: strict and non-strict. In strict mode, the instances being encoded must be largely valid with respect to the schema; most deviations from the schema will result in an encoding error. In non-strict mode, any deviations are accepted and encoded using more generic events. Examples of deviations are attributes whose actual values do not match the type defined in the schema or elements whose structure does not correspond to that in the schema. Given that strict grammars have fewer productions (no need for SE(*) or AT(*) in most cases) shorter event codes can be used to encode each option.

Instead of being dynamically extensible as the built-in grammars, schema-informed grammars are created statically based on the information in the available schema. This process will add productions of the form AT(qname) or SE(qname) guided by the attribute and element declarations in the schema. Let us continue the example from the previous section by assuming the following schema is available statically.

Example 2-2. Notebook (XML Schema)

<?xml version="1.0" encoding="UTF-8"?>
<xs:schema xmlns:xs="http://www.w3.org/2001/XMLSchema" elementFormDefault="qualified">
  <xs:element name="notebook">
    <xs:complexType>
      <xs:sequence maxOccurs="unbounded">
        <xs:element name="note" type="Note"/>
      </xs:sequence>
      <xs:attribute ref="date" />
    </xs:complexType>
  </xs:element>
  <xs:complexType name="Note">
    <xs:sequence>
      <xs:element name="subject" type="xs:string"/>
      <xs:element name="body" type="xs:string"/>
    </xs:sequence>
    <xs:attribute ref="date" use="required" />
    <xs:attribute name="category" type="xs:string"/>
  </xs:complexType>
  <xs:attribute name="date" type="xs:date"  />
</xs:schema>

The schema for the element note states that it has a mandatory attribute date and an optional attribute category, and that its structure is composed of an element subject followed by an element body. An automaton that corresponds to the strict grammar for this element is shown next.

Figure 2-3. Strict Schema-Informed Grammar for SE(note)

Note that AT(category) is accepted before AT(date) even though their order is reversed in the schema. This is because attributes in schema-informed grammars must be sorted lexicographically, first by local name and then by namespace URI. Attribute sorting reduces the number of options which, in turn, greatly simplifies grammar creation and improves compactness. Since this automaton does not include transitions on AT(*) or SE(*), any deviations from the schema will result in an encoding error.

Generally speaking, schema-informed grammars should be favored over built-in grammars. Schema knowledge characterizes constraints of the structure and content type of XML information items. Hence schema-informed grammars do not evolve while processing and value items such as characters and attribute values are encoded according to their types. As a consequence, processing speed increases and compaction is improved.

2.2.1 Built-in EXI Datatype Representations

EXI uses built-in datatype representations to represent so called content value items in an efficient manner. In other words, all attribute and character values are encoded according to their EXI datatype representation associated with their XML Schema datatype. Type information can be retrieved from available schema information. The following table lists the mapping between [XML Schema Datatypes] and the Built-in Datatype Representations supported in EXI.

Enumerated values are efficiently encoded as n-bit Unsigned Integers where n = ⌈ log ₂ m ⌉ and m is the number of items in the enumerated type. The ordinal position (starting with position zero) of each value item in the enumeration in schema-order is used as identifier. Exceptions are for schema union datatypes, list datatypes, as well as QName or Notation and types derived therefrom by restriction. The values of such types are processed by their respective built-in EXI datatype representations instead of being represented as enumerations.

The interested reader is referred to the Efficient XML Interchange (EXI) Format 1.0 document which describes in details the encoding rules for representing built-in EXI datatypes. When the preserve.lexicalValues option is true, all values are represented as Strings. Some values that would have otherwise been designated to certain built-in EXI datatype representations are represented as Strings with restricted character sets. In the absence of external type information (no available schema information) all attribute and character values are typed as Strings.

2.2.2 String Table

String tables are used in memory-sensitive areas allowing a compact representation of repeated string values. Re-occurring string values are represented using an associated compact identifier rather than encoding the string literally again. When a string value is found in the string table (i.e. a string table hit) the value is encoded using a compact identifier. Only if a string value is not found in the associated table (i.e. a string table miss) is the string encoded as String and a new compact identifier is introduced.

EXI puts the following four information items into string tables and partitions the string tables based on the context in which they occur.

• uri

• prefix

• local-name

• value

The table below shows EXI information items used in section 2.1.2 EXI Body and its relations to the string table partitions (e.g. a prefix information item is assigned to the Prefix partition while value information items are assigned to the Value partition).

Each EXI string table partition is optimized for more frequent use of either compact identifiers or string literals depending on the purpose of the partition. The URI and the Prefix partitions are optimized for frequent use of compact identifiers while the LocalName and the Value partitions are optimized for frequent use of string literals.

In the subsequent paragraphs, more details about the different partitions are given by making use of the previously introduced Notebook example. The Notebook XML Document example is repeated here to simplify algorithm illustrations.

<?xml version="1.0" encoding="UTF-8"?> 
<notebook date="2007-09-12">
 <note category="EXI" date="2007-07-23">
  <subject>EXI</subject>
  <body>Do not forget it!</body>
 </note>
 <note date="2007-09-12">
  <subject>Shopping List</subject>
  <body>milk, honey</body>
 </note>
</notebook>

The uri portion of qname content items and uri content items are assigned to the URI partition. The partition is initially pre-populated with three likely entries (see figure below). When a schema is provided, there is an additional entry that is appended and the URI partition is also pre-populated with the name of each target namespace declared in the schema, plus namespace URIs allowed in wildcard terms and attribute wildcards.

Figure 2-4. Initial Entries in URI Partition

The local-name portion of qname content items and local-name content items are assigned to LocalName partitions. Respectively, prefix content items are assigned to Prefix partitions. Both partition types are initially pre-populated with likely entries (see figure below). These types of partitions are further differentiated according to the associated namespace URI. In our notebook example no prefixes are used and the default namespace URI ("" [empty-string]) is used. When a schema is provided, LocalName partitions are also pre-populated with the local-name of each attribute, element and type declared in the schema, sorted lexicographically. Further local-name entries are appended in the order they appear in the actual XML instance (no additional sorting is applied).

Figure 2-5. Initial Entries in Prefix and LocalName Partitions

The figure above shows in highlighted form uri and local-name items used throughout the entire example document. For instance, the notebook sample assigns 7 local-name entries, such as notebook and date, to the empty URI namespace. Whenever local-name and/or uri information items occur again, the compact identifier is used instead.

The last string table partition type is the Value partition. A Value partition is initially empty and grows while processing an XML instance. The total number of value items or the maximum string length of value content items can be restricted to save memory on small devices (see valuePartitionCapacity and valueMaxLength EXI Options). Attribute and Character content-values of type String are assigned to this partition.

Figure 2-6. Final Entries in Value Partition

The figure above illustrates that value content items can be indexed from two different partitions, a 'global' partition and a 'local' partition. When a string value is neither found in the global nor in the local value section its string literal is encoded as String and the string value is added to both, the associated local and the global string index.

In our example we assume that all value items are represented as String, as it is the case in schema-less grammars or if the fidelity option Preserve.lexicalValues is true. When a string value is found in the local value section for a given element or attribute, EXI can use the corresponding compact identifier to encode the re-appearance more efficiently. The value "2007-09-12" appears twice in the date context. The second occurrence results in a local value hit and is respectively encoded as a 1 bit compact identifier.

On the other side, if a string value is not found in the local section, but is found in the global section, the corresponding global compact identifier is used. The value "EXI" appears two times in the notebook example, respectively in the context of category and subject. Hence, the second appearance results in a global value hit encoded as a 3 bit compact identifier since there are 6 entries in the global section (3 = ⌈ log ₂ 6 ⌉). Due to the different table sizes, a global compact identifier is generally less compact than a local compact identifier. Still, global value hits avoid the repeated encoding of string literals.

The number of bits needed to encode a compact identifier depends on the actual number of entries of the associated table at that time. Since all tables are growing while parsing an XML instance, the number of bits is not fixed. The figure above illustrates the situation after coding the entire XML instance. This growth effect applies to all string table partitions and makes the format very compact for small documents.