Balisage Paper: Document similarity

Similarity and identity

Similarity comes in degrees. In everyday language, the word “similar” is often related to words like “identical” and “different”, for example when we say that two things are “so similar that they are in effect identical”, or when we say that they are so dissimilar that they are “completely different”.

The similarity measures presented later may inform us that documents A and B have a similarity score of 0.89, while documents A and C are only 0.67 similar, measured on a scale from 0 to 1. As values, both 0 and 1 may put some strain on our imagination. The value 1 would indicate complete similarity, and 0 complete dissimilarity.

It may be hard to think of examples of complete dissimilarity: For any two objects,^[2] there are always innumerable ways in which they may be similar. Any two randomly picked documents, for example, may be similar regarding language, vocabulary, compositional, linguistic or rhetorical structure, theme, genre, style, plot, narrative, dominant meter, and so on. When it comes to digital documents (or digital objects in general) they will at least be similar in that there is some specific byte or bit value that they do both contain -- or not contain.

When we consider digital objects, it may perhaps seem easier to think of examples of complete similarity. For example, two documents may consist of exactly the same sequence of words, or characters, or bytes, or even bits. But even then, they are similar only at a certain level of abstraction. Considered as physical representations of sequences of bits, bytes, characters etc., they will at least be different in that they occupy different portions of some physical data carrier.^[3]

We observed that similarity comes in degrees. Identity does not, at least not according to the standard philosophical concept of identity: the only way for two objects to be identical is for them to share all their properties. And if they do, they are not two objects at all, but one and the same object.

As formulated, this assumes that identity is a question of sharing of properties. Furthermore, it assumes not only the so-called indiscernibility of identicals (x=y ⇒ (Fx⇔Fy)), but also the identity of indiscernibles ((Fx⇔Fy) ⇒ x=y).^[4] If A and B are identical, “A” and “B” are just two names for the same object. So the discovery about the relation between the Evening Star and the Morning Star was not a discovery that two objects have all the same properties, but that they are the same object known under two different names.^[5]

Identity is an equivalence relation, i.e. it is reflexive, symmetric and transitive. Unlike other equivalence relations, however, identity is a relation that every object has to itself and to no other object. Some common views are that concrete objects are identical if and only if they occupy the same region of space and time, abstract objects if they share all their predicates, and sets if they have exactly the same members.

Like identity, the concept of similarity also has a prominent place in philosophy, and many or most attempts to explain what similarity is draw on the notion of identity. While identity is similarity in regard to all properties, one might say, similarity is identity with regard to some subset of properties.

Unfortunately, this way of defining identity and similarity leads to certain paradoxes.^[6] In particular, certain problems with the notion of similarity made Nelson Goodman, among others, formulate a critique [Goodman] which cast widespread doubt on the usefulness of the concept of similarity as an analytic tool.

A slightly modified concept of similarity (and identity) which arguably avoids these paradoxes, and at any rate is more useful for our purposes, is one according to which similarity is defined as similarity in some respect, where the respect in which some things are judged similar is always decided by context [Douven and Decock 2010]. In this conception of identity and similarity, both relations are intransitive and context-sensitive relations. (In addition to being, according to the authors, vague and “somehow” subjective.)

So, on this view, which is also the view on which our discussion is based, in order to make a meaningful statement that two objects are similar, or that they are similar to a particular extent, it is necessary always to make clear, referring to context, in respect to which property the similarity is supposed to hold.

What is a document?

If similarity is always and only to be understood as similarity with respect to some particular property or set of properties, and if the properties an object can possess depend on the nature of the object (as on most accounts they do), then any measure of document similarity necessarily reflects some underlying model of documents and their properties.

It is common to distinguish documents from texts by saying that a document is a concrete object instantiating an abstract object, the text. This may itself be seen as an account or statement of similarity: the many copies of a book are similar, and may for some purposes even be considered identical, because they are all instances of the same abstract object, i.e. the text.

