Extensions to CorCode

I've been thinking about the exact role of CorCode and how we render it on screen as HTML. There are some problems with the simple CorTex, CorCode, CorPix model that need figuring out. Hopefully they're just details.

TEI and XSLT

For TEI embedded markup people write XSLT stylesheets to transform the text, typically into HTML. Since a particular encoding of a text is embedded in it, and is highly customised, the XSLT stylesheet that transforms it cannot be fully portable to other people's texts:

1. they may want to render the same data differently, or
2. they may have custom tags and attributes that need rendering according to their local GUI requirements

The reason that TEI tries to mandate particular names for tags and attributes is so that standard stylesheets can be used. In practice this does not work very well because just as the encoding is customised the stylesheets also need customisation as required by these two points. On the other hand, if we no longer mandate any standard encoding and just allow the user to specify fully the names of properties (aka tags) then it is up to the encoder to specify what is to be done with them.

How to do this in HRIT?

One objective of designing HRIT is to make things easy and to make them work smoothly. So the user should download Cortex and CorCode and they should automatically merge locally and produce output that looks good in their local GUI tool. But how?

Both functions of the transformation - the one into a visual appearance and its interpretation by the application are specific to the encoding itself. So I am thinking that the transforming css file that performs both duties in HRIT needs to be closely associated with the CorCode. It shouldn't need to be transformed locally for a particular application because how can that transformation do anything without knowledge of the format? Imagine I write a css file to render King Lear, and use it within single view. Cool. But what happens if I download Little Dorrit by Charles Dickens in the same application, and my css file no longer works? So the css file can't belong to the application, or at least most of it can't. It has to belong to the CorCode. This is more or less what TEI already does: an XSLT stylesheet is designed for a particular collection of customised text encodings and is useless outside of that domain.

Ergo: Corform

So maybe we need a fourth type of basic data: corform that is as tightly bound to corcode as corcode is itself bound to cortex. That sounds less evil to me than extending the corcode format to support formatting. The good news is that we wouldn't need as many corforms as corcodes, because they would be version- and even file-independent. But it would be both functionally and visually specific to a specific application. We might assign each corcode a "style" and then specify corforms like render that style. We'd want many corforms for each style but not the other way around. So a suitable rest resource url might look like: http://luc.edu/hrit/corform/style-name/app-name/render-name. "app-name" could be "default", meaning any application, or it could be "hritsingle" meaning the single view application; a suitable style-name might be "TEI"; "render-name" might be "freds-format". An individual corform resource would be in css.

So the way it would work in practice the user would specify a particular corform resource manually, and it would be saved until changed. But if none was specified, the application name combined with the corcode's style name should identify a default rendering in every case.

Writing a basic php5 extension

I wanted to put formatter into a php extension because the CorCodeDemo currently has to write the CorCode and CorTex returned by the server to temporary files because formatter is currently a C commandline tool, and the CorTex and CorCode responses are too long to be commandline arguments. Also making formatter directly accessible from within php will effectively make it a replacement for XSLT, which is my intention.

The trouble with "hello world" as a php extension

I followed the instructions at http://devzone.zend.com/article/1021 but there were several problems. Documenting them might help others.

The first gotcha I discovered was that you're supposed to build php from the latest sources and install that on your system. This is actually quite dangerous on a Linux system because doing so invalidates the version installed by the package manager. The default deb package on Ubuntu puts files here, there and everywhere, and making the source code build put everything in exactly the same places is rather difficult and would destroy the package manager information about php. On the other hand, putting it elsewhere gives you two versions and the actual one invoked depends on the order directories are searched. The main problem this leads to is that building an extension in any version other than the one it is run in will prevent the extension from loading. My original php version was 5.3.2, which is what my server is still using. The latest version is currently 5.3.6, which became my commandline version. I didn't want to delete the old version because I had spent some effort installing and configuring it with xdebug, mysql and xslt.

The second gotcha was that the commandline php.ini file is not the same as the one used by the web server. On my system the apache2 one is in /etc/php5/apache2 and the commandline one is in /etc/php5/cli. You really must check the following:

1. that the extension_dir used during execution is the one you put your extension in
2. that the php.ini file that loads your extension is the one actually being used by php on the commandline (or server)

You can check the php.ini file by invoking on the commandline:

php -i | grep php.ini

And the extension_dir similarly:

php -i | grep extension_dir

Like me you'll probably be surprised by what it says. But match them up, and match the compile and the execution versions and it will work. Remember though, that the server will use a different php.ini file, and a different extension_dir. The best way around this dilemma is to download the same version of the source as is currently installed on your system, and build with that.

