A long long time ago ... (XML from Word part 2)

... continuing from XML from Word.

To begin your unflattening, you will have to prepare a piece of data to explain what the structure of the final output needs to look like.  If you are simply unflattening HTML or Word using heading numbers, this is fairly straightforward.  If your document has a good bit more style and structure, you may need to do a bit more work.  Assuming you have a good XML Editor (just about any decent one can do this next step), you should be able to produce an XML Schema from a sample XML document.  The schema will suck, looking something like this:

<xs:schema xmlns:xs="http://www.w3.org/2001/XMLSchema" elementFormDefault="qualified">
  <xs:element name="body">
    <xs:complexType>
      <xs:choice maxOccurs="unbounded">
        <xs:element ref="p"/>
        <xs:element ref="h1"/>
        <xs:element ref="h2"/>
        <xs:element ref="h3"/>

        <xs:element ref="h4"/>

        <xs:element ref="h5"/>

        <xs:element ref="h6"/>
      </xs:choice>
    </xs:complexType>
  </xs:element>
   ,,,
</xs:schema>

Take the table of <xs:element> names and put them into another file somewhere, and add attributes that indicate the nesting level for each element, like this:
<table>
  <element ref="body" level="0"/>
  <element ref="h1" level="1"/>
  <element ref="h2" level="2"/>    

  <element ref="h3" level="3"/>    

  <element ref="h4" level="4"/>    

  <element ref="h6" level="5"/>    

  <element ref="h6" level="6"/>    

  <element ref="p" level="7"/>    

</table>

This table basically assigns a nesting level (or precedence) to each element name, so that you (or software) can figure out the nesting level.

Where the magic comes in is how I use it next to apply the structure.  You can do this sort of processing of a list of elements really easily in Java or JavaScript or C++ if you understand how to write parser for a language whose parse tree can be described with operator precedence.  But if you want to do this using XSLT, you'll need a lot of research, or a really twisted brain to figure this out. Fortunately for you, I just spent the last week in Portland, so my brain is already twisted after three days of Evidence Based Medicine at OHSU ;-).

