2.1. Paragraph split and merge

Two of the first paragraph edit actions we observed are split and merge. Authors usually split large paragraphs into smaller ones or merge several small paragraphs into a bigger one.

Figure 3 (Section one) shows a paragraph merge on the text processor. Its impact on JATS is represented in Figure 4 (sect. 1). Compared to text processors where this edit action is relatively straightforward and consists of adding or removing line breaks between text blocks, its impact on JATS is more complex. We observe a combination of U+(n-1)D, n being the initial number of the paragraphs to merge. The existing XML diff algorithms usually show this edit action as three or more edit actions: U+2D in the best case scenario or I+3D, while U is seen as a combination of D+I.

The split edit action is presented in Figure 3 (Section two) and is the opposite of merge. In Figure 4 (sect. 2), we can see the split edit impact on JATS, and the delta representation for this change is symmetrical and of similar complexity to that of merge.

Representing a split or merge edit action as a combination of a sequence of basic edit actions is not convenient for the human reader and requires a higher-level interpretation.

2.2. Text move

Another edit action we observed during the author revision rounds is the text move. Authors move parts of paragraphs from one location within the article to another. Figure 3 (Section three) shows the text move action made by the author on the text processor where part of a text labelled "m" was moved from the second to the first paragraph in Section 3. Figure 4, (sect. 3) shows the impact of this edit on JATS that appears as 2U in the best case scenario or as 2(D+I).

Again, representing a text move edit action as two paragraph updates is not convenient for the human reader and requires a higher-level interpretation.

2.3. Subsection upgrade/Section downgrade

Subsection upgrade is yet another edit action we observed during the author revision rounds. This edit action occurs when authors upgrade a subsection to a section. Each subsection/section is composed of one label, one title and the section body that is further composed of paragraphs, figures, etc. Figure 3 (Section four) shows a subsection upgrade made by the author in the text processor. This edit action is usually seen as a combination of label change, font increase and indent decrease. As JATS does not hold any layout information, the complexity of detecting such edits on JATS documents is higher, and multiple nodes are affected by the change, as we can observe in Figure 4 (sect 4.1 -> sect. 5). The entire Subsection 4.1 is removed and inserted as Section 5. Moreover, we also observe some induced changes in the following sections where their label and ID are automatically changed according to the section numbering plan. Within our example, the initial Section 5 is renumbered as Section 6. Within the current XML diff algorithms, comparing the two JATS files will result in a full D of Subsection 4.1 and a full I of Section 5, followed by an attribute and label change on the initial Section 5 becoming Section 6.

The downgrade edit action is the opposite of upgrade. Figure 3 (Section six) shows a section downgrade made by the author in the text processor. This edit action is seen as a combination of label change, font decrease and indent increase. Its impact on JATS—see Figure 4 (sect. 6.1)—is exactly the same as for an upgrade, but in the opposite direction.

Neither the subsection upgrade nor the section downgrade edit actions are well represented within the existing XML diff algorithms. Those edit actions are represented as sequences of delete–insert edit actions and are difficult to interpret from a human reader perspective.

2.4. Style edit

In Section 1, we described JATS as a structural text document with no layout information that only carries the article data and structure. However, JATS also holds textual styling that is an important piece of information in the article. The majority of the paragraphs within the article hold text styling information such as bold, italic and underline. Styling change is purely visual in the text processor—see Figure 3 (Section five -> Section six), where one part of the text was styled bold and another one italic and underlined. On the other hand, styling information is represented as node elements on JATS, and their change directly impacts the XML tree—see Figure 4 (sect. 5 -> sect. 6). Within our example, inserting a bold style around a text portion consists of inserting a new node that will wrap this text content, which adds another layer of complexity for the XML diff algorithms. Most of the existing XML diff algorithms will represent this change as a new node I containing the edited text portion and a U of the edited paragraph text node. This kind of delta output is, again, not easy for human readers and is hard to interpret as a style edit action made by the author.

2.5. Citable object reference edit

Another common element we can observe in paragraphs are citable object references. Authors usually cite bibliographies, figures, tables and other sections within the article. Those references appear as <xref> nodes in JATS and are visible in most paragraphs. In order to cite an object, its label and ID are used. Those auto-incremental values are assigned to each citable object and are dependent on its appearance in the citable objects list. A reference citation is seen as <xref ref-type="bibr" rid="B2-journal-xx-yyyyy">2</xref>, where "B2-journal-xx-yyyyy" represents the ID, and the number 2 represents the label. If the paragraph is changed from citing the bibliography B2-journal-xx-yyyyy to B3-journal-xx-yyyyy, both the ID and the label will be changed within the <xref> node. Those two properties make it difficult to track author edits on the citable objects list. Let us assume a scenario where there are five references that the author is using as the bibliography. If a new reference were to be added at position 2, the IDs and labels of all the following references would be incremented, i.e., the "B2-molecules-25-00430" would switch to "B3-molecules-25-00430", and so on. The same applies for their labels. This change would then also impact all the references those objects have within the article, where the <xref> from our previous example would change to <xref ref-type="bibr" rid="B3-journal-xx-yyyyy">3</xref>, and the same for the following references. Having those induced changes while adding or removing citable objects would result in them being represented in most XML diff tools, instead of a simple citable object I, as I+n(A+U) in the best case scenario, or I+n(D+I) if the A and U are seen as full <xref> D+I, n being the number of auto-incremented bibliographies.

