Tree View

I added Tree view to the Ecdosis front toolset. Since a multi-version document (MVD) represents multiple versions of the same work it is pretty much like multiple variants of a genome. A phylogenetic tree is very close to a stemma describing the relationships between witnesses in a multiple-manuscript tradition. A genome is a sequence of nucleotides expressed in a four-letter vocabulary (GACT) but a single version of a historical document can also be expressed as a sequence of letters in the Unicode character set. Like genomes, historical texts are also subject to insertions, deletions, substitutions and transpositions. Hence the same tools used by geneticists ought to work for humanists also.

Distance matrices

The question arises how to generate a stemma or tree from a set of versions. Many of the phylogenetic approaches use a distance matrix: a table that describes how different each version is from every other version. Since in an MVD all the bits of text that are shared by versions and the bits that are different have already been computed, making a distance matrix is easy. The distance matrix for the four versions/layers of Abed Ben Haroun by Charles Harpur looks like this:

	A	B	C	D
A	0.0	0.05344	0.10688	0.11508
B	0.05344	0.0	0.13370	0.08087
C	0.10688	0.13370	0.0	0.19323
D	0.11508	0.08087	0.19323	0.0

Obviously the edit-distance between each version with itself is 0, which explains the diagonal of zeros in the table. The larger the number the more 'distant' it is from the other version. So here the biggest difference is between versions C and D. Of the other values only half are needed, since the distance between versions A and D is the same as the distance between D and A. But the format is traditional, and can be fed into a tree-drawing algorithm. There are many of these but one of the best distance-based methods is neighbour-join. The version I chose is a refinement of that technique published some years ago by Desper and Gascuel called 'FastME'. The tree-view is provided by the 'drawgram' program in the Phylip package, which allows different visualisations of rooted trees, since these represent most closely the humanist's stemma.

Stemmatic trees are useful even in cases where all the sources are written by the same person. What it shows in this case is which version derived from which – something that would require a lot of manual labour to discover. Often it is unclear in a collection of manuscript versions exactly which preceded which, but a phylogenetic tree makes this easy. Here's an example of Harpur's The Creek of the Four Graves. The h-numbers indicate physical versions and the internal layers are the bit added to the name introduced by a /.

How to make them

It is only really possible to make these trees from within Ecdosis. A back-end Java Web-service called Tree reads the MVD from the database and computes the distance matrix. It then builds the tree and streams it back to the Web-browser directly as an image. The controls at the bottom of the screen are contained in a JQuery module wrapped up as a Drupal module, which now form part of the Ecdosis-front collection. It is called 'tree'. There are some examples on the Charles Harpur site. Many of the 700 poems have more than one version so you should be able to select other poems from the Browse menu.

Multi-version documents and standoff properties

I have written two new papers for Digital Scholarship in the Humanities on 'standoff properties as an alternative to XML', and a second on 'Automating textual variation with multi-version documents'. Together they form the basis of a model of how I think historical documents should be encoded. The now 25 year old drive for 'standardisation' has led to something of a dead-end: people have begun to realise that it is not in fact possible to standardise the encoding of documents written on analogue media. Instead of reusability, sharability and durability, such 'standards' provide only a fertile ground for embedding private technology and interpretations into texts that cannot then be reused for any other purpose. 'Standard' encoding also fails to propose a usable solution to textual variation, which is the one feature that all historical documents share. Rather than attempting to create a new standard, this model reuses existing formats already in use worldwide: HTML, CSS, RDFa, Unicode. Although the model can be fully expressed in these formats its internal representation predisposes the data into a form that facilitates the things that digital humanists want to do with it, rather than throwing up barriers to its processing and reuse. What is needed is something simple that works. This is my attempt to explain how that can be achieved.

Fixing Search

The previous post explained that searching historical documents is fraught with problems that industrial search engines simply cannot handle. And the reason they can't is because they treat the underlying data as if it was a digitally-authored word-processor file, rather than a historical and manually written physical artefact.

The most serious of these problems is how to deal with versions – both internal and external. An internal version is created whenever an author or scribe changes something in the text, through deletion, replacement or insertion. After each round of corrections the author could, if he or she liked, write out the text in full as a clean draft. This kind of version hidden inside a document may be termed a layer. But when a new physical copy is produced, the differences between copies is termed external variation.

Some people seem to think that internal variation can be represented as a format: it is a crossing-out or insertion in the same document rather than a whole new text. Not so. Consider the last three lines of this poem:

Take out the markup and you will get:

Yet even that one subject is to one's prone to starts of wrong 
Of evil As ever So he shall sometimes prove insure: 
  in the clearest well thus fountain ever lies
