Who created this UI? It sucks!

As someone who writes regularly, I am often just as frustrated with Microsoft Word (or any other word processor I've ever used) as others report themselves to be with the user interfaces of EHR systems. Even Apple hasn't solved the problems I need solved.

How many clicks does it take to insert a figure reference to the figure below or above?  How much work is it to create a citation for the link I just inserted into the document?  These should be one button clicks, not the multi-step process they are today.

Why has this crime against writers continued to persist over decades? Nay, centuries... millennia even.

Word processor designers, here's a very clear specification for what I want:

Cross References

Given I have turned the option on, when I type the words "the figure|table|section below" or "the figure|table|section above" and there is a figure or table citation within the current section, insert a reference to it, or if a section, provide me with a list of sections to choose from that I can ignore if I want (so that if I continue typing, it just disappears).  And if I hit undo, treat the automatic insertion as the operation I want undone.

Hyperlinked Bibliography

Given I have turned the option on, when I insert a hyperlink, add new or reuse an existing citation source for the link if it already exists.  Find the individual author and creation date in the page data or metadata, or use a corporate author for the web site.  Include the URL in the citation.  If the URL includes a fragment identifier, find the text where that identifier appears and add it to the title of the reference (e.g., "Hyperlinked Biobligraphy in Who Created this UI? It sucks!).  If the link is to a page in a PDF (e.g., using #page=9 in PDF links) or other media format, treat it as a "document from a website", otherwise use "website" as the reference style.  Use the page title from the <title> tag in the page header.  Prompt me for missing information, but again, let this prompt dialog NOT interfere with my current work, and go away if I continue to type.  Same deal on undo here.  If I say undo, first undo the automatic insertion.

Finally: Stop turning on display formatting marks when I want to insert an index reference term.

   Keith

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.