This type of simple author edits creates a lot of noise in the delta output that needs to be detected and eliminated by the XML diff algorithm. Without any filtering, one reference I or D can reproduce hundreds of other edits within JATS due to the induced changes it generates.

3.1. XML diff base - JNDiff

Due to the high scoring of the JNDiff algorithm [13] in comparing JATS documents, we decided to ground our new edit pattern recognition using the core functionalities of JNDiff for "Level 1" XML edit detection. JNDiff has good performance and is highly reliable in respect of detecting differences between two XML documents. The logic of the algorithm is as follows: It first builds one virtual tree object per document; then, it detects inserts and deletes as basic/"Level 1" edit actions; finally, it tries to refine the detected "Level 1" differences and convert them to "Level 2". Each time a specific insert–delete sequence is turned to "Level 2" change, it is removed and replaced in the change list by its "Level 2" representation. Our new edit pattern detection will be added to the JNDiff refinement logic in order to recognise and represent them in the delta.

3.2. XML tree annotation

In order to represent the XML trees in the following edit pattern detection on JATS documents, we use the conventional labelled ordered tree model. As we always compare two JATS documents A and B—two XML trees—each node belonging to the document A is labelled $\alpha$ and the document B $\beta$. We assign to each node an identifier m for document A and p for document B. In addition to the identifier, the node depth regarding the tree represented by n for document A and q for document B is also added, resulting in the annotation $\alpha [m,n]$ for document A and $\beta [p,q]$ for document B.

As we can see in Figure 5 representing the XML tree of the document A, each node has a specific annotation. $\alpha [0,0]$ represents the article node, being the root node. $\alpha [0.0,1]$ and $\alpha [0.1,1]$ represent Section 1 and Section 2, respectively, Section 1 being the node number 0.0 at depth 1 and Section 2 the node number 0.1 at depth 1. Section titles and paragraphs are within depth 2 and have node numbers 0.0.0 to 0.1.1. Finally, text nodes are at depth 3 and have node numbers 0.0.1.0 and 0.1.1.0. On the left, we can observe shallow nodes, and on the right, deeper nodes.

Figure 5

Example of XML tree on document A using the conventional labelled ordered tree model α[m,n] and β[p,q], where m and p represent the node identifier and n and q the depth.

3.3. Text similarity vs. text equality

The existing XML diff algorithms use text equality while trying to match different edit actions. Taking the example of tree merge—see Figure 6, where the P1 and P2 paragraphs are merged into P3—the merge is detected only if the text in paragraph P3 is exactly the same as the sum of the texts in P1 and P2. This approach is suitable for data-centric XML documents where high edit precision is required. On the other hand, text-centric XML documents are prone to small textual edits where grammar and sentence rephrasing are common. It is then important to replace text equality checks with text similarity while evaluating "Level 2" changes. This way, the algorithm is more flexible and can detect "Level 2" changes even with small textual change interference represented in Figure 6 by the addition of "but the". All the following "Level 2" change patterns we present use text similarity with a threshold that we experimentally defined at 95%; however, this value can be changed for further fine tuning. Once the "Level 2" change pattern has been detected, and if the text node has a similarity different from 100%, the text updates have to be detected in the usual way regardless of the "Level 2" change.

Figure 6

Paragraphs P1 and P2 merged into P3 while a text change common to text-centric XML document was introduced, showing the benefits of text similarity over text equality use for "Level 2" change detection.

3.4. Order of the edit detection

The edit patterns detection order—See Figure 7—remains important as some "Level 2" edits are composed of a combination of "Level 1" or even "Level 2" edits. In the example whem two paragraphs are merged, seen as one paragraph delete ("Level 1") and one text update ("Level 2"), it is important to run the paragraph merge pattern detection before the tree delete and text update detection. Regarding the section upgrade, this edit pattern is composed of several tree moves and text updates, and it is thus important to run this pattern detection before tree move and text update. Following an empirical evaluation, we decided to choose the following "Level 2" edit pattern detection order:

Figure 7

Edit pattern detection order used as higher-level edits is usually composed of other "Level 1" or "Level 2" edits, which makes their detection order important.

3.5. Subsection upgrade/Section downgrade

As seen in Figure 4 (sect. 4 -> sect. 5), upgrading one subsection with x nodes into a section results in x(D+I) "Level 1" edits. Moreover, as the remaining section numberings will also change due to their auto-incremental nature, we observe additional y(A+D+I)) "Level 1" edits, y being the number of remaining sections following the upgrade: A for id; D+I for the title. In total, a simple section upgrade will result in x(D+I) + y(A+D+I) "Level 1" edits. Within our example, see Figure 8, upgrading Subsection 1.1 into Section 2 results in depth lowering on each of the upgraded section elements followed by the title and ID change.

Figure 8

Impact of subsection upgrade on JATS XML tree: we observe that the depth of the upgraded Subsection 1.1 is lowered by one, becoming, on the depth level, the same as their previous parent (Section one).

By applying the following mathematical formula on the lists of node changes detected between documents A and B, respectively annotated c$\alpha$ and c$\beta$, we can evaluate if the specific change pair fulfils the subsection upgrade condition:

