Диссертация (1145120), страница 24
Текст из файла (страница 24)
Пример и-картыАктуальность задачи слияния двух версий и-карт связана с тем, что в процессе коллективной работы нескольких пользователей один из них может потерять Интернет-соединение и продолжить работу над локальной копией икарты. При восстановлении соединения требуется объединить локальную исерверную версии и-карт40.
При этом требовалось обеспечить работу алгоритма по умолчанию для обычных пользователей и вместе с тем предоставить «продвинутым» пользователям возможности по анализу конфликтов40При этом задача синхронизации изменений пользователей, работающих с одной и-картой в режиме online решалась другими средствами.136слияния и разрешению их «вручную», то есть наиболее предпочтительнымспособом.В базовом 3DM-алгоритме была изменена процедура идентификации(matching) одинаковых узлов в разных ветках — в отличие от 3DM, в данномслучае все узлы имеют уникальные идентификаторы. С другой стороны, была введена дополнительная метрика с пороговым значением для определения«похожести» модифицированных узлов, поскольку, несмотря на одинаковыеидентификаторы, пользователи могли перестать отождествлять сильно изменившиеся узлы в локальной и серверной копиях.
Также были внесены изменения в обработку конфликтов move/move, update/update, update/delete.Модифицированный алгоритм был реализован нами на языке Haxe41 ивстроен в продукт Comapping [200].Были сформулированы следующие требования к решению задачи слияниядвух версий и-карт, часть из которых относится к модификациям алгоритмаслияния XML-файлов, а часть — к пользовательскому интерфейсу целевогопрограммного сервиса.1. Процедура слияния должна иметь полностью автоматический режимдля пользователей, которые не могут или не хотят разбираться в ее деталях. Это значит, что должен существовать способ разрешать все конфликты, обнаруженные при слиянии, автоматически, то есть по умолчанию.2.
Чтобы предотвратить потерю информации в процессе слияния, конфликтные ситуации, возникающие при удалении какой-либо части икарты в одной из её версий и при изменении этой части в другой, в автоматическом режиме должны решаться в пользу сохранения изменённой части.41Язык Haxe — это многоплатформенный язык программирования, предназначенный дляразработки Web-приложений. Он может быть использован для создания как серверной,так и клиентской частей приложения.
Подробности об этом языке см. в [274].1373. Локальная и серверная копии не являются в нашем случае симметричными — при разрешении конфликтов в автоматическом режиме предпочтение должно отдаваться серверной копии. Мы считаем, что пользователи, у которых Интернет-соединение не прерывалось, должны получить минимум сюрпризов после выполнения процедуры слияния.Далее мы будем использовать термин локальная версия для обозначения версии и-карты, с которой пользователь работает локально, послепотери соединения с Интернетом, а термин серверная версия — чтобыобозначить версию и-карты, с которой работают пользователи, сохранившие Интернет-соединение.4.
Процедура слияния должна иметь «продвинутый» режим использования, то есть информация о конфликтах должна сохраняться и показываться по требованию пользователя, чтобы у него была возможностьпри необходимости разрешить конфликты способом, отличным отпринятого по умолчанию.5. Созданное решение должно быть встроено в Comapping, при этом последний сохраняет историю изменений и-карты (эта история позволяетпроследить, как, кем и когда изменялась и-карта); в связи с этим нельзясохранить результат слияния, удалив предыдущую серверную версию,так как иначе история всех предыдущих изменений станет бесполезной.
Поэтому необходимо создавать edit-скрипт для перевода серверной версии в целевую.6. Реализация 3 way merge. Поскольку в нашем случае исходный XMLфайл может быть доступен для алгоритма слияния, было целесообразнореализовать 3 way merge парадигму, так как она гарантирует лучшеекачество результата.Рассмотрим теперь то, как 3DM-алгоритм был модифицирован в рамкахреализации задачи слияния и-карт в Comapping.138Изменение процедуры идентификации. Мы предполагаем, что у каждогоузла и-карты есть уникальный идентификатор (id). Поэтому процедура идентификации по сравнению с 3DM-алгоритмом упрощается: у нас при объединении версий сопоставляются друг другу только узлы с одинаковыми id. Сдругой стороны, id узлов и-карты не видны пользователям и-карт, поэтому впроцессе редактирования локальной и серверной копий они могут перестатьсвязывать старое и новое содержимое узла, хотя эта связь остаётся в виденеизменного id.
В таких случаях сопоставлять две версии узла друг другу неимеет смысла, несмотря на то, что у них одинаковые id. Поэтому в процедуреидентификации мы дополнительно проверяем «похожесть» сопоставленныхпо id узлов с помощью определённой метрики. Метрика «похожести» узлов,предложенная для данного алгоритма, определяется тремя следующими параметрами: местоположением узла в ветке (изменилось ли оно относительноместоположения узла в базовой версии), сходством содержимого узлов (задаётся числом в интервале [0, 1]) и «похожестью» списков детей узлов (задаётся числом в интервале [0, 1]). Сходство содержимого определяется схожестью плоского текста в узлах (двух строк без учёта регистра, форматирования, иконок и т.д.). Для сравнения текста в узлах мы используем алгоритмнахождения Q-расстояния между строками [429]42 с различным значениемпараметра Q в зависимости от средней длины сравниваемых слов: Q равно 2,42Самый простой способ вычислить разницу (расстояние) между строками — это определить для каждого алфавитного символа количество его вхождений в обоих строках, а также подсчитать модуль разности и сложить полученные по всем символам числа.
Однакооказывается, что чем больше длина сравниваемых строк, тем выше вероятность назватьпохожими совершенно различные строки. Поэтому в [262] предлагается использоватьдругую метрику — Q-расстояние между строками. Q-расстояние определяется аналогичноприведённой выше простой метрике, только подсчитывается количество появлений встроке не отдельных символов, а всевозможных блоков длины Q. Применяя этот метод,можно использовать различные значения Q в зависимости от размера сравниваемых строк(чем длиннее строки, тем больше Q), что даёт лучшие результаты при сравнивании больших строк. Более формально процесс вычисления Q-расстояния между двумя строкамиописывается так: для каждой строки строится ассоциативный вектор, в котором всевозможным подстрокам длины Q сопоставляется количество раз, которое эта подстрокавстречается в исходной строке; Q-расстояние равно модули разности этих векторов.
Qрасстояние равно 0, если строки равны.139если длина меньше 50 символов, Q равно 4, если длина от 50 до 150 символов, Q равно 6, если длина от 150 до 500 символов, и Q равно 8, если длинабольше 500 символов. «Похожесть» списка детей узлов мы определили как2*M/N, где M — это число пар детей, совпадающих по id, N — общее количество детей у обоих узлов. Пустые списки детей считаем похожими со значением 1.
В зависимости от значения первого параметра мы определяемнижние пределы для двух других параметров, и если «похожесть» содержимого узла и «похожесть» списка детей опускается ниже этих пределов, то узлы не идентифицируются как одинаковые. Значения пределов следующие:если узел был перемещён в ветке, то пороговое значение определяется равным 0.3 для обоих параметров, если не был перемещён — то 0.1. Данные коэффициенты были выбраны с учётом следующих соображений: (i) в первомслучае пределы должны быть выше, поскольку, перемещая узел, пользователь, как минимум, перестаёт связывать его с прежним местоположением, ипоэтому имеет смысл требовать большей схожести сопоставляемых узловдля положительной идентификации; (ii) в целом коэффициенты должны бытьзанижены, поскольку наша цель — идентифицировать отрицательно толькоочевидно «разошедшиеся» узлы.Неравнозначность локальной и серверной копий.
3DM-алгоритм не делаетразличий между двумя сливаемыми файлами, поэтому он часто в процессесвоей работы меняет их местами, исходя из внутренних, технических соображений. В нашем случае этот подход не может быть использован, как указывалосьвыше.Поэтому,вчастности,симметричныеконфликты(move/move, update/update), а также ситуацию спорного порядка узлов мыразрешаем всегда в пользу серверной версии. Таким образом, в случае конфликта update/update узлу присваивается его содержимое из серверной копии, а в случаях, когда для двух узлов невозможно определить, в каком порядке они должны следовать в списке детей, то они сохранят такой же порядок следования, как в серверной версии.140Разрешение конфликта move/move.
3DM-алгоритм разрешает конфликтmove/move слиянием поддеревьев из двух версий и копированием результатав обе локации при порождении целевой версии. Однако при вложенных конфликтах такой подход ведёт, во-первых, к множественному раскопированиюодних и тех же узлов, а во-вторых, к дублированию конфликтов (дублируется, как минимум, каждый конфликт в скопированном поддереве). Поэтомумы разрешаем этот конфликт по умолчанию помещением «слитого» поддерева только в одну локацию — ту, в которой он оказался в серверной версии.Однако у пользователя остаётся возможность разрешить его другим способом.Обработка конфликта update/delete.
Как уже говорилось выше, наш механизм синхронизации двух версий и-карты должен избегать потерь изменений, поэтому при разрешении конфликта update/delete мы, в отличие от 3DMалгоритма, по умолчанию оставляем поддерево в целевой версии. Пользователь может выбрать и вторую альтернативу разрешения данного конфликта.Изменения в edit-скрипте. 3DM-алгоритм порождает edit-скрпит, переводящий исходную версию карты в целевую. В нашем случае это не подходит,как было указано выше.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
