ПРОГРАММИРОВАНИЕ, 2011, No 6, с. 56-66
ЯЗЫКИ И СИСТЕМЫ ПРОГРАММИРОВАНИЯ
УДК 681.3.06
О ЗАДАЧЕ СЛИЯНИЯ КАРТ ПАМЯТИ (MIND MAPS) ПРИ КОЛЛЕКТИВНОЙ РАЗРАБОТКЕ
© 2011 г. Д.В. Кознов, Е.В. Ларчик, М.М. Плискин, Н.И. Артамонов Санкт-Петербургский государственный университет, 198504 Санкт-Петербург, Петергоф г., Университетский просп., 26
E-mail: dkoznov@yandex.ru Поступила в редакцию 13.06.2011 г.
В данной работе представлено решение задачи слияния карт памяти (Mind Maps) в контексте процесса коллективной Интернет-разработки таких карт. Эта задача актуальна, например, в ситуации, когда один из разработчиков теряет Интернет-соединение, но продолжает изменять карту памяти локально, и его товарищи также меняют ее. Таким образом, при восстановлении Интернет-соединения возникает потребность в слиянии локальной и серверной копий карты памяти. Задача решена на основе известного алгоритма слияния XML-файлов 3DM, модифицированного в соответствии с особенностями нашей задачи: (1) необходимость двух режимов работы -по умолчанию и с предоставлением пользователю возможности самостоятельно разрешать конфликты; (2) необходимость максимального сохранения изменений, сделанных в поддеревьях при разрешении конфликтов Update/Delete; (3) несимметричность сливаемых деревьев (серверная копия считается более приоритетной); (4) необходимость применения edit-скрипта к исходной версии для сохранения истории изменений; (5) наличие уникальных идентификаторов у узлов сливаемых деревьев (то есть более упрощенная процедура идентификации) и потребностью „разносить" узлы с одним и тем же значением идентификатора, но сильно разным содержанием.
1. ВВЕДЕНИЕ1
Задача слияния (merge) двух разных версий одного и того же файлового актива является классической задачей конфигурационного управления (configuration management): два или более человек меняют один и тот же актив независимо друг от друга и после этого необходимо объединить сделанные изменения в рамках единой версии актива. Слияние текстовых файлов является решенной задачей (см., например, работу [1]), и соответствующие алгоритмы входят в многочисленные промышленные средства версионного контроля, например, в CVS/Subversion. Однако для более сложных структур данных - XML-файлов, UML-моделей и т.д. - эта задача требует более
хРабота выполнена при поддержке гранта Российского фонда фундаментальных исследований (РФФИ) № 11-01-00622-а.
сложных решений, так как простое текстовое слияние часто нарушает структуру актива -дерева, графа и пр.
Задача слияния XML-файлов стала актуальна в силу широкого использования данного формата для представления различных данных, совместно используемых в Интернете. Сюда относится и совместная разработка офисных документов (существуют многочисленные внутренние XML-форматы документов -OpenXML, БоеБоок и др.), и синхронизация XML-данных в условиях ограниченной сетевой пропускной способности (например, для мобильных устройств) и пр.2 В настоящее время разработано несколько алгоритмов решения задачи слияния XML-файлов [2-6]. Существуют также практические реализации
2Подробный обзор различных практических задач, где появляется необходимость сливать ХМЬ-файлы, приводится в работе [2].
этой задачи: средство с открытым кодом 3DM [7], XML Diff and Merge - свободно распространяемое Java-средство от компании IBM [8], а также коммерческий продукт DeltaXML [9]. Все они позволяют получить разницу между двумя XML-файлами, а также слить их в один файл. Кроме того, существует система контроля изменений документов So6 [10], которая позволяет нескольким пользователям редактировать XML-файлы одновременно. Таким образом, можно сказать, что в общем виде данная проблема решена. Однако конкретные практические задачи формулируют особые требования к слиянию XML-файлов, что влечет необходимость модификации существующих алгоритмов. Одной такой задачей является слияние карт памяти (Mind Maps), представленных в виде XML, в процессе их коллективной разработки Интернет-средствами.
Карты памяти (Mind Maps) - это графическая нотация и метод, предназначенные для работы со знаниями в самых разных областях: в обучении, бизнесе, при написании книг, статей, в научной деятельности, при планировании личных и семейных мероприятий, при психологическом тестировании и т.д. Данный подход был предложен Тони Бьюзеном в конце 70-х годов прошлого века [11] и доказал свою состоятельность. В связи с этим появилось много программных продуктов, поддерживающих карты памяти - Freemind [12], MindManager [13] и др.3 В последнее время стали активно развиваться Интернет-средства, поддерживающие коллективную работу с картами памяти - Comapping [15], Mindomo [16] и MindMeister [17]. Не смотря на то, что эти средства хранят карты памяти на сервере в базе данных, в них, как правило, реализован импорт/экспорт в XML-представление. Однако до настоящего момента в них отсутствует возможность слияния двух версий одной и той же карты памяти, хотя ее можно реализовать на основе существующих подходов к слиянию XML-фалов. Данная возможность необходима, например, когда группа пользователей работает
3Полный список программных средств поддержки карт памяти можно найти здесь [14].
с одной картой памяти в online-режиме и один из них теряет подключение к Интернету (например, он находится в дороге и работает на своем ноутбуке) и продолжает работу над картой памяти локально. В это же время его товарищи, также работая с этой картой, изменяют серверную версию. После восстановления Интернет-подключения необходимо слить вместе две версии.
В рамках данной работы известный алгоритм слияния XML-файлов 3DM [3] был применён для решения задачи слияния карт памяти в продукте Comapping [15]. Алгоритм был модифицирован так, чтобы были удовлетворены специфические требования Comapping: обеспечение работы алгоритма по умолчанию для обычных пользователей и, вместе с тем, обеспечение „продвинутых" пользователей возможностями проанализировать конфликты слияния и разрешить их вручную" наиболее предпочтительным способом. В алгоритме 3DM была также изменена процедура идентификации (matching) одинаковых узлов в разных ветках, так как в отличие от 3DM в нашем случае все узлы имеют уникальные идентификаторы. С другой стороны, мы ввели дополнительную метрику идентификации с пороговым значением для определения похожести" модифицированных узлов, поскольку, не смотря на одинаковые идентификаторы, пользователи могли перестать отождествлять сильно изменившиеся узлы в локальной и серверной копиях. Также мы внесли изменения в процедуры обработки конфликтов слияния Move/Move, Update/Update, Update/Delete.
Статья организована следующим образом. В разделе 2 делается обзор карт памяти и продукта Comapping. В разделе 3 в общем виде обсуждается задача слияния XML-файлов, вводятся основные термины, а также обсуждается метод определения Q-расстояния между строками, который часто используется при слиянии текстовой информации в узлах сливаемых XML-файлов. В разделе 4 уточняется постановка задачи. В разделе 5 дается обзор имеющихся средств для слияния XML-файлов и обосновывается выбор алгоритма 3DM как наиболее подходящего с
учетом специфики нашей задачи. Наконец, в этом разделе были описаны те расширения, которые мы внесли в 3БМ-алгоритм.
2. ТИПИЧНЫЕ СРЕДСТВА РАБОТЫ С КАРТАМИ ПАМЯТИ НА ПРИМЕРЕ COMAPPING
В начале 70-х годов прошлого века английским психологом Тони Бьюзеном была предложена техника работы с информацией, основанная на использовании карт памяти (Mind Maps ) [11]. Карта памяти представляет собой диаграмму с очень простой нотацией. В центре диаграммы находится главный элемент, олицетворяющий собой ключевую идею или концепцию. Этот элемент затем соединяется с другими элементами, поясняющими и детализирующими его, которые располагаются вокруг и т.д. (рис. 1). Карты памяти имеют следующие достоинства - лёгкость восприятия и запоминания информации, экономию времени на поиск в тексте ключевых слов (благодаря тому, что они более заметны и связаны между собой ясными и уместными ассоциациями), развитие у человека системного мышления в процессе создания таких карт и т.д.
Далее мы опишем Web-приложение Comapping - типичный инструмент в этой области. Читателю будет проще познакомиться с общими принципами и проблемами программной разработки карт памяти на основании описания
4
конкретного примера инструмента.
Для представления карт памяти Comapping использует древовидную нотацию, в которой уточнение концепций происходит слева направо (так называемый left-to-right mindmapping), и, соответственно, главный элемент карты памяти находится левее остальных (см. рис. 2). Такая нотация в сочетании с алгоритмом автоматического перераспределения элементов на экране облегчает чтение и понимание карты.
Comapping также включает в себя следующие возможности: связывать с элементами карты
4Продукт Comapping является результатом сотрудничества датской компании Area9 и петербургской компании ЗАО „ ЛАНИТ-ТЕРКОМ", а также Санкт-петербургского государственного университета. Исследования по применению продукта в образовательном процессе поддержаны компанией Hewlett-Packard.
памяти файлы и заметки, проверять правописание текста в узлах карты памяти; осуществлять текстовый поиск и фильтрацию элементов карты, а также публикацию карт в блогах и на сайтах; печать карты любых размеров; экспортирование карты памяти в форматы PDF, HTML, RTF, SVG, импорт/экспорт в форматы других средств работы с картами памяти (FreeMind, MindManager).
Кроме этого, Comapping фокусируется на предоставлении максимально удобных средств для совместной работы пользователей: несколько пользователей одновременно могут открыть одну и ту же карту для просмотра или редактирования, при этом можно видеть, какие участки карты редактируют в данный момент другими пользователями (рис. 3), можно также общаться во встроенном чате; есть средства для объединения пользователей в группы, а также для изменения прав доступа к карте памяти сразу всем участникам группы; существует механизм email-оповещений об изменениях карты памяти другими пользов
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.