The formula verifies whether the contents of Subsection 1.1 and Section 2 are similar, and in addition, whether the depth of Section 2 is lower than the depth of Subsection 1.1. Having this condition satisfied will result in a subsection upgrade detection. By running the formula on our example, the following scenario occurs: for each change detected in document B ($\beta [p,q]$), evaluate if the text content of $\beta [0.1,1]$ "title"+"cd" is similar to the text content of $\alpha [\mathrm{0.0.2},2]$ "title"+"cd". In addition, evaluate if the depth of the modified $\beta [0.1,1]$ element is lover than the depth of the $\alpha [\mathrm{0.0.2},2]$ element. As both conditions are satisfied, the tree upgrade pattern is recognised.

The delta output of such pattern detection is represented as one "Level 2" change named "upgrade", having two information elements: "upgrade_from" and "upgrade_to".

Downgrade is the opposite of upgrade, where it is enough to invert the depth comparison in order to adapt the upgrade formula to detect downgrade patters. Once a downgrade pattern has been detected, the delta output will contain one "Level 2" change named "downgrade", having two information elements: "downgrade_from" and "downgrade_to"

3.6. Paragraph merge and split

As seen in Figure 4 (sect. 1), merging x paragraphs into a unique paragraph will be seen as x+1 "Level 1" edits, composed of xD+I. Using the update "Level 2" edit, the number of edits observed is lowered to x, with (x-1)D+U. We propose here a new way of detecting tree merge. Within our example, see Figure 9, nodes $\alpha [\mathrm{0.0.2},2]$ and $\alpha [\mathrm{0.0.3},2]$ are merged with node $\alpha [\mathrm{0.0.1},2]$. Represented with "Level 1" changes, this edit pattern detection results in 3D ($\alpha [\mathrm{0.0.1},2]$ with content "ab", $\alpha [\mathrm{0.0.2},2]$ with content "cd" and $\alpha [\mathrm{0.0.3},2]$ with content "ef"), followed by I of $\beta [\mathrm{0.0.1},2]$ with content "abcdef".

Figure 9

Impact of paragraph merge on JATS XML tree: we observe that the text contents "cd" and "ef" from paragraphs 2 and 3 are merged with the text content "ab" of paragraph 1.

By applying the following mathematical formula on the lists of node changes detected between documents A and B, respectively annotated c$\alpha$ and c$\beta$, we can evaluate whether a specific node pair fulfils the tree merge condition, the merge being valid only if two or more nodes from c$\beta$ fulfil the tree merge condition:

This mathematical formula verifies for every node content on $\beta$ whether there are nodes on $\alpha$ whose content is subset $\beta$ node content and where both depths on $\beta$ and $\alpha$ are identical. By running the formula on our example from Figure 9, the following scenario occurs: for each change detected in document B $\beta [p,q]$, test if the mathematical condition is verified for a given node in document A ($\alpha [m,n]$); if so, the examined node is a merge candidate. The algorithm will test for a given node in document B $\beta [\mathrm{0.0.1},2]$ all nodes within the same depth in document A $\alpha [\mathrm{0.0.1},2]$, $\alpha [\mathrm{0.0.2},2]$ and $\alpha [\mathrm{0.0.3},2]$, with their respective text content "ab", "cd" and "ef". As their text contents are all contained in $\beta [\mathrm{0.0.1},2]$ "abcdef" and they all have the same depth 2, they will be added to the merge candidate pool. In the end, if there is more than one merge candidate in the pool, a "Level 2" tree merge edit is detected. The resulting delta using the merge pattern detection while merging n paragraphs into a unique paragraph will be seen as one "Level 2" edit, containing n-1 merge_from and one merge_to information element.

Split is the opposite of merge, where instead of evaluating whether the text content of changed $\alpha [m,n]$ nodes is contained by $\beta [p,q]$, we evaluate whether the text content $\beta [p,q]$ nodes are contained by $\alpha [m,n]$. While using the split edit pattern detection, splitting one into n paragraphs will be represented as one "Level 2" edit containing one split_from and n split_to information element.

3.7. Style edit

As seen in Figure 4 (sect. 5 -> sect. 6), styling information is seen as XML nodes on JATS. The most often observed styling elements are <b> for bold, <i> for italic, <sub> for subscript, <sup> for superscript and <u> for underline. Style edits have no narrative impact, and the paragraph textual structure remains the same. On the other hand, the JATS XML structure is heavily impacted by those styling nodes, which makes their change detection complex. Most of the existing XML diff algorithms have difficulties representing text changes in paragraphs containing styling elements. Having no impact on the narrative structure, one of the possible solutions we propose to deal with style edits is to separate styling and textual change detection on JATS. This is possible by converting style nodes to simple text using encryption (XML tags to text conversion). This way, the bold "hello" text is encrypted from initially <b>hello</b> to a pure text variant, for example, _|b|_hello_|/b|_. This simplifies a lot the detection of the styling changes as there is no need to operate with complex tree changes—everything is seen and treated as simple text.