A sediment—disturb it, and 'twill rise.

This is pure nonsense. The author never wrote that. It is not a text to be searched, viewed or compared, but that is what is being recorded when people treat internal variants as if they were formats, and that is what is being indexed by industrial search-engines.

So in order to search reliably the internal states of the document must first be separated out into coherent layers.

The scrapbook analogy

Let's say you have three copies of a novel. I'm thinking about a favourite sci-fi novel of mine, but there are plenty of other similar cases. The first one is a serialisation in a magazine. The second is the inaugural American edition, the third is the British edition, which was abridged by the publisher. I want to make one edition of all three. So I photocopy each page, and where the text is either unique in one copy or shared across several versions I cut out that portion and paste it into a scrapbook. As I do so I can preserve the order of the fragments so that each bit of each version precedes the next bit in the same version. There are printed books that do this already. Things like Michael Warren's 'Parallel King Lear', where the various quartos and the folio versions are laid down side by side so the reader can see the insertions, deletions and variants. But returning to the scrapbook idea, by copying each shared piece of text, however small (maybe just one letter) all duplication between the copies can be eliminated.

Well, nearly all. If a section was the same but transposed between two versions then the scrapbook idea won't work: the text will have to be copied from the 'before' to the 'after' location.

A digital scrapbook

If we do the same thing with three digital copies of the novel by finding all the bits in common electronically we can also eliminate the copies in the transposed text. The first time the transposed text occurs we record it as normal. The second or third times it is reused we simply refer to it, without copying it. So now our digital scrapbook is just one document, but it records all the text of the work from the three copies just once. By labelling each fragment with the set of versions it belongs to, say "1,2" or "2,3" or "1" or "2" etc. it will be possible to reconstruct the text of any copy by reading in order only those fragments that belong to it. So reading all the fragments labelled with a "2" or "1,2" or "2,3" etc will reproduce the text of version 2. And the same goes for the other versions.

And as explained above, internal variations are inherently no different from the external ones. They can be treated as separate editions of the text, as long as we can tease apart the internal versions and produce coherent copies from them. This is always possible, although the arguments are too long to include here.

Indexing a digital scrapbook

The benefits for search can only be realised if we can produce an index of this digital scrapbook, by treating it as just another kind of document. In a real world scenario some texts will be scrapbooks and some won't. We need one way to index them all uniformly. The scrapbook idea is cool, but it is so radical that it threatens to break industrial search engines. How can this be avoided?

The poetry example given above when represented as a digital scrapbook might look internally as four layers:

[1-4] Yet even [1,2] that one [2] 's [1] subject is [2] prone [1,2] to starts [1] Of evil [2] As ever [1-4] : in the clearest [3,4] he shall sometimes prove insure [3] So [1,2] well thus [3,4] fountain ever [1-4] lies [1-4] A sediment—disturb it, and 'twill rise.

The versions to which each fragment of text belong are represented here as some numbers in square-brackets before the fragment they refer to. But forgetting about that for now this 'document' can be treated like any other. The location of each word has a position that can be measured by counting characters from the start of the file. The position of 'subject' is 20, counting all the preceding characters of "Yet even ", "that one" and "'s ", without regard to the versions they belong to. This is a kind of global, cross-version position of each word. For example, the word "one's", in version 2, starts at position 14, which is the same as the word "one" in version 1. But so long as we have a position for each word in our index this causes no problem because we already know that they are two different words. All we need is some program that can read digital scrapbooks, which is no big deal.

Admittedly, the index will not record which versions "one" and "one's" belong to, but this can be deduced by reading the digital scrapbook at position 14. Following the fragments for "one's" reveals that this text is in version 2, whereas the word "one" (followed by a space) belongs to version 1.

So no reinvention of the wheel is needed to index a digital scrapbook, or an ordinary file, and the positions of words in both types of file can be stored in the same index.

Finding the text

Now we have our index it should be easy enough to find something in it. The index tells us in which documents a particular word can be found, and at what position(s) in the file. Any standard search engine could be used for this purpose, but in practice it is probably better to make your own, because of what comes after.

First the 'hits' have to be arranged into 'digests' which are just short summaries of the relevant bits of the source documents. To do this naturally requires the search engine to read the source documents again. So a search engine would have to be aware of digital scrapbooks. But that can be done, since it is just another format. Finally the hits have got to be displayed. That also requires knowledge of the digital scrapbook format, but the beauty is that a single hit in a single digital scrapbook will be displayed as one hit, not as 20 hits in 20 versions or layers. And the user can move around inside the scrapbook and read the text of any version and see how the hits propagate across the versions. Take a look for yourself.