To make this stylesheet work, you are going to need to run two passes over your XML (or have two separate stylesheets.  The first pass simply adds an attribute to each element that assigns it the precedence level from the previous document, and then turns this result tree into a node-set (via the EXSLT node-set extension function) and sends it to the next phase.

<xsl:stylesheet xmlns:xsl="http://www.w3.org/1999/XSL/Transform"

  xmlns:exslt="http://exslt.org/common" 

  extension-element-prefixes="exslt" version="1.0">

  <xsl:output indent="yes" method="xml"/>

  <xsl:variable name="prec" select="document('precTable.xml')"/>

  <xsl:template match="/">

    <xsl:variable name="pass1">

      <content>

        <xsl:for-each select="content/*">

          <xsl:copy>

            <xsl:copy-of select="@*"/>

            <xsl:attribute name="text">

              <xsl:value-of select="."/>

            </xsl:attribute>

            <xsl:attribute name="_level">

              <xsl:value-of select="$prec/table/element[@ref=local-name(current())]/@level"  />

            </xsl:attribute>

          </xsl:copy>

        </xsl:for-each>

      </content>

    </xsl:variable>

    <xsl:apply-templates select="exslt:node-set($pass1)/content/Tabular" mode="process"/>

  </xsl:template>

What this does is basically run through each element child of <content> and add an _level attribute to that element.  It gets the element by finding it in the /table/element list, looking for one whose @ref attribute matches the name of the element.  Why do I do this step?  Locality of reference for the next ugly bit.  Basically, this is an optimization that makes the next optimization really shine.  My file has 35000 lines.  The algorithm that you might figure out for yourself in XSLT (if you can twist your brain around it) runs on the order of O(n³).  On my first attempt at an algorithm, I was looking for the children of each parent.  That lookup that I preprocess would be needed 42 trillion times if not preprocessed, and it doesn't run quickly since it is essentially a linear search.  Even with the optimized version below, this lookup is best not repeated if you can precompute it, so I do.

The algorithm I finally figured out after failing several times runs a lot faster. I estimate it is around O(n log n). I owe Jeni Tennison a beer if I ever see her again (and Steve Meunch), because I wouldn't have figured it out were it not for her post on his algorithm.

What I realized was that each element in the file has can have unique key computed which identifies its parent, and that key can be expressed in XSLT as the unique identifier of the first preceding sibling of that element whose level in the hierarchy is lower that then of the element.  You declare this in XSLT using the following line:

  <xsl:key name="parent" match="*"

    use="generate-id(preceding-sibling::*[@_level &lt; current()/@_level][1])"/>

Then, these next two templates do the magic restructuring:

  <xsl:template match="/" mode="process">
    <content>
      <xsl:apply-templates select="/content/*[1]"/>
    </content>
  </xsl:template>

  <xsl:template match="*" mode="process">
    <xsl:copy>
      <xsl:copy-of select="@*[local-name()!='_level']"/>
      <xsl:apply-templates mode="process" select="key('parent',generate-id())"/>
    </xsl:copy>
  </xsl:template>

That's a remarkably short bit of code for the magic it performs!  The first template simply kicks things off.  For each element the next template processes, it makes a copy of the XML (using xsl:copy and xsl:copy-of, and then inserts the content of all of the nodes which claim (through the parent) key to be its direct children.  If you instrument the output with <xsl:message> elements as I did when I first ran it, you'll see a BIG pause (at least if you run a 35000 line file through it), and then magically, everything will come out in a great big WHAM!

What is happening here is that first pause is the indexing stage, where the XSL process goes: "OK, he really does mean to use the parent key, I better go make an index." (Yes, I tend to anthropomorphize software).  Then it identifies every node (all 35000) of them, and executes the XPath expression in the use attribute.

generate-id(preceding-sibling::*[@_level &lt; current()/@_level][1])

That XPath expression says: for each preceding child whose level is less than mine, take the first one. Most XSLT processors are smart about any expression which ends in the pattern [number], especially when number is 1, or the expression last().  That usually means that the expression can be computed more efficiently and short circuited once the first item is found.  The indexing step likely has average case execution time of O(n log n).  Each element generates an index key.  The elements are found in O(n).  At the deepest layer, their are O(n) nodes, and it takes a constant time to find their parent. Their are O(log(n)) layers in the tree, and it takes approximately the same amount of time to compute their parent(less actually for balanced trees of breadth X [each node containing X children]).  The recursive processing step is O(n) once the index is precomputed. Putting all that together give O(n log n), which finally made this work without a week of processing time.

The real trick here was instead of trying to find the children of each node, turning the problem on its head and finding the parent of each child.  That is what makes the whole algorithm simple.

How does this apply to standards?  The file I was processing was a vocabulary table written in a giant Word document.

A long long time ago ... (XML from Word)

A very long time ago (more than 15 years), I worked on a product that allowed you to take inputs from various formats and restructure them as XML (or SGML).  It was a very useful tool, and made it very easy to convert Word documents to XML, especially when those documents didn't have a great deal of nested structure.

This is fairly common: Word, HTML and many other file formats don't really handle heading level nesting the way you would output information in XML.  When you wind up with a document that has a lot of "structural" information it its styles, getting that structural information represented in your XML can be very handy.  But it can be a royal PITA to get that structure back from the Word document.

I used to do this with a Word macro, but these days I find it easier to extract the styled information into an HTML file.  Use the "Save As..." and then use Filtered HTML as your output format, and what you will get is pretty decent HTML which won't contain a lot of Word specific gunge.  Your next step will be to remove all the stupid content in between <o:p> and </o:p> tags that Word inserts to support empty paragraph and whitespace handling in various versions of the IE browser (from about 5.X on they changed various things that needed special HTML handling for each version).

After you've done that, you need to tidy up the HTML so that it is proper XHTML to begin the final phase of restructuring.  To do this, I use jtidy, the Java implementation of Dave Ragget's Tidy program.  The command line is fairly simple:

java -jar jtidy.jar -m -asxml filename

This command will read filename, cleanup the HTML and turn it into XHTML (-asxml), and then modify (-m) to original file to contain the cleaned up output.

So what was
<p class=foo><span class=bar>Stuff<br></span></p> 
becomes:
<p class='foo'><span class='bar'>Stuff<br/></span></p> 
This will make your life a lot easier. In the next two steps.

The next step simply uses the class attribute as the element name in the output.  So all tags are now rewritten using the class names (which were originally your style names in Word).  Here's the stylesheet to start XML-ifying the XHTML.

<?xml version="1.0" encoding="UTF-8"?>
<xsl:stylesheet xmlns:xsl="http://www.w3.org/1999/XSL/Transform" 
  xmlns=""
  xmlns:html="http://www.w3.org/1999/xhtml"
  version="1.0">
  <xsl:output method="xml" indent="yes"/>
  <xsl:strip-space elements="*"/>
  <xsl:template match="html:head"/>
  <xsl:template match="html:body">
    <content>
      <xsl:apply-templates/>
    </content>
  </xsl:template>
  <xsl:template match="html:*">
    <xsl:choose>
      <xsl:when test="contains('1234567890',substring(@class,1,1))">
        <xsl:element name='_{@class}'>
          <xsl:apply-templates/>
        </xsl:element>
      </xsl:when>
      <xsl:otherwise>
        <xsl:element name='{@class}'>
          <xsl:apply-templates/>
        </xsl:element>
      </xsl:otherwise>
    </xsl:choose>
  </xsl:template>
  <xsl:template match="html:a">
    <xsl:attribute name="id">
      <xsl:value-of select="@id"/>
    </xsl:attribute>
  </xsl:template>
</xsl;stylesheet>

Now, you still have this flattened XML.  What you need to do is "unflatten" it, and I'll explain how to do that in my next post.

An XML Book for non-Geeks

In the preface of The CDA Book, I insist that you must have at least a basic understanding of XML technologies in order to fully understand the HL7 CDA Standard.  While I was in Saudi Arabia recently, a Health Informaticist with an interest in CDA asked me to recommend an XML book.  He isn't a software engineer, but wanted to quickly develop the needed expertise in XML in order to better utilize The CDA Book.

I have numerous XML books on my shelf, as well as many SGML books.  But my tastes are not what I think he needed.  Nor do I think they are what many clinical or management folks need either. What they want is enough to understand what the technology can do, with enough examples and pointy brackets to explain what is needed, but not so technically overwhelming as to frighten them away.

For the non-technical I'd recommend a book that was written in 2002 and still has valuable content even now, more than a decade later.  It's not one of those 500 page or 1000 page tomes that are also useful as a hammer or a booster chair, nor is it one of those dumbed down, Dummy or Idiot titles that I really don't care for.  The title is XML Pocket Consultant, published by Microsoft.

The book is divided into four parts, each part including from 2 to 6 chapters.  Part I covers XML.  Part II DTD's (skip that) and Namespaces (read that).  Part III is XML Schema, and Part IV is XSLT and XPath.  It's a handy book for me because it goes into enough detail that I can use it as a pocket reference book, but it is also good book for non-technical folk because chapters are fairly short (20-40 pages), and each chapter provides a good overview of a single topic that can be easily digested.

This book won't make you an XML expert, but it may make you look like one to your colleagues, and it is a book that at least one expert (me) still uses.

Is XML Schema Worth it?

Wes Rishel asks whether XML Schema is worth it in a post yesterday.  Then he goes on to complain about its failings as a validation technology, and then segues to JSON.


There really are three different problems that Wes is discussing.  The first problem to address is whether data can be described in a way that can be easily parsed.  The second problem is whether the data that has just been parsed is properly structured.  The last problem is whether the structured communcation makes sense:

1. How easy is this stuff to parse?
2. Is it structured right?
3. Does it mean something for my business?

Parsing
The JSON/XML debate addresses the first question.  JSON is certainly easier to parse than XML. But there are a lot more tools for dealing with parsed XML afterwards than there are for JSON (at this point in time, that will change in the future).

Structure
Structure reverts back to Wes's first question, has XML Schema been worth it? I'd have to say that it has been.  From an industry perspective, there really is no denying that XML Schema provides a great deal of value across the IT domain, and without it, there's a lot of stuff we wouldn't have been able to do.  It hasn't been the simplest technology to work with.  But from Schema came web services (of the sort used within enterprises), information models, mappings from databases to XML and vise versa, and a whole host of other cool stuff.  Schema hasn't solved every problem that exists; as a specification language, it has its limits.  XML Schema is limited to creating and parsing structures that can be handled without look-ahead.  It makes it pretty easy to create context-free languages for communicating between systems.

On the JSON front, there was an attempt to create a JSON Schema language, but it seems to have died on the vine.  Unfortunately, the "JSON" crowd sees little need for schema, because JSON, RESTful and all the other Web 2.0 parts are intuitively easy to use and therefore validation isn't needed (that really is an oversimplification of the case).  I could spend a whole post on that topic (and probably will in the near future).

Business Meaning
Unfortunately, many problems require context-sensitive validation, which you cannot get from a simple context-free grammar production.  Co-occurrence constraints (like this code here implies that kind of code in that structure over there), are examples that introduce context-sensitivity into validation problems.  What XML Schema cannot do by itself can be assisted by languages like Schematron, which can do other things like co-occurrence very easily.  Schematron is a very easy to use XPath based validation language, but it is miserable at other tasks, like creating easily understood structures.  Context sensitive validation usually addresses things like business rules (this code isn't allowed to be used with that one), otherwise known as "edits" to coders.

In summary
In the end, to deal with these validation problems, it doesn't matter whether your parenthesis are shaped like this <> (XML) or like this { } (JSON) or even like this () (LISP).  Eventually, you WILL want to validate it (even if it is in JSON).

Tools like XML Schema can aid with that validation, but they don't and never really will solve the entire problem. It doesn't really matter what you do, or what tool you work with, because that last problem, addressing validation at the business level, is not a technology problem.  Business rules are created by people, and they defy logic and software algorithms.

-- Keith

Element Order Schema Important Not IS XML

A discussion on the IHE XDS Implementors Google Group spawned this question:

Why is order important in XML Schemas in cases where the order really doesn't matter with respect to data structuring requirements.  After all, the real issue is just that you have some number of child elements of a particular type.  Why should order matter?

There are a couple of answers to this question.

First is simply that the order is important when the schema says it is.  There are cases where the order of a collection of items has meaning.  This usually occurs in narrative.  Language is quite sensitive to order -- at least in "proper" construction, but as my wife often notes in our communication, "Order word important not is."

It does make sense to put the table header element (<thead>) before the body of the table (<tbody>), and it eases processing (it also simplifies table formatting to put the <tfoot> before the <tbody>).  There are also cases where order really doesn't matter.  Compare for example, dates in European locale to those in the US locale.  Today can be encoded as either <month>12</month> <day>27</day> <year>2011</year>, or <day>27</day> <month>12</month> <year>2011</year> or even <year>2011</year> <month>12</month> <day>27</day> without any loss of meaning.

In SGML DTD's there are three different operators for content models:

• The comma (,) created lists (xsd:sequence in XML Schema).
• The vertical bar (|) created choices (xsd:choice in XML Schema)
• And the ampersand (&) created conjunctions where all elements needed to be present in any order (xsd:all in XML schema.

The ampersand operator was not actually supported by the XML DTD content specification.

Why would you make order important when there is no other requirement for it to be so?

Another reason why order is important is that it makes parsing XML easier to do.  Most XML Schema constructs can be parsed quite simply without any look-ahead using finite automata.  While the "xsd:all" construct can be readily converted to a data structure that can support parsing, you cannot use a finite automaton indiscriminately.  The number of states needed to support the "xsd:all" construct is on the order N! where N is the number of particles in the list of elements allowed. For example, in the date example given above: the first element could be year, month or day.  After that, there are two ways left to choose the next element, and then only one to choose the last.  See the list below.

1. <Year>
1. Y M D
2. Y D M
2. <Month>
1. M Y D
2. M D Y
3. <Day>
1. D Y M
2. D M Y

XML (and XML Schema) is designed to be parsed and validated without using look-ahead because SGML (its predecessor) had the same constraint.  So parsers that deal with "xsd:all" typically keep a list of the particles, and do the validation that all of them were used no more than once afterwards.

Even so, it's much simpler to create a parser that doesn't need to worry about this sort of stuff.  This is why the & content model construct does not appear in XML 1.0 DTD content model, and was only reintroduced with XML Schema.

Another reason why order is important has to do with how elements are extended in XML Schema.  An complex type can be defined that extends another complex type by appending elements to the end.  This makes it easy for the parser to figure out what goes where.  Essentially what it does is create an xsd:sequence containing the content-model of the base type followed by the content model of the new type.  Which means that sequences extend naturally (because a sequence of two sequences is the same as the one sequence with all the particles of the two sequences put together in order), but xsd:all groups do not (becuase a sequence of two xsd:all groups is not the same as one xsd:all group containing the particles of the two).

Now, a brief note on how to create extensible Schemas.  The trick is to use wild cards.  You will typically have a complex type definition for the content of an item, and that will contain some sort of group (usually a sequence).

<xsd:complexType name="extendableElement">
  <xsd:complextContent>
    <xsd:sequence>
      <xsd:element name="foo" type="fooType"/>
      <xsd:element name="bar" type="barType"/>
      <xsd:element type="xsd:any" minOccurs='0' maxOccurs='unbounded' />
    </xsd:sequence>
  </xsd:complexContent>
  <xsd:anyAttribute/>
</xsd:complexType>

What the wildcard at the end does is allow any element to be included at the end of your sequence, or any attribute to be added to the extendable element.  You could include namespace='##other' to say that the element (or attribute) has to be from a namespace other than your schema's target namespace.  This is in fact what I proposed as being the best way to extend HL7 V3 XML these days.

And so, now you know why order is important in most XML Schemas, even when it is not.

XPath, Math and a bit of History

More than a decade ago now I worked for an XML company named eBusiness Technologies.  Several years before that name (and before it had been purchased), it was an SGML company named Electronic Book Technologies.  Under either name, EBT was well known for its expertise in markup languages.  My product manager co-chaired the XSLT committee, the guy next door (Steve DeRose) wrote the XPath and XPointer, and a fellow two offices down was deeply involved in the XML Workgroup.

So, one of the perks of my job at the time was to go to XML Conferences.  And when the company closed its doors in 2001, and I moved into healthcare, I was still pretty involved in the XML scene. So in 2002 I submitted a paper to the Extreme Markup languages conference and it was accepted.  While I was there, they had organized a poster session.  It wasn't the typical poster session.  They had poster-board and magic-markers, so people could craft posters there on the spot.  I put together a poster that is now somewhere lost in my basement talking about the mathematical properties of XML and XSLT.  It was something that one of the inventors of XPath hadn't even realized when I showed it to him.

There are eight atomic XPath axes:

1. child 
2. descendant
3. parent
4. ancestor
5. following
6. preceding
7. attribute
8. self

Four additional axes are combinations of two axes or features (sibling is not an axis, so I call it a feature)

1. following-sibling combines following and sibling
2. preceding-sibling combines preceding and sibling
3. descendant-or-self combines descendant and self
4. ancestor-or-self combines ancestor and self

The last axes is namespace, and it is kind of special because it flows downward from the point of declaration.

The descendant axis is the transitive closure of the child axis.  That is to say that a child is a descendant, as is a child of a child, et cetera.  The same is true with parent and ancestor.

I add, for the purpose of the poster, the "left" and "right" axes.  The left axis contains the node immediately preceding the context node.  The right axis contains the node immediately following the context node.

Using these, I can define the preceding and following axis as the transitive closure over the left and right axis resp.

If you number the nodes consecutively in an XML document in the order in which they appear, you get some interesting features.  I've found it helpful build a table that shows the nods, along with a pointer to the first non-descendant node and the parent node.  Here is an example data set to work with where this has been done.

Node   #	Type	XML	FirstNonDesc	Parent
1	Element	<html>	27	0
2	Element	<head>	8	1
3	Element	<title>	5	2
4	Text	This is the title	5	3
5	Element	<link href='file.css' type='text/css' rel='stylesheet'/>	6	2
6	Element	<script type='text/javascript'>	8	2
7	Text	alert("hello world");	8	6
8	Element	<body>	27	1
9	Element	<table cols='2'>	27	8
10	Element	<thead>	16	9
11	Element	<tr>	16	10
12	Element	<th>	14	11
13	Text	Axis	14	12
14	Element	<th>	16	11
15	Text	description	16	12
16	Element	<tbody>	27	9
17	Element	<tr>	5	16
18	Element	<td>	2	17
19	Text	Left	1	18
20	Element	<td>	2	17
21	Text	X - 1	1	20
22	Element	<tr>	5	16
23	Element	<td>	2	22
24	Text	Right	1	23
25	Element	<td>	2	22
26	Text	X + 1	1	25
27	EOF

Now, something cool happens.  Let's look at the eight atomic axes and the left/right ones I added (for completeness):

Simple Axes		Transitive Axes
Axes	Function	Axes	Function
Child	Y.parent = X	Ancestor	Y < X && Y.FirstNonDesc < X
Parent	Y = X.parent	Descendent	Y > X && X.FirstNonDesc < Y
Left	Y = X + 1	Preceding	Y < X
Right	Y = X - 1	Following	Y > X
Sibling	Y.parent = X.parent && X != Y
Self	Y = X

The function given in the table shows what computation you need to perform on two nodes X and Y to determine if the node Y is related to the node X by the relationship specified by the axes.  These can be computed very quickly (in one clock-cycle on most CPUs today).  So, if each node in the XML document is represented by tuple as described above, you can very quickly compute the XPath relationships.  If you add other integers representing a string position and offset for strings stored in an array buffer you can handle name and namespace tests, and with another numeric identifier, you can also handle the namespace nodes and attributes (which is a longer discussion I won't go into).  So, in about 32 bytes, you can represent an XML node really well.

This in part is the basis for the Document Table Model found in Xalan, my favorite XSLT parser.  I don't know if they use the "First Non-Descendant" index as I have done above, but they surely store something to manage the document structure. The math here is very pretty, and is an interesting emergent property of XML and XPath that even the creators of those specifications hadn't fully understood when they built them (based on personal discussions with those very same people).

Why think about this now after all these years?  Well, I've been looking at mapping HQMF into XPath.  This ancient history could be the foundation for an XML based document repository that would enable searching collections of C32 document collections using XPath.  And it could be really fast.

BIN Counts in X12 and Canonicalization

Someone complained to me the other day about a problem transmitting claims attachments between systems.  While I don't usually get into X12 transactions, this is one that I'm pretty familiar with because it was a topic of great concern to the Claims Attachments SIG in 2007.

You see, attachments use EDI formats to exchange information.  Many of these systems still use "big iron", and translation between ASCII on one end and EBCDIC on the other, and visa versa are common.  This was a challenge because carraige return/newline pairs in one environment get translated to single characters in another, and so forth.

The X12 BIN Segment has two parts, the binary data, and a count of the length of that data.  The challenge is that the whitespace is being changed from 2 characters to 1 or visa versa.  And then when the system outputs the record in the new encoding, the length is off.  This problem is clearly stated in the 275 transaction that contains a BIN segment:

It has been noted that line constraints, transfer protocols ... may insert additional control characters ... If this occurs in BIN02, the senders stated count in BIN01 may no longer be equal to the received content of the data in BIN02.

This is a truly big challenge, because if BIN02 count doesn't match BIN01, business logic set up to detect errors could wind up rejecting the response to the request for an attachment.

There is an even more sinister problem in XML.  There are three different valid ways to represent the character A, each with a different length.  Once as the letter A, another using a decimal character entity, and the final as a hexadecimal character entity.  As far as an XML processor is concerned, all three are the same.  And then there are different character sets that an XML processor must support.

This would seem to provide a challenge for creating digital signatures, but XMLDSIG addresses that with the Canonicalization Algorithm.  The algorithm ensures that the digital signature is computed over the same content by ensuring a consistent octet stream is used for the computation.

In X12, the BIN01 serves a similar purpose as a digital signature.  It is a "check" that the data has not been modified (but it doesn't support non-repudiation or any other cool features of XMLDSIG.  Canonicalizing Base-64 is simple.  Ignore any whitespace.

Given that the specification notes the disparity, I would presume that receivers are expected to deal with it.  So, give an innaccurate count to start with.  Don't count the whitespace because it doesn't matter.  Better yet, use the octet length of the original CDA document.  The challenge here is that senders and receivers would have to change the counting algorithm for the BIN segment to make it ignore whitespace.  That might be hard, but the only other solution I can think of is to upgrade the operating systems and hardware.  I haven't run into an EBCDIC to ASCII issue in years.

Affects of Efficient XML on HL7 Version 3

Diego Kaminker (cochair of the HL7 Education workgroup) reminded me this morning that I'm overdue on a post about Efficient XML, a new standard recently recognized by the W3C.  The creation of this standard is pretty significant for several reasons.  As designed, XML (and its predecessor SGML) were created to be text markup languages suitable for expert human users to use to annotate electronic text.  Because of this design, XML has become very easy for software engineers to use for a variety of different tasks.  XML users (and SGML users) have become quite familiar with editing raw markup directly in text files.  But the most common use for XML and its predecessor was software processing of the text and associated markup.

Uses for this markup abound and include display and formatting of text, book production (where I first encountered it), communication of software commands and responses to them (e.g., Web Services), structuring of tabular and hierarchical data, electronic commerce, et cetera.  One of the major complaints from the EDI world was that XML was notoriously costly for messaging in several ways:

1. Data Size
   Converting data elements from a binary format to text-based formats increases the size of the data, often by an order of magnitude.  The use of XML tags to delimit data elements instead of position in a data field, or simpler delimiters creates quite a bit of additional bytes to transmit.  End tags in XML are quite redundant -- useful for humans, but not all that useful for computers at a certain point in the production cycle.  These additions can add yet another order of magnitude to storage requirements.
   Impacts on Data Size affect:
1. Storage Capacity
2. Transmission Bandwidth
3. Memory Utilization
2. Processing/Marshalling
   Converting from binary data types for numbers, dates, times and similar data types to text requires computing time.  Dealing with all those start and end tags, and parsing decisions on the text also requires computing time.  The compute time spent on these tasks could be better spent on OTHER things, especially given that parsed XML has similar representations on many different platforms.

These problems make it difficult for devices with limited resources to efficiently use XML for computation or communication, even though the format has numerous other advantages for software development.  What are some of these benefits?

1. Ready access to tools which make content visible and editable.  Because XML is fundamentally text, any text editor can be used to open it up and edit it.  You may not recall a time when this was a problem for other data, but I do.  
2. Standards AND tools for describing the content allowed to be in an XML document.
3. Standards AND tools  to translate the content from one format to another.
4. Engineer (which is not necessarily the same as human) readability.
5. Implementability ... one of the guiding principals of the XML work was that it had a particular complexity goal in mind.  An XML parser should be implementable as a semester long college Senior project.

These benefits, and Moore's law trends in storage, network speed, memory sizes and processor speed have meant that the processing and data size issues have not significantly interfered with XML dominance as a data syntax.  But, small devices, or large bandwidth applications have still had some problems.  In the UK, one of the reported problems in adopting HL7 Version 3 was the verbosity of the V3 XML syntax.  In this particular case, the volume is on the order of hundreds of millions of messages per day.  The computation resources to parse the XML were significant, as was the bandwidth.

The HL7 Implementation Technology Specification workgroup  began development of an ITS that would simplify (flatten) the XML in 2008.  Those efforts began before I had even started this blog, so I don't even have a post on how I felt about that particular effort.  I can tell you I was quite negative on that ballot and it didn't go forward.  I ran a little test and what I found was that several existing models were only marginally improved (<10%) by the new algorithm.  I believe I argued successfully at that time that the right way to approach the problem was lower in the stack, rather than at the XML ITS layer.  

This argument applies not just to HL7 XML messaging, but to any form of XML processing.  What the application deals with is the XML Infoset, typically stored using the XML Document Object Model .  What is communicated to the application is an XML document.  Between communication and processing is a layer which translates the XML document from the XML syntax into the the XML Infoset.  That's where EXI has a huge impact.  By changing the format from text-based content to one better able to address the EXI requirements, an EXI implementation is better able to perform the translation back and forth between these layers.  It does so using a much reduced footprint from both a storage and a processing perspective.  Diego reports to me that in his brief experiment, a 60KB CDA document is compressed at a ratio of 20:1, which nearly makes up for the 1-2 orders of magnitude size increase.   Diego plans on performing other tests to evaluate performance.

What I have been able to determine from the W3C bake-off comparing the various technologies that they considered, and from the vendor's website for the technology that "won" is that you can also expect somewhere between 1-2 orders of magnitude improvement on processing (parsing) speed.

What happens next?  Having reached the point of becoming a standard, people are going to want to start implementing this in their products.  There are already 2 open source and one commercial implementation of the standard available. I think you can count on EXI being incorporated into your favorite XML parser pretty quickly.  Java implementations will probably be available sooner than C++/.Net.  Once web servers and browsers start supporting this technology, it will be interesting to see what it does to the browsing experience on sites that support it and which exchange XML or XHTML.   

One of the nice features about the EXI standard is that you can enable others who communicate with you to take advantage of it quite readily.  It plugs into the communications stack at the content encoder/decoder. At least one of the commercial products out there EXI enables your protocol stack.  You won't get all of the benefits of using EXI, but at least your communication partners could.  For XML based Web Services, this is a no-brainer feature to support.  Just make sure your client and server technologies support EXI on the stack and support use of x-efi as an encoding in Content-Encoding and Accept-Encoding headers.