Since abstractions can operate on different levels, i.e. be more or less inclusive, this way of accounting for similarities allows for example bibliographers to distinguish between different items, print-runs, editions, translations etc. of the same work.^[7]

The distinction can be (and has been) applied equally well to digital documents, though with a couple of noticeable differences. When the distinction is applied to traditional documents, questions are often raised concerning the status of the text, and how we can interact with abstract objects. When the distinction is applied to digital documents, questions tend to be raised concerning the status of the document side of the equation as well: The notion of a digital document may itself seem to involve abstraction.^[8]

In our discussion of document similarity, and also of transcription, we will employ a distinction similar to the one between abstract objects and their instantiations, namely the distinction between types and their tokens.

This distinction was introduced by Peirce, when he observed that even though there is only one word (type) “the” in English, there may be many tokens of that word on any page. [Peirce] If we loosely call any perceivable pattern on a page a “mark”, then some of those marks are tokens, namely those which instantiate types.

Each token instantiates one and only one type within a given repertoire of types, though tokens of one repertoire (e.g. the letters of the alphabet) may combine to form composite tokens of composite types (e.g. English words, sentences or documents). One and the same token may instantiate types within different type repertoires (such as “I” which may be a token both of the Latin letter I, the English first person singular pronoun, and a sentence).

There is no requirement that different tokens of the same type be perceptually similar. For example, type identical tokens of handwritten, typewritten, printed or digital documents may look very different. Nor is it always easy to identify features possessed by all tokens of a type. If there are any properties shared by all instances of lowercase G, for example, in all fonts and all standard forms of handwriting, for instance — other than being an instance of lowercase G —, they are not immediately obvious.

Two further questions demand brief discussion: what are documents made of? and how are those constituent parts organized to make up the document? We do not seek to settle these questions here, only to identify several different possible answers, each of which leads to a different model of documents, and thus to a different set of possible properties and a different concept of document similarity.

Transcription and t-similarity

A different approach to the question of document similarity might start from purely practical considerations. For centuries, documents were reproduced by transcription, with the implicit requirement that the transcript be similar to the exemplar in whatever respects were necessary for the purpose at hand. Historically, and up until our own time, one of the reasons for transcription has been to provide better access to unique manuscripts and rare books which could otherwise only be consulted by visiting the source library or archive, or by transportation of the document itself. In such cases, the transcript would be more accessible than the original; it might also be easier to read than the exemplar and thus provide access for a wider audience. Transcription was often the first step towards a printed edition of the source, which would thus have been made available to an even wider audience.

Transcription, as it is practised in textual criticism, often as part of the preparation of a documentary or critical edition of some body of documents, is sometimes described as the attempt to reproduce a particular document as faithfully as possible.^[10]

In scholarly contexts, transcripts were (and still are) important because for some purposes they can serve as substitutes for the exemplar, i.e. the original document. No transcript can preserve all properties of the exemplar. But in order to be usable as a substitute for the exemplar in any given context, the transcript must reproduce with complete accuracy the properties of the exemplar relevant to that context. With respect to any given context, therefore, transcription preserves similarity of documents with respect to some particular property or properties. For this reason, transcription seems well positioned to shed some light on the nature of document similarity with respect to a particular property.

Our earlier work on the logic of transcription has led us to believe that the essential property of transcripts is that as a general rule transcripts do not reorder, correct, amend, or normalize the text of the exemplar in any way. Generalizing or oversimplifying slightly, we might say that they do not add anything to or remove anything from the exemplar. Thought of in this way, transcription should be the archetype of document similarity. If a document, T, is a transcript of another document, E, then for the relevant purposes (and with respect to the relevant properties) T is as similar as possible to E.

One might perhaps have thought that digital text technology, with the availability of cheap, high quality facsimiles, would have made transcription obsolete. What can be a more faithful reproduction, and thus more similar, to the exemplar than a high-quality image? Indeed, digital facsimiles are of tremendous value to textual scholarship, and in many cases they can reduce the need for transcription.