Searching historical texts is broken

Searching is the mainstay of digital editions of historical texts. If nothing more, editors will usually supply readable transcriptions of the sources and an index-based search. Indeed, the fact that digital scholarly editions only ever had these features has been a complaint since the start of the century¹. Since then, generic XML publishing tools for historical texts like SADE² and TAPAS³ have scarcely moved beyond that model. So Search is something that everyone thinks can be easily added to their edition. But when we look "under the hood" we find that current search technology falls well short of what is needed.

Searching = Lucene

Just about the only search engine used in the digital humanities seems to be Lucene, and its various aliases Solr, Nutch and ElasticSearch. However, Lucene was never designed with transcriptions of historical texts in mind, and certainly not XML. What drove its design was the plain text document and forms used in a business context. It was first published in 1999, and probably written a bit before that. In other words it was effectively pre-XML. So Lucene was not based around the idea of searching document trees, but plain text documents.

Inverted indices

Like many search engines Lucene does not actually search text when you type in a query. Instead it searches a prepared index of words that tells it in which documents a particular search-term may be found, instead of which words are in the document. This is called an "inverted index". Since documents may be quite large the idea of "fields" was introduced to increase the precision of a search. Words would still be in the same document but they might belong to different sub-sections, so allowing the user to drill down and find the term, without knowing precisely where it actually was.

XML and HTML files are organised rather differently. Instead of fields, segments of text are arranged into an explicit hierarchy, each segment being assigned a name, which may be qualified by attributes. So we might describe a segment as being a "division" of type "chapter" to indicate a chapter. However, Lucene knows nothing about all this. It may be told that a particular word occurs inside a "field" called "division" but it doesn't know that the division is a chapter, or that it is part of a book called "Nostromo". In most cases knowing the "field" or element in which a search term occurs, such as "paragraph" or "line", will not prove very illuminating. We can't say "find all the quotations in letters" or some such hierarchical query, because Lucene does not understand hierarchies and does not even understand XML very well either. What it understands are documents and fields.

Non-linear text

You may think: so what? Text is the most important thing, and that is what Lucene retrieves. The problem is that digital scholarly editions use XML to structure the text in non-linear ways. Take the theoretical example: <l>The quick <del>red</del><add>brown</add> fox jumps over the lazy dog.</l>. Depending how the parser reads this document the Lucene indexer may or may not insert a space between "red" and "brown". But at best it will see "The quick red brown fox jumps over the lazy dog". If we query that nonsensical sentence then Lucene will retrieve it, but it is not in the text. The text is supposed to be "The quick red fox" or "The quick brown fox" but Lucene will not find either expression. Admittedly, a non-literal search will retrieve all documents in which the words "red", "fox" and "brown", "fox" occur, but that's not the same thing. And for longer variants the text simply becomes incomprehensible.

Take this real-world example from a single line of a poem in a manuscript by Charles Harpur:

<l>Yet even <app><rdg>that one <del>subject is to</del> starts</rdg> 
<rdg><del>that one's prone to starts of wrong</del></rdg> 
<rdg><emph>he</emph> shall sometimes prove insure:</rdg></app></l> 

Lucene will see the nonsensical:

Yet even that one subject is to starts 
that one’s prone to starts of wrong 
he shall sometimes prove insure: 

as the text of this line. Not only will the word "starts" be retrieved in two separate hits, but the reader will be highly puzzled by what Lucene returns when it formats and displays the result.

Hyphenation

Unfortunately, this is not the end of it. When we transcribe historical documents it is vital to record the line-breaks of the original source. If we don't do that we can't reference the "chapter and verse" of a passage. We can't display the text with line-breaks next to its page-facsimile, and we can't synchro-scroll with any precision two versions of the same work side by side. If we leave out line-breaks we may as well abandon all precision in the transcription altogether.

But line-breaks often occur in the middle of words. We may transcribe "quick-", "ly" on separate lines, but Lucene will see this as two words. OK, so what if we just join up all hyphens to the text of the next line when indexing? That's hard because in XML line-breaks will be marked by tags like </l>, and other tags representing page-breaks may intervene. But let's say that somehow we manage it. Then what about "sugar-cane" or "dog-house" or "avant-garde"? Hyphenated words may equally be split over a line. And what about authors who insist on hyphenating words that need not be, such as Conrad's use of "thunder-head"? The problem is, most technicians don't give a damn about these subtleties, and will index whatever is in the files, because it is too much work to fix the problem properly. But humanists who are interested in texts are pedantic as to the correctness of a text to the last full stop. And yet, when they search their magnum digital opus they seem content to find that the most common two-letter word is "ly".