In Figure 10, we can see an example where some parts of the paragraph 1 text content are styled. "a" is made bold, "b" is made italic and underlined and "c" remains unchanged. By observing the impact of this modification on JATS, we can observe that the node $\alpha [\mathrm{0.0.1},2]$ changes from having one child text node "abc" $\alpha [\mathrm{0.0.1.0},3]$ to six nodes: $\beta [\mathrm{0.0.1.0},3]$, $\beta [\mathrm{0.0.1.0.0},4]$, $\beta [\mathrm{0.0.1.1},3]$, $\beta [\mathrm{0.0.1.1.0},4]$, $\beta [\mathrm{0.0.1.1.0.0},5]$ and $\beta [\mathrm{0.0.1.2},3]$. By encrypting all those newly added styling elements to simple text, we retrieve only one text node for paragraph 1, which facilitates change detection.

Figure 10

Impact of styling addition on JATS XML tree: we observe that adding bold to one part of the text and italic + underline to another changes the XML tree structure, as each styling addition is seen as a new element added to the existing XML tree.

Once we have simple text nodes on both sides, we split them into two lists, $listOfTextA$ and $listOfTextB$, using the styling encrypted tags as separators. The two lists are then compared using the JAVA DiffUtils⁷ library that returns the $diffList$ containing two parameters: difference content and type. With the type having one of three values (insert, delete or change), we are able to find style insertions, deletions and updates. In our example, DiffUtils will return three style inserts: bold, italic and underline. Deletions are observed when styling is removed and edits when styling type or styled text portion change. An example can be demonstrated in Albert Einstein’s quote "Logic will get you from <b>A to Z</b>; imagination will get you everywhere" that is changed to "Logic will get you <b>from A to Z</b>; imagination will get you everywhere". Note the bold part change from <b>A to Z</b> to <b>from A to Z</b>. DiffUtils will return two differences in this example: the bold part content change with "from" added and the text part changed with "from" deleted. We interpret this change as a styling edit where the styled portion of text changed.

Using the described approach, jats-diff is able to detect three different style changes: "text–style–insert", "text–style–delete" and "text–style–update". "Text–style–update" is used for both style type changes and style content changes.

Using the styling "Level 2" pattern recognition in our previous example allows us to change the delta output from one D+6I to three text-style-insert. The change consumer can understand this way that there is only styling and no content changes applied by the author.

3.8. Text move

As seen in Figure 4 (sect. 3), moving text portions from one paragraph to another will result in four "Level 1" edit actions, 2(D+I). Making text moves within the document will be represented in a similar way to making real content changes, which does not represent real modification made by the author. Within our example (see Figure 11), text "c" from node $\alpha [\mathrm{0.0.2.0},3]$ has been moved to node $\alpha [\mathrm{0.0.1.0},3]$. There, we can observe two change pairs: $\alpha [\mathrm{0.0.1.0},3]$ - $\beta [\mathrm{0.0.1.0},3]$ and $\alpha [\mathrm{0.0.2.0},3]$ - $\beta [\mathrm{0.0.2.0},3]$.

Figure 11

Impact of text move on JATS XML: we observe that moving some text content from paragraph 2 to paragraph 1 has an impact on both nodes.

By applying the following mathematical formula for each of the detected change pairs between documents A and B, respectively annotated c$\alpha$ and c$\beta$, we can evaluate if two specific change pairs fulfil the text move condition:

The formula evaluates whether each of the change pair differences have common text between them. If true, then the text move pattern is detected. By running the formula on our example, the following scenario occurs: for each change pair between document A and B, $\alpha [m,n]$ and $\beta [m,n]$, evaluate whether there is another change pair, ${\alpha }^{\prime }[m,n]$ and ${\beta }^{\prime }[m,n]$, where the content difference between both change pairs is similar. This results in verifying whether $\beta [\mathrm{0.0.1.0},3]$.content–$\alpha [\mathrm{0.0.1.0},3]$.content is similar to or equals ${\alpha }^{\prime }[m,n]$.content–${\beta }^{\prime }[m,n]$ content. As both content differences will return "c", the text move condition is satisfied.

The delta output of such pattern detection is represented as one "Level 2" change named "text-move", having two information elements: "text-move_from" and "text-move_to".

3.9. Citable objects

As seen in Section 2.5, in addition to styling nodes, paragraphs are also composed of references used to cite citable objects available in the article. The most common citable objects are bibliographies, but we also observe figures, tables and sections. References are inserted as <xref> nodes containing the "ref-type" and "ID" as attributes and the citing reference label as text. The "ID" and the label are auto-incremental values dependent on the citable object appearance order; thus, inserting or removing a citable object automatically changes the remaining citable objects’ auto-incremental values. Those induced changes are not interesting for the human reader and should be ignored as they are not directly made by the author.

Figure 12 shows the impact of adding one additional bibliography $\beta [\mathrm{0.1.0},2]$ at position one in the bibliography list. This change will move the initial position one bibliography $\alpha [\mathrm{0.1.0},2]$ to position two $\beta [\mathrm{0.1.1},2]$, which implies that its label and ID auto-incremental numbering value will change from 1 to 2. This then has a direct impact on the xref node $\alpha [\mathrm{0.0.1.1},3]$ that will change to $\beta [\mathrm{0.0.1.1},3]$ with a different attribute "ID" and a different label, citing the previous Reference 1 that became Reference 2. This kind of induced change is not interesting for the human reader, for whom the only relevant information is the insertion of the new bibliography. We propose here a solution on how to ignore those non-relevant changes and only keep the relevant changes made by the author. The main idea is to first scan the citable objects list and detect insertions, deletions and the impact of those edits on their positions within the list. Citable object insertion will auto-increment and deletion will auto-decrement all following citable object IDs and labels, which will then impact all cited references within the paragraphs. A precise list containing the original and new citable object numbering values is then used to scan all cited references within the paragraphs and ignore the changes detected where the original numbering value is changed to the new value as an induced change. This way, only real cited reference changes are kept in the delta output, and the induced ones are ignored.

