Multi-Version Documents

C++ Version of nmerge

2009-11-01T13:51:00.000-08:00

One problem with the current design of nmerge is that it is written in Java. The commandline tool is a thin C wrapper around that, and if you want to process larger files you can't pass in arguments to increase available memory. So it just fails to work on large files. Also if you want to run it on servers that don't have, or won't allow, Java (true of many commercial hosting sites) you're also out of luck. Since the Digital Variants people and probably a large number of humanities projects will have these problems also, I have decided to convert it into pure C++. This should be relatively easy, and the benefits are:

memory usage will be limited only by what is available on the machine, not to that allocated to the Java Virtual machine (JVM)
nmerge-c++ will be callable from PHP or another scripting language without requiring installation of a JVM.
nmerge can optionally write to a database instead of directly to disk. This is usually the only way you can save changes on a commercial hosting site.
The C++ version will use far less memory than the Java version and should be a bit faster.

Overall, these changes will facilitate the building of a practical web application or plugin, which can be added to existing sites. Initially, my intention is to produce a Joomla! plugin that other people can use.

Some changes that will be possible in this revision include:

Grouped transpositions. By assessing individual transposition candidates as a group it will be possible to detect larger transpositions that contain small corrections.
Proper multi-tasking of the merging process in C++ will hopefully speed up the algorithm considerably.

That's the plan. I thought I'd let you know where I'm taking this, and it is to turn it into a generally usable tool.

There is at least one drawback, of course. C++ is cumbersome to write code in, compared to the relative heaven of Java. It's like painting a room with a brush instead of a roller.

Whoops!

2009-10-23T15:16:00.000-07:00

A favourite quotation of Edgar Dijkstra is that 'testing shows the presence, not the absence of bugs'. This is very true. In Australian homes too you can squash a few cockroaches and think you've got them all, but how do you know there isn't a whole colony hiding in the skirting boards? I'm guilty of putting in a '!' when I shouldn't have. My only explanation was that I was jetlagged in Montreal and fed up with preparing my presentation. For some reason I put in that 'not', which prevented nmerge from finding any left-side transpositions at all. All I can say is: 'Whoops!'

I'll fix it in the next hour or so and upload the new version as 1.0.2, and update Alpha too. The transposition algorithm is not perfect - I never said so, if you read the Balisage paper, particularly at the end - but it is workable. One thing you should keep in mind is that this is a unique program in its field. Several people have written merging programs for humanistic texts, and a couple have even included transpositions (MEDITE, JNDiff). But only between two texts at a time. I merge N texts into one digital representation.

One thing I'd like to do soon is make it find transpositions in groups (a flaw that Peter Robinson rightly pointed out). And it could be even faster, if I can work out how to parallelise the algorithm. That's why I 'built' this fancy i7 computer.

The good thing about computing variants automatically rather than manually is that it is not final. Any improvements in the algorithm are immediately visible. Whereas making systematic changes to a manually coded set of texts with complex variants is not trivial.

New Versions of nmerge and Alpha posted

2009-09-01T04:50:00.001-07:00

The difference here is that nmerge now includes the full source code, released under the GPL v3, and also contains a single example text that I can give away under the same license. It is the first scene of Shakespeare's King Lear. I have tried to make it as true to the source texts as I can but it's a lot of work getting markup to look like a manuscript. I never realised before how much the tags interfere with that. It's very annoying. Anyway, let me know if there are any mistakes. Or any ideas on how Alpha can be improved. I'm sure there are lots.

Of course it is full of markup hacks, mainly lines split over speeches, but I couldn't fix that without introducing another layer for each MS. I'd prefer using some other technology other than markup for the content but there isn't one yet. Oh well!

Here's the link.

Balisage Presentation 13 August 2009

2009-08-13T19:44:00.001-07:00

My talk at Balisage in Montreal went very much as planned. The slides took as long as I had paced them to last: 28 minutes. Then I did two software demonstrations, one of the nmerge commandline tool and another of the Alpha multi-version wiki. The former is more or less finished (though I keep tweaking it) and the Alpha wiki is about half done, but usable. There was time afterwards for a few questions. The best of these came from Fabio Vitali, who also works with Angelo Di Iorio on a diff calculating algorithm for edited XML texts. He convinced me after the talk that their method of computing diffs has some advantages over my simplistic greedy approach for XML texts. But my method I think is still a good fallback in the general case. I think the best thing is to try to incorporate the basic idea of their JNDiff algorithm, which is making the merging algorithm optionally XML-aware, rather than try to use their code, which is not really open-source yet.

I think the paper went down well because of the demos. No one else whose talk I saw presented any finished software. It was mostly work in progress - the usual conference fare. But reactions to it were not very critical. They had little to say I think because it was not about an application of XSLT or XQuery - their favourite tools. But the talk at least has exposed the MVD idea to a wider audience. No more excuses any more for not mentioning it when discussing solutions to overlapping hierarchies.

I received favourable comments from the upper reaches of the Balisage hierarchy which seemed genuine. And I am encouraged by that.

I have updated nmerge with the version I demonstrated at Montreal. Also there is a copy of the wiki in its current state, minus any MVDs. I can't use any of the usual examples because of copyright restrictions. So I'll have to create some of my own pretty soon.

The Biggest Advantage of Using MVDs

2009-08-12T17:40:00.000-07:00