OK, so how do we fix it?

Lucene can be forced to retrieve the exact location of words in a document, but this makes the indices enormous.

It is possible to write a program to tease apart the internal structures of an XML document so that we can separately index "The quick brown fox" and "The quick red fox", but then Lucene will return one hit for each copy of the non-different text we make, like "The quick". Such a program is also far harder to write than is generally supposed, and would only work for the specific set of XML texts it was designed for.⁴

With XML there is no nice way around the hyphenation problem.

"OK, so what's your solution?" I hear you ask. For that, I'm afraid, you'll have to wait for the next instalment of this blog.

References

¹ Peter Robinson, 2003. "Where we are with Electronic Scholarly Editions, and where we want to be" Jahrbuch für Computerphilologie 5.

² SADE Publish Tool, 2015.

³ Julia Flanders and Scott Hamlin, 2013. "TAPAS: Building a TEI Publishing and Repository Service", JTEI 5.

⁴ Desmond Schmidt, 2014. "Towards an Interoperable Digital Scholarly Edition" JTEI 7, Section 5.

Why digital editions lack longevity (and how to fix it)

If there is one point on which all theorists agree it is that the software component of the digital scholarly edition is ephemeral:

'compared to books -- in particular, compared to scholarly editions -- software lives out its life in but the twinkling of an eye.'¹

'computer related technologies are hardly renowned for their longevity'²;

'... the price seems to be the interface: while the digital scholarly community has developed meaningful ways to support the longevity of the dataset, the same cannot be said about interfaces.'³

'how can the continued—and useful—existence of a system or tool be guaranteed, or at least facilitated, once a project's funding has been spent?'⁴.

The client-server model

But it may be a mistake to point the finger of blame so quickly at the graphical user interface, when the real culprit is the ubiquitous client-server model, in which the function of the application is split between the web-server and the browser.

In Web 1.0 almost all the action happened on the server. Since rendering in the client was unreliable it was considered virtuous to actually create Web pages on the server and then send them down to the client. Users were even told to 'turn off Javascript' for safety reasons, because interactivity was just a superfluous enhancement.

Client-server model: Web 1.0

With the arrival of consistent cross-browser functionality in Web 2.0 developers began to build much more interactivity into the browser. Now the user could participate in the creation of Web content. Facebook, blogs, Twitter and all the rest happened. Man went mobile, but the humble Web application, the client-server model wasn't all that deeply changed. The same tools were available to developers as in Web 1.0 – and they did the same things with it: building secret functionality into the server component, and leaving the interactive stuff for the browser and UI-guys to figure out. It was kind of a 50-50 division of labour.

Client-server model: Web 2.0

So, what's this got to do with digital editions?

A lot, as it turns out. The Web is under constant attack from hackers trying to gain control of servers. As a result, the server software is constantly updated. It is practically guaranteed that, once a digital edition built for the Web is finished, that it will fail within 6 months to two years counting from the moment of project end. Digital humanists get money in grants. And when the grant money runs out, as the guys above say, there is no one left to maintain it. Then 'poof!' goes the digital edition. It drops off the Net, the code breaks and all that is left are the source data files that actually need that software to process them. And only the authors have access to them. So they are nearly as useless as the software.

But the problem here is not the lack of longevity in the GUI software. Because that is all based on HTML, CSS and Javascript. To my knowledge none of those technologies has yet undergone a change that is not backwards-compatible. The original web-page made by Tim Berners Lee still works perfectly in modern browsers with a zillion more features than what he had back then. Extrapolating from that, a digital edition made today with just those technologies and no others could be expected to live on more or less indefinitely. Why? Because those technologies are too big to fail. There are around 40 billion web pages on the Internet, and a sizeable portion of them would break if there was any change to the underlying technology that was not backwards-compatible. So as they say, 'it ain't gonna happen'.

On the other hand, server software changes in incompatible ways all the time. My old Java programs don't work any more because 'deprecated' features are eventually withdrawn. But the worst problems concern security changes which are automatically applied to the server operating system by administrators. Failure to keep those security measures up to date will result, sooner or later, in the hacking of your digital edition. So it will die if you do not constantly spend money on it. Corporate users love the client-server model because it allows them to keep one step ahead of the competition. The constant updates delight them, and they have permanent staff to carry them out. But we don't. And as digital humanists we are left with their tools to do our work.

What can be done about it?

