| 1 |
<!DOCTYPE html> |
| 2 |
<html> |
| 3 |
<head> |
| 4 |
<meta charset="utf-8" /> |
| 5 |
<meta name="viewport" content="width=device-width,initial-scale=1" /> |
| 6 |
<meta name="creator" content="BSD.lv" /> |
| 7 |
<meta name="author" content="Kristaps Dzonsons" /> |
| 8 |
<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/highlight.js/9.12.0/styles/default.min.css" /> |
| 9 |
<link rel="stylesheet" href="https://fonts.googleapis.com/css?family=Alegreya+Sans:400,400italic,500,700" /> |
| 10 |
<link rel="stylesheet" href="diff.css" /> |
| 11 |
<script src="https://cdnjs.cloudflare.com/ajax/libs/highlight.js/9.12.0/highlight.min.js"></script> |
| 12 |
<script src="diff.js"></script> |
| 13 |
<title>Lowdown Diffing Engine </title> |
| 14 |
</head> |
| 15 |
<body> |
| 16 |
<h1 id="lowdown-diffing-engine">Lowdown Diffing Engine</h1> |
| 17 |
<p>In this paper, I briefly describe the “diff” engine used in |
| 18 |
<a href="https://kristaps.bsd.lv/lowdown/lowdown.1.html">lowdown-diff(1)</a> tool |
| 19 |
in <a href="https://kristaps.bsd.lv/lowdown/index.html">lowdown</a>. The work is |
| 20 |
motivated by the need to provide formatted output describing the |
| 21 |
difference between two documents—specifically, formatted PDF via the |
| 22 |
<strong>-Tms</strong> output, although <strong>-Thtml</strong> and the other output modes are of |
| 23 |
course supported.</p> |
| 24 |
<ins> |
| 25 |
<p>This documents an early work in progress—both source code and |
| 26 |
documentation. The source is documented fully in |
| 27 |
<a href="https://github.com/kristapsdz/lowdown/blob/master/diff.c">diff.c</a>. |
| 28 |
This paper itself is available as |
| 29 |
<a href="https://github.com/kristapsdz/lowdown/blob/master/diff.md">diff.md</a>, or downloadable as |
| 30 |
<a href="https://kristaps.bsd.lv/lowdown/diff.pdf">diff.pdf</a>. |
| 31 |
Please direct comments to me by e-mail or just use the <a href="https://github.com/kristapsdz/lowdown">GitHub |
| 32 |
interface</a>.</p> |
| 33 |
</ins> |
| 34 |
<p>For a quick example of this functionality, see |
| 35 |
<a href="https://kristaps.bsd.lv/lowdown/diff.diff.html">diff.diff.html</a><ins> |
| 36 |
(or </ins><ins><a href="https://kristaps.bsd.lv/lowdown/diff.diff.pdf">diff.diff.pdf</a></ins><ins>), which |
| 37 |
shows the difference between this document and a [fabricated] earlier |
| 38 |
version.</ins><del>.</del></p> |
| 39 |
<h2 id="introduction">Introduction</h2> |
| 40 |
<p>Let two source files, <del><em>foo.md</em></del><ins><em>old.md</em></ins> and <del><em>bar.md</em></del><ins><em>new.md</em></ins>, refer to the old and new versions of a file respectively.<ins>The</ins> <ins>goal</ins> <ins>is</ins> <ins>to</ins> <ins>establish</ins> <ins>the</ins> <ins>changes</ins> <ins>between</ins> <ins>these</ins> <ins>snippets</ins> <ins>in</ins> <ins>formatted</ins> <ins>output.</ins> <ins>Let</ins>’s <ins>begin</ins> <ins>with</ins> <ins>the</ins> <ins>old</ins> <ins>version,</ins> <ins><em>old.md</em></ins><ins>.</ins></p> |
| 41 |
<pre><code class="language-markdown">*Lorem* ipsum dolor sit amet, consectetur adipiscing elit, sed do |
| 42 |
eiusmod tempor incididunt ut [labore](index.html) et dolore magna |
| 43 |
aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco |
| 44 |
laboris nisi ut _aliquip_ ex ea commodo consequat. Duis aute irure dolor |
| 45 |
in reprehenderit... |
| 46 |
</code></pre> |
| 47 |
<p>In the new version, <em>new.md</em>, I add some more links and styles.</p> |
| 48 |
<pre><code class="language-markdown">*Lorem* ipsum dolor sit amet, consectetur adipiscing elit, sed do |
| 49 |
eiusmod tempor incididunt ut [labore](index.html) et dolore [magna |
| 50 |
aliqua](index.html). Ut enim ad minim veniam, quis nostrud exercitation |
| 51 |
ullamco laboris nisi ut _aliquip_ ex ea commodo consequat. Duis *aute |
| 52 |
irure* dolor in reprehenderit... |
| 53 |
</code></pre> |
| 54 |
<p>The most simple way of viewing changes is with the venerable |
| 55 |
<a href="https://man.openbsd.org/diff.1">diff(1)</a> utility. However, this will |
| 56 |
only reflect changes in the input document—not the formatted output.</p> |
| 57 |
<pre><code class="language-diff">--- old.md Tue Oct 17 11:25:01 2017 |
| 58 |
+++ new.md Tue Oct 17 11:25:01 2017 |
| 59 |
@@ -1,5 +1,5 @@ |
| 60 |
*Lorem* ipsum dolor sit amet, consectetur adipiscing elit, sed do |
| 61 |
-eiusmod tempor incididunt ut [labore](index.html) et dolore magna |
| 62 |
-aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco |
| 63 |
-laboris nisi ut _aliquip_ ex ea commodo consequat. Duis aute irure dolor |
| 64 |
-in reprehenderit... |
| 65 |
+eiusmod tempor incididunt ut [labore](index.html) et dolore [magna |
| 66 |
+aliqua](index.html). Ut enim ad minim veniam, quis nostrud exercitation |
| 67 |
+ullamco laboris nisi ut _aliquip_ ex ea commodo consequat. Duis *aute |
| 68 |
+irure* dolor in reprehenderit... |
| 69 |
</code></pre> |
| 70 |
<p>Not very helpful for any but source-level change investigation. And |
| 71 |
given that Markdown doesn’t encourage the usual “new sentence, new line” |
| 72 |
of some languages (like <a href="https://man.openbsd.org/mdoc.7">mdoc(7)</a>), even |
| 73 |
this level of change analysis is difficult: a single change might affect |
| 74 |
multiple re-wrapped lines.</p> |
| 75 |
<p>A similar possibility is to use |
| 76 |
<a href="https://www.gnu.org/software/wdiff/">wdiff(1)</a>, which produces a set of |
| 77 |
word-by-word differences.</p> |
| 78 |
<pre><code class="language-markdown">*Lorem* ipsum dolor sit amet, consectetur adipiscing elit, sed do |
| 79 |
eiusmod tempor incididunt ut [labore](index.html) et dolore [-magna |
| 80 |
aliqua.-] {+[magna aliqua](index.html).+} Ut enim ad minim veniam, quis |
| 81 |
nostrud exercitation ullamco laboris nisi ut _aliquip_ ex ea commodo |
| 82 |
consequat. Duis [-aute irure-] {+*aute irure*+} dolor in |
| 83 |
reprehenderit... |
| 84 |
</code></pre> |
| 85 |
<p>One could then extend the Markdown language to accept the insertion and |
| 86 |
deletion operations and let the output flow from there. |
| 87 |
(In fact, that was my first approach to solving the problem.)</p> |
| 88 |
<p>Unfortunately, doing so entails extending a language already prone to extension and non-standardisation. <del>Here</del> <del>is</del> <del>some</del> <del>added</del> <del>text.</del> More unfortunately, a word-based diff will not be sensitive to the <del>shmarkdown</del> <ins>Markdown</ins> language itself, and in establishing context-free <del>foo</del> <del>bar</del> <del>baz</del> <ins>sequences</ins> of similar words, will overrun block and span element boundaries.</p> |
| 89 |
<p>On the other end of the spectrum are difference tools specific to the |
| 90 |
output media.</p> |
| 91 |
<ins> |
| 92 |
<p>One can directly analyse PDF output using (for example) the |
| 93 |
<a href="https://poppler.freedesktop.org/">poppler</a> tools, which would extract |
| 94 |
text, then examine the output with a linear difference engine such as |
| 95 |
<a href="https://code.google.com/archive/p/google-diff-match-patch/">Diff, Match, |
| 96 |
Patch</a>. |
| 97 |
This is not an optimal solution because, as with the word diff above, it |
| 98 |
only compares words and cannot distinguish semantic artefacts such as in |
| 99 |
italics, links, code blocks, and so on.</p> |
| 100 |
</ins> |
| 101 |
<p>There are even more <a href="https://www.w3.org/wiki/HtmlDiff">HTML diff</a> tools |
| 102 |
available, so it’s tempting to use one of these tools to produce an HTML |
| 103 |
file consisting of differences, then further use a converter like |
| 104 |
<a href="https://wkhtmltopdf.org/">wkhtmltopdf</a> to generate PDFs.</p> |
| 105 |
<p>Since the HTML difference engines often respect the structure of HTML, |
| 106 |
this is much more optimal in handling semantic difference. However, |
| 107 |
re-structuring the difference does not easily produce a document of the |
| 108 |
same style or readability as the PDFs themselves.</p> |
| 109 |
<p>The most elegant (and reliable) solution is to attack the problem from |
| 110 |
the language-level itself. Since the |
| 111 |
<a href="https://kristaps.bsd.lv/lowdown/lowdown.3.html">lowdown(3)</a> |
| 112 |
library is able to produce a full parse tree for analysis, it stands to |
| 113 |
reason, given the wealth of literature on tree differences (instead of |
| 114 |
the usual linear difference, as in the case of |
| 115 |
<a href="https://man.openbsd.org/diff.1">diff(1)</a> and friends), one can work |
| 116 |
within the language to produce differences.<del><sup id="fnref1"><a href="#fn1" rel="footnote">1</a></sup></del></p> |
| 117 |
<h2 id="algorithm">Algorithm</h2> |
| 118 |
<p>The algorithm is in effect an ordered tree diff. I began with |
| 119 |
well-studied algorithms for a well-studied problem: XML tree |
| 120 |
differences. (The HTML difference tools described above inherit from |
| 121 |
those algorithms.) For an overview of algorithms, see Change Detection |
| 122 |
in XML Trees: a Survey<sup id="fnref2"><a href="#fn2" rel="footnote">2</a></sup>. I base the |
| 123 |
<a href="https://kristaps.bsd.lv/lowdown/lowdown.1.html">lowdown-diff(1)</a> algorithm off |
| 124 |
of Detecting Changes in XML Documents<sup id="fnref3"><a href="#fn3" rel="footnote">3</a></sup>.</p> |
| 125 |
<p>The reason for this choice instead of another is primarily the ease in |
| 126 |
implementation. Moreover, since the programmatic output of the |
| 127 |
algorithm is a generic AST, it’s feasible to re-implement the algorithm |
| 128 |
in different ways, or augment it at a later date.</p> |
| 129 |
<p>The BULD algorithm described in this paper is straightforward. It |
| 130 |
begins with a short sanitisation pass.</p> |
| 131 |
<ol> |
| 132 |
<li><p>Annotate each node in the parse tree with a hash of the subtree |
| 133 |
rooted at the node, inclusive. |
| 134 |
(<a href="https://github.com/kristapsdz/lowdown/blob/master/diff.c">diff.c</a>, |
| 135 |
<code>annotate_sigs()</code>)</p></li> |
| 136 |
<li><p>Annotate each node with a weight corresponding to the subtree rooted |
| 137 |
at the node. |
| 138 |
(<a href="https://github.com/kristapsdz/lowdown/blob/master/diff.c">diff.c</a>, |
| 139 |
<code>annotate_sigs()</code>)</p></li> |
| 140 |
<li><p>Enqueue the new document’s root node in a priority queue ordered by |
| 141 |
weight. Then, while the priority queue is non-empty: |
| 142 |
(<a href="https://github.com/kristapsdz/lowdown/blob/master/diff.c">diff.c</a>, |
| 143 |
<code>lowdown_diff()</code>)</p> |
| 144 |
<ol> |
| 145 |
<li>Pop the first node of the priority queue.</li> |
| 146 |
<li>Look for candidates in the old document whose hash matches the |
| 147 |
popped node’s hash. |
| 148 |
(<a href="https://github.com/kristapsdz/lowdown/blob/master/diff.c">diff.c</a>, |
| 149 |
<code>candidate()</code>)</li> |
| 150 |
<li>Choose an optimal candidate and mark it as matched. |
| 151 |
(<a href="https://github.com/kristapsdz/lowdown/blob/master/diff.c">diff.c</a>, |
| 152 |
<code>optimality()</code>)</li> |
| 153 |
<li>If the no candidates were found, enqueue the node’s children into |
| 154 |
the priority queue.</li> |
| 155 |
<li>A a candidate was selected, mark all of its subtree nodes as |
| 156 |
matching the corresponding nodes in the old tree (“propagate |
| 157 |
down”), then mark ancestor nodes similarly (“propagate up”). |
| 158 |
(<a href="https://github.com/kristapsdz/lowdown/blob/master/diff.c">diff.c</a>, |
| 159 |
<code>match_up()</code>, <code>match_down()</code>)</li> |
| 160 |
</ol></li> |
| 161 |
<li><p>Run an optimisation phase over the new document’s root node. |
| 162 |
(<ins><a href="https://github.com/kristapsdz/lowdown/blob/master/diff.c">diff.c</a></ins><del><a href="https://github.com/kristapsdz/lowdown/blob/master/diff.c">diff.c</a></del>, |
| 163 |
<del><code>node_optimise()</code></del><ins><code>node_optimise_bottomup()</code></ins><ins> and </ins><ins><code>node_optimise_topdown()</code></ins>)</p></li> |
| 164 |
<li><p>Step through both trees and create a new tree with nodes cloned from |
| 165 |
both and marked as inserted or deleted. |
| 166 |
(<a href="https://github.com/kristapsdz/lowdown/blob/master/diff.c">diff.c</a>, |
| 167 |
<code>node_merge()</code>)</p></li> |
| 168 |
</ol> |
| 169 |
<p>My implementation changes or extends the BULD algorithm in several small |
| 170 |
ways, described in the per-step documentation below.</p> |
| 171 |
<h3 id="sanitise">Sanitise</h3> |
| 172 |
<p>Before the BULD algorithm is run, the input tree is sanitised. This |
| 173 |
process merges all adjacent text nodes into a single text node. By |
| 174 |
doing so, possible differences are pushed into large blocks of |
| 175 |
contiguous text—which in this case are managed by the word-difference |
| 176 |
algorithm described later in this paper.</p> |
| 177 |
<h3 id="annotation">Annotation</h3> |
| 178 |
<p>Each node in the tree is annotated with a hash and a weight. The hash, |
| 179 |
MD5, is computed in all data concerning a node. For example, normal |
| 180 |
text nodes (<code>LOWDOWN_NORMAL_TEXT</code>) have the hash produced from the |
| 181 |
enclosed text. Autolinks (<code>LOWDOWN_LINK_AUTO</code>) use the link text, link, |
| 182 |
and type.</p> |
| 183 |
<p>There are some nodes whose data is not hashed. For example, list |
| 184 |
numbers: since these may change when nodes are moved, the numbers are |
| 185 |
not part of the hash. In general, all volatile information that may be |
| 186 |
inferred from the document structure (column number, list item number, |
| 187 |
footnote number, etc.) is disregarded.</p> |
| 188 |
<p>Non-leaf nodes compute their hashes from the node type and the hashes of |
| 189 |
all of their children. Thus, this step is a bottom-up search.</p> |
| 190 |
<p>Node weight is computed exactly as noted in the paper.</p> |
| 191 |
<h3 id="optimal-candidacy">Optimal candidacy</h3> |
| 192 |
<p>A node’s candidate in the old tree is one whose hash matches. In most |
| 193 |
documents, there are many candidates for certain types of nodes. |
| 194 |
(Usually text nodes.)</p> |
| 195 |
<p>Candidate optimality is computed by looking at the number of parent |
| 196 |
nodes that match on both sides. The number of parents to consider is |
| 197 |
noted in the next sub-section. The distance climbed is bounded by the |
| 198 |
weight of the sub-tree as defined in the paper.</p> |
| 199 |
<p>In the event of similar optimality, the node “closest” to the current |
| 200 |
node is chosen. Proximity is defined by the node identifier, which is |
| 201 |
its prefix order in the parse tree.</p> |
| 202 |
<h3 id="propagate-up">“Propagate up”</h3> |
| 203 |
<p>When propagating a match upward, the distance upward is bound depending |
| 204 |
on the matched sub-tree as defined in the paper. This makes it so that |
| 205 |
“small” similarities (such as text) don’t erroneously match two larger |
| 206 |
sub-trees that are otherwise different. Upward matches occur while the |
| 207 |
nodes’ labels are the same, including attributes (e.g., link text).</p> |
| 208 |
<p>I did modify the algorithm to propagate upward “for free” through |
| 209 |
similar singleton nodes, even if it means going beyond the maximum |
| 210 |
number allowed by the sub-tree weight.</p> |
| 211 |
<h3 id="optimisation">Optimisation</h3> |
| 212 |
<p>The <a href="https://kristaps.bsd.lv/lowdown/lowdown.1.html">lowdown-diff(1)</a> |
| 213 |
algorithm has two optimisations, both lightly derived from the paper: |
| 214 |
top-down and bottom-up propagation.</p> |
| 215 |
<h4 id="top-down">Top-down</h4> |
| 216 |
<p>The top-down optimisation, which is performed first, takes matched nodes and matches un-matched, non-terminal children by label.<ins>The</ins> <ins>children</ins> <ins>examined</ins> <ins>must</ins> <ins>be</ins> <ins>siblings</ins> <ins>of</ins> <ins>adjacent</ins> <ins>matching</ins> <ins>nodes.</ins></p> |
| 217 |
<p>This is useful when, say, a document consists of several paragraphs |
| 218 |
where the text has changed within paragraphs. It won’t be able to match |
| 219 |
the text content, but it will match the paragraphs, which will push the |
| 220 |
difference downward in the tree.</p> |
| 221 |
<h4 id="bottom-up">Bottom-up</h4> |
| 222 |
<p>In the bottom-up propagation, the weight of any given sub-tree is used |
| 223 |
to compute how high a match will propagate. I extend the paper’s |
| 224 |
version optimisation by looking at the cumulative weight of matching |
| 225 |
children.</p> |
| 226 |
<p>This works well for Markdown documents, which are generally quite |
| 227 |
shallow and text-heavy.</p> |
| 228 |
<p>For each unmatched non-terminal node with at least one |
| 229 |
matched child, the weights of all matched children with the same parents |
| 230 |
(where the parent node is equal in label and attributes to the examined |
| 231 |
node) are computed. If any given parent of the matched children has |
| 232 |
greater than 50% of the possible weight, it is matched.</p> |
| 233 |
<h3 id="merging">Merging</h3> |
| 234 |
<p>The merging phase, which is not described in the paper, is very |
| 235 |
straightforward. It uses a recursive merge algorithm starting at the |
| 236 |
root node of the new tree and the root node of the old tree.</p> |
| 237 |
<ol> |
| 238 |
<li>The invariant is that the current node is matched by the corresponding |
| 239 |
node in the old tree.</li> |
| 240 |
<li>First, step through child nodes in the old tree. Mark as deleted all |
| 241 |
nodes not being matched to the new tree.</li> |
| 242 |
<li>Next, step through child nodes in the new tree. Mark as inserted all |
| 243 |
nodes not having a match in the old tree.</li> |
| 244 |
<li>Now, starting with the first node in the new tree having a match in |
| 245 |
the old tree, search for that match in the list of old tree children.</li> |
| 246 |
<li>If found, mark as deleted all previous old tree nodes up until the |
| 247 |
match. Then re-run the merge algorithm starting at the matching |
| 248 |
child nodes.</li> |
| 249 |
<li>If not found, mark the new node as inserted and return to (2).</li> |
| 250 |
<li>Continue (after the recursive step) by moving after both matching |
| 251 |
nodes and returning to (2).</li> |
| 252 |
</ol> |
| 253 |
<p>If adjacent nodes are un-matched normal text, the normal text nodes are |
| 254 |
compared word-by-word to compute a shortest-edit script. This is |
| 255 |
enabled by <a href="https://github.com/kristapsdz/libdiff">libdiff</a>, which |
| 256 |
implements an algorithm for computing the longest common |
| 257 |
subsequence<sup id="fnref4"><a href="#fn4" rel="footnote">4</a></sup>. See <sup id="fnref5"><a href="#fn5" rel="footnote">5</a></sup> for background information.</p> |
| 258 |
<ins> |
| 259 |
<h3 id="tables">Tables</h3> |
| 260 |
</ins><ins> |
| 261 |
<p>Tables are currently in the “hacks” state in that they’re considered as |
| 262 |
opaque bodies. Tables that have changed in any way are simply deleted |
| 263 |
and re-added: there’s no attempt to discern actual differences.</p> |
| 264 |
</ins><ins> |
| 265 |
<p>There are ways to reduce this opacity, such as being able to detect and |
| 266 |
account for added or removed rows. However, ultimately there is some |
| 267 |
opacity in that changed table headers do not have a representable form |
| 268 |
in the output.</p> |
| 269 |
</ins><ins> |
| 270 |
<h3 id="metadata">Metadata</h3> |
| 271 |
</ins><ins> |
| 272 |
<p>Like tables, metadata key-value pairs are opaque bodies. Metadata has a |
| 273 |
complex relationship with Markdown documents, which leaves how to handle |
| 274 |
the “difference” uncertain.</p> |
| 275 |
</ins><ins> |
| 276 |
<p>The difference engine, after computing differences like any other opaque |
| 277 |
nodes, simply passes the difference to front-ends, which determine how |
| 278 |
to handle this for themselves. For front-ends that use the metadata in |
| 279 |
creating document headers (e.g., HTML, LaTeX, roff), the policy is not |
| 280 |
to process deleted metadata.</p> |
| 281 |
</ins><ins> |
| 282 |
<p>Thus, metadata won’t strictly represent the document differences.</p> |
| 283 |
</ins><ins> |
| 284 |
<h3 id="footnotes">Footnotes</h3> |
| 285 |
</ins><ins> |
| 286 |
<p>Footnotes required some consideration because the order in which the |
| 287 |
definitions and references are printed must be synchronised. Now a |
| 288 |
process keeps track of all references (added, deleted, unchanged) and |
| 289 |
renumbers then. When references are emitted, these are emitted in the |
| 290 |
correct order.</p> |
| 291 |
</ins> |
| 292 |
<h2 id="api">API</h2> |
| 293 |
<p>The result of the algorithm is a new tree marked with insertions and |
| 294 |
deletions. These are specifically noted with the <code>LOWDOWN_CHNG_INSERT</code> |
| 295 |
and <code>LOWDOWN_CHNG_DELETE</code> variables.</p> |
| 296 |
<p>The algorithm may be run with the <code>lowdown_diff()</code> function, which |
| 297 |
produces the merged tree.</p> |
| 298 |
<p>A set of convenience functions, <code>lowdown_buf_diff()</code> and |
| 299 |
<code>lowdown_file_diff()</code>, also provide this functionality.</p> |
| 300 |
<h2 id="future-work">Future work</h2> |
| 301 |
<p>There are many possible improvements to the algorithm.</p> |
| 302 |
<del> |
| 303 |
<p>Foremost is the issue of normal text nodes. There should be a process |
| 304 |
first that merges consecutive text nodes. This happens, for example, |
| 305 |
when the <code>w</code> character is encountered at any time and might signify a |
| 306 |
link. The parsing algorithm will start a new text node at each such |
| 307 |
character. </p> |
| 308 |
</del> |
| 309 |
<p>The merging algorithm can also take advantage of |
| 310 |
<a href="https://github.com/kristapsdz/libdiff">libdiff</a> when ordering the |
| 311 |
output of inserted and deleted components. Right now, the algorithm is |
| 312 |
simple in the sense of stopping at the earliest matched node without |
| 313 |
considering subsequences.</p> |
| 314 |
<del> |
| 315 |
<p>Lastly, the <strong>-Tms</strong> and <strong>-Tman</strong> output needs work to make sure that |
| 316 |
the insert/delete macros don’t disrupt the flow of text.</p> |
| 317 |
</del> |
| 318 |
<p>Document last updated: $Date$</p> |
| 319 |
<div class="footnotes"> |
| 320 |
<hr/> |
| 321 |
<ol> |
| 322 |
|
| 323 |
<li id="fn1"> |
| 324 |
<p>This is just to illustrate a removed footnote. <a href="#fnref1" rev="footnote">↩</a></p> |
| 325 |
</li> |
| 326 |
|
| 327 |
<li id="fn2"> |
| 328 |
<p><a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.73.8912&rep=rep1&type=pdf">Change Detection in XML Trees: a |
| 329 |
Survey</a> |
| 330 |
(2005), Luuk Peters. <a href="#fnref2" rev="footnote">↩</a></p> |
| 331 |
</li> |
| 332 |
|
| 333 |
<li id="fn3"> |
| 334 |
<p><a href="https://www.cs.rutgers.edu/~amelie/papers/2002/diff.pdf">Detecting Changes in XML |
| 335 |
Documents</a> |
| 336 |
(2002), Gregory Cobena, Serge Abiteboul, Amelie Marian. <a href="#fnref3" rev="footnote">↩</a></p> |
| 337 |
</li> |
| 338 |
|
| 339 |
<li id="fn4"> |
| 340 |
<p><a href="https://publications.mpi-cbg.de/Wu_1990_6334.pdf">An O(NP) sequence comparison |
| 341 |
algorithm</a> (1990), |
| 342 |
Sun Wu, Udi Manber, Gene Myers. <a href="#fnref4" rev="footnote">↩</a></p> |
| 343 |
</li> |
| 344 |
|
| 345 |
<li id="fn5"> |
| 346 |
<p><a href="https://www.cs.dartmouth.edu/~doug/diff.pdf">An Algorithm for Differential File |
| 347 |
Comparison</a>(1976), |
| 348 |
James W. Hunt, M. Douglas McIlroy. <a href="#fnref5" rev="footnote">↩</a></p> |
| 349 |
</li> |
| 350 |
|
| 351 |
</ol> |
| 352 |
</div> |
| 353 |
</body> |
| 354 |
</html> |