HritSample Module

I've managed to create a CMS-independent Hello World! Hrit module that runs in Joomla!

So what, huh? Well, this will make it easy for anyone to write a Hrit module in future, which they can load into any popular CMS, starting with Joomla! The cross-CMS compatibility is provided by a single php file, that is the first point of entry in the extension by the Joomla! system. Also needed is a Joomla!-specific xml file for describing the extension. Thereafter the php entry point delegates everything to the 'module', which is a folder containing a real controller and a real view class that doesn't refer to Joomla! in any way, shape or form.

A HRIT Module wrapper tool

Eventually we will need a wrapper program to take such a module and prepare it for the various CMSes automatically. For that purpose an XML file would have to be added to each module to describe its contents, which the wrapper would read and turn into a CMS-specific form.

Hritcore module

To make writing Hrit modules really easy all of the Hrit-specific functionality is contained in another CMS-independent module called hritcore, which is added to the php include-path and from which not only superclasses for Hrit but also the mvdguilib.js Javascript functions, which provide cross-browser functionality for interactivity, can be called.

One of these support files is a surrogate or imitation HritRest service, which just accesses a local database for experimental purposes, rather than a remote service over the web. There is only one public method: get, which takes a REST-style URL as its only argument, and spews back whatever the caller requested. So if users request:

http://localhost/cortex/english/shakespeare/kinglear/act1/scene1/F1

they will get the F1 version of act 1, scene 1 of Shakespeare's King Lear, etc. And if they replace the first bit of the url by 'corcode' they will get the corcode for that version, and similarly for corpix.

Where this still needs to go

Later, when this kind of url is possible on the real REST service the HritRest.php file can be done away with. Shouldn't be long before the two example views: SingleView and CompareView are ready to demonstrate.

Next step, though, is to incorporate formatter (and why not also splitter and stripper?) into the php service and do away with XSLT forever. Oh, what a joy!

Formatter inside PHP

The formatter is a program to replace XSLT, but it uses our standoff markup solution called CorTex/CorCode. At the moment the CorCodeDemo calls formatter on the command line as an external script. But it struck me that because it replaces XSLT it ought to be called the same way that XSTL is - within the PHP daemon as a PHP extension. That way we won't get the hit of inefficiency by running it as a commandline tool. Instead it will just be available, once installed, for any HRIT-modules we design. I don't yet know how to do it, but since everything is open-source it should be easy.

Another refinement is the reuse of MvdCore, a Joomla! component I wrote to facilitate writing a robust set of Joomla! plugins for the MVD-GUI. But since it doesn't refer to Joomla!, except in order to exist as a module, I thought I would use it as a basis for every HRIT module, as a kind of framework library. That way, writing new modules should be dead easy and they will automatically work in every browser. Now that's cool.

Brave New World

Now we've thrashed out a pretty good picture of how the HRIT system will look, I decided to make the MVD-GUI in its image. That is, to use the HRIT REST service, the HRIT API, and write a HRIT compatibility layer for all my modules to run in. The BIG advantage of this is that, provided a compatibility layer is available for a particular CMS, the same module will run unmodified in that CMS (Content Management System). The only catch is that I'd have to find somewhere to host the HRIT Java REST service (cloud, left). So here's my current design for the compatibility layer:

In the Model-View-Controller design the Model handles all interactions with the database. Give me this, here is that, etc. So an implementation of the HRIT API fits that design pretty well (the pink box). It wouldn't have to access any databases directly, because it would get all the data it needs from the REST Service. So it could be the same on all CMSes.

The Controller on the other hand (orange boxes) deals with all the user-clicks in the view and decides what to do with them. It interposes between the view and the model to decide when to call the model and what to return to the view. It's the 'business logic' of the application. An individual CMS can't and does not in practice mandate an MVC design, but it does define conventions for calling modules. So in Drupal and Joomla!, HRIT modules will be defined with a library of functions that will act as the master controller for the module. Whereas the module itself will have its own private controller that will call the master one. The private controller will include the master controller with a require statement and assume the existence of certain functions or static methods inside that controller, say HRITController::doSomething().

The View (green box) can do what it likes, so long as it only uses PHP functionality, and doesn't call any CMS-specific routines or rely on any CMS-specific data. If it needs something like that it will have to get it from the compatibility layer via its private controller.

HRIT standoff format