The answer lies in moving all the functionality into the client. With open source software there is no need to hide anything on the server. So we rewrite all the server code in Javascript, move it to the client, and turn the server into a dumb service that just gets and saves data. This gives us three advantages: archivability, interoperability and durability.

Client-server model: Web 4?.0

For archiving, digital editions can be taken off the server and saved as archives that work directly off the file-system (on a USB stick or DVD etc.), without the need for a Web-server, but only for reading. Editions could also be shared or sent to other locations. We can say: 'Here's my edition: tell me what you think of it.' That is like giving someone a copy of your book to read: you won't and can't change it.

But since these editions use only globally interoperable data formats we and our friends can also collaborate in creating and updating them through a master copy on a server. We can update their editions in our browsers and they can update ours in theirs, and everything will work perfectly. We can even annotate and understand the semantic content of an edition because the formats it uses are standard, and the tools to do that already exist.

On durability, if we leave it on the server it should run more or less indefinitely because there is almost nothing to hack, and nothing to break. It would be an interesting experiment to make one and see how long it lasts, adding a clock on the website to show how many years, months, days it has been running correctly without modification.

How to archive a digital edition

If we want to archive our edition we must first save the website's static content, by following its internal links, just as you do when you save a web-page as 'complete' in your browser. But to preserve the dynamic pages is harder. We can easily save the database files, but all the server software will have to be converted into a form that will run in the browser. This is hard for XML-based editions because almost all XML software only works on the server: eXistDB, XQuery, Cocoon, XSLT, Lucene (and Solr, Elastic search). Since we didn't write it we don't control it, so converting it to run in the browser is practically impossible. Which is another reason not to use XML. But with our XML-free approach, by writing all the software we need for the edition ourselves, this becomes absolutely achievable. Since our server code is written in Java it is not too hard to convert it all into Javascript. And we can also use that new client software to run the live, updatable server version of the edition.

However, I don't expect people will rush out to do this because they all love XML too much. But they also don't have any answer to the longevity problem, which is far and away the biggest problem we face. Solve that, and digital editions that last nearly as long as books can become a reality.

References

¹ C. Michael Sperberg-McQueen, 1994. “Textual Criticism and the Text Encoding Initiative.” Proceedings of MLA '94, San Diego.

² Lou Burnard, 2013. "The Evolution of the Text Encoding Initiative: From Research Project to Research Infrastructure" JTEI 5.

³ Elena Pierazzo, 2014. Digital Scholarly Editing: Theories, Models and Methods, p.15.

⁴ Mark Hedges, Heike Neuroth, Kathleen M. Smith, Tobias Blanke, Laurent Romary, Marc Küster and Malcolm Illingworth, 2013. "TextGrid, TEXTvre, and DARIAH: Sustainability of Infrastructures for Textual Scholarship" JTEI 5.

TILT is making good progress

Check out the TILT blog. You can also follow us on Twitter @bltilt.

nmergec: a better way to collate and merge variant texts

The original idea of multi-version documents (MVDs) in 2009 was intended to address a common problem when editing cultural heritage texts: often the source documents are not cleanly reproduced texts that only exist in one version. In reality most historical documents exist in multiple drafts, have internal corrections, or are published as a set of editions or manuscript copies. An MVD is designed to gather all this information into a single digital bundle that can be commented on, or displayed in a variety of ways, because its structure mimics that of the documents it represents.

The basic principle of an MVD is that text occurring multiple times is only represented once, whereas the generally accepted method is to transcribe each physical document representing a work as a separate digital file, and to record internal variations within each document via markup. But this raises three serious difficulties:

1. Markup was originally designed to represent formats as applied to linear text. Using it to describe non-linear text, as found in internal variations, leads to a conundrum: how can markup be used to describe changes in formats or textual structure through variation, when markup is already used to describe those very features? For example, two paragraphs joined up by an editorial stroke, or a cancelled format. Markup can't describe itself.
2. There is a lot of redundancy between the versions represented as separate documents. If each of 20 versions has the same text at the same location, then why record it 20 times? And every time you copy or edit that piece of text you have to make sure it is the same throughout the 20 copies. This makes a lot of work for no reason. Computers are supposed to reduce work, not increase it.
3. Comparison and annotation of the multiple files creates a logistical problem: each time two texts are compared requires the repetition of a costly computation, whose result is the same each time. Comparing two documents with internal versions is practically impossible, unless you throw away the internal variation, in which case why record it in the first place? And to annotate a piece of text shared between versions the same annotation has to be applied to each copy separately.

There has to be a better way to reorganise the underlying data of a work so that the information structure facilitates the kinds of operations the user wishes to perform upon it. This is the motivation behind the MVD.

