Семантическая разница

http://martinfowler.com/bliki/SemanticDiff.html

artifacts (артифакты): текстовые и бинарные файлы
editing tools: tool allow to perform operations with artefact
объектная модель: в процессе редактирования, утилита редактирования создаёт объектную модель, над которой выполняет операции.
то есть утилита редактирования гарантированно умеет преобразовывать артфакт в объектную модель и обратно (возможно, что не весь артефакт, а работая с ним по частям, если он большой)
xml: это такой промежуточный уровень. У него есть своя модель и свой набор операций над моделью.
то есть операции более высокой модели выражаются в терминах операций над более низким уровнем модели (в данном случае - моделью XML),
а операции над XML выражаются в терминах операций редактирования модели текста
модель текста: даже тут есть варианты, может это что-то простое, типа StringBuilder с операциями Remove, Insert, Replace
а может это сложное типа модели текста LibreOffice
version control systems (системы управления версиями): often referred to as diffs from the command that can produce them in Unix.; Ну надо же, применяем мы change, а когда присматриваемся к различиям, то это и не change вовсе, а "set of differences"...
почему это не одно и то же? Как выявляют differences?
diff (and merge) algorithms (алгоритм создания патча, алгоритм применения патча)
semantic diff: A semantic diff would understand the purpose of the change, rather than just the effect.
Extract Method refactoring in a tool
With current tools they see the change in the program text, but they don't know that I did a refactoring.
when I examine the diff between the two versions it can't show me the changes in such a way that highlights the refactoring.
This also can make merges more awkward than it might if it actually knew what I was doing.
understanding: Это когда выдвигают гипотезы и ищут им подтверждения (а в идеале - аксиомы (факты) и доказательства (выводы)

Сценарии

Сценарии, где нужно выделять разницу:
1) патчинг XML
2) парчинг AST
3) сравнение дерева директорий
4) сравнение химических соединений (в биоинформатике)

Модификация последовательностей

Ну есть же пример, как это делать в простом случае (когда используется только одна модель (модель текста), а не иерархия моделей). Распиши как это работает и сделай по-аналогии.

longest common subsequence (LCS)

Если у нас деревья, то где этот алгоритм может понадобиться? При сравнении (нормализованных - отсортированных в определенном порядке, например) списков дочерних узлов?
Given strings A and B, the LCS problem is to find the longest string C that is a common subsequence of A and B. When this is done, the file comparison output can be generated by simultaneously scanning strings A, B, and C, flagging characters that appear in A but not in C one way, and flagging those that appear in B but not in C another way.
The LCS method has strong appeal: It is a simple formal statement of the problem that yields good results.

it has two basically different disadvantages. The first is that it is not necessarily the correct formalization of the problem. In the two examples below, the longest common subsequence is probably not what is desired.
Minimization of the number of inserts plus deletes is not a good formulation of the problem since the differences between any two strings can be trivially displayed as one deleted string and one inserted one.
(а что если в стоимость операции добавлять длины аргументов операции? может тогда это станет более хорошей формулировкой?)
In the second example, the LCS method does not find a moved block of characters (it never does), but the "better" display both shows the moved block and finds edits within the blocks.
The author's opinion is that there is no "correct" formulation of the problem, just as there is no "correct" way to determine which of two equivalent algebraic expressions is simpler.
(но можно же сравнить по длине алгебраического выражения или по суммарной сложности выполнения операций алгебраического выражения, пф. ты сделай и покажи людям, а до тех пор они тебя слушать не будут...)

The second disadvantage of the LCS method concerns the computational problems associated with it [1, 6, 7]. In the worst case, it can take time O(mn)-that is, time proportional to the product of the lengths of the two strings.

1978, Heckel (где могут быть использованы дифы)

http://documents.scribd.com/docs/10ro9oowpo1h81pgh1as.pdf
computationally efficient (with time linear in the file length)
For most applications the algorithm isolates differences similar to those isolated by the longest common subsequence.

We make two observations:
1. A line that occurs once and only once in each file must be the same line (unchanged but possibly moved). This "finds" most lines and thus excludes them from further consideration.
2. If in each file immediately adjacent to a "found" line pair there are lines identical to each other, these lines must be the same line. Repeated application will "find" sequences of unchanged lines.

1983, Tichy (стоимость операций, покрытия=coverages)

http://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1377&context=cstech
Что хорошего в этой статье? Есть одна строка, есть другая строка, они ищут минимальное покрытие, которое переносит первую строку во вторую. С чем я не разобрался - так это с тем, могут ли они копировать одни и те же буквы дважды из одного исходного места в два конечных места.

Есть идея, что параметры (конкретные их значения) - это последовательность микроопераций (по вставке одной буквы).
И если искать в пространстве микроопераций, то алгоритм нахождения всех микроопераций будет в точности A*.
проблема в том, что микрооперации после свёртывания дают операции боолее высокого уровня, оценки которых отличаются от суммы оценок микроопераций (ну значит изначально были выбраны неправильные микрооперации. Надо простроить стоимости операций начиная от уровня инструкций процессора (или MSIL достаточно? или операций над .Net API?) проблема с более высокими операциями - у них пропадает простота аргументов, и это затрудняет подбор аргументов)
"The storage space required for a move is negligible compared to thet of an add command"
Unfortunately, the definition of an LCS is such that the n cannot be included in the LCS.