However, a transcript is usually not primarily a reproduction of the visual appearance of a document, but of its textual content. Manuscripts with difficult handwriting and archaic or idiosyncratic spelling may be hard to read for non-specialists. A digital image cannot be analysed and searched in terms of linguistic criteria, but a transcription can. So one might say that digital facsimiles provide visual similarity, but do not necessarily provide the kinds of accessibility and processability we may desire. Achieving a form of similarity compatible with ease of reading, searching, and textual manipulation is a prime concern of transcription.^[11]

Optical character recognition comes closer to the aims of transcription. Today most printed and many hand-written documents can be OCR-read with considerable degree of accuracy, and many projects use OCR as part of the preparation of transcripts. It is hard to predict how close OCR-readers may come to human readers on all kinds of documents. As things stand today, they can at least often serve as efficient tools in preparing a transcription.

Transcription of difficult source material requires exceptional reading skills so far found only in human experts. And all transcription requires knowledge of the linguistic, historical and cultural context of the document in question. When visual evidence is inconclusive, as it often is, disagreements about what is the correct transcription of a particularly difficult passage in a manuscript are settled by arguments as to what is the most probable interpretation of the text in question.

We said above that a transcript T of an exemplar E is similar to E, in some very strict sense of similarity. A more precise and formal account of this relationship, which we may call t-similarity, can be given very briefly, in terms of the type-token distinction already introduced:

If T is a transcript of E, then T and E are tokens of the same type.^[12]

T-similarity is not designed to capture every aspect of the relation between T and E, but only the specific kind of similarity that must hold between them. Whereas transcription is an irreflexive, asymmetric, and intransitive relation, t-similarity is (under appropriate assumptions) an equivalence relation, i.e. it is reflexive, symmetric and transitive.^[13]

The brief, general definition of t-similarity just given conceals considerable underlying complexity. In all but trivial cases, a transcript instantiates a composite type, which may contain tokens of e.g. letters, words, sentences, quotations, cross-references, notes, and comments, some of which are sequentially and/or hierarchically ordered, others only partially ordered etc.

A somewhat more detailed formulation of t-similarity may be given as follows: If T and E are t-similar, then, with certain well-defined exceptions, the following rules apply:

We said earlier that typically, transcriptions do not reorder, correct, amend, or normalize the text of the exemplar in any way. The four rules just stated are a way of making this statement precise. Note that if transcription is taken (as it often is) to be the task of creating an artifact which is as similar as possible to its exemplar (at least, for the kinds of purposes for which transcription serves), and if these four rules capture the essential properties of transcription, then it follows that these four properties of reciprocity, purity, completeness, and type identity provide an explicit account of what it means for one document to be as similar as possible to another (again, within the limits imposed by the context within which transcription is relevant).

If the description of transcription just offered were entirely true, without qualification, we would need to say no more about transcription. In reality, of course, as could perhaps be expected, it is not true without qualifications.

Transcripts usually include material not found in the exemplar, such as page numbers and explanatory notes. Some transcripts omit material found in the exemplar: deletions, marginal remarks or insertions in a different hand. Different transcribers apply different criteria for type identity: some normalize spelling or expand abbreviations, some preserve allographic variation where others do not, while yet others preserve type identity not on letters but only on the word level. Sometimes such deviations from t-similarity are marked, often not.

Differences between transcripts may mean that the transcribers disagree about the content of the exemplar: when one transcript of the manuscripts of the nineteenth-century German writer Ludwig Büchner renders a word as Woyzeck and another as Wozzeck, it signals a disagreement about how to read Büchner's handwriting.^[14] However, differences between transcripts may also simply indicate that the two transcripts follow different transcription practices. If one transcript shows an abbreviation where the other shows a word fully spelled out, it does not mean the two transcribers disagree about what is on the page, only that they have reached different conclusions about how best to make the transcript useful. (Are we trying to support simple textual searches? Abbreviations may need to be expanded. Are we trying to make it possible for students of paleography to find occurrences of particular short forms? Abbreviations may need to be carefully recorded.) The presence, in cultural practice, of different transcription practices does not mean that there are no facts of the matter, or that transcripts cannot agree or disagree about those facts, or that transcripts cannot simply be right or wrong. But it does mean that understanding the logical implications of a given transcript requires a hermeneutic attempt to understand the transcription's practice.