Variant graphs

The basic idea of the MVD is the variant graph. Instead of representing text as a linear stream of characters it represents it as a branching stream that diverges or merges as required. Consider this short segment of Charles Harpur's Social Charity, MS C376 (and this is just one of five realisations of this poem):

In this one manuscript one can discern five layers:

Yet even that one subject is to starts
Of evil: in the clearest well thus lies

Yet even that one's prone to starts of wrong
As ever: in the clearest well their lies

Yet even he shall sometimes prove insure:
So: in the clearest fountain their lies

Yet even he shall sometimes prove insure:
So: in the clearest fountain there lies

Yet even he shall sometimes prove insure:
As in the clearest fountain ever lies

The variant graph of all the above looks like this:

This covers the text from "Yet even" to "in the clearest", which are shared by all five versions. Note that the resolution of this variant graph is the character. Although for some uses a word-granularity is better, for side-by-side display the character-level granularity is superior. It doesn't leave the user guessing as to exactly what is different in any two versions. Also, if desired, it is possible to increase granularity to word-level, but if you start from word-level it is harder to descend to character level.

It is important to realise that this is an internal data structure of a program written out to explain how it works, not a display format. Its purpose is to increase efficiency by removing redundancy, which it clearly does. Even better from the efficiency point of view the above complex graph with all its nodes and arcs can be reduced to a simple list of textual fragments belonging to versions:

[1-5]Yet even
[3-5]he s
[1-2]t
[1-5]ha
[3-5]ll sometime
[1-2]t one
[2]'
[2-5]s pro
[3-5]ve in
[2]ne
[1]
[1,3-5]su
[3-5]re:\n
[4]
[3,5]So
[1]bject is
[1-2] to starts
[2] of wrong
[1]
[1-2]\n
[2,4]As
[4]
[2]
[1]Of
[1-2] ev
[2]er
[1]il
[1-3,5]:
[1-5] in the clearest

THIS is what an MVD is, not the graph as such, although this is also a graph, just expressed differently. The list can be converted back into the graph by following three simple rules:

1. Forced: if one fragment's versions intersect with the versions of the following fragment, then they define a node in the graph, to which the first and the second fragments attach as incoming and outgoing arcs respectively. For example, "to starts" (versions 1,2) intersects with "of wrong" (version 2). In the graph above this corresponds to a node between these two arcs.
2. Overhang: If a fragment is not attached as outgoing to the preceding fragment by the forced rule, it attaches to the last fragment with which it intersects. For example, "bject is" (version 1) attaches as outgoing to the same node as the earlier "su" (versions 1,3-5), forming the words "subject is".
3. Reverse overhang: All fragments not attached as incoming by rule 1 attach to the node of the next fragment in the list with which they intersect. So "ve in " (versions 3-5) attaches to "su" (versions a and 3-5) several fragments lower.

Any list of fragments so composed no matter how many versions it contains, no matter how complex, can be turned into a variant graph using these three rules. This is a lot simpler than the earlier nmerge program, which required five rules. The difference is that nmergec generates restricted variant graphs that have this property. So not any variant graph can be decomposed into such a list, only those generated by nmergec.

Some digital humanists have recognised that the variant graph is an intuitive way to conceive textual variation, but they only see it as a display format. But it is so much more than that. In fact the only way to represent complex cases of variation is to use the list of fragments, because in that way complexity does not increase as more versions are added. An MVD is thus best understood as an efficient data representation of the underlying content of a work.

Of course, getting the list of fragments in the first place is the problem. And that is what nmergec is designed to solve.

How nmergec works

Collation programs examine two versions at a time within a window of 50 words or a page. The first matching word they find between the two versions is taken as a position where the two texts are the same, and then the window is moved on by one word. Anything that did not match is a variant, insertion or deletion. The problem with this is that you can only see alignments within the window, and often they are outside it. And alignment word by word is incredibly error-prone. You can easily have transpositions, insertions or deletions that throw it out of alignment. That's why some early collation programs needed human input to help them.

CollateX, Juxta and Juxta Commons use comparison tools adapted from computer code comparison, which were designed to work at the granularity of lines, not words. They have been adapted to work with words, and as a result they are slow, and can only recognise small transpositions over short distances. The fact is, many transpositions occur on a much greater scale. Sometimes whole chapters in a novel are rearranged between drafts.For example, Wittgenstein rewrote his manuscripts by cutting them up into bits and rearranging them. We need something that is much more powerful and designed for the purpose.

MUM to the rescue!

