-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy path2-3-way-diff-xml.htm
196 lines (158 loc) · 9.43 KB
/
2-3-way-diff-xml.htm
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
<!DOCTYPE html>
<html>
<head>
<meta charset="utf8" />
<title>А не закодить ли 2-Way и 3-Way Diff для XML?</title>
</head>
<body>
<table><tr><td style="vertical-align:top;">
<h1>А не закодить ли 2-Way и 3-Way Diff для XML?</h1>
</td><td style="vertical-align:top;">
<a href="index.htm">блог всячепуза</a>
<br />
</td></tr></table>
Реализация алгоритма O(ND) из работы <strong>1986, Myers</strong> для 2-way merge не даёт конкурентного преимущества,
<br>
потому что O(ND)-алгоритм сравнивает файлы парами (A, O), (B, O), а не все три файла сразу.
<br>
Как реализовывать O(ND) сравнение на C#, есть статья <strong>20060314, Hertel</strong> (<a href="http://www.mathertel.de/diff/">http://www.mathertel.de/diff/</a>).
<br>
<br>
Конкурентного преимущества он не даёт, потому что приводит к неоптимальным результатам,
<br>
как описано в работе <strong>2007, Khanna</strong>
<br>
<br>
Поэтому имеет смысл реализовывать алгоритм SDiff3 (Similarity-Based State-Based Synchronizer) из работы <strong>2015, Autexier</strong>
<br>
<br>
Всего нужно прочитать 94 страницы + 45 для tree diff, норматив скорости перевода для профессионалов - 10 страниц в день (<a href="http://www.norma-tm.ru/article/article1-4.html">*</a>),
<br>
для понимания, возможно, потребуется читать что-то ещё, поэтому для оценки возьмем 5 страниц в день. 95 страниц = 19 дней на изучение области
<br>
( хотя есть оценка в 1 месяц - <a href="http://c2.com/cgi/wiki?DiffAlgorithm">http://c2.com/cgi/wiki?DiffAlgorithm</a>,
если 21 рабочий день, то похоже )
<br>
объём кода будет ~5000 строк, 10 строк в день пишут в среднем, гениальные программисты в 10 раз быстрее обычных, итого +50 дней.
<br>
<br>
Общий вывод - похоже на работы по грантам РФФИ
<br>
<a href="http://www.math.spbu.ru/user/kromanovsky/docline/pdf/luciv.koznov.andreev.2012.sysprog.pdf">http://www.math.spbu.ru/user/kromanovsky/docline/pdf/luciv.koznov.andreev.2012.sysprog.pdf</a>
<h3>Литература для 3-way diff, 2-way diff и LCS</h3>
<dl>
<dt>2015, Autexier S, Similarity-Based Diff, Three-Way Diff and Merge</dt>
<dd><a href="http://ijsi.org/ch/reader/create_pdf.aspx?file_no=i217&year_id=2015&quarter_id=2&falg=1">http://ijsi.org/ch/reader/create_pdf.aspx?file_no=i217&year_id=2015&quarter_id=2&falg=1</a>
<br>
19 страниц
</dd>
<br>
<dt>2011-11, Ritcher Bill, Guiffy SureMerge - A Trustworthy 3-Way Merge, <a href="http://www.guiffy.com/SureMergeWP.html">http://www.guiffy.com/SureMergeWP.html</a></dt>
<dd>14 страниц, читать, чтобы понять, что без использования алгоритмов tree diff хороших результатов для исходников не получится</dd>
<br>
<dt>2010-06-04, Johansen Martin Fagereng, Testing Eclipse Compare’s Algorithm for Three-way Merging</dt>
<dd>
<a href="http://www.uio.no/studier/emner/matnat/ifi/INF4290/v11/undervisningsmateriale/report.pdf">http://www.uio.no/studier/emner/matnat/ifi/INF4290/v11/undervisningsmateriale/report.pdf</a>
<br>
19 страниц, читать нужно чтобы понять, как можно тестировать, как могут существовать ошибки в алгоритме сравнения, и какие
</dd>
<br>
<dt>2007, Khanna S., Kunal K., Pierce B.C., A Formal Investigation of Diff3</dt>
<!--
Khanna S, Kunal K, Pierce BC. A formal investigation of diff3. In: Arvind V, Prasad S, eds.
FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science. Lecture
Notes in Computer Science. Springer Berlin Heidelberg. 2007, volume 4855. 485-496.
-->
<dd><a href="http://www.seas.upenn.edu/~sanjeev/papers/fsttcs07_diff3.pdf">http://www.seas.upenn.edu/~sanjeev/papers/fsttcs07_diff3.pdf</a>
<br>
12 страниц
</dd>
<br>
<dt>1986, Myers Eugene , "An O(ND) Difference Algorithm and its Variations" by , Algorithmica Vol. 1 No. 2, p 251.</dt>
<!--
Myers EW. An o(nd) difference algorithm and its variations. Algorithmica, 1986, 1(2): 251㉦.
-->
<dd><a href="http://xmailserver.org/diff2.pdf">http://xmailserver.org/diff2.pdf</a>
<br>
15 страниц, изучить, потому что это один из алгоритмов git - <a href="http://git.661346.n2.nabble.com/diff-ing-files-td6446460.html">http://git.661346.n2.nabble.com/diff-ing-files-td6446460.html</a>
</dd>
<br>
<dt>1977. Hunt, J.W. and Szymanski, T.G. "A Fast Algorithm for Computing Longest Common Subsequences.’’ Communications of ACM 20, 5 (1977), 350-353</dt>
<dd>
<a href="http://www.cs.bgu.ac.il/~dpaa111/wiki.files/HuntSzymanski.pdf">http://www.cs.bgu.ac.il/~dpaa111/wiki.files/HuntSzymanski.pdf</a>
<br>
4 страницы,
<br>
<a href="https://en.wikipedia.org/wiki/Hunt%E2%80%93McIlroy_algorithm">https://en.wikipedia.org/wiki/Hunt–McIlroy_algorithm</a>
<br>
<a href="https://ru.wikipedia.org/wiki/Наибольшая_общая_подпоследовательность">https://ru.wikipedia.org/wiki/Наибольшая_общая_подпоследовательность</a>
<br>
<a href="https://en.wikipedia.org/wiki/Longest_common_subsequence_problem">https://en.wikipedia.org/wiki/Longest_common_subsequence_problem</a>
<br>
15 страниц, читать нужно, потому что LCS это база для O(ND)
</dd>
</dl>
<h3>Литература для tree diff</h3>
<dl>
<dt>2007, Joe Tekli; Richard Chbeir; Kokou Yetongnon, Efficient XML Structural Similarity Detection using Sub-tree Commonalities</dt>
<dd><a href="http://le2i.cnrs.fr/IMG/publications/Efficient%20XML%20Structural%20Similarity%20Detection%20using%20Sub-tree%20Commonalities.pdf">http://le2i.cnrs.fr/IMG/publications/Efficient XML Structural Similarity Detection using Sub-tree Commonalities.pdf</a>
<br>
15 страниц
</dd>
<dt>1989, Kaizhong Zhang and Dennis Shasha, Simple fast algorithms for the editing distance between trees and related problems</dt>
<dd>
<a href="http://www.grantjenks.com/wiki/_media/ideas:simple_fast_algorithms_for_the_editing_distance_between_tree_and_related_problems.pdf">http://www.grantjenks.com/wiki/_media/ideas:simple_fast_algorithms_for_the_editing_distance_between_tree_and_related_problems.pdf</a>
<br />
18 страниц
<br>
Tutorial: <a href="http://www.youtube.com/watch?v=hwiks-n7vso">http://www.youtube.com/watch?v=hwiks-n7vso</a>
</dd>
<br>
<dt>1979, Kuo-Chung Tai, The Tree-to-Tree Correction Problem</dt>
<dd><a href="http://www.grantjenks.com/wiki/_media/ideas/treetotreecorrect.pdf">http://www.grantjenks.com/wiki/_media/ideas/treetotreecorrect.pdf</a>
<br>
12 страниц
</dd>
</dl>
<h3>Прочая литература</h3>
<dl>
<dt>2003, Yuan Wang David J. DeWitt Jin-Yi Cai, X-Diff: An Effective Change Detection Algorithm for XML Documents, University of Wisconsin – Madison, WI, U.S.A.</dt>
<dd>
<a href="http://www.inf.unibz.it/~nutt/Teaching/XMLDM1112/XMLDM1112Coursework/WangEtAl-ICDE2003.pdf">http://www.inf.unibz.it/~nutt/Teaching/XMLDM1112/XMLDM1112Coursework/WangEtAl-ICDE2003.pdf</a>
<br />
X-Diff: An Effective Change Detection Algorithm for XML Documents. Yuan Wang, David J. DeWitt, Jin-Yi Cai. ICDE 2003.
<br />
<a href="http://pages.cs.wisc.edu/~yuanwang/papers/xdiff.pdf">http://pages.cs.wisc.edu/~yuanwang/papers/xdiff.pdf</a>
<br />
sources on Java and C:
<br />
<a href="http://pages.cs.wisc.edu/~yuanwang/xdiff.html">http://pages.cs.wisc.edu/~yuanwang/xdiff.html</a>
<br />
</dd>
<dt>1995-01, David T. Barnard, Gwen Clarke, Nicholas Duncan, "Tree-to-tree Correction for Document Trees", Technical Report 95-372, Department of Computing and Information Science
Queen's University, Kingston, Ontario K7L 3N6, Canada</dt>
<dd>
<a href="http://research.cs.queensu.ca/TechReports/Reports/1995-372.pdf">http://research.cs.queensu.ca/TechReports/Reports/1995-372.pdf</a>
<br />
"Our algorithm allows subtree operations but is otherwise similar to that of Zhang and Shasha."
<br />
</dd>
<dt>A Semantical Change Detection Algorithm for XML</dt>
<dd><a href="http://www.inf.ufpr.br/carmem/pub/seke07.pdf">http://www.inf.ufpr.br/carmem/pub/seke07.pdf</a>
<br />
</dd>
<dt>Yan Chen, Sanjay Madria, Sourav Bhowmick, "DiffXML: Change Detection in XML Data"</dt>
<dd>
<br />
</dd>
</dl>
<br />
<br />
<a href="https://lib.lesscomplex.org/cms/tag/diffxml">https://lib.lesscomplex.org/cms/tag/diffxml</a>
<br />
<a href="http://tomx.inf.elte.hu/twiki/pub/Tudas_Labor/2012Summer/XRel_Change_SQL.pdf">http://tomx.inf.elte.hu/twiki/pub/Tudas_Labor/2012Summer/XRel_Change_SQL.pdf</a>
<br />
<a href="https://www.cise.ufl.edu/~helal/projects/ubidata/publications/sbbd-02-final.pdf">https://www.cise.ufl.edu/~helal/projects/ubidata/publications/sbbd-02-final.pdf</a>
</body>
</html>