Если у нас операции модификации определены иерархично (операция из более высокой модели преобразуется в набор операций более низкой модели), то и изменения наверное можно разделить на уровни и выявлять не сразу, а постепенно (по уровням), то есть сначала найти самые простые изменения на уровне текста, на их основе сообразить, какие изменения были проведены на уровне XML, а отсюда понять, какие изменения прикладного уровня имелись в виду.

Иерахчиность в данных

"finding the optimal matching for unordered trees is known to be NP-hard"

1977, Stanley Selkow

1977, Stanley M. Selkow, The tree-to-tree editing problem

2013, Байцерова Юлия Сергеевна, под руководством Вояковская Н.Н., Проверка избыточности и минимизация множества тестов
http://se.math.spbu.ru/SE/YearlyProjects/2013/YearlyProjects/2013/445/445-Baytserova-report.pdf

Метрика Стэнли Селкова введена им для вычисления расстояния между
помеченными упорядоченными деревьями. Помеченным упорядоченным деревом он
называет непустое конечное множество T с функцией маркировки λ, такое что:
1) Т имеет особую вершину, называемую корнем дерева
2) Остальные вершины (исключая корень) разделены на m≥0 непересекающихся
множеств Т1, … , Тm, и каждое из этих множеств является деревом. Эти
множества называются поддеревьями дерева Т
3) С каждой из вершин v ϵ Т связана метка λ(v). Метка для корня дерева Т
обозначается как λ(Т). Пусть даны два дерева: А и В с поддеревьями А1, … , Аm
и В1, … , Вn соответственно, тогда А и В равны, если λ(А) = λ(В), m = n и Аi
 = Вi

для 1 ≤ i ≤ m
Далее вводятся так называемые операции редактирования:
1) Операция замены метки L(si
, sk), примененная к дереву Т, дает дерево T* с λ(Т*)
= sk и поддеревьями Т1, … , Тm
2) Операция вставки I(A) для 0 ≤ i ≤ m и дерева А, примененная к дереву Т в i-ой
позиции, дает дерево Т* с λ(Т*) = sj
 и поддеревья Т1, … , Тi
, А, Тi+1, … , Тm
3) Операция удаления D(Ti) для 1 ≤ i ≤ m, примененная к Т в i-ой позиции, дает
дерево Т* с λ(Т*) = sj
 и поддеревьями Т1, … , Тi-1, Тi+1, … , Тm
С каждой операцией редактирования связывается неотрицательная стоимость
следующим образом. С каждой парой меток (si
, sj) связывается стоимость СL(si
, sj)
применения операции L(si
, sj). Для каждой метки si
 выражениями СI(si) и СD(si)
обозначаются стоимости применения операций I(T) и D(T) соответственно, где Т – дерево
с одной вершиной и λ(Т) = si
. Для произвольного дерева Т:
СI(Т) = ΣvϵT CI(λ(v)) и СD(Т) = ΣvϵT CD(λ(v)) 

Пусть есть деревья А и В и множество последовательностей операций
редактирования, которые, будучи примененными к дереву А, дают дерево, равное В.
Тогда вычисление расстояния между деревьями сводится к вычислению функции δ(А, В),
обозначающую минимальную сумму стоимостей для каждой последовательности.
Сложность алгоритма: O(|TA|×|TB|), где |TA|, |TB| - число листьев деревьев ТА и ТВ
соответственно.

http://web.cs.wpi.edu/~sms/cs3133/index.html

1989, Zhang, Shasha

1989, Kaizhong Zhang and Dennis Shasha, Simple fast algorithms for the editing distance between trees and related problems
http://www.grantjenks.com/wiki/_media/ideas:simple_fast_algorithms_for_the_editing_distance_between_tree_and_related_problems.pdf

http://cs.nyu.edu/cs/faculty/shasha/papers/
Этот Shasha ещё вполне живой и в сознании, у него есть email и можно ему написать (только писать надо так, чтобы ему захотелось ответить)

http://www.youtube.com/watch?v=hwiks-n7vso

1996, Chawathe

Our emerged change distilling algorithm is based on the tree differencing algorithm of Chawathe et al. (1996).
http://ilpubs.stanford.edu:8090/115/1/1995-46.pdf

delta tree

Gabriel Valiente

http://www.cs.upc.edu/~valiente/publications.html

2001, Gabriel Valiente. An Efficient Bottom-Up Distance between Trees.
http://www.lsi.upc.es/~valiente/abs-spire-2001.pdf

Что особенного в XML

There are some specific aspects of XML which deserve mention:
1) attributes, which are guaranteed to have unique names within a node;
2) IDs, which are guaranteed to be unique within a document.