A Maximal Unique Match or MUM is the longest unique common sequence of matching characters between two versions. It has to be unique because the longest match might occur several times, and aligning on one of those would probably be a mistake. Imagine a text with 20 spaces at the start of each line. Once the longest sections of actual text had been aligned those sequences of spaces would be the longest matches left. So it has to be unique. Nmergec uses the powerful Ukkonnen suffixtree algorithm to find MUMs, and it uses that to find the best point to align two texts. In the example above the MUM between versions 1 and 2 is marked in bold:

Yet even that one subject is to starts
Of evil: in the clearest well thus lies

Yet even that one's prone to starts of wrong
As ever: in the clearest well their lies

If we imagine that the first version is the MVD and the second one is the one we are adding to it then the leftovers after accepting this alignment will be "Yet even that one's prone to starts of wrong As ever" and "eir lies". Now all we have to do is to repeat the process on each of these fragments recursively until all that can be aligned is aligned. This is called a greedy algorithm: it gobbles up the biggest bits first, then progressively smaller sections. It's perhaps not perfect but it is undeniably fast, or as fast as these things get. Extending it to work on a full MVD with already many versions is not hard, we just choose a match the same way, but between the whole graph and the new version. I won't draw it because it will be too messy, but it is the same principle.

Transpositions

After the first alignment subsequent alignments don't always match with the "opposite" text. An example is:

I had written him a letter which I had, for want of better
Knowledge, sent to where I met him, years ago, down the Lachlan.

I had written him a letter which I had, for want of better
Knowledge, sent to where I met him down the Lachlan, years ago,

I've marked the transposition in bold. After aligning the longer text that surrounds it, nmergec eventually computes the alignment ", years ago". But it only fits on the other side of an already aligned section:

The big change in nmergec is that it treats transpositions in just the same way as direct alignments. The only difference is that transpositions are assessed based on length and distance between the two halves. If they are too far apart for a given length they are rejected. For example, the "transposition" of the word "is" between the beginning and end of a chapter is not a transposition at all, but the transpostion of "is" between "is there" and "there is" is a transposition. Transpositions are not copied, but the half in the new version "points to" the first half in the already existing MVD, like a child to its parent.

Rafting

As we sail down the rapids, bits of our former boat can be lashed together to form a raft that may save our lives. Similarly, matches between versions are often not exact. There may be a different type of quotation mark, or a small change, but the match basically goes on after that. The problem is, with suffixtrees or any kind of literal match, these small variations break up the matching process into chunks that, for example, mess up the assessment of whether something is a transposition or not. Also the greedy algorithm described above relies on choosing the biggest chunk first to get the best alignment between two texts, and this influences which bits are transposed and which bits get aligned "directly". So rafting is chaining together matches that have a short section of mismatch, but continue afterwards. Our Clancy of the Overflow example continues:

He was shearing sheep when I knew him, so I sent the letter to him, Just `on spec', addressed as follows, `Clancy, of The Overflow'.

He was shearing when I knew him, so I sent the letter to him, Just 'on spec', addressed as follows, 'Clancy, of The Overflow'.

"In this case the MUM is composed of three sections: 1) "when I knew him, so I sent the letter to him, Just ", 2) "on spec', addressed as follows, " and 3) "Clancy, of The Overflow'.". In-between there is variation in using back-quotes for opening quotes rather than the single quotes of version 2. So these three MUMs get assessed as one block, but are aligned as three separate blocks. So "matches" in the variant graph or MVD are still literal matches, with little variants in between. Up to two characters may mismatch in the MVD or in the new version and the match will be allowed to continue.

Working with any language

Collation programs are usually designed to work on texts in the language of their author. Most of them work OK with European languages that can be expressed in 8-bit characters, but fail on anything more complex. Nowadays everyone uses Unicode, which may convert many characters like accented letters, punctuation etc into multi-byte sequences in UTF-8, the most widespread encoding in modern computing. This plays havoc with programs designed only to work with 8-bit characters, so I decided from the start to make nmergec work with 16-bit Unicode. That way it could handle Chinese and Indian languages, ancient Greek, Russian, etc with ease. To do this I had to use ICU, a library maintained by IBM and now the embodiment of the Unicode standard in code form. ICU can convert just about any encoding into another. An MVD can be in any encoding you like, but internally nmergec uses 16-bit Unicode for all comparisons. Unless you are editing a text in an obscure dead language like ancient Phoenician you don't need more than 16 bits, and even then nmergec will continue to work because it uses UTF-16, so 32-bit characters will just get split into multi-character sequences. I think multi-language handling is very important and as far as I am aware no other merging/collation program supports it.

Immortal code

