Mariage

I've been looking again at how the jclCompression libraries work, and it's sent me back to some thinking about how I should be saving this data in the first place. It needs careful planning. There's a range of conditions we need to avoid and allow for which make the simple bundling of files into an archive inadequate. These are my decisions:

• We'll use a plain zip format. Compression/file size are not major issues, and zip is very portable.
• Since the two input files ("left" and "right" texts) might have the same filename (being taken from different locations on a disk, but named identically), we'll need to store some info about them which specifies exactly where they came from. This means we can't zip them with their original names, so we might as well zip them with "left.xml" and "right.xml".
• Other files include similarities.xml (the current state of the similarities list), a putative combined file (described in a previous post, based on teiCorpus), and a metadata file.

There are two or three initial things I need to do before actually implementing a file save:

1. Rework the id-creation code so that it enforces uniqueness across the two files, not just within one file. This is necessary since we'll be creating a single corpus file incorporating the two documents. Perhaps we should think about the possibility of users creating multiple-document archives here, and try to create ids which are not only unique across two documents, but have more chance of being unique even when more files are added. However, the user can themselves enforce this right now by setting the id prefixes in the settings XML tab, so maybe we can just leave that to the user.
2. We need to figure out an appropriate metadata file format, which can be used to describe the contents of the archive. Dublin Core in RDF???
3. Figure out how to structure the corpus file, and create a routine for building it.

It's become clear that what we actually have here is a "project", and that we ought to be able to save all the data (source XML files, NCD values, lists of modified lines, current state of processing, settings in the main screen etc.) in one big file -- a compressed archive -- and reload it. I've begun creating the infrastructure to support this (the usual Modified variable, filename tracking, SaveChanges prompting etc.). I've got the New and Save stuff all written with the exception of the actual code which saves the file; this is going to be based on a TJclCompressionArchive object, which looks simple enough from the one demo that comes with it, but I don't know if it'll work out in the end. I would have used the open-source ZipMaster component, but it's currently uncompilable in Delphi 2009. I don't see why the JCL component won't do the job, though.

The task of confirming or rejecting proposed matches may be a long one -- in fact, in the case of our Sonnet data, it will be very long -- so we need to be able to save and reload the current state of the task. I've added a property called currItem which is set by the review window when it closes, and saved to disk as an attribute of the root <similarities> element in the data file.

Woke up with some good ideas about how to allow the user to vet the correspondences that have been found. At the end of the comparison and adjustment process, the matches are now sorted by similarity with the most similar first. Then the app pops up a new window with a list of the lines to be matched in two listboxes, and displays each match as highlights in the two list boxes, allowing the user to specify whether a match is a direct correspondence, and interesting parallel, or is completely unconnected. They can work through the entire set like that, or when they've done all the significant matches, they can stop. I've also added a feature so that you can double-click lines to select a match which is somewhere else in the list directly, and then specify that as a good match. Once a correspondence is made, its lines get a grey background, so you can see the remaining unmatched lines easily.

Next I think I need to do this:

• Allow the user to choose to discard all non-significant matches before saving (that would be all matches which are below a certain level, or more likely, those which are etNone in their equivalence field (meaning the user has not specified them as matches or interesting correspondences).
• Create a file format in which all this data can be saved and reloaded as a block. The obvious thing is a zip file containing all the input and output files. This would enable you to stop work on a set of correspondences, then start again later.
• Write save/load code for the file format.
• Add one additional file type to the output format: a collocation of the two documents as a <teiCorpus>, incorporating with all the match data.
• Write XSLT for the document above so that it can be displayed as a "critical edition" based off either of the two texts.
• Figure out if it's worth writing code to incorporate more than two texts, or whether the user should do that manually.

Found the JEDI jclCompression library has implementations of BZip2 and GZip, so I've added those as options, and also added an "Average of all 3" option. The results from each of these are quite different, but they agree from a relative point of view; ZLib is always highest, with GZip next, and BZip2 usually lowest, but they're equally good at distinguishing between texts. The differences are noticeable, and none of them now agree with the results from NCD on Linux, which is odd; LZip did in my earlier testing. However, there are now lots of options for calculating the results, which is useful, and we should be able to figure out what provides the best algorithm by producing good human-readable output based on the results. That's my next task.

Reworked the GUI to make room for more user controls, and added recursion options for the adjustment calculation, then rewrote the code to allow for controlled recursion with a breakout if no further changes are happening, and progress updates. Then we ran some tests. We can do 999 recursions on our test data without achieving stability, and the results are actually not good; there's a tendency to end up with a spurious mapping between the lines such that one strong correspondence in a block can cause the rest of the alignment to fall in with it. There must be a sweet spot at which you've maximized the returns from the contextual assessment, without allowing "strong" areas to take over their surrounding correspondences. We need to do more testing here to see whether there's actually any value in recursion or not.

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.