но атрибуты могут быть необязательными (а обязательными могут?), или может поменяться схема, и тогда атрибут добавится или пропадёт.

Иерархичность в операциях

У утилиты редактирования (редактирования чего? артефакта, например текстового файла) есть некая объектная модель (например абстрактное синтаксическое дерево (abstract-syntax-tree, AST) текста).
с объектами этой модели можно выполнять операции. Операции преобразуют артефакт (возможно в нескольких местах)

Утилита создания патча должа:
- знать про объектную модель утилиты редактирования (и список операций на той модели)
- уметь преобразовывать артефакт в его объектную модель и обратно
- уметь выявлять операции, глядя на две версии (версии артефакта? или глядя на две версии объектной модели?)

Если есть несколько уровней моделей, то должен быть способ описывать связь между операциями разных уровней (реализация операций более высокого уровня в терминах операции более низкого уровня). Угу, например C# (для анализа доступный через reflection).
то есть факт - операция может быть описана в виде формальных символов (обозначим простейшие операции, опишем более сложные в терминах простейших)

Здесь не очень ясно, как вписывается утилита редактирования с её операциями, ведь именно операции этой утилиты приводят к изменениям нижнего уровня (например увеличение отступа блока текста)
в то же время, модель утилиты редактирования не включена в стек моделей (прикладная-xml-байты). Ну дополни, в чем проблема-то, сделай "прикладная-xml-редактор-байты" (надо бы сравнить с OSI, потому что у меня нет уровней "символов" и "концов строк" между байтами и редактором)

Если есть два разных артефакта, то можно поискать кратчайшую цепочку операций, превращающих один артефакт в другой артефакт.
что значит "кратчайшая"? Операции имеют вес, например длину записи в .diff-файле (или время выполнения. Не очень понятно, важно ли время. что лучше - одна трудоёмкая операция или много простых)
то есть поискать цепочку операций с минимальным суммарным весом.
так как набор операций ограничен и описан в модели, можно было бы поудмать о переборе все возможные вариантов цепочек (как в алгоритме A*)
неограниченными операции делает добавление параметров операции (например, если это операция набора (вставки) текста, то количество вариантов вставляемого текста бесконечно), тут важен подбор параметров (и непонятно, как его проводить, даже глядя на артефакты или модели.

Имея описание операций, можно ли выявлять (обнаруживать) их последствия?
Как восставновить отдельную операцию, если их было много?

Есть что-то общее с парсингом (там тоже могут быть разные варианты восстановления AST)
Есть что-то общее с распознаванием образов (на входе объектные модели (как структуры из элементов), а надо создать описание разницы (как последовательный набор операций (с параметрами) над элементами и над связями элементов))
Есть что-то общее с экспертными систмами (там построение и проверка гипотез)

Нужен ли ручной парсинг XML?

It's too late to analyse two XMLs by their DOM models. Information about linking of XML nodes to original character positions is already lost
so with no information about linking, it's impossible to convert editing changes in XML text into editing changes in XML nodes

Ну распарси вручную, будет у тебя информация о том, какие редактирующие изменения текста повлияли на какие элементы XML-модели.
(только где гарантия, что редактирующие измнения текста ты правильно выделил? Кругом гипотезы)

Графы в общем виде

2004, Fausto Giunchiglia; Mikalai Yatskevich; Enrico Giunchiglia, Efficient semantic matching
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.103.9186&rank=4

Как угробить много времени неясно ради каких целей

Чего пытаемся добиться, сначала придумав XML-формат, а потом разрабатывая утилиты для него?
Сценарий 1 (use case) - редактирование списка пакетов и версий пакетов в файле packages.config
ведь в моём частном конкретном случае есть всего-лишь список пакетов, линейный. А в линейном списке, который к тому же множество (то есть нет дубликатов и не важен порядок), найти различия - тривиальная задача - отсортировать два списка и сравнить. Что лишнее - удалить, чего не хватает - добавить, ... (конечно это не совсем множество, а множество узлов направленного ациклического графа зависимостей, но учет зависимостей и порядка установки берет на себя утилита nuget, пусть она и разбирается)
Сценарий 2 (use case) - редактирование файла machine.config
В принципе то же самое. Если не трогать остальное содержимое файла, то то, что меня волнует - это список провайдеров БД
Казалось бы - напиши простую частичную грамматику, которая будет конкретно этот участок выделять и обрабатывай наздоровье.
(ну а если такой секции нет, то что?)
Вот, есть же простые adhoc-решения. Нет надо выдумать несуществующий университет Subsurface Habbitation University, к нему несуществующую кафедру Nascent Intelligence Department и от его имени опубликовать докторскую на отвлечённую тему. Ну не смешно?

http://le2i.cnrs.fr/IMG/publications/Efficient XML Structural Similarity Detection using Sub-tree Commonalities.pdf
2007, Joe Tekli; Richard Chbeir; Kokou Yetongnon, Efficient XML Structural Similarity Detection using Sub-tree Commonalities