I suddenly realised now I am here in Montreal preparing to defend my ideas against 100 experts from around the world that I have failed to notice all this time the biggest advantage of MVDs. And it is this: The alternative to computing the interrelations between multi-version texts can only be encoding them manually. In speaking of the supposed advantages of standard XML tools what is often forgotten is the enormous human cost of training people to use markup, and getting them to encode it and check it against the originals. I know from experience that this is very expensive. We literally spent thousands of man-hours encoding variants in Wittgenstein. If we could have had a tool for doing that automatically, much of that time and money would have been saved.

Another advantage of computing interrelations automatically is that it is so easy to get back what you put in, unmolested. Hand-encoded XML hard-wires the interconnections between versions, and getting back the original text can be a hard problem if you decide later to change to another technology. With nmerge I just press the "archive" button and it is done.

If computers are good for anything they are good for saving human effort.

Alpha Prototype Ready

2009-07-26T17:52:00.000-07:00

I am renaming the multi-version wiki Alpha, simply because it's easier to say than Phaidros. It's a bit of a joke, really, because 'Alpha' was just the description of the product I developed for DH2008. It was the 'alpha' release of that.

The old Alpha didn't do transpositions, and to remedy this deficiency I have been labouring hard for the past year. NMerge was revised to support transpositions, but I hadn't integrated it into the multi-version wiki. But when I finally saw the result of the new nmerge in the web browser, it was suddenly clear that there were still some bugs in the transposition algorithm. Finding out exactly what was going wrong, though, took me about a week of solid debugging. But it is done now and I am finally satisfied. And now I have something to take to Montréal to show the audience. And I can say: 'Hey folks, you said this conference was all about theory, but here's something that actually works.' I think that is a pretty good argument.

In this screendump of part of the TwinView of Galiano's 'El mapa de las aguas' you can see the transposition of 'otras de un hachazo' from after 'de un bocado rabioso' (in version B, left) to before (in version C, right). To consistently detect cases like this manually would be near to impossible.

Red text is deleted in the left-hand version with respect to the version on the right. Blue text is inserted, and transpositions are shown in grey. Black text is merged and, like transpositions, clicking on it aligns the text on each side. This use of these simple features of HTML results in a surprisingly effective UI.

Character-Level vs Word-Level Alignment

The use of character-level alignment by default is new to this version. For example, the expression 'el molino chico' became 'el molino' through the deletion of the character sequence 'o chic'. This goes to show that what humans would expect – the deletion of ' chico' – and what the computer detects, don't always correspond. I don't think that is a bad thing. The alternative would be to fail to see changes of spelling such as 'desaparecido' for 'desparecido' or the capitalisation of 'Ojos' for 'ojos'. A word-level granularity would puzzle the reader while he/she tried to work out the difference. It is clearer to see small changes like these highlighted, so I agree with the MEDITE people that character-level alignment is more powerful. After all, you can always reduce character-level granularity to word-level but if you only have word-level alignment you are stuck with it.