The HRIT standoff XML format is designed to replace embedded markup by using standoff properties. It is not intended to be definitive, and the same information could easily be recorded using another format. All that matters is that it suffices. It supports the following features:

1. The text is in a separate file, which may be referred to by multiple HRIT markup files.
2. Several markup files can be combined to enrich the text simultaneously.
3. Properties may overlap
4. Both HRIT markup files and the underlying text files can be freely edited

The format doesn't perform these functions it just allows them to happen. So it is actually pretty simple.

Header

The header provides some essential structure and infomation:

<?xml version="1.0" encoding="UTF-8"?>
<hrit-markup style="TEI">

A CorCode is of course closely bound to a CorTex version. In the HRIT system each cortex and corcode is uniquely identified by a URN in the FRBR mould as a sequence of hierarchical names, e.g. "/corcode/english/shakespeare/kinglear/act1/scene1/folios/F1". A CorCode URN is the same as the corresponding CorTex URN except that the first component is "/corcode" instead of "/cortex". So there is no need to record that relationship explicitly in the markup.

The "style" attribute on the other hand is a reference to the URN identifying a CSS format file. This is used to render a CorCode into an external HTML form for display. It's not a complete name because the same corcode/cortex might be rendered in multiple ways, depending on the application and the user's preferences. Each CSS file points to just one CorCode, and hence the unique style name here. A full format identifier would look more like "/corform/TEI/hritsingle/luc-style", which would mean 'the core format for "TEI" corcodes in the hrit-single application in the LUC style'. The CorForm concept is new and we are still working out the details, but it seems clear that this kind of information has to be stored in the "cloud" with the cortexs and corcodes.

Ranges

The body of a HRIT markup file is composed of an ordered series of ranges. Each range points to a span in the base text and is specified by its relative offset from the previous range and its length. This facilitates editing, since changing one range only invalidates the immediately following one. It also has a name because it represents a property. Finally it may contain annotations, which are mostly leftover attributes from XML, although they can also be used to store invisible programming information such as links. But these will need to be backed up by direct functionality in a GUI; they are not intended to be edited by the user.

<range name="pb" reloff="0" len="0">
<annotation name="ed" value="F3"/>
<annotation name="n" value="765"/>
</range>
<range name="sp" reloff="271" len="20"/>

Removed ranges

If a range is labelled as removed="true", it can't be formatted and cannot specify a range in the base text. An example is the teiHeader element in TEI. Since this is metadata its content has a fundamentally different status to the text of the body. So the default recipe of stripper specifies that this element and all its children are removed. A removed element may have its own private content that is stored as part of the standoff markup. This 'content' can belong to any point in the file, but usually to the start, so it can have a reloff attribute, though not a len:

<range name="title" removed="true" reloff=0">
<content>Mr. William Shakespeares Comedies, Histories, &amp; 
Tragedies. Published according to the True Originall Copies.
</content>
</range>

This may sound like a hack, but the information has to be stored somehow if we later want to reverse the conversion from HRIT back to TEI. Of course files originating in the HRIT system itself won't have any removed elements.

Nesting of ranges

If a HRIT markup file has been imported from XML then its ranges will effectively be nested. But this information is not used during formatting, since ranges can freely overlap.

Tail

This is just:

</hrit-markup>

This format is still subject to development and may be changed in future.

How fast can we diff two strings?

On this question I have yet to read of any advance on Esko Ukkonen's 'Algorithms for Approximate String Matching' which appeared in Information and Control, 64, 100-118 in 1985. As per his predecessors, he uses the edit-graph to model the matching process, laying out the B-string across the top and the A-string down the left hand side (see diagram below). Finding the shortest edit script is akin to moving through this graph one square at a time. The x coordinates are just indices into the B-string, and the y-coordinates are expressed as x-i, where i is the index of the relevant diagonal. (The diagonals are numbered 0 at the origin, with increasing negative values on the 'down' side and increasing positive values on the 'right' side.) From each square there are three possible moves: right, corresponding to a deletion from the B-string; down, corresponding to an insertion from the A string; diagonally down and right, corresponding to a match (if the characters at that point are equal) or to an exchange if they are not.

In this diagram we transform 'aback' into 'beak'. First we delete 'a'. Then we match 'b', insert 'e', match 'a', delete 'c' and match 'k'. Note that each move takes us one beyond the square it was performed in.

Progressive refinement of the p-band

