Сравнение коллекций является одной из
Сравнение коллекций является одной из традиционных задач сопоставления версий и анализа изменений при оптимистической репликации структурированных данных и документов [1]. Программные средства сравнения, предоставляющие подобную функциональность, являются неотъемлемыми компонентами современных систем контроля версий. Подобные системы нашли применение в задачах управления конфигурацией программного обеспечения (software configuration management), управления мобильными базами данных (mobile database management), организации цифровых архивов, документооборота (document management), построения платформ и систем коллективной инженерии (collaboration workspaces, concurrent engineering environments), управления web–контентом (content management). Так, среди наиболее популярных решений коллективной программной инженерии следует отметить системы управления версиями ПО: CVS, Subversion, OpenCM, BitKeeper, Visual SourceSafe, Perforce, Synergy CM и т.п. [2]. Оформленные в виде программных утилит с пользовательским интерфейсом средства сравнения имеют многочисленные самостоятельные приложения. Например, утилиты командной строки cmp, diff, sdiff, diff3 известного проекта GNU [3] позволяют определить первый отличный байт для заданной пары файлов, вычислить минимальное множество отличий между двумя файлами, интерактивно объединить два файла в один общий, а также представить структуру изменений при одновременной модификации одного файла двумя пользователями или программами и сгенерировать файл, являющийся результатом слияния двух версий относительно базовой с предупреждениями о возникших конфликтах. GNU Diffutils работают преимущественно с текстовыми файлами, для бинарных файлов они могут лишь констатировать факт сходства или различия. Пакет JojoDiff включает набор утилит для сравнения бинарных файлов: jdiff — сравнивает два файла, jpatch — реконструирует второй файл из первого на основе списка изменений, сгенерированного jdiff, jsync — синхронизирует файлы или директории между двумя компьютерами.
Приложения KDiff, Xxdiff, gtkdiff, tkdiff, Diffstat, ExamDiff предоставляют средства визуального сравнения произвольных текстовых файлов. Известная утилита UN*X dirdiff позволяет сравнивать деревья каталогов и синхронизировать изменения между ними. Развитые графические средства сравнения текстовых файлов, а также синхронизации директорий включает в себя популярный файловый менеджер TotalCommander. Перечисленные программные средства производят сравнение произвольных текстовых или бинарных файлов без учета семантики их содержимого. Ряд программных утилит и приложений позволяет сравнивать документы в различных текстовых или бинарных форматах, HTML, XML, Multimedia данные. В частности, учитывая типизацию отдельных термов в текстовых данных, утилита spiff позволяет адекватно сравнивать числовые данные с плавающей точкой, а также исходные тексты на популярных языках программирования. Набор приложений CSDiff/CS-ExcelDiff/CS-HTMLDiff позволяет установить и отобразить изменения документов, представленных в форматах Microsoft Word, Microsoft Excel, HTML. Программы ExamDiff Pro, Compare Suite, Diff Doc поддерживают сравнение документов в различных форматах популярных офисных приложений, PDF, HTML, в том числе документов, хранящихся в архивах. Интегрированные пакеты Microsoft Office 2003 и 2007 имеют развитые встроенные средства сравнения и слияния версий документов. Наборы средств diffxml, 3dm, XMLComparator обеспечивают сравнение, коррекцию и слияние документов в XML разметке. Программы Image Comparer, ImageDupeless специализируются на сравнении графической, а Similarity — звуковой информации, хранимой в файлах наиболее распространенных форматов. Средства сравнения реляционных данных позволяют определить изменения схем и содержимого популярных баз данных. В частности, программа DataDiff находит отличающиеся записи в альтернативных базах данных под управлением MySQL, утилита mysqldiff — находит отличия в определениях таблиц СУБД MySQL, утилита MDBDiff позволяет выявить структурные изменения в базах данных Microsoft Access, Oracle SchemaDiff — изменения в схемах Oracle, pgdiff — изменения в реляционных таблицах двух баз данных под управлением PostgreSQL с возможной генерацией команд конвертации схемы одной базы данных в другую.
Универсальная программа с web-интерфейсом SQLDiff устанавливает и показывает отличия между двумя SQL таблицами для распространенных реляционных СУБД (Oracle, DB2, PostgreSQL). Ряд программных компонентов сравнения обеспечивает работу с объектными моделями. В частности, библиотека difflib, реализованная на Python, позволяет вычислять изменения в объектных данных. Программный модуль UMLDiff [4], функционирующий в среде программной инженерии Eclipse, определяет структурные изменения статических UML моделей. Более подробные сведения о вышеперечисленных утилитах и библиотеках, а также об аналогичных программных средствах сравнения данных и документов можно найти в Интернет-обзорах и каталогах [5–8]. Несмотря на разнообразие приложений, в которых математические методы и программные средства сравнения находят содержательное применение, следует отметить строгую функциональную специализацию и определенную ограниченность перечисленных выше средств. Главной причиной этого является ориентация на конкретные классы приложений с предопределенной семантикой. Безусловно, подобная направленность делает данные средства чрезвычайно полезными при решении конкретных прикладных задач, однако не дает возможность распространить их на нетривиальные масштабные междисциплинарные информационные модели, описываемые сотнями (иногда тысячами) типами данных и ограничений. Более того, часто и в простых случаях результаты сравнения оказываются неадекватными решаемой задаче. Например, сравнение документов в разметке XML позволяет идентифицировать изменения, связанные с появлением, удалением, модификацией элементов, однако не фиксирует изменения положения элементов относительно друг друга. Приложения, для которых порядок следования элементов данных существенен, не могут доверительно использовать результаты сравнения. Например, приложение, фиксирующее изменения в рейтинговом списке ученых, упорядоченном в соответствии с показателем результативности научной деятельности, не может корректно интерпретировать результаты сравнения и нуждается в более адекватном способе представления изменений в соответствии с семантикой модели данных. В обобщенной постановке задача сравнения обычно не рассматривается, хотя все упомянутые выше виды документов, файлов, схем баз данных могли бы быть прозрачно представлены информационными моделями/метамоделями, и их сравнение могло бы быть проведено на более общей методологической и инструментальной основе.
Подобная постановка является критично важной для приложений семантической реконсиляции, оперирующих произвольными типами данных при заданной прикладной модели с формально описанными структурой и алгебраическими ограничениями. В подходе, предложенном и развитом в наших работах [9–12], вычисление изменений данных рассматривается в качестве ключевого элемента реконструкции конкурентных транзакций и их семантически согласованной реконсиляции на основе заданной информационной модели. Учет семантики модели позволяет на формальной, математически строгой основе провести сравнительный анализ реплицируемых данных и выработать непротиворечивые (семантически корректные) и содержательные (обеспечивающие полноту итоговой транзакции) политики реконсиляции. В определенном смысле подход следует важному доминирующему направлению информационных технологий, предполагающему активное использование моделей на всех этапах программной инженерии и анализа информации. Деятельность международных сообществ по разработке соответствующих информационных стандартов и многофакторных прикладных моделей, прежде всего, в рамках ISO 10303 STEP [13] и OMG MDA [14] также следует этой тенденции. В настоящей работе обсуждаются проблемы сравнения коллекций — стандартных типов данных, поддерживаемых популярными языками моделирования и программирования, повсеместно используемых в приложениях и представляющих собой наиболее сложные и интересные конструкции для рассматриваемых задач реконсиляции. Главным лейтмотивом статьи является вопрос об адекватности способов представления изменений типам коллекций, а также о выборе эффективных алгоритмов нечеткого сравнения коллекций в соответствии с их семантикой.