When Thucydides wrote his History of the Peloponesian War in the fourth century BC he said he was creating a "possession for ever", and it turned out to be true. But when writing computer programs that is a hard act to follow. Technologies come and go, and any program written today is likely to be useless in two years' time. I didn't want to keep coming back to my program just because some dimwit in some mega company thought it cool to change their programming language or tools just to roll out some new feature. So I wrote nmergec in C, one of the oldest and still the most popular programming language on the planet. Why? Who uses it any more? Surely C will soon die because it is so old. C is popular for several reasons, which happen also to be my reasons for choosing it:

C is incredibly stable. I have programs on my computer written in 1980 in C that still compile flawlessly. C is the language of Linux, OSX, iOS, BSD and Android, and all other flavours of UNIX, and variations of it are used to write mobile phone software and virtually all device drivers. C is going to be around for a very long time.

Also C is as fast as anything out there, and I needed speed. C is compiled directly into machine code, whereas almost all the new fancy languages like Node, Python, Haskell, Ruby, etc. are basically scripting languages that get compiled every time they run. That makes them about 100 to 1000 times slower than C. True, Java may be a bit faster in some test cases, but I have found that C is dramatically faster than Java when you have a complex program.

C allocates and frees memory as it goes. Java uses a garbage collector, which slows it down at crucial moments, and also makes it a memory-hog. You have to declare in advance how much memory you want to use in Java for your program to run, but in my case this is inconvenient because it depends on the size of the files. Since Java wastes so much memory this was the main reason it was limited to 70K files in the old nmerge.

Almost any language already in use can link to a C program. In Java you have JNI, and parts of Java itself already use C for speed. In PHP you can define an extension which is written in C. The same goes for most other languages. C is versatile, and will compile in any programming environment.

You may say that few people will be able to understand what I have written because it is complex and in a language not much used in the digital humanities. True, but those who are serious to extend or repair the tool will either make the effort or hire someone who has the skill. I have documented it well, it is carefully organised into manageable chunks, and it has a comprehensive test suite. I can do no more.

Size matters

Cultural heritage texts can be big things. Often alterations between versions can span entire works, such as Joseph Furphy's Such is life:

Notice how the author's original manuscript was revised by cutting out two entire chapters, which were replaced by two new ones in the printed book, but then the excised chapters were revised and published as two separate books. Variation occurs on this scale in real-world examples, not just at the microscopic level of individual sentences. Nmergec was designed to compare texts of several megabytes. I haven't tested the whole program yet on files that large, at this time of writing, but it is designed to do it. No other comparison program can handle variation over spans this large.

NMergeC is modular

One of the problems with the old nmerge was that it kept growing as more and more features had to be added. I needed a way to generate stemmas or trees showing the ancestors and children of versions. I also needed to produce an apparatus aligned by words, to compute the degree of difference between each version. So in nmergec I decided to break each of the program's functions into modules. The nmergec program itself just loads and saves MVDs, nothing more. mvd_add adds one version to an existing MVD. There are other modules, as yet incomplete, which do a great variety of tasks, but operate on MVDs. If you want nmergec to do something new just write a plugin. There is a simple application-programming interface to do this, though I haven't documented it yet. The following plugins are already defined or will soon be adapted from parts of the old nmerge:

• create an new empty MVD
• generate a table suitable for an apparatus
• compute the variants of a section of one version
• add a new version
• delete one version and its contents from an MVD
• list the versions of an MVD
• compute a phylogenetic tree using neighbour-join
• save an MVD as an archive of separate versions
• read one version
• read in an archive and convert to an MVD
• compare two versions
• search for a string
• rename an MVD
• replace an existing version with a new one

Keeping it simple (or the KISS principle)

One way to visualise an MVD is as a deck of cards. Each textual fragment corresponds to the value of a card, and the suit corresponds to the set of versions to which the fragment belongs. We also sort the deck into a particular order, like a card-shark cheating in some way. NMergec differs from nmerge in that it operates directly on the cards or fragments, and never builds an explicit graph. Most of the complexity of nmerge was caused by this simple difference. NMergec can be understood as a card-shuffling program, that splits cards into segments and shuffles them into a very particular order. The variant graph still exists, but it is implicit, and doing it this way is a lot simpler. For example, let's say you have 2,000 versions of a work. That is quite possible with New Testament texts. If you create a variant graph of even a short section of such a work it is incomprehensible. It is also, unsurprisingly, just as complex for the programmer to make sense of. But a list of fragments remains simple no matter how many versions are added to it, and never becomes a "huge hairy mess".

NB: "nmergec" is pronounced "en-merge-see", not "en-merge-ec"