Figure 12

Impact of citable object insert on JATS XML tree: we observe that adding a new citable object (bibliography reference) in the references list will change the auto-incremental values (label and ID) of the following references, which directly impacts all (more...)

4.1. Text similarity index propagation

After evaluating different text diff algorithms, we decided to use the Jaccard index [21] that is calculated for every change node pair between document A and document B, regardless of whether the change is of "Level 1" or "Level 2". Once the similarity index is calculated for every change in the delta, those are propagated upwards in the XML tree by applying the following equation:

Figure 13 presents two JATS versions where node $\alpha [\mathrm{0.0.0.0},3]$ lost "b", representing half of its initial content, and node $\alpha [\mathrm{0.0.1.0},3]$ had textual 50% content changes on "d" that represent 50% of the entire text node content. The delta output will show in this example one text update per modified node $\alpha [\mathrm{0.0.0.0},3]$ and $\alpha [\mathrm{0.0.1.0},3]$.

Figure 13

Paragraph text modifications between two XML trees. Paragraphs 1 and 2 represent 25% each of the Section 1 content, while paragraph 3 represents the remaining 50%. We can observe that text element pairs "ab", "cd" and "efgh", respectively, on text nodes (more...)

Using our similarity calculation algorithm, we could deduce that text node $\alpha [\mathrm{0.0.0.0},3]$ has a similarity of 50% compared to its document B version node $\beta [\mathrm{0.0.1.0},3]$. Calculating the same for the $\alpha [\mathrm{0.0.1.0},3]$ and $\beta [\mathrm{0.0.1.0},3]$ nodes, we can deduce that the two text nodes have a similarity of 75% ("d" representing 50% of the entire text node, and modified by 50%). Once both similarities have been calculated, we can now propagate those upwards on the tree in order to measure the similarity between the two section trees $\alpha [0.0,1]$ and $\beta [0.0,1]$, both containing three paragraphs each. Here, you can find details on applying the previous formula to the Figure 13 example:

• N = 3 as Section 1 has three child nodes;
• n0 represents $\alpha [\mathrm{0.0.0},2]$; n1 represents $\alpha [\mathrm{0.0.1},2]$; n2 represents $\alpha [\mathrm{0.0.2},2]$;
• $S_{n0}$ = 0.5; $S_{n1}$ = 0.75; $S_{n2}$ = 1;
• $I_{n0}$ = 0.25; $I_{n1}$ = 0.25; $I_{n2}$ = 0.5.

The example previously provided in Figure 13 is rather simple for comprehension purposes, but the same mathematical formula can be applied to more complex cases where, for example, we can observe text moves, node moves, subsection upgrades, etc. as soon as we convert an xml subtree to simple text by concatenating their individual text nodes to a single text block.

4.2. Element lists and special objects similarity

We previously saw how to calculate text similarity and propagate this similarity upwards on the XML tree. Having the text similarity makes sense for paragraphs, subsections and sections; it is, however, rather useless for other types of XML subtrees that are presented as lists (authors, references, tables and figures). For those, it makes more sense to express the similarity in number of changed/unchanged elements (4/5 authors, or 28/30 references).

Figure 14 shows a modification to the last name of author 2. If we used the similarity propagation for the parent node "authors", we would observe a similarity percentage that is highly influenced by the length of the modified last name. For one-word last names, which are the most common, our two algorithms would return a similarity of 0%, although only one character has changed in the last name. To accentuate this problem even more, let us assume authors 1 and 3 have very short first and last names, and author 2 has a short first and a very long last name. The author 2 last name could, for example, be composed of 10 characters, while the other first and last names are composed of only 2 characters, meaning that regarding its size, the author 2 last name is of the same size as all the other author text nodes.

Figure 14

Paragraph text modifications between two XML trees. Paragraphs 1 and 2 represent 25% each of the Section 1 content, while paragraph 3 represents the remaining 50%. We can observe that text element pairs "ab", "cd" and "efgh", respectively, on text nodes (more...)

We can conclude that text similarity calculation for those special types of XML subtrees can be inappropriate as this is purely based on text content. In such cases, it is much better to use child element counters and represent their parent element similarity that way. For this concrete example, we would say that authors have a similarity of 2/3, as two authors are exactly the same, and one was modified. In order to have even a higher precision, we propose to use the following semantic information for such lists:

• Initial: number of child elements on document A;
• Final: number of child elements on document B;
• Modified: number of modified child elements;
• Deleted: number of deleted child elements;
• Inserted: number of inserted child elements.

As the new edit actions detection and the similarity index have been described, we will continue with the algorithm output description and provide some examples where we will analyse the algorithm delta outputs for the described edit actions.

5.0.1. Delta output XML