The basic idea of Ukkonen's (and Myers) algorithm is that the only positions of interest as we traverse the graph are the most advanced positions on each diagonal. So instead of storing NxM positions (as in the dynamic programming method of Needleman and Wunsch for example) we only need to store N+M diagonal positions – quite a saving. Ukkonen further reduces the search space to a narrow diagonal strip down the centre of the graph – the p-band (p.105f) – which can gradually narrow as we proceed toward the end (p.106). Both ideas have been republished as alleged improvements to his algorithm (e.g. Wu 1989 – cited 88 times). Ukkonen defines p as ⌊1/2(d_mn/Δ–|n-m|)⌋. In plain English the worst possible cost is incurred by exchanging all the characters on the 0 diagonal and then deleting all the characters horizontally until you get to M,N. Any path on the graph that is more than half that cost away from the goal has no chance of reaching it more efficiently than that. What is more, we can update p as we get closer to the goal, and we get a better idea of the cost of reaching D_mn.

Based on this idea my program assesses dynamically, for each move in the graph, whether it could result in a shorter path to the goal than the worst result of the currently best diagonal. If not, then it is dropped. My algorithm is also very space-efficient. Rather than allocating an array of size M+N (the lengths of the two strings) to hold the diagonals, I use a linked list to store only the active ones.

Moving through the graph

We construct a linked list of diagonals and number them, starting with the one between the two strings at 0,0 (the origin), numbered 0. The other diagonals along the y-axis are numbered -1,-2,-3 etc and the ones along the x-axis are numbered 1,2,3 etc. Then we assess the even and odd numbered diagonals in the list in alternate passes. The reason is that the computation of the even-diagonals interferes with that of the odd-diagonals. For each diagonal at index i and horizontal position x we compute the maximum x-value that would result from:

an insertion from the i+1 diagonal
a deletion from the i-1 diagonal
an exchange on the i diagonal

Whichever takes us further east along the diagonal (and by implication also further down) will be the best move. All things being equal we favour the exchange move because it promises to be the cheapest overall. After processing the even and odd diagonals we increment the d-value: our record of how much it has cost to transform B into A so far. If we are at one or the other edge of the linked list, and it is necessary, we also create a new diagonal to the left or right. This won't be processed in the current pass because it is odd when we are even and vice versa.

Finding the snakes

A match or 'snake' as Myers called them, is just a run of matching characters in the edit graph, and they give the diagonal method all its speed. But we have to be clear as to when we look for them. The very first square of the edit graph at 0,0 may or may not contain a matching character. If it does, we have to match the snake before checking for an exchange, but we will still have to do a delete and an insertion from 0,0. The reason is that otherwise we might miss an optimal snake starting on the -1 or 1 diagonal. Another position of care arises at the very last square at M-1,N-1. Until we have checked that square for a match as well as for insertion, deletion and exchange we won't have reached the real 'end', which is one character beyond M-1,N-1. For all other squares we just test for the existence of snakes after each edit operation, so we can be certain at the start of the next pass that the characters at the head of each diagonal do not match.

Exchanges vs insertions and deletions

Traditionally diff algorithms don't compute the exchanges. But an exchange move from x,y to x+1,y+1 costs only 1, whereas a deletion+insertion move to the same location costs 2. So exchanges are often much cheaper. The insertion/deletion pair can be recovered from any pair of exchanges. Replacing xxx with yyy is the same as deleting xxx and inserting yyy. Here's the result of my implementation of Ukkonen's algorithm. When you consider how many comparisons the program could have made (the entire graph) as opposed to the ones it did make (the squares marked with 'x'), you can see how efficient it is:

Recording the path

Finding the optimal path through the graph is no use if it doesn't allow us to construct a shortest edit script. One simple way to do this is to associate a path with each diagonal. The path will be implemented as a linked list. Each component of the path has an x,i origin, a length and a type (nothing [for the initial move], inserted, deleted, exchanged or matched). If the type changes, from, say, matched to exchanged, we create a new path-component and link it backwards to the last one. (If we went forwards we would need multi-way branches.) But if the type is unchanged we simply increase the length of the existing one. When we finally get to the end, the backwards-pointing path of the successful diagonal will contain the shortest edit script. To print it we just reverse the order and print it out. Here's the edit script for the above graph:

matched 11 chars at x=0 y=0
exchanged 4 chars at x=11 y=11
matched 25 chars at x=15 y=15
exchanged 3 chars at x=40 y=40
matched 1 chars at x=43 y=43

Downloadables

pdiff prints out an edit script but also generates a trace of moves taken in the edit graph if both strings are smaller than 100 bytes. It's free under the GPLv3 and is written in C++. It can also diff entire files.