Mariage

I've added recent file handling for the application, which makes testing much easier because recent files are automatically reloaded. I've also finished a first pass through the output system, which now saves copies of the modified original XML files (including line ids); an XML version of the data structure; and a CSV version of it, suitable for loading into a spreadsheet program. I got hold of a nice pair of witnesses for a Wyatt poem, and I'm now using this for testing; they diverge quite a bit, so I was pleased to find that the app is actually doing its job, in the sense that for each line in each witness, it is fairly reliably identifying the "correct" corresponding line in the other witness, even when they're quite far apart. I'm now also able to run several recursions of the NCD adjustment algorithm, and the indications are that eventually you end up with a stable dataset (i.e. additional recursions don't change the data), but I haven't tested enough to know that yet. We also don't know whether multiple recursions make the results more or less reliable or useful; that remains to be seen.

Also tested on Wine, and everything works, but takes about 33% longer. Not a big deal really, although it would add up on a very large data set.

Next I have to make the recursion configurable, and have the record also keep the original raw score throughout the recursions; and I also want to enable it to do recursions until no further changes happen, if that ever arises.

Today I added a GUI for configuration of the steps in pre-processing lines (normalization, whitespace collapsing, lower-casing, etc.). Then I wrote the basic back-end process for parsing and processing the lines to create the massive list of raw and adjusted similarity metrics. It takes about 30 seconds to run through 100 vs 100 lines, which is 10,000 comparisons. Multiplying upwards, that would suggest that we can do our 5,000,000-comparison Sonnet texts in about five hours, but that doesn't include encoding and saving the results as XML, so I think we'll have to at least double that, even assuming that we don't run into memory issues. The app takes 15MB on startup, and runs up to 22MB when it's created its list of records (10,000); so we can assume it will take up something like 3.5GB to do its work; obviously this isn't going to happen in memory, so some disk paging will take place, but it's not too bad at all. It looks practical to achieve this in one day's dedicated running of a single Windows machine.