'Collation' programs based on XML use word-level granularity because a finer resolution would make the markup impossibly complex (you'd have to mark up each letter separately). That doesn't have to be a restriction once we abandon the print-oriented concept of 'apparatus.' For the digital medium, at least, a new digital presentation of variation is needed. Let it evolve.

Interface 09 and Multi-Version Wiki

2009-07-02T15:27:00.000-07:00

We will be presenting a poster at Interface09 at the University of Southampton. There will also be a demo of the multi-version wiki, which I hope will be an iteration further on from that presented at Oulu for Digital Humanities 2008. The new multi-version wiki is simply the old wiki with the new nmerge library added, but that includes support for transpositions, which is kind of important. It is a Jetty 6 based web application that runs inside your browser, and allows you to view and edit MVDs in a variety of intuitive ways.

Digital Variants Portal

Eventually the wiki will be broken up and integrated into the Digital Variants Website I am building. In this form the wiki will be a series of portlets inside a portal. Each portlet conforms to JSR 286 and is implemented in Jetspeed 2. A portal allows the user to configure his or her own interface on the web using the portlet components. It also promotes reuse of the portlets by other parties. We are going for broke with this design: I for one don't believe that deficient or obsolescent technology has any place in designs for the future. If we can build it, we will.

nmerge 1.0 posted

2009-06-05T01:57:00.000-07:00

OK, I've posted the first BETA version of nmerge for UNIX/Linux/OSX only. I'll add a Windows installer as soon as I can get around to it. Of course I expect it to go wrong immediately, even though I have tested it thoroughly. But I can only really gather more information by trying it on other files. And it comes currently with no example files.

Some basic installation instructions for the non-GNU afficionados:

Download the nmerge-1.0.tar.gz file using the link above
Open a terminal window, navigate to the download file and unpack it using tar xzf dir.tar.gz or just double click on it if you have a Mac
In the terminal window type cd nmerge-1.0
./configure
make
sudo make install

You should now have a command "nmerge". If it complains about the Java make sure you have a valid JRE installed. It must be at least version 1.5.0 (1.4.2 is no good). To find out type java -version in the terminal window. Download a more recent JRE from Sun. (You only need the JRE not the JDK unless you also want to develop Java software). If it still doesn't work you have an issue that you should post on Google code.

The first update will contain the source code and documentation. I left it out because of my inexperience with GNU automake.

Balisage Paper Accepted

2009-06-02T15:45:00.000-07:00

My Balisage paper about how to create and edit MVD files has been accepted. I have already bought the flight tickets and registered, so I will be going to Montreal on August 11-14. That's the other side of the world for me and I think I must be mad. But this is the only way to properly air the MVD concept and get some reactions from the people most likely to field valid objections. If they clear it, then I think that will vindicate it as far as it can be at this stage. The draft paper is here, although it is rather technical. I will post my simplified slide show when I have it.

Out of the Tunnel

2009-06-02T03:13:00.000-07:00

Well, it all works. Now I just have to build an installable package for it. To be honest I don't think many if any people will want to use nmerge. It's too user unfriendly because it has no real user interface. People want a GUI these days, and nmerge is designed to be the Swiss army knife for whatever GUI you might want to put on top of it. Nevertheless I will post it as soon as possible with a GNU type installer and maybe a Windows one if that is not too hard (perhaps using Nullsoft). The main point is that a milestone has been reached: the MVD file format is born. (Hooray!)

After that it will be time to add my own GUI, which is just an updating of the Phaidros wiki which has lain untouched for nearly a year now. It is time to update it with some killer features: e.g. Tree View, which will show the genealogy of a set of versions via a graphical tree which you can configure and regenerate according to taste. I have some other ideas too which can be blended in gradually.

The Light at the End of the Tunnel

2009-05-28T04:50:00.000-07:00

Well I finally got 'compare' to work properly. The delay was caused by having to redesign the 'chunking' mechanism that delivers the text back to the browser as a series of blocks with all the same characteristics. So all the deleted text can be made red, and the inserted blue and the merged black. And the user can click on the black text and be taken to the corresponding part of the compared text. Very important, but also very tricky to get absolutely right. And in this version I had to allow for transpositions, and they are even more complicated. But now at last it works. I will post the project on Google Code in the morning, because I am too tired now.

usage

create

help

add

del

desc

arch

unarch

export

import

update

read

list

comp

find

vars

Several Days Later ...

Almost done testing the code. Just a few minor problems with find (again) and variants. The latter could be quite a useful feature in the GUI. For example, selecting a piece of text could conceivably show its variants dynamically in a sub-window at the bottom. I favour an in-line solution using popup text, but that will have to wait. This feature should demonstrate that we don't need to 'collate' separate physical versions any longer to get this information.

HyperNietzsche vs MVD

2009-05-14T16:22:00.000-07:00

I decided after all to make some general remarks about the recently proposed 'Encoding Model for Genetic Editions' being promoted by the HyperNietzsche people and the TEI. Since this is being put forward as a rival solution for a small subset of multi-version texts covered by my solution, I thought that readers of this blog might like to know the main reasons why I think that the MVD technology is much the better of the two.

One Work = One Text

Because it is difficult to record many versions in one file using markup, the proposal recommends a document-centric approach. In this method each physical document is encoded separately, even when they are just drafts of the one text. As a result there is a great deal of redundancy in their representation. They interconnect the variants between documents by means of links which are weighted with a probability, and they see in this their main advantage over MVD. But this is based purely on a misunderstanding of the MVD model. The weights can of course be encoded in the version information of the MVD as user-constructed paths. We can have an 80% probable version and a 20% probable version just as well as physical versions.

Actually I think it is wrong to encode one transcriber's opinion about the probability that a certain combination of variants is 'correct'. A transcription should just record the text and any interpretations should be kept separate. How else can it be shared? The display of alternative paths is a task for the software, mediated by the user's preferences.

The main disadvantage in having multiple copies of the same text is that every subsequent operation on the text has to reestablish or maintain the connections between bits that are supposed to be the same. You thus have much more work to do than in an MVD. I believe that text that is the same across versions should literally be the same text. This simplifies the whole approach to multi-version texts. I also don't believe that humanists want to maintain complex markup that essentially records interconnections between versions, when this same information can be recorded automatically as simple identity.

OHCO Thesis Redux

The section on 'grouping changes' implies that manuscript texts have a structure that can be broken down into a hierarchy of changes that can be conveniently grouped and nested arbitrarily. Similarly in section 4.1 a strict hierarchy is imposed consisting of document->writing surface->zone->line. Since Barnard's paper in 1988 where he pointed out the inherent failure of markup to adequately represent a simple case of nested speeches and lines in Shakespeare - sometimes a line was spread over two speeches - the problem of overlap has become the dominant issue in the digital encoding of historical texts. This representation, which seeks to reassert the OHCO thesis, which has been withdrawn by its own authors, will fail to adequately represent these genetic texts until it is recognised that they are fundamentally non-hierarchical. The last 20 years of research cannot simply be ignored. It is no longer possible to propose something for the future that does not address the overlap problem. And MVD neatly disposes of that.

Collation of XML Texts

I am also curious as to how they propose to 'collate' XML documents arranged in this structure, especially when the variants are distributed via two mechanisms: as markup in individual files and also as links between documentary versions. Collation programs work by comparing basically plain text files, containing only light markup for references in COCOA or empty XML elements (as in the case of Juxta). The virtual absence of collation programs able to process arbitrary XML renders this proposal at least very difficult to achieve. It would be better if a purely digital representation of the text were the objective, since in this case, an apparatus would not be needed.

Transpositions

The mechanism for transposition as described also sounds infeasible. It is unclear what is meant by the proposed standoff mechanism. However, if this allows chunks of transposed text to be moved around this will fail if the chunks contain non-well-formed markup or if the destination location does not permit that markup in the schema at that point. Also if transpositions between physical versions are allowed - and this actually comprises the majority of cases - how is such a mechanism to work, especially when transposed chunks may well overlap?

Simplicity = Limited Scope

Much is made in the supporting documentation of the HyperNietzsche Markup Language (HNML) and 'GML' (Genetic Markup Language) of the greater simplicity of the proposed encoding schemes. Clearly, the more general an encoding scheme the less succinct it is going to be. Since the proposal is to encorporate the encoding model for genetic editions into TEI then this advantage will surely be lost. In any case there seems very little in the proposal that cannot already be encoded as well (or as poorly, depending on your point of view) in the TEI Guidelines as they now stand.

A Slight Delay in a Good Cause

2009-05-08T03:48:00.000-07:00

OK, I'm not finished yet, when I said I would, but software is like that. Sorry. I decided that in order to really test the program properly I should have a complete test suite that I can run after making any changes to make sure that everything in the release is OK. Well when I say 'make sure' a test can only tell you if a bug is present, not tell you that there are none. But that's a lot better than letting the user find them. If I release something that is incomplete or not fully tested then I know the sceptics will attack the flaws. They will say 'See, it doesn't work, I told you so!' I can't afford that, so I have to be careful. So far I have tests for fourteen out of 16 commands.

I also added an unarchive command to go with the archive command. With 'archive' users can save an MVD as a set of versions in a folder, plus a small XML file instructing nmerge how to reassemble them into an MVD. This contains all the version and group information etc. So if you don't believe the MVD format will last, it doesn't matter. You always have the archive and that is in whatever format the original files were in. A user could even construct such an archive manually. The 'unarchive' command takes this archive and builds an MVD from it in one step.

Here's a progress bar for the tests. Green means there is a test routine and it passes. Yellow means there is a test routine but it doesn't pass yet. Red means there is no test routine and I don't know for sure if it works, but it might. There was an intermittent problem with update, but this is now fixed.

usage

create

help

add

del

desc

arch

unarch

export

import

update

read

list

comp

find

vars

I'm going for a beta version with this release. I think it's good enough.

OK now there's a project on Google code. I must say it was much easier than creating a Sourceforge project. They wanted me to write an epic about it and even then I had to wait 1-3 days for their royal approval. On Google code it was instant. Cool.

Nmerge tool code-complete

2009-04-30T16:32:00.001-07:00

The nmerge commandline tool is now code-complete. I guess it's a 'pre-alpha' version. Since this is a revision of a previous working version, though, testing should not take too long. I would estimate that, after the Labor day weekend (Monday 4th May) I should have an alpha-version. But with software you never know. This version supports the new merging algorithm from the submitted Balisage 2009 paper, which works pretty well.

Nmerge is also a JAVA library that can be used from within a JAVA application, like the Phaidros wiki, to provide support for Multi-Version-Documents. Once it has stabilised I will rewrite it as a C++ commandline tool. But for now we have to put up with a slightly more cumbersome syntax. Here is the "usage" statement produced by the program so you can get some idea of what it does. Once it is reasonably well tested I will put the source code on SourceForge under the GPL v3.

The command syntax is a bit complicated, but so is what it is trying to do. I envisage that this tool could be used in a shell or commandline script to automate, say, the construction of an MVD from a set of files. At least that's what I use it for. In any case the -h option prints out an example or two of how to use each command. The -c option specifies the command you want to perform on the MVD, and the other arguments are the parameters that the command uses, provided they make sense. If they don't you'll get an error message.

With the nmerge tool MVD becomes a real format. There's no GUI user interface because if I added one, you couldn't take it away and put in your own. If you need one, wait for Phaidros.

usage: java -jar nmerge.jar [-c command] [-a archive] [-b backup] 
     [-d description] [-e encoding] [-f string] [-g group] [-h command] 
     [-k length] [-l longname] [-m MVD] [-n mask] [-o offset] [-p]
     [-s shortname] [-t textfile] [-v version] [-w with] [-x XMLfile]
     [-?] 

-a archive - folder to use with archive and unarchive commands
-b backup - the version number of a backup (for partial versions)
-c command - operation to perform. One of:
     add - add the specified version to the MVD
     archive - save MVD in a folder as a set of separate versions
     compare - compare specified version 'with' another version
     create - create a new empty MVD
     description - print or change the MVD's description string
     delete - delete specified version from the MVD
     export - export the MVD as XML
     find - find specified text in all versions or in specified version
     import - convert XML file to MVD
     list - list versions and groups
     read - print specified version to standard out
     update - replace specified version with contents of textfile
     unarchive - convert an MVD archive into an MVD
     variants - find variants of specified version, offset and length
-d description - specified when setting/changing the MVD description
-e encoding - the encoding of the version's text e.g. UTF-8
-f string - to be found (used with command find)
-g group - name of group for new version
-h command - print example for command
-k length - find variants of this length in the base version's text
-l longname - the long name/description of the new version (quoted)
-m MVD - the MVD file to create/update
-n mask - mask out which kind of data in new mvd: none, xml or text
-o offset - in given version to look for variants
-p - specified version is partial
-s shortname - short name or siglum of specified version
-t textfile - the text file to add to/update in the MVD
-v version - number of version for command (starting from 1)
-w with - another version to compare with version
-x XML - the XML file to export or import
-? - print this message

MVDs in binary or XML?

2009-04-23T15:13:00.000-07:00

A pattern is emerging in the effect that the MVD concept is having on people. They take on board its power at representing variation but they don't like the idea of representing the data in binary form. Instead they think it is possible to represent variation in some form of XML. So far I've heard proposals to use TEI-XML, RDF or GraphML. It's tempting, of course, to carry on using XML when this is the tool we are all most familiar with. However, my point of developing the MVD format was precisely to get around the limitations of all forms of markup. You can't represent a variant graph in XML satisfactorily if the text you are recording the variation of is itself XML – and it usually is. The reason is that you can't represent cases where the markup itself varies: for example the deletion of a paragraph break:

<del></p><p></del>???

Of course there are hacks to get around this particular case but they have negative consequences. What you end up doing is modifying the markup to accommodate weaknesses in the representational power of markup itself. I think that is a fundamentally flawed strategy. It is just another form of putting presentational information into markup that is supposed to be generic. If you try to represent variation in a set of texts or in one text using markup you very quickly run up against the problem of overlap. And markup is very poor at representing that as we all know. The only way to completely get around the overlap problem is to represent variation using a non-markup based technology. That's the whole point of MVDs that doesn't seem to have been widely acknowledged yet.

MergeTester released

2009-04-05T00:32:00.000-07:00

For the thesis I wrote MergeTester, a simple utility that implements the merging algorithm from chapter 5. Although not a practical program, it does demonstrate how the program works and allows the user to test it on folders of versions in any format. It builds up a variant graph of the versions and prints them out one arc at a time. From the printout the user could manually reconstruct the graph or part of it.

The advantage of the program lies in the fact that the way it works is not obscured by any other code and it does not depend on 3rd party libraries. Any comments and reports of bugs found will be gratefully received!

At the moment I am incorporating it into nmerge, which will also be released shortly. Nmerge can convert a variant graph into an MVD, so the merging algorithm will then become practical.

Final Version of Multi-Version Documents Paper Published by Elsevier

2009-03-18T19:16:00.000-07:00

The final version of my MVD paper has now appeared online. This hyperlink is permanent and can be used in citations. The paper reference is Schmidt, D. and Colomb, R, 2009. A data structure for representing multi-version texts online, International Journal of Human-Computer Studies, 67.6, 497-514.

Thesis Submission

Also I have now submitted my thesis. The final title was 'Multiple Versions and Overlap in Digital Text'. Here's the abstract:

This thesis is unusual in that it tries to solve a problem that exists between two widely separated disciplines: the humanities (and to some extent also linguistics) on the one hand and information science on the other.
Chapter 1 explains why it is essential to strike a balance between study of the solution and problem domains.
Chapter 2 surveys the various models of cultural heritage text, starting in the remote past, through the coming of the digital era to the present. It establishes why current models are outdated and need to be revised, and also what significance such a revision would have.
Chapter 3 examines the history of markup in an attempt to trace how inadequacies of representation arose. It then examines two major problems in cultural heritage and linguistics digital texts: overlapping hierarchies and textual variation. It assesses previously proposed solutions to both problems and explains why they are all inadequate. It argues that overlapping hierarchies is a subset of the textual variation problem, and also why markup cannot be the solution to either problem.
Chapter 4 develops a new data model for representing cultural heritage and linguistics texts, called a 'variant graph', which separates the natural overlapping structures from the content. It develops a simplified list-form of the graph that scales well as the number of versions increases. It also describes the main operations that need to be performed on the graph and explores their algorithmic complexities.
Chapter 5 draws on research in bioinformatics and text processing to develop a greedy algorithm that aligns n versions with non-overlapping block transpositions in O(MN) time in the worst case, where M is the size of the graph and N is the length of the new version being added or updated. It shows how this algorithm can be applied to texts in corpus linguistics and the humanities, and tests an implementation of the algorithm on a variety of real-world texts.

MVD is Not a Replacement for Markup

2009-03-10T13:47:00.000-07:00

Some people still think of MVD as a replacement for markup. It isn't. It complements markup systems or any technology that can represent content. As I said in the main page What's a Multi-Version Document? an MVD represents the overlapping structure of a set of versions or markup perspectives. It doesn't need to represent any of the detail of the content, which is the responsibility of the markup.

I realise that it's easy, and natural, to seek to dismiss radical ideas simply because they are radical. The difference in this case is that MVD is a technology that definitely works. It's not all that radical anyway. Consider the direction in which multiple-sequence alignment is going in biology. They have also realised that the best way to represent multi-version genomes or protein sequences is via a directed graph (e.g. Raphael et al., 2004. A novel method for multiple alignment of sequences with repeated and shuffled elements, Genome Research, 14, 2336-2346). I prefer to think of that idea as parallel to mine, and his 'A-Bruijn' graph is rather different from my MVD, but it represents the same kind of data in much the same way. Acceptance that this basic idea can also be applied to texts in humanities and linguistics is just a matter of time.

The Inadequacy of Markup

If markup is adequate for linguistics texts, why is it that every year someone thinks up a new way to manipulate markup systems to try to represent overlap? If it were adequate there would be no need for new systems, but we continue to see 1-3 new papers on the subject every year. It's seen as a game. Look at the Balisage website: 'There's nothing so practical as a good theory'. Perceived as an unsolvable problem, overlap is the perfect topic for a paper or a thesis.

In the humanities, overlap in markup systems is more than an annoyance; it wrecks the whole process of digitisation. In simple texts you can just about get by, but it's a question of degree. Try to use markup to record the following structures:

Deletion of a paragraph break
Deletion of underlining
Changes to document structure
Transposition
Overlapping variants

These can all be done somehow in markup, I admit, but very poorly. And they are features that occur all the time in original texts. The fundamental problem is that you can't adequately fit a non-hierarchical structure into a hierarchical template. To choose markup alone as a medium to preserve our textual cultural heritage is to resign yourself to mangling that information.

Why do we have to use markup to record complex structures it was never designed to represent? Hand that complexity over to the computer and let it work it out. That's what MVD lets you do. If you are getting a headache shuffling around angle brackets and xml:ids, then think again. Is this any proper way for humans of the 21st century to interact with the texts of their forebears?

MVD Paper available online

2009-02-18T13:59:00.001-08:00

Elsevier have published the paper I wrote with Bob Colomb about Multi-Version Documents online. The Greek text has dropped out of Figure 16, but the rest is good. I hope this has an impact, and it is certainly something I will be referring to in future. It represents everything I knew about the MVD idea and its implications as of December 2008.

Thesis Complete

This morning I submitted a near-final draft of my thesis 'Multiple Versions and Overlap in Digital Text' to my two supervisors. The last chapter describes some new work on aligning multi-version texts automatically. Here's a table taken from the thesis which summarises its performance on a variety of multi-version texts.

The SZ column is the average version size in kilobytes, NV is the number of versions, TT is the total time taken to merge all versions, AT is the average time to merge one version after the first, both in seconds. The test machine had a 1.66GHz Core Duo processor, using one core. The Romulo doesn't merge properly at the moment because there is almost nothing in common between the versions, so the merge times don't mean much in this case.

The key is the AT column, which is how long it takes to 'save' an edited version back into the document. As you can see, it's pretty fast, considering that this is a hard problem. As far as quality goes, I can't see any bad alignments or false transpositions, except in the Malvezzi case. Once I can coerce the input into a sensible format this should also work.

Balisage

It looks as if I will be going to Balisage this year. I will be presenting a boiled down version of Chapter 5 of the thesis, which is all new work. I'll be very interested to hear their reactions, especially as I can now demonstrate the theory. (Their motto is 'There is nothing so practical as a good theory').

The MVD File Format

2008-12-04T13:19:00.000-08:00

Several people have asked me what is inside an MVD, so I thought I would put it on the record.

The idea behind the Multi-Version Document or MVD format is to use the list form of the variant graph as the basis for an encoding of a single work, in all its versions or markup perspectives, as a single digital entity. The advantages of this form of digital document should be obvious. It enables a work to be viewed and searched, its versions compared and edited as one file. For example, all versions of Homer's Iliad or the seven markup perspectives of the American National Corpus (Ide, 2006) could be encapsulated in a single compact and editable representation. Also, the relationships between various parts of each version, the what-is-a-variant-of-what information, is also recorded. Storing a multi-version work as a set of separate files has the great disadvantage of requiring this kind of data to be recalculated each time it is needed. In an MVD this has already been calculated once and is thus built-in.

If the content of each version is itself XML, then XML is a poor format for an MVD. An MVD may, however, be written in binary or XML format. In the latter case, the XML content of each version, inside the XML encoding of the MVD structure, is escaped. That is, all instances of '<', '>' and '&' have to be replaced by their equivalent entities '<', '>' and '&'. The purpose of the XML form of an MVD is merely to allow the researcher to look inside it to see what is there. Editing it by hand is virtually impossible, because the delicate list format produced by Algorithm 1 can so easily be broken.

A tinker-proof binary format is therefore preferred. If desired for archival purposes, an MVD can be written out as a set of separate XML files, but the format uses open-source software to encode its content, so it is also archivable. The structure of an MVD is shown below:

The outer wrapper is a Base64 encoding, expressing binary data as plain text.

The inner wrapper is the ZIP encoding performed by the open source Zlib library (Gaily and Adler, 1995). This serves the double purpose of scrambling the data to deter tinkering, and compressing it so that one MVD typically occupies little more space than a single original version. Even the alteration of a single byte of the outer Base64 wrapper will very likely break the inner ZIP encoding and the document will fail to load, as it should. Inside the ZIP container are the four parts that comprise the real content:

Magic	the presence of this hexadecimal string guarantees that this is an MVD
Groups	these are labels for a hierarchy of arbitrary depth used to group versions or other groups
Versions	these provide a simple description sufficient to identify the ID, short name and long name of each version, whether or not it is a partial version, and its group
Pairs	the pairs list that defines the variant graph itself

No further detail is needed, and would in fact damage the general applicability of the format. Groups can be used to express any desired classification system for versions. The short name of a version would typically be a siglum or other short name for convenient reference, and the longer name would typically be a full version name. All other details of a version's text are the responsability of the content format.

References

J.-L. Gailly and M. Adler (1995) Zlib

N. Ide and K. Suderman (2006) Integrating Linguistic Resources: The American National Corpus Model. In Proceedings of the Fifth Language Resources and Evaluation Conference.

From Toy Time to Big Time

2008-11-30T12:49:00.000-08:00

I don't know if this warrants another entry but the test program is now robust enough to handle large real world files in XML. I tried it on three 16K texts and it took 13.5 seconds overall to merge them with hundreds of transpositions. That is probably too many, but it does break up longer transpositions if it finds an alignment or insertion/deletion in the middle. The next step is to incorporate the test program into the NMerge library and thus allow the results to be displayed in the multi-version wiki.

The transposition program works in the real world and it is fast.

Transpositions Conquered

2008-11-16T14:23:00.000-08:00

Today the test program correctly merged three versions of a single sentence of the Sibylline Gospel, detecting four transpositions and encoding them correctly. The sentences were:

A: Et sumpno suscepto tribus diebus morte morietur et deinde ab inferis regressus ad lucem veniet.

B: Et mortem sortis finiet post tridui somnum et morte morietur tribus diebus somno suscepto et tunc ab inferis regressus ad lucem veniet.

C: Et sortem mortis tribus diebus sompno suscepto et tunc ab inferis regressus ad lucem veniet.

I must thank Nicoletta for supplying this splendid example, which in a small space contains so many transpositions. Here is the variant graph built automatically from the three versions. When I say 'automatically' what I mean is that I drew the graph manually from the program's textual output. The program was set to make no variants of less than five characters, although it does split arcs down to a single character. There are two transpositions, each present twice. I have indicated these by drawing the transposed forms in grey. The parent arcs are in black and the two are connected by dotted lines. The triple repetition of 'Et' at the start of the graph could be removed by reducing the minimal variant size. At the moment I am happy to see such high quality output without resorting to fine tuning.

The best thing about the program is the degree to which repetitions between versions have been systematically removed. This is the whole objective of the variant graph model.

This is, of course, only a test program. The algorithm will eventually be added to NMerge and all this will happen behind the scenes in the multi-version wiki whenever you save.

Transpositions

2008-10-26T17:39:00.000-07:00

Transpositions are undeniably part of real world texts, and must be included in any practical solution to the technical problems of how to represent overlapping structures in digital texts. The MVD or variant graph model described on this website includes transpositions, but until now there has been no way to calculate them automatically.

Transpositions can't be supported in any markup scheme. In principal, any section of the document can be transposed, not only small bits of text. This means that a feature like the ‘copyof’ attribute (Smith, 1999), if used to record transpositions, would have to allow any element to be contained in any other element – thus destroying the whole idea of a document schema or DTD. Also, the transposed sections might not even contain well-formed markup, i.e. they might contain unmatched start or end-tags. So this approach doesn’t work.

The method I have been using until now is that suggested by Lopresti and Tomkins (1997): that one should do all the alignments, variants, deletions and insertions first, and then consider pairs of insertions/deletions as candidates for transposition afterwards. The problem is that, while this works well for two versions, it leads to problems caused by ‘contamination’ between multiple versions. You end up with the same word being recorded as a variant of itself in another version. What is left over after the completion of alignment is a lot of noise that does not form a suitable basis for the calculation of transpositions.

The French Connection

Alternatively, the approach adopted by Bourdaillet (2007) in his thesis is the exact opposite: do the transpositions (and alignments) first, then what is left over can be considered as candidate variants, insertions and deletions. His method is, however, still tied to just two versions, but there are some useful ideas that can be applied to the case of aligning N versions too.

One reason why I suspect he avoided trying to merge N versions into one document was that he didn't have a data structure to record it, but also because, until now, this has been considered to be too hard a problem. However, I believe that it is solvable, by combining his general approach with the MVD document structure. I will try to describe how it will work, by illustrating a simple example step by step.

The Case for Automatic Detection of Transpositions

You might think that automatically detecting transpositions would be a bad idea. If the author transposed some text in a holograph, this should be clear from the manuscript and can simply be encoded as such by the editor. But what about the case where there are several versions of the same work – perhaps redrafts of a single text or independent versions created by copying? Spotting such transpositions visually is very hard work. In these cases calculating transpositions is a good idea, and saves the editor a lot of trouble. Even in the holograph case, calculating transpositions can still be useful. So long as the computer gets it right we don't have to encode it manually (which saves work); only when it gets it wrong do we have to do anything.

Outline of the Proposed Method

Imagine you have already aligned N versions into an MVD. Now you want to add the N+1th version to the structure. (This is the standard inductive formulation: if we can prove that it works in this case, then it will always work.) The Longest-Common-Substring or LCS is the longest section of text shared by the MVD and the new version where successive characters are all the same. The basic algorithm uses this property to merge the entire graph. In essence the algorithm is simply:

Merge the variant graph and the new version where the LCS occurs.
Call the algorithm recursively on the two unaligned sections before and after the LCS.

The Challenge

As an example consider the three versions:

1. The quick brown fox jumps over the lazy dog.
2. The quick white rabbit jumps over the lazy dog.
3. The quick brown ferret leaps over the lazy dog.

Imagine we have already built an MVD out of this. Now we want to merge it with:

4. The white quick rabbit jumps over the dog.

There is a small transposition here: version 4 has ‘white quick’ instead of ‘quick white’ in version 2. Let’s see if the algorithm can detect it.

Following the Algorithm as it Works

We can add the fourth version to the graph very easily, by creating one big arc with the text of the version and attaching it to the start and end of the graph, like this:

This is already a valid variant graph, but it is full of redundancy. Every word of the new version can also be found in the ‘old’ graph. Apart from wasting storage, this redundancy fails to inform us of the relationship between the various parts of the new version and the rest of the document. The algorithm will correct this problem by gradually removing all of the copies.

The ‘longest-common-substring’ (or LCS) between the first three versions and the 4th one is ‘rabbit jumps over the’ from version 2, even though bits of that string are shared by other versions. What we do is align version 4 with the LCS, leaving two bits at either end non-aligned. The two bits are ‘The white quick’ and ‘dog.’:

Note that ‘rabbit jumps over the’ has now acquired version D. We then call the same routine (this is called recursion) on these two bits left over, but align them with the corresponding parts of the MVD that precede OR follow the LCS in version 2.

We now have two subgraphs containing arcs that definitely precede or follow the LCS. All the other arcs that are effectively parallel to the LCS are left in place but are not considered further. Now we have to try to align Arc 1 ‘The white quick’ with Graph 1 and Graph 2, and likewise align Arc 2 ‘dog.’ with graphs 1 & 2. Because we now have more than one subgraph we will have to consider transpositions. However, when we compare the LCS between Arc 2 and Graph 1 (nothing) with that calculated between Arc 2 and Graph 2 (‘dog.’) it is clear that no transpositions are possible. Instead, the best alignment is the direct one of ‘dog.’ between versions ABC and D:

We have no more D-text to align here so the process stops. The empty D-arc becomes a deletion in version D. On the other hand, there is still work to do on the left, in Graph 1. Here comparison between Graph 1 and Arc 1 suggests either ‘white’ or ‘quick’ as the LCS. We will choose ‘quick’ because it is more central:

This is still not quite right. The instance of ‘white’ on the left is clearly a transposition of the ‘white’ on the right. Again the merging of the LCS leads to two arcs and two graphs:

Calculation of the LCS between Arc 1 and Graph 2 yields ‘white’, shown here in bold. So we merge the LCS into the graph, except that this is a transposition, and so we must leave the text where it is and point to the target of the transposition. This leaves only one copy of ‘white’ in the graph, and another copy, shown in grey, that points to it.

We are still not finished. ‘The’ appears twice. So we need one further LCS calculation between the ‘The’ D-arc and the ‘The’ ABC-arc:

Now the two ‘The’s are merged, all that remains is to introduce an empty ABC-arc to indicate that ‘white’ only appears in that position in version D.

Taking Stock

We have been recursing into smaller and smaller portions of the graph. That does not mean that these portions or subgraphs are in any way detached from the rest of the graph. The other parts were simply omitted for clarity. Overall the graph now looks like this:

The text of version D has been fully assimilated. It has been aligned with ALL the versions of the graph, not just with the one that was most similar to the version we were trying to add. (This is what biologists do in their ‘progressive’ alignment technique, and they don't even attempt transpositions). The result is a much better alignment with a lot less redundancy. To add further versions to the MVD we simply repeat the above steps, with the new variant graph as our starting point.

Time Complexity

I believe this routine may eventually be O(N log N), that is as fast as the famous ‘quicksort’ routine of Hoare from 1961, which it resembles. At the moment it is somewhat slower because my current calculation of the LCS takes O(N²) time in the worst case. The LCS between two strings can be calculated in O(N) time according to Gusfield. But that requires the construction of two suffix trees using Ukkonen's 1995 algorithm. I have implemented that for the text of the new version but I can't generate a suffix tree for the variant graph because it is too difficult, and may not be possible in O(N) time. To calculate the LCS I just traverse the graph, looking for runs of matching characters in the new version which has been converted into a suffix tree using Ukkonen's algorithm. Overall I think this is O(N²). However, even as it now stands, the algorithm is still very fast because expected performance is usually much better than that.

References

D. Lopresti and A. Tomkins, ‘Block edit models for approximate string matching’, Theoretical Computer Science 1997, 181, 159–179.
J. Bourdaillet, Alignment textuel monolingue avec recherche de déplacements: algorithmique pour la critique génétique PhD Thesis, Université Paris 6 Pierre et Marie Curie, 2007.
C. Hoare, ‘Partition: Algorithm 63’, ‘Quicksort: Algorithm 64,’ Communications of the ACM 4(7), 321–322, 1961
D. Smith, ‘Textual Variation and Version Control in the TEI’ Computers and the Humanities, 33.1, 1999, 103–112.
E. Ukkonen, ‘On-line Construction of Suffix Trees’ Algorithmica 14 (1995), 249--260.
D. Gusfield Algorithms on Strings, Trees and Sequences, Cambridge: Cambridge University Press, 1997.

MVD paper accepted

2008-09-11T00:23:00.001-07:00

In case anyone was wondering if my theories have been independently verified, the International Journal of Human-Computer Studies has just accepted my paper that explains the core idea behind the MVD technology. This is a respected technical journal and I spared no detail in the paper, which is 16 pages long. There is a link at the bottom of the "What is an MVD?" page to the PDF I submitted.

Improvements to Alignment

2008-07-29T14:27:00.000-07:00

In preparation to publicly releasing the NMerge code I have been revising the alignment algorithm, as there were significant weaknesses in the naïve approach I had previously adopted. In cases like the Sibylline Gospel, there is a great deal of variation in a small space, and simply requiring the user to choose a base text for alignment doesn’t work very well. There seem to be a few reasons for this:

The user doesn't actually know to which existing version a new version should be aligned. It should be the task of the software to find this out.
There can't be a distinction, as I originally supposed, between updating an existing version and adding a new one. The newly revised version might resemble another version more than the one it came from. For example, we might change ‘the quick brown dog’ back to ‘the quick brown fox’. In the case of manuscript traditions like the Sibylline Gospel this happens all the time, because the versions aren’t a succession of edits, but a set of parallel alternatives. To avoid this problem I now automatically calculate the most similar version already in the MVD and then align with that.
When you add a new arc to the graph you need to look for identical paths not merely identical arcs that are already in that position. Now when the program finds an existing path with the same text, spanning the same two end-points, the new arc can be discarded and its version simply added to the path instead: In this simplified real-world example, the new D-version was aligned with version C, overall its most similar version. However, in this location the D-variant ‘milia hominum’ already exists in version A. When the program tried to add the D-Arc it realised that there was already an A-path with the same text and instead merely added the D-version to that path.

This is only the first stage of a series of improvements. Still to come:

Calling the alignment algorithm recursively to handle contamination, i.e. aligning to more than one base text. After aligning to the most similar version, any significant portions of the new version that didn't align can be realigned to the most similar version between the two endpoints of the unaligned section.
Calculating what is a variant of what, one use of which might be to generate a kind of apparatus criticus
Calculating transpositions. These can be done after the other alignments are complete: any leftover insertion/deletion pairs meeting certain criteria can be tested for equality, and the transposition carried out.

XML Awareness

While NMerge remains ignorant of XML, as it should, the public interface class now breaks up ‘words’ based on angle-brackets as well as white space. In addition I am contemplating moving this code and the class that XML-izes the differences between versions into a separate package. The latter functionality is needed by the wiki since a difference might occur in the middle of a tag, and the marker for this needs to be moved to the start of the next piece of real text, so it can be displayed.