Often transcripts come with descriptions of their conventions in the form of legends or statements of practice. Typically such statements describe deviations from what is assumed to be general norms of practice, or norms within an implied community of practitioners. Those general norms themselves are usually not stated explicitly, perhaps because they seem to be too obvious to allow mention without offence to the reader. What such statements of practice seem to describe, in addition to deviations from norms of the community, are exceptions from our account of t-similarity.

We believe, that is, that the three properties of t-similarity (purity, completeness, type identity) constitute a sort of “default” transcriptional implicature, a core of tacit assumptions underlying all transcription. Furthermore, we believe that deviations from this default implicature can usefully be described in a systematic way simply by making explicit a distinction often implicitly made, between “normal” and “special” tokens in transcript and exemplar.

Special transcript tokens are tokens which transcribe no token in the exemplar. Special exemplar tokens are tokens which are not transcribed by any token in the transcript. With suitably formulated rules for the interpretation of special transcript and exemplar tokens, a fully operationalized account of the t-similarity between transcript and exemplar can be given.

This allows us to judge, in the case of differences between transcripts of the same exemplar, whether they differ only because of differences in transcriptional policy, or because one makes statements on matters about which the other is silent, or whether they actually make different claims about the exemplar.

In what follows, where we present some formal methods for measuring similarity, we will argue that our theory of t-similarity may provide a rationale, or a common theoretical underpinning, for the various methods discussed. They may all be understood to measure, in some way or other, similarity between any pair of documents in terms of their t-similarity, typically by counting how many additions, omissions and substitutions are required to account for the difference between them. The different methods vary, however, in their underlying document model: they model documents as simple or composite tokens or of various types, organized as e.g. sequences, bags, sets or graphs.

Set- and bag-based similarity measures

Perhaps the simplest alternatives to the sequence measures just discussed are measures that ignore the fact that the items in question (characters, or in many application word types) form a sequence at all. If we pay attention only to which types appear in the sequence, ignoring the sequence in which they appear, then we can apply measures designed to quantify the similarity between sets.

Like Levenshtein distance, the measures discussed in this section can be thought of as counting exceptions to t-similarity (i.e. additions, omissions and substitutions). The difference is that the Levenshtein distance counts changes to sequences, and these measures count changes to sets or bags of types or tokens.

A widely used measure for set similarity is Jaccard similarity.^[20] It counts first the number of items that appear in both sets (the cardinality of their intersection), and then the number of items that appear in either or both (the cardinality of their union), and then divides the one by the other. In a formula: |A∩B| / |A∪B|.^[21]

An obvious refinement to this approach is to keep track not just of which character types appear in the two strings, but how often they are used: that is, to treat the string as a set of character occurrences, or as is more commonly said, a bag of characters.^[22] This may allow us to register the difference between strings in which a particular character occurs frequently from documents in which it is used only once.^[23]

Applied to our examples, the Jaccard set and bag measures produce the following results:^[24]

As was perhaps to be expected, Levenshtein similarity is more sensitive to the order of the characters in the strings than either of the Jaccard measures, but the Jaccard bag measure deviates less from Levenshtein than the set measure. It can also be observed that, with a small exception for the third and a big exception for the sixth pair, the Jaccard measures give the same relative ranking of similarities as the Levenshtein measure.

In addition to the Jaccard similarity, many other similarity measures can be applied to sets and bags. We list here all the ones we have considered in this work. In the following formulas, A and B are the two collections being compared, |A| is the cardinality of A, and min(X, Y) is the smaller of X and Y.

