The MVD File Format

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 '&lt;', '&gt;' and '&amp;'. 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

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

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.