Next I need to tidy up the GUI, add Recent File handling, add the saving-to-disk code (both source files with their added ids, along with the huge comparison file, whose format I haven't figured out yet). But we might have something usable by a couple of weeks from now!

After some work on implementing the shifting of huge numbers into a HugeInt type, during which I learned some useful things, I went back to the original equation and realized that we'd misinterpreted it; it's not the compressed stream that's treated as a number, but the length of the compressed stream. That makes the whole calculation easier, and the numbers perfectly manageable in normal integer and extended float types.

Armed with this, I successfully implemented the NCD calculation in Delphi (yay), using ZLib. I tested this against the results from the CompLearn NCD, and the results match perfectly. The only oddity was the identity case, in which CompLearn consistently gives back exactly zero, whereas my code was giving back very low, but still above zero, numbers. After puzzling over this (I'm having a slow brain day), it struck me eventually that they're simply trapping for the identity case and returning zero. I can do that too, so now I do.

The actual calculation is only part of the battle. What we have, potentially, for (say) the Sonnet, is about five million calculations, and from these, we need to create adjusted values based on our context-based algorithm. This means we need small, fast structures to store the data. I elected to do this with a Delphi TList (fast and simple) containing records (fast, small, and easy to save and load from disk in binary format). I built the basic structures, using 20-char shortstrings for the id values -- this is not ideal (and not Unicode), but in practical terms it's perfectly sufficient and it's also fast and small.

Each record now has the id of its string from text 1 and the id from text 2. It also has the ids of the preceding string (=line, mostly) in text 1, and the successor in text 1; and the preceding and succeeding lines in text 2. The reason for needing these will be clear shortly.

When we come to calculate the adjusted value, we need to reference the NCD calculations from the preceding two lines, and the succeeding two lines. Since the original NCD can be ANY line from text 1 against ANY line from text 2, it will be rare that the preceding and succeeding records we need are even close to the one we're dealing with, let alone being next to it. To handle this, I've written lookup functions. The idea is that when the first NCD value is calcalated for any two lines, the calling code will surely know the ids of the preceding and succeeding lines in each text, because it's working through the lines in order, so it can store those ids in the record when it creates it. Later, those ids can be used to find the related pairing records preceding and following this one, so that the adjusted calculation can be done. That's all now implemented, although nothing has been tested as yet -- testing is for tomorrow.

All this is posited on the same list object holding all the records. This seemed impractical at first for a large set, but when I did the math it turned out that we'd be using about 750MB of memory for 5,000,000 comparisons; this will actually work OK, I think, as long as the machine isn't doing anything else (and it won't be, when we come to run the whole calculation for something like the Sonnet). If it does prove to be a problem, I think I might be able to find some method of paging the data out to disk, but I hope I don't have to; in-memory lookups will be way quicker.

I have a working proof-of-concept written in Delphi, which can invoke the ncd executable and retrieve its results through the use of temporary files, including a batch file. It's a bit hacky, but it could be the basis for a robust approach, especially if I build a complete file of all the lines in the second witness, and run each line of the first witness against it. The command line has -t [filename of multiple lines] -f [filename of single line to compare], and the results come back space-separated, so they're easy to parse. This is probably the best option; the hard thing is going to be providing useful feedback, but it would make sense to batch up the input lines into groups of 10, so we can keep showing incrementing progress, and allow for cancelling out of the procedure.

At the same time, I'm toying with the idea of implementing the algorithm itself natively in Delphi. The difficulty will be doing arithmetic on the huge numbers which are the compressed streams of data; I have no idea how to do that, so I've put out a couple of feelers and I'm letting the idea percolate in my brain a little. I found this very useful library, which I had to tweak a bit to get it to compile under Delphi 2009; it should give me the arithmetic support I need, and I think the rest is just a matter of figuring out how to get compressed streams into the byte arrays representing huge integers.

LW pointed out some minor display issues with the end part of the Amboise part 2, so I've reworked a little of the markup, and refined a little of the XSLT, to make things show up the way they're supposed to. I should go back and do the same for volume 1 too...

The markup in this work had been diverging from validity for a long time, so a whole stack of errors had accumulated, and the overall hierarchy was no longer easily discernible. I've worked through the whole text with the primary aim of fixing the hierarchy, and we now have a valid document. However, there are a number of things that still need to be looked at. I'm recording these here so that PG and I can sit down and work through them:

• Forme works are only occasionally marked up. We need to make sure that all page numbers, catchwords and signatures are caught and tagged as <fw>s.
• Stanza breaks are not usually marked; the run of lines continues unbroken, inside one <lg> tag, through what are clearly paragraph-style breaks. We need to identify all those breaks, and then close and re-open <lg> elements.
• Related to the above, there are some lines at the beginning of verse-paragraphs which are indented. These lines need rend="text-indent: 2em;" or whatever the measurement is.
• PG made a valiant attempt to use <salute>, <closure>, <sign> and <name> tags in the prefatory material (which is largely dedications, so has a lot of this kind of thing in it). However, the markup structures we're using make this difficult, and none of the existing formulations was valid; because of the need to render the code valid before we go any further, I've pulled out those tags and used plain <p> tags, with some <name> tags left in place, for those locations. However, the intent was correct, and we must revisit those areas of the text to devise and implement the correct formulations for them (and then handle them in the XSLT output).

The sad old operating system that is OSX has an annoying habit of littering hard drives with .DS_store files, and it even does this on network drives from other, non-OSX machines; these cause occasional stumbles in RSync operations, and also just get in the way and annoy the heck out of me. Finally I was bugged enough to find a solution. If you log in to the Mac with admin privileges and type this in a terminal:

defaults write com.apple.desktopservices DSDontWriteNetworkStores true

then restart the Mac, the behaviour appears to be prevented. I haven't found a way to stop the Mac from doing it on the local drive, though.

Now if only I could find a way to make the menu and dialog boxes for every application show up on the same monitor that the application happens to be running on...

I've begun writing the GUI for our pilot test, and I have two XML files happily loading and being displayed, and xml:id attributes being added to all the target elements (a requirement for the subsequent processing). Now I've started trying to figure out how to run the NCD process externally and get back its return value. The problem is that the return value is a float, and in Windows it seems to be impossible to get anything back from an external process except an integer (with GetExitCodeProcess). Presumably NCD is writing to StdOut. I did find this site which suggests a possible solution, which I'll look at tomorrow.

Spent a couple of hours with Stew working on the algorithm and the specific arithmetic we need to make our critical edition generator run. The basics are straightforward, but we obviously need an application that can do the work (which will take days or possibly even weeks), and we need to finalize the formats in which we choose to store the results. I don't think the correspondence values have much relevance for TEI, so a simple concise XML format will probably do.

After this, and some discussion with the project team, I started work on a Windows application to wrap the CompLearn engine, after determining that jclUnicode has the canonical normalization functionality I need. Delphi will be fast and user-friendly, as opposed to the other alternative (Java), and it's another opportunity to put some more work into the open-source units on which Transformer and IMT depend.

CC and I have been discussing the possibility of using the Sonnet de Courval material as a testing ground for automated critical-edition building. Our (currently very vague) plan is to start with the Satyre Ménipée, which exists in several editions. What we need to do initially is to find a plausible and usefully sophisticated algorithm for generating a similarity score between lines; I think this will need to be based on the kind of algorithms used (for instance) in the sciences, to measure similarities between protein structures, etc. We'd need to process every line in each text, first normalizing it, stripping punctuation and lower-casing it; then compare it to every other line in all the variants, computing a similarity score. The scores would then have to be re-processed to weight them, based on the similarities of the surrounding lines. At the end of this (very computationally-intensive) process, we would have scores for every line vs every other line (although it would probably be logical to discard scores below a certain level, to reduce the quantity of data). Based on this, we could generate a "critical edition" which allowed you to choose any text as a base text, and view the others as variants based on it.

The difficult part for me is the similarity metric we need to use. I've only just started my reading, but so far I haven't found anything in the humanities that makes sense. I'll need to do a lot of reading to get up to speed with this.

UPDATE: It looks to me that CompLearn is the answer to this. The arguments in the 2005 paper that describes it are very compelling, and my tests with small text files and single lines suggests that it works extremely well, in that it basically agrees with my own common sense view of how similar two strings are. It gives a score between 0 (identical) and (presumably) 1 for completely different -- although the most I've managed to score is 0.529412 with short strings in latin characters; comparing a short English string with a short Japanese string gives 0.789474. Interestingly, I get the same score whatever the English string is; the meaning of this is slighly beyond me at the moment, but it's been a long day...