In the interest of completeness, we provide an overview of the values of these various similarity measures applied to the earlier examples of pairs of strings here (for comparison, the column gives Levenshtein similarity values):

Until now, we have been dealing with examples of similarity measures applied to strings analyzed as sequences, sets or bags of character types. It should be observed, therefore, that the various similarity measures may behave differently when applied to strings analyzed as sequences, sets, or bags of strings or word types.

Calculating sequence-based measures like the Levenshtein similarity requires time and space proportional to the product of the lengths of the two sequences. For documents of normal length, that can make sequence-based measures prohibitively slow. From a practical point of view, set- and bag-based measures are attractive because they are relatively straightforward to calculate. Perhaps surprisingly, however, simple measures of this kind can and do produce useful results, as will be illustrated below.

In any sufficiently long documents written in an alphabetic script, it is likely that every letter of the alphabet will at some point make an appearance, so that any two documents will have a very high set similarity measure on characters. And any pair of naturally occurring documents in the same language will normally share many high-frequency words, so that no two documents are likely to have a very low bag similarity measure on characters.

But if we take word types, not letter types, as the members of the two sets, we get a comparison of the vocabulary of the two documents, of the kind that has long been used by literary historians to compare and contrast authors or works and even to trace literary influence.

On the principle that a book about a given topic will use terms related to that topic frequently, and terms related to tangential topics only rarely, the idea of comparing documents using the bag of words model was early examined by developers of information retrieval systems.

But since the meaning of a document depends critically upon the meanings of its sentences, and the meaning of a sentence depends, in many languages (notably English, but not only in English), upon the order of its words, it may seem unlikely that a similarity measure which systematically throws away information about the order of words has any chance of producing useful results.

Sequence information without sequences: n-gram similarity measures

One way to make set- and bag-based measures at least partly sensitive to the sequence in which items appear is to model a document not as a set or bag of words or characters but as a set or bag of word or character n-grams.

To illustrate this approach, let us consider the sequence abcdefghij and three other sequences derived from it:

The Levenshtein and Jaccard measures for the three pairs are:

As may be seen, the Jaccard measure is unaffected by the permutations of the letters, and the Levenshtein measure is unaffected by ways in which the variants preserve portions of the original sequence.

If we consider not the set of letter types but the set of letter pairs in the strings, however, or the set of letter triples, or subsequences of length n (n-grams), we can get rather different results for these sequences:

As may be seen, including all the n-grams of length n or shorter will produce a higher similarity score than excluding the shorter n-grams. If there are any principled reasons for choosing a particular value for n, we do not know what they are; of course, larger values of n also lead to larger sets and slower computations.

Identifying genetically related documents

A simple use for document similarity measures, and one of those which first raised our interest in the topic, is that of finding genetically related texts or portions of texts.

Wittgenstein's Nachlass consists of roughly three million word tokens distributed over roughly 54,000 paragraphs. Many of the paragraphs are earlier versions or later revisions of other paragraphs. It is reasonable to expect that these paragraphs are similar in some particular respect, and it is a matter of some practical interest to find a similarity measure which will assign a high similarity score to pairs of paragraphs which are genetically related in this way, and lower similarity scores to paragraphs unrelated by origin or topic.

A number of methods have been employed in order to identify such pairs; the application of the bag of words model is one of the simplest of these. It has turned out to give surprisingly interesting results.

Consider the following three short paragraphs from Wittgenstein's Nachlass:

We expect any reader will note (even if they do not read German) that the first two paragraphs are similar, and the third is not very similar to either. And although they work on such a simple level, the Jaccard similarity measures are effective here: in the bag-of-words and set-of-words models, the Jaccard similarities are as given in the following table. Levenshtein distances measured on characters and on words (after stripping punctuation) are given for comparison. And indeed paragraph 2 is a re-working in Manuscript 104 (the so-called ‘Proto-Tractatus’ of paragraph 1, which appears in Manuscript 103; paragraph 3 is also from Manuscript 104, but occurs in a different context and is not directly related to paragraphs 1 and 2.^[37]

Calculating pairwise similarity for several paragraphs can produce useful visualizations, which (in our testing so far) produce plausible clusterings. If we plot each paragraph of testbed 2 as a point and place them on the Cartesian plane so that the similarity of any two paragraphs is at least roughly reflected in their distance, we get a display of their Jaccard similarity on sets (Js) like the following:

Figure 1: 16 paragraphs from Wittgenstein Nachlass, Jaccard measure on sets

Here, links connect documents with highest similarity (black for higher, gray for lower scores).^[38]

The Symmetric subsumption measure on bags (Hb) produces a similar clustering, as shown in the following diagram:^[39]

Figure 2: 16 paragraphs from Wittgenstein Nachlass, Symmetric subsumption measure on bags

The tests done so far indicate that indeed, the higher the score, the more likely that the paragraphs are revisions or earlier versions of each other. For testbed 2, all set- and bag-based measures, whether calculated on single words, bigrams or trigrams, give roughly the same results.

As may be seen, the set and bag method has turned out to have interesting results. How can that be?^[40]

An important part of the explanation is that we are comparing relatively short texts. The mean size of paragraphs in the Wittgenstein Nachlass is 58 tokens, and the mean number of types is 41. For any given set of 58 word tokens distributed over 41 word types, the number of ways in which they can be sequenced is astronomic, but the number of ways they can be sequenced into a meaningful sequence of words is severely limited.

But even on longer documents, the bag of words and set of words models are effective in identifying genetically related texts. In fact, somewhat to our surprise, also when applied to testbed 1 (the Wikipedia articles), almost all of the set- and bag-based similarity measures identify the same seven document pairs as most similar to each other, namely those seven document pairs which were genetically related.

Here, for example, is a plot of the Dice similarity measure on bags. As may be seen, the strongest similarities detected are those of genetically related documents: versions a, b, and c of the article on Gottlob Frege, versions a and b of the article on Niklas Luhmann, and versions a, b, and c of the article on Ludwig Wittgenstein. The articles on Niklaus Wirth, Donald Knuth, and other topics are all isolated.

Figure 3: 12 Wikpedia articles, Dice measure on bags

The Cosine similarity measure calculated on sets of bigrams produces essentially the same result:

Figure 4: 12 Wikpedia articles, Cosine measure on sets of bigrams

Identifying thematically related documents

Often document similarity is used for information retrieval: given an article on a particular topic and a request to find other articles on the same topic, similarity measures can be used to seek those articles, without any digressions through the difficult thickets of controlled subject vocabularies and the like, which is helpful since indexers and makers of controlled vocabularies find it difficult to keep up with the pace of publication in science and scholarship.

On testbed 3, our sample of 7 documents from the Balisage proceedings series, we ran a variety of tests to see if any would put the three papers indexed as being about DITA together. The results were not encouraging. On the assumption that inclusion of punctuation and case sensitivity and the most frequent word forms, while possibly important for identifying genetic similarity, might have the opposite effect for thematic similarity searches, we omitted punctuation, used cased-insensitive indexing and a stop-list containing all word forms occurring in 6 or 7 of the 7 documents. The results were still not very convincing. Here, for example, is the plot of the Jaccard similarity on bags:

Figure 5: 7 Balisage articles, Jaccard measure on bags

As may be seen, K1 and K2 are indicated as more similar to each other than to the other documents. But their assumed similarity to CU (the “DITA”-papers are CU, K1, and K2) is not reflected, and none of the documents are noticeably closer to each other than to the others.

Several measures identified the similarity between K1 and K2, but only two measures (specifically the Szymkiewicz-Simpson similarity on sets and bags) did assign the highest similarity measure to the two pairs K1-K2 and K2-CU, thus placing the three DITA documents in a cluster, as shown here for the Szymkiewicz-Simpson similarity on bags:

Figure 6: 7 Balisage articles, Szymkiewicz-Simpson measure on bags

Notice, however, that this is the only of the 10 set- and bag-based measures in which there is a visible gap in the range, with pairs of thematically similar documents above the gap and pairs of thematically dissimilar documents below it.^[41]

Identifying similar markup

In order to experiment with similarity measures on documents encoded in different markup vocabularies, we took three copies of each document in testbed 3 from the Balisage proceedings web site (the Balisage XML, the XHTML found in the epub version of the paper, and the HTML served to browsers) and translated them into six other formats using Libre Office (saving as Flat XML ODF document, docbook.xml, and Open Office XML) and Microsoft Word (saving as Word XML, Word 2003 XML document, and Strict Open XML document).

Applying the various methods for set- and bag-based measures directly on these variously marked up documents, however, did not provide useful results, as exemplified by this plot of the Jaccard similarity on bags:

Figure 7: 7 Balisage articles, each in 9 formats, Jaccard measure on bags

There are no useful clusters here, no groups of documents clearly closer to each other than to documents outside the group. Many of the adjacent pairs are indeed versions of the same paper, but not all, and the versions of a given paper do not form identifiable clusters.

It appears (but it is hard to think of good ways to test this hypothesis) that what has happened here is that the frequent occurrence of particular element type names (and namespace names?) has caused documents using the same XML vocabularies to be classed as similar, because of the high frequency of common items for things like paragraphs and titles. This does not completely swamp the effect of the text nodes, but it does obscure it.

In order to try to separate the effect of the documents' character data content from the effect of the markup itself, we created various derived forms from each XML document, filtering the documents in various ways to emphasis different aspects of the markup structure in the documents. In all of them, comments, processing instructions, teiheader, script and style elements as well as attribute-value pairs were filtered out. In the discussion below, we will refer to the various derived forms using the following labels:^[42]

In retrospect, the results were perhaps predictable; we confess nevertheless to having been surprised by them.

For example, the Szymkiewicz-Simpson similarity measure on sets of the p transform produces the following plot:

Figure 8: 7 Balisage articles, each in 9 formats, transform p, Szymkiewicz-Simpson measure on sets

The clusters correspond almost exactly to the nine differently marked up versions of the seven documents. Similar plots were produced by several of the set- and bag-based similarity measures using transforms p and e.

It is reassuring, in its way, to find that when similarity measures are applied to sets or bags of element type names, the measures successfully classify documents by the vocabulary used to mark them up. It is, however, not a particularly compelling use case for quantitative measurements of document similarity to use them to do what can be done easily by just examining the root elements and namespace declarations of the various documents.

Identifying structurally similar documents

Our final experiment involved a collection of 29 short documents and document fragments tagged in TEI, consisting of

Since all of the documents are using the same parent vocabulary, we hoped it might be possible to use markup-sensitive similarity measures to detect useful groupings of these documents. Jaccard similarity on bags on the e transform produces the following plot:

Figure 9: 29 TEI documents, transform e, Jaccard measure on bags

As can be seen, there are links between the verse and drama versions of Peer Gynt and Agrippine, the four songs form a separate cluster, the limericks seem to form a sub-cluster within the other poetry cluster, and the only prose text in the collection does not come out as similar to any of the other documents. (On the other hand, it is surprising that the same goes for the Horse3 versions of Peer Gynt and Agrippine.)

A Jaccard similarity on bags, with text nodes leveled and with n-grams of length 1 to 5 shows slightly different clustering: here, the versions of Peer Gynt cluster with each other, as do the versions of Agrippine (with a few strays), but again all the non-dramatic verse is in a single cluster.

Figure 10: 29 TEI documents, transform e, Jaccard measure on bags of 1-5-grams

A similar plot for the same model with text nodes not leveled clusters versions of the same or similar texts more tightly (as might be expected), without completely dissolving the markup-based clusters:

Figure 11: 29 TEI documents, transform m, Jaccard measure on bags of 1-5-grams