The following Document Type Definition (DTD) defines the structure of the delta output XML document. It represents both the "Level 1" and the "Level 2" edits that can be detected by jats-diff. We observed there 13 edit actions: Delete, Insert, Update Attribute, Upgrade, Downgrade, Merge, Split, Move, Text Style Insert, Delete and Update, Text Move and Text Update.

<!DOCTYPE jats-diff [
        <!ELEMENT jats-diff (delete|insert|update-attribute|upgrade
        |downgrade|merge|split|move|text-style-insert|text-style-delete|
        text-style-update|text-move|text-update)*>
        <!ELEMENT delete>
        <!ATTLIST delete
                nodenumberA #REQUIRED>
        <!ELEMENT insert>
        <!ATTLIST insert
                at #REQUIRED
                children #REQUIRED
                nodenumberB #REQUIRED
                pos #REQUIRED>
        <!ELEMENT update-attribute>
        <!ATTLIST update-attribute
                name #REQUIRED
                newvalue #REQUIRED
                nodenumberA #REQUIRED
                nodenumberB #REQUIRED
                oldvalue #REQUIRED
                op #REQUIRED>
        <!ELEMENT upgrade>
        <!ATTLIST upgrade
                at #IMPLIED
                nodecount #REQUIRED
                nodenumberA #IMPLIED
                nodenumberB #IMPLIED
                op #REQUIRED
                pos #IMPLIED>
        <!ELEMENT downgrade>
        <!ATTLIST downgrade
                at #IMPLIED
                nodecount #REQUIRED
                nodenumberA #IMPLIED
                nodenumberB #IMPLIED
                op #REQUIRED
                pos #IMPLIED>
        <!ELEMENT merge>
        <!ATTLIST merge
                at #IMPLIED
                direction #REQUIRED
                nodenumberA #IMPLIED
                nodenumberB #IMPLIED
                op #REQUIRED
                pos #IMPLIED>
        <!ELEMENT split>
        <!ATTLIST split
                at #IMPLIED
                direction #REQUIRED
                nodenumberA #IMPLIED
                nodenumberB #IMPLIED
                op #REQUIRED
                pos #IMPLIED>
        <!ELEMENT move>
        <!ATTLIST move
                at #IMPLIED
                direction #REQUIRED
                nodecount #REQUIRED
                nodenumberA #REQUIRED
                nodenumberB #REQUIRED
                op #REQUIRED
                pos #IMPLIED>
        <!ELEMENT text-style-insert>
        <!ATTLIST text-style-insert
                nodenumberB #REQUIRED
                op #REQUIRED
                pos #REQUIRED>
        <!ELEMENT text-style-delete>
        <!ATTLIST text-style-delete
                nodenumberA #REQUIRED
                op #REQUIRED
                pos #REQUIRED>
        <!ELEMENT text-style-update (bold|italic|underline|overline|sup|sub|
        monospace|preformat|named-content|sc|b|i|u)*>
        <!ATTLIST text-style-update
                nodenumberA #IMPLIED
                nodenumberB #IMPLIED
                op #REQUIRED
                pos #REQUIRED>
        <!ELEMENT move-text>
        <!ATTLIST move-text
                nodecount #REQUIRED
                nodenumberA #IMPLIED
                nodenumberB #IMPLIED
                op #REQUIRED
                text-position-from #IMPLIED
                text-position-to #IMPLIED>
        <!ELEMENT text-update>
        <!ATTLIST text-update
                length #REQUIRED
                nodenumberA #REQUIRED
                nodenumberB #REQUIRED
                op #REQUIRED
                pos #REQUIRED>
        ]>

For the previously observed edits, in Table 2, we can also see the attributes used to give additional information on the specific edit action. Those attributes allow the reader to identify the exact position of the change inside the original document A or the modified document B.

Table 2

Delta output edit action attributes

We will continue with providing the delta output for specific examples per edit action:

Insert: addition of a new keyword "test keyword"

    <insert at="373" nodecount="1" nodenumberB="388" pos="7">
        <kwd>test keyword</kwd>
    </insert>

Delete: removal of an existing keyword "river monitoring"

    <delete nodecount="2" nodenumberA="386">
        <kwd>river monitoring</kwd>
    </delete>

Attribute Update: section 6 ID change from "sec6" to "sec6dot1"

    <update-attribute name="id" newvalue="sec6dot1" 
	 nodenumberA="38" nodenumberB="36" oldvalue="sec6" 
	 op="change-attr"/>

Section Upgrade: Subsection 2.3 that is upgraded to Section 6. The upgrade operation is composed of two parts: upgrade_to and upgrade_from

    <upgrade at="388" nodecount="5" nodenumberB="601"  op="upgradedTo" pos="5">
        <sec id="sec6"/>
    </upgrade>
    <upgrade nodecount="4" nodenumberA="447" op="upgradedFrom">
        <sec id="sec2dot3"/>
    </upgrade>

Section Downgrade: Section 5 that is downgraded to Subsection 2.4. The downgrade edit representation is composed of two parts: downgrade_to and downgrade_from:

    <downgrade at="410" nodecount="89" nodenumberB="452" op="downgradedTo" pos="5">
        <sec id="sec2dot4"/>
    </downgrade>
    <downgrade nodecount="88" nodenumberA="517" op="downgradedFrom">
        <sec id="sec5"/>
    </downgrade>

Paragraph Merge: merge two paragraphs into one. The merge operation is composed of three parts: one merge_to and two merge_from:

    <merge at="0" direction="9:9" nodenumberB="9" op="mergedTo" pos="4">
	    <p>Text paragraph four with some additional text of paragraph five</p>
    </merge>
    <merge direction="9:9" nodenumberA="9" op="mergedFrom">
	    <p>Text paragraph four</p>
    </merge>
    <merge direction="11:9" nodenumberA="11" op="mergedFrom">
	    <p>with some additional text of paragraph five</p>
    </merge>

Paragraph Split: split one paragraph into two different paragraphs. The split operation is composed of three parts: one split_from and two split_to:

    <split at="0" direction="9:9" nodenumberB="9" op="splitedTo" pos="4">
	    <p>Text paragraph four</p>
    </split>
    <split at="0" direction="9:11" nodenumberB="11" op="splitedTo" pos="5">
	    <p>with some additional text of paragraph five</p>
    </split>
    <split direction="9:9" nodenumberA="9" op="splitedFrom">
	    <p>Text paragraph four with some additional text of paragraph five</p>
    </split>

Move: move one keyword from its initial position 2 to position 4 within the keywords list:

    <move move="376::378" nodecount="2">
        <kwd>remote sensing</kwd>
    </move>

Style insert: insert bold style around the word "disasters":

    <text-style-insert nodenumberB="117" op="insert-style" pos="319">
        <b>disasters</b>
    </text-stvle-insert>

Style delete: remove bold style around the word "monitoring":

    <text-style-delete nodenumberA="117" op="delete-style" DOS="14">
        <b>monitoring</b>
    </text-style-delete>

Style edit: Movie one keyword from its initial position 2 to position 4:

    <text-style-update nodenumberB="117" op="update-style-to" pos="14">
        <i>monitoring</i>
    </text-style-update>
    <text-style-update nodenumberA="117" op="update-style-from" pos="14">
        <b>monitoring</b>
    </text-style-update>

Text Move: move portion of the text from one paragraph to another:

    <text-move nodecount="1" nodenumberB="6" op="movedTo"  text-position-to="19">
	    text of paragraph  five
    </text-move≫
    <text-move nodecount="1" nodenumberA="12" op="movedFrom"  text-position-from="21">
	    text of paragraph  five
    </text-move>

Text Update: change one word from "central" to "centralised":

    <text-update length="7" nodenumberA="368" nodenumberB="368" op="text-deleted" pos="33">
	    central
    </text-update≫
    <text-update length="11" nodenumberA="368" nodenumberB="368" op="text-inserted" pos="33">
	    centralised
    </text-update>

5.0.2. Semantics output XML

Once the initial "Level 1" and "Level 2" edits have been identified, jats-diff will refine those and use change semantics in order to improve the visual representation of the detected changes and avoid representing the so-called induced changes we saw in Section 2. Moreover, the similarity index will also be calculated, and the results will be presented in the form of an XML tree structure.

We will see below some real-life examples where change semantics are used in order to refine a long list of "Level 1" and "Level 2" induced edits and summarise those in a human-readable format:

Citable objects: insertion of a new bibliography item in the references list <ref-list> at position 153 (out of 156). Oppositely, the delta XML will show for this simple bibliography insert over a dozen of different edit actions: text updates, attribute updates, etc.

0 - article
    * depth: 0
    * similar-word: 99.9
   
      606 - back
      * depth: 1
      * similar-word: 99.8
     
        1932 - ref-list
        * Initial: 156
        * Final: 157
        * depth: 2
        * similar-word: 99.7
     
          7993 - ref
          * id :B153
          * depth: 3
          * change-type: insert

jats-diff considers the following to be special objects: tables, bibliographies, figures and mathematical formulas. Those objects are special due to the fact that their edits are not human readable and have to be represented in a different way: for tables (as seen in the previous example), the similarity index is calculated per table content and caption.

Element lists and special objects: modification of a table:

0 - article
* depth: 0
* similar-word: 100.0
 
  3977 - back
  * depth: 1
  * similar-word: 99.8
 
    6312 - sec
    * id :sec-type="display-objects"
    * depth: 2
    * similar-word: 99.5
 
    6313 - table
    * Initial: 6
    * Modified: 1
    * Final: 6
    * depth: 2
    * similar-word: 99.6
 
      6895 - table-wrap
      * id :t006
      * depth: 3
      * change-type: table-edit 
        * table
            * 66.7 
        * caption
            * 98.0
      * similar-word: 89.9

Most of the special objects (tables, figures) but also bibliographies are within so-called element lists. jats-diff also uses change semantics in order to represent those in a more readable way. In the previous example where a table edit is shown, we can observe that the entire table list is shown with its initial, modified and final values. The initial value represents the total number of tables in document A, the modified value represents the number of edited tables and the final value represents the total number of tables in document B.

Similarity index

As seen in the two previous examples, the similarity index is calculated and propagated through the JATS XML tree. jats-diff allows calculating different similarity indexes: similartext, similartext-word, Jaccard and TFIDF. By default, the similartext-word index is used that allows the reader to obtain insights about lexical changes. In addition to the existing lexical similarity indexes, work is in progress to add different similarity indexes such as Topic Model and Word2Vec that can allow extracting semantic changes and distinguishing between simple sentence rephrasing and sentence meaning changes.

0 - article
* depth: 0
* similar-word: 99.5
 
  155 - body
  * depth: 1
  * similar-word: 99.3
 
    156 - sec
    * id :sec1
    * 1. Introduction
    * depth: 2
    * similar-word: 99.9
 
      169 - p
      * depth: 3
      * change-type: text-update - text-inserted
      * similar-word: 99.3
 
    175 - sec
    * id :sec2
    * 2. Materials
    * depth: 2
    * similar-word: 96.2
 
      199 - sec
      * id :sec2dot2
      * 2.2. Imagery Surveyed from UAV and Satellites
      * depth: 3
      * similar-word: 77.8
 
        202 - p
        * depth: 4
        * change-type: delete

We compare in the next section the new jats-diff algorithm with the other state-of-the-art XML diff algorithms that work well with text-centric documents.

6.1. Information extraction capacity

The initial evaluation phase consists in comparing the "Level 1" and "Level 2" information extraction capacities of the new jats-diff algorithm with JNDiff, XyDiff and XCC. Table 3 shows the results grouped by algorithm and level. During this performance analysis, we created different JATS XML file pairs, one original and one modified version of the same article. The modified version is composed of one of the human edits that is described in the "Human edit description" column. The output of each of the compared algorithms is then verified for its ability to detect the given edit type.

Table 3

Level 1/2 edit detection and similarity index calculation capacities for jats-diff, JNDiff, XYDiff and XCC.

As seen in Table 3, jats-diff is able to detect all of the "Level 1" and "Level 2" edits. In addition, there is a similarity index calculated and propagated upwards of the XML for each change detected. This is followed by JNDiff with a perfect score for "Level 1" and a low score for "Level 2" edits. JnDiff can also detect "wrap" and "unwrap" edit patterns that are similar to style edits. This is followed by XyDiff with similar results in addition to text insert detection, where XyDiff mostly uses text updates to represent text inserts. This is because XyDiff calculates the longest common sub-string (LCS) and minimises the edit distance, which increases the complexity for a human reader to interpret the results. XCC follows XyDiff but with additional issues in detecting tree delete and tree move edits compared to JNDiff.

Concerning the delta output, Table 3 shows that jats-diff uses the minimal number of edit actions for almost all edit pattern detection. For a few of them where JNDiff, XyDiff or XCC output a lower number of edit actions, they are usually represented as a simple delete–insert combination which does not reflect real changes made by humans at all, which we observe in the next section where we evaluate the delta file size for each of the jats-diff. If we push the theory of minimising the number of edit actions, one could think of using the delete–insert combination on the complete document, which will minimise the number of edit actions but maximise the delta file size.

6.2. Execution performance

Although not critical in our working environment, algorithm performance for both execution time and memory usage stays important. Compared with other XML diff algorithms that are made with the purpose of comparing hundreds of thousands of XML documents (for example, XyDiff and webpage difference extraction), jats-diff will have to compare academic articles in JATS XML format during the publication process. Their number is counted in hundreds per day, which is far from the number of documents to be compared that XyDiff usually faces.

Using the JNDiff core functions for "Level 1" change detection, the execution time and memory usage of jats-diff is minimum at the level of JNDiff. Adding new "Level 2" pattern detection requires additional analysis of the detected "Level 1" differences; thus, it requires more time and memory for the algorithm to be executed. The similarity calculation and propagation is carried out separately by analysing the delta output and requires additional execution time.

We divide jats-diff into two parts: first, the new "Level 2" pattern detection, and second, the similarity calculation and propagation. JATS articles are large XML files that may vary from 100 KB to 400 KB. The tests⁹ were run on a JATS document pair A and B representing real-life author changes during a revision round, affecting every aspect of the article: the title, authors, affiliations, paragraphs, figures, tables and references.

Figure 15 shows both the execution time (15a) and the maximum and average memory used (15b) during a comparison of two real-life author changes in JATS documents. As expected, both parts of the new tools take more time and memory to perform the diff and semantics extraction; however, those are acceptable within our environment as the information consumers are humans with the aim to compare the original and revised version of academic articles, which does not need to be done in real time while the authors submit their revised version.

Figure 15

Execution time and memory usage for comparing two real-life author changes in JATS documents.

6.3. Current limitations

Although the jats-diff algorithm was tested for all previously described edit actions, its implementation is still a work in progress, and the algorithm is not yet tested in production; therefore, there are still some edge cases where the jats-diff fails. As regards the tests, we mostly tested the algorithm up to the 2nd level of complexity where up to two edit actions are mixed at the same time. For those, below is the list of some actions that are failing:

• Upgrade Subsection 2.3 to Section 6 and move one <p> of the upgraded subsection to Section 5;
• Split the last paragraph of Section 1 into two paragraphs below each other and move Section 1 after Section 2;
• Split the last paragraph of Section 1 into two paragraphs below each other and update the text in the second split part;
• Merge the last two paragraphs of Section 1 and move Section 1 after Section 2;
• Merge the last two paragraphs of Section 1 and update style range in the merged paragraph;
• ...