Содержание к диссертации
Введение
Глава 1. Анализ задачи восстановления структуры группового телеметрического сигнала 9
1.1. Понятие телеметрии 9
1.2. Телеметрические параметры и телеметрические сообщения . 11
1.3. Групповой телеметрический сигнал. Анализ особенностей формирования 14
1.4. Обобщенный процесс анализа телеметрической информации . 19
1.5. Анализ задачи восстановления структуры группового телеметрического сигнала 22
1.6. Анализ существующих решений 24
1.7. Выводы 38
Глава 2. Трехэтапная процедура восстановления структуры группового телеметрического сигнала. Модель формата кадра и графовая модель ГТС 40
2.1. Трехэтапная процедура восстановления структуры группового телеметрического сигнала 40
2.2. Модель формата кадра группового телеметрического сигнала . 44
2.3. Символьное представление медленноменяющихся телеметрических параметров 47
2.4. Графовая модель группового телеметрического сигнала 51
2.5. Выводы 57
Глава 3. Методы восстановления структуры группового телеметрического сигнала 60
3.1. Метод экспресс-поиска структуры группового телеметрического сигнала 60
3.2. Метод последовательного восстановления структуры группового телеметрического сигнала 68
3.3. Метод комплексного поиска структуры группового телеметрического сигнала 95
3.4. Выводы 105
Глава 4. Экспериментальные исследования 107
4.1. Описание реализации комплекса программ восстановления структуры ГТС 108
4.2. Экспериментальные исследования на модельных данных 112
4.3. Экспериментальные исследования на реальных данных 128
Заключение 132
Литература
- Групповой телеметрический сигнал. Анализ особенностей формирования
- Модель формата кадра группового телеметрического сигнала
- Метод последовательного восстановления структуры группового телеметрического сигнала
- Экспериментальные исследования на модельных данных
Введение к работе
Актуальность работы. Современный этап развития телеметрических систем характеризуется быстрым ростом объема передаваемой информации. В настоящее время для ракетно-космической техники (РКТ) количество передаваемых параметров исчисляется тысячами, а длины временных рядов, определяющих поведение параметров, превышают миллион отсчетов. Наряду с объемом передаваемой информации изменилась и сложность передаваемого потока телеметрии: с целью оптимального использования ограниченных по пропускной способности каналов связи стали применяться разнообразные схемы коммутации измерительной информации. В связи с этим возникает задача контроля и восстановления структуры передаваемых информационных потоков. В рамках этой задачи, как правило, предполагается, что структура анализируемого потока неизвестна, и ее необходимо восстановить.
В работе рассматривается ограниченный класс телеметрических потоков, которые обладают сложной циклической структурой и поступают с объектов РКТ. В ракетно-космической отрасли такой поток принято называть групповым телеметрическим сигналом (ГТС). Частичные знания о структуре каждого ГТС известны и регламентируются стандартом, который определяет общие правила формирования сигнала. Полная информация о структуре является для каждого объекта РКТ частной и выбирается в соответствии с целями и задачами испытаний и штатной эксплуатации.
Существует определенный задел в литературе, представленный работами Балтрашевича В. Э., Васильева А. В., Кукушкина С. С. и опытно-конструкторскими работами, проводимыми в научно-исследовательском центре представления и контроля информации по космодрому Плесецк, однако, большинство из существующих решений находятся на этапе развития, когда большая часть действий выполняется непосредственно экспертом. При этом практически не используется информация о ранее накопленных ГТС с известными структурами. Как следствие, восстановление структуры одного ГТС с неизвестной структурой от объекта РКТ в среднем требует не менее нескольких часов. Необходимо подчеркнуть, что это труд высококвалифицированных специалистов, нехватка которых является острой проблемой. Таким образом, является актуальной задача разработки методов и моделей восстановления структуры ГТС, которые позволят сократить время восстановления.
Цель и задачи исследования — разработка методов и моделей, обеспечивающих сокращение времени восстановления структуры ГТС с неизвестной структурой за счет повышения степени автоматизации восстановления и использования информации о ранее накопленных ГТС с известными структурами.
Для достижения поставленной цели были решены следующие задачи:
1) анализ существующих решений задачи восстановления структуры ГТС
с неизвестной структурой и выработка путей преодоления их основных недостатков;
разработка трехэтапной процедуры восстановления структуры ГТС с неизвестной структурой;
разработка метода экспресс-поиска структуры ГТС с использованием информации о ранее накопленных ГТС с известными структурами;
разработка метода последовательного восстановления структуры ГТС с неизвестной структурой, базирующегося на анализе бинарного представления ГТС и позволяющего определить типы медленноменяющихся телеметрических параметров;
разработка графовой модели ГТС, учитывающей структуру ГТС и поведение входящих в его состав параметров, и метода комплексного поиска структуры ГТС, использующего данную модель;
программная реализации предлагаемой трехэтапной процедуры восстановления структуры ГТС.
Объектом исследования диссертационной работы является процесс восстановления структуры ГТС.
Предметом изучения являются методы и алгоритмы, позволяющие осуществить восстановление структуры ГТС, а также модели описания ГТС и его структуры.
Методы исследования. Теоретическая часть работы выполнена на основе численных методов математической статистики, машинного обучения, теории графов и алгоритмов на строках. В экспериментальной части работы применяются численные методы и методы имитационного моделирования. Для выполнения экспериментальной части создан и зарегистрирован в реестре программ для ЭВМ программный комплекс.
Научную новизну работы составляют следующие положения:
Трехэтапная процедура восстановления структуры ГТС с неизвестной структурой, включающая этап экспресс-анализа (применяется метод экспресс-поиска), этап полного анализа (метод последовательного восстановления) и этап уточнения (метод комплексного поиска).
Метод экспресс-поиска структуры ГТС с неизвестной структурой на базе аппроксимации распределения информационных слов ГТС. Метод позволяет для анализируемого ГТС при минимальном количестве априорной информации об его структуре определить набор потенциальных структур, представленных среди ранее накопленных ГТС с известными структурами.
Метод последовательного восстановления структуры ГТС с неизвестной структурой, позволяющий на основе анализа бинарного представления ГТС в автоматическом режиме восстановить его структуру и метод включает группу алгоритмов на основе корреляционного анализа и анализа характеристик изменения слов в кадре для построения модели формата кадра и алгоритм определения типов медленноменяющихся телеметрических параметров с использо-
ванием метрики неточного сравнения символьного представления временных рядов.
4) Графовая модель ГТС на базе атрибутированного графа отношений, учитывающая как структуру ГТС, так и поведение его составляющих параметров. Метод комплексного поиска структуры ГТС с неизвестной структурой на базе сравнения графовых моделей ГТС с использованием редакционного расстояния. Метод позволяет с целью уточнения структуры анализируемого ГТС определить наиболее схожие ГТС среди ранее накопленных с известными структурами.
Практическая значимость работы заключается в разработке алгоритмов и программ восстановления структуры ГТС, позволяющих сократить время, необходимое на восстановление структуры, в среднем в 4 раза.
Материалы диссертационной работы были использованы при выполнении опытно-конструкторской работы (ОКР), посвященной обработке измерительной информации РКТ и их оснащения (шифр «Модернизация»), и при выполнении ОКР, посвященной системе комплексного анализа результатов пусков РКТ (шифр «Математика-ПИК»), проводимых в ОАО «Научно-инженерный центр Санкт-Петербургского электротехнического университета» («НИЦ СПб ЭТУ»). Результаты работы внедрены в в/ч 85487 (ОКР «Математика-ПИК») и в в/ч 13991-П (ОКР «Модернизация»).
Работа поддержана программой в рамках конкурсов научных достижений аспирантов СПбГЭТУ «ЛЭТИ» в 2011 году.
Научные положения, выносимые на защиту:
трехэтапная процедура восстановления структуры ГТС;
метод экспресс-поиска структуры ГТС;
метод последовательного восстановления структуры ГТС, включающий набор алгоритмов построения модели формата кадра ГТС и алгоритм определения типов медленноменяющихся телеметрических параметров;
графовая модель ГТС и метод комплексного поиска структуры ГТС;
Апробация работы. Основные результаты диссертационной работы докладывались и обсуждались со специалистами ОАО «НИЦ СПб ЭТУ», на кафедре математического обеспечения и применения ЭВМ СПбГЭТУ, а также на следующих конференциях:
14-я всероссийская конференция «Математические методы распознавания образов» (ММРО-14), Владимирская обл., г. Суздаль, 2009 г.
двенадцатая национальная конференция по искусственному интеллекту с международным участием (КИИ-2010), г. Тверь, 2010 г.
XIV международная конференция по мягким вычислениям и измерениям (SCM'2011), Санкт-Петербург, 2011 г.
научные сессии Национального исследовательского ядерного университета (НИЯУ) «МИФИ», Москва, 2010, 2011 и 2012 гг.
научно-технические конференции профессорско-преподавательского
состава СП6ГЭТУ, Санкт-Петербург, 2010, 2011 и 2012 гг.
Публикации. Материалы диссертации опубликованы в 11 печатных работах, из них 2 статьи в рецензируемых журналах, 1 статья в нерецензируемых журналах и 7 докладов в сборниках трудов конференций.
Разработанный автором комплекс анализа структур данных был зарегистрирован в реестре программ для ЭВМ (свидетельство № 2011616384).
Структура и объем диссертации. Диссертация состоит из введения, 4 глав, заключения и библиографии. Общий объем диссертации 147 страниц, из них 134 страниц текста, включая 36 рисунков. Библиография включает 99 наименований на 13 страницах.
Групповой телеметрический сигнал. Анализ особенностей формирования
Измеряемые физические величины (t) разделяются на постоянные и переменные во времени. Для постоянной величины достаточно определить лишь одно ее мгновенное значение. Переменные во времени величины могут быть детерминированными и случайными. При детерминированном характере, например, гармоническом, изменения мгновенного значения (t) неизвестной может быть амплитуда. Закон изменения параметра может быть определен по мгновенным значениям i. Наиболее общим является телеметрирование параметров со случайным законом изменения величины (t).
Телеметрируемые параметры классифицируются по ряду признаков. По характеру изменения во времени ТМП делятся на функциональные и сигнальные. Функциональные параметры f являются непрерывными функциями времени, число градаций параметров по уровню бесконечно. Плавно изменяются многие физические параметры, например температура, давление, влажность и т. д. Сигнальные параметры c характеризуются скачкообразным изменением во времени значения физической величины. К ним относятся, например, параметры «включено–выключено», «норма–не норма». «да–нет» и т. п.
В зависимости от скорости изменения во времени ТМП делятся на медлен-номеняющиеся параметры (ММП) и быстроменяющиеся параметры (БМП). Первые характеризуются шириной спектра от 0 до 50 Гц, а вторые имеют верхнюю границу спектра от единиц до десятков и сотен кГц. К медленно-меняющимся параметрам относятся температура твердых и жидких тел и газов, давление, механические и угловые перемещения, скорость, ускорение и т. д. В группу быстроменяющихся параметров входят вибрации, акустические шумы и переходные процессы в различных системах. Информация о ТМП передается в виде телеметрических сообщений S(t).
Замечание. Подавляющее большинство ТМП в ракетно-космической отрасли является медленно меняющимися функциями времени [7].
Определение 1.3. Под телеметрическим сообщением понимается сообщение, передаваемое телеметрической системой, несущее информацию о контролируемых событиях и процессах, а также служебную информацию.
Для современной телеметрии характерны три вида сообщений: 1) сообщения о событиях типа «включено–выключено», «да–нет», «работает – не работает» и т. п. Показателем таких событий является состояние объекта или системы на данный момент времени, в который произошло событие; 2) сообщения, несущие информацию о величинах телеметрических параметров в определенный момент времени. Такие сообщения содержат сведения об отдельных измерениях физических величин; 3) сообщения о процессах конечной длительности, представленных в непрерывной или дискретной форме. С помощью датчиков ТМП функционального типа преобразуются в первичные сигналы S(t). Так как подавляющее большинство современных и перспективных телеметрических систем являются цифровыми, то, не умаляя общности, будем считать, что такие первичные сигналы представляются в дискретно-квантованном виде. При дискретно-квантованном представлении осуществляется квантование и во времени, и по амплитуде одновременно [8]. В результате этого представления непрерывно меняющийся сигнал S(t) заменяется в дискретные моменты времени t дискретными по амплитуде уровнями S. При этом вместо действительного значения сигнала после преобразования выдается значение либо ближайшего к нему нижнего уровня, либо ближайшего верхнего уровня. В таком случае, каждое телеметрическое сообщение — это информационное слово, длина в битах которого определяется разрядностью установленного двоичного аналого-цифрового преобразователя.
Таким образом, измерения ТМП как последовательность информационных слов представляется в виде временного ряда: C = (c1, . . . ,cn), где ci — это измерение параметра в момент времени ti, n — это количество измерений данного параметра.
В рамках работы телеметрической системы формируется ТМП c различным функциональным назначением. Это может быть угловая скорость объекта, давление в камере сгорания, контактный параметр включения системы охлаждения, кодовый параметр блока разведения и прочие. Будем считать, что множество типов априори задано как конечный алфавит .Для идентификации каждому типу ТМП ставится в соответствие буква t . Здесь необходимо подчеркнуть, что буква характеризует определенный тип ТМП с характерным для него поведением. Так в случае, если проводится несколько испытаний одного и того же сложного технического объекта (СТО), будут получены различные измерения ТМП, однако набор меток типов ТМП будет один и тот же для всех испытаний. В случае, если в техническую систему будут внесены новые конструктивные особенности и необходимо будет снимать показания других параметров, то набор передаваемых типов ТМП изменится.
С каждым типом ТМП ассоциировано эталонное поведение 8. Эталонное поведение задается с помощью одной или нескольких реализаций: в = [Е\, ,Ет}, (1.1) где Е( — реализация, задаваемая временным рядом е\,..., е1п и определяющая один из возможных вариантов поведения, т — количество реализаций. Эталонное поведение задается экспертом на основании знаний о конструктивных особенностях СТО или как «примеры» поведения полученного в результате испытаний.
Модель формата кадра группового телеметрического сигнала
В рамках ОКР «Модернизация» [26] задачу оценки разрядности информационного слова, длины малого кадра предлагается решать путем оценки периодов между пиками автокорреляционной функции (АКФ). Корреляционной обработке подвергаются выборки из двоичных последовательностей данных (Ві), сведенные в последовательность информационных слов (Xj) определенной разрядности Рс. Вместо вычисления автокорреляцинной функции может быть вычислена функция f(a), применяющая оператор свертки к оригинальному временному ряду и временному ряду, смещенному на лаг а [33].
При этом кадровым периодам соответствуют пики с сильной корреляционной связью, а канальным — с менее сильной. Однако, так как мощность пиков АКФ определяется соотношением мощностей регулярной и случайной составляющих, а для канальных интервалов это значение меньше пиков интервалов цикла, то для рассмотрения выборки оценка канальных периодов оказывается неэффективной. Используя в качестве Го в выражении (1.4) последовательно все потенциальные длины информационного слова анализируемых данных, по расстоянию между соседними пиками Кх будет получена оценка длительности кадра. При отсутствии априорной информации о разрядности информационного слова определение кадровых периодов проводится, последовательно увели 31 чивая Pc от минимума до максимума (для стандарта IRIG [10] — от 4 до 64 бит). Однако, как показали дальнейшие исследования [34, 35] существует ряд проблем.
Во-первых, это большое количество действий, которые должны быть выполнены непосредственно экспертом. Попробуем оценить из каких составляющих складывается время работы алгоритма определения длины кадра и длины информационного слова. Для всех потенциальных длин информационных слов для всего ГТС или части, выбираемой экспертом, осуществляется построение АКФ. При этом будем считать, что априорной информации нет, и необходимо осуществить анализ всех длин слов: 4-64 бит. Время, необходимое для построения АКФ, обозначим как T(akf). Далее, на основании визуального анализа графиков АКФ для каждой длины слова экспертом выбирается несколько потенциальных длин кадра. Это время можно оценить как количество графиков, умноженное на время просмотра одного графика, которое в среднем будет занимать 30 секунд (построение графика и анализ). Таким образом, получаем, что время анализа всех графиков составляет 30 минут. Далее, необходимо проверить полученные пары длин слов и длин кадров, к примеру, это можно сделать с использованием графического представления ГТС, рассмотренного в разделе 1.6.1. Будем считать, что в среднем получается 10 пар, на каждую пару потребуется 20 секунд времени, чтобы проверить их. В результате оценим время данного решения как: T = T(akf) + 33мин.
Вторая проблема заключается в том, что максимальные значения коэффициентов АКФ достигаются при смещениях, кратных реальной длине кадра в битах только при условии, что при текущей длине информационного слова возможно получить такое смещение. Однако, если реальная длина кадра в битах и текущая предполагаемая длина слова взаимно простые, то пики будут приходится на смещения, отличающиеся на 1-2 бита.
Еще одной проблемой является то, что максимальные абсолютные значе 32
ния корреляционной функции при различных длинах слов примерно равны. И при этом, в ряде случаев максимальные значения автокорреляционной функции достигаются не при смещении равном реальной длине кадра, а при длинах лишь кратных. Это объясняется тем, что в кадре включаются также субкоммутируемые параметры, поэтому более точное совпадение будет происходить при длинах большого кадра. Данный факт не позволяет использовать простую эвристику: максимальное значение корреляции при длине малого кадра. Дополнительно необходимо отметить, что в работе предполагается анализ всего ГТС, что потребует крайне большие объемы вычислений.
Применение метода разностных операторов для определения суб- и суперкоммутаций В работе [26] измерения параметров предлагается представлять в виде матрицы, являющейся упорядочения по времени последовательности информационных и служебных слов, составляющих кадр данных. Двоичный поток ГТС (Ві), состоящий из измерений параметров с определенной длиной информационного слова Рс, представляется в виде сгруппированных в поток информационных слов (Xj) и кадров. Каждый кадр представляется в виде матрицы из последовательности Q строк с одинаковым количеством элементов столбцов L (информационных слов) (рисунок 1.10). При этом должно соблюдаться условие равенства длины кадра в информационных словах произведению Q L. Таким образом, ТМИ можно представить в виде последовательности матриц телемет-рирования MT[q,l], играющих роль операндов метода разностных операторов (последовательных разностей). К последовательности матриц телеметрирова-ния применяется метод разностных операторов [36, 37]. Так в работе [26] в рамках метода разностных операторов предполагается определение математического ожидания между соответствующими элементами предшествующих и последующих по времени матриц MT[q, /].
Метод последовательного восстановления структуры группового телеметрического сигнала
Алгоритм определения длины информационного слова осуществляет корреляционный анализ частоты изменения бит в словах и основан на том, что для функциональных параметров наиболее часто изменяемыми являются младшие биты двоичного представления.
Алгоритмы поиска суб- и суперкоммутаций являются модификацией существующих алгоритмов (см. 1.6.2). Алгоритм поиска субкоммутаций основан на том, что в результате объединения в субкоммутаторе измерений различных параметров среднее изменение значения слова с субкоммутацией будет иметь достаточно большое абсолютное значение. Дополнительно, глубина субкоммутации равна периоду АКФ, построенной для измерений анализируемого слова. Для определения периода автором был разработан алгоритм, в рамках которого осуществляется итеративный анализ упорядоченного множества пиков АКФ на наличие периода. Алгоритм поиска суперкоммутации строит иерархию частей кадров соответствующих возможным кратностям суперкоммутации в анализируемом слове и последовательно анализирует их с использованием метода разностных операторов. За кратность суперкоммутации принимается значение, при котором следующее значение кратности приводит статистику изменения анализируемого слова к резкому скачку по значению. Такой подход позволяет убрать высокую чувствительность оригинального алгоритма в случае длин слов большой разрядности. Дополнительно применяемое отсечение множества потенциальных кратностей для анализируемого слова сокращает объем вычислений.
Определение длины кадра в битах Напомним основные недостатки существующего алгоритма определения длины кадра. Как было указано в разделе 1.6.2 максимальные значения коэффициентов автокорреляции достигаются, когда длина смещения в битах кратна реальной длине кадра, если при текущей предполагаемой длине информационного слова возможно получить такое смещение. В противном случае пик приходится на минимально отличающееся смещение. Так, например, при предполагаемой длине информационного слова в 10 бит максимальный пик приходится на смещение, равное 768, что составляет 7680 бит или 5 кадров при реальной длине кадра 1536 бит (192 слова по 8 бит). В случае длины слова в 11 бит (11 и 1536 взаимно простые), пик приходится на 4609 бит, что на 1 больше реальной длины 3 кадров — 4608 бит.
Другой проблемой является то, что максимальные абсолютные значения корреляционной функции при различных длинах слов примерно равны. И при этом, в ряде случаев максимальные значения автокорреляционной функции достигают не при смещении равном реальной длине кадра, а при длинах лишь кратных.
На основании данных фактов, используя один только корреляционный анализ, не удастся с высокой точностью определить длину кадра в битах. Для преодоления данных недостатков необходимо разработать дополнительную проверку, которая позволит отсечь пики АКФ при длинах, отличных на один бит от реальной длины кадра. Автором была разработана проверка с использованием критерия наблюдаемости маркера.
Проверка наблюдаемости маркера
При корректных длинах кадра и информационного слова в начале каждого кадра должен находиться маркер — специальный параметр, значение которого не изменяется на протяжение всего сеанса работы телеметрической системы [10]. Вследствие наличия в ГТС сбойных участков, связанных как с неполадками в работе телеметрической системы, так и с особенностями ее технологического цикла, свойство константности маркера не является с математической точки строгим. В качестве примера на рисунке 3.4 представлен график типичного поведения маркера. На данном графике по оси абсцисс располагается время, по оси ординат — значение параметра. На графике видно, что на первых участках работы телеметрической системы наблюдаются сбойные участки: на них маркер принимает случайные значения. Однако на большей части ( 80%) ГТС гарантируется сохранение его значения [7]. Если длина кадра в битах определена с ошибкой хотя бы на 1 бит, то константность значения первого слова (маркера) не наблюдается (см. рисунок 3.5).
Экспериментальные исследования на модельных данных
Улучшения временной сложности, однако, не представляется возможным, УУ УУ оно остается 0(Сі IC2I). Если задать, что сравниваемые строки (символьные представления рядов) имеют примерно одинаковую длину w, то оценка времени работы алгоритма составит 0(w2) и оценка памяти 0(w). Необходимо отметить, что данная оценка справедлива только для сравнения двух строк, при сравнении строки с т эталонами время работы увеличивается в т.
Далее оценим временные затраты и затраты по памяти для алгоритма построения символьного представления (алгоритм 2.3.2). Для перевода в ККА-представление необходимо просмотреть весь исходный временной ряд длиной п, вычисляя по ходу среднее значение для w сегментов. Таким образом имеем время работы 0(п) и потребуется памяти 0(w). Перевод из ККА в символьное представление осуществляется за линейное время от количества элементов w. В результате временная сложность работы всего преобразования из исходного временного ряда в символьное представление потребует 0(п + w), а так как п » w, то последнее слагаемое можно опустить: 0(п). Затраты памяти соответственно будут 0(w).
Здесь необходимо отметить, что вычисление символьного представления достаточно проводить один раз, после этого полученную строку можно сохра 95 нять и использовать повторно.
Метод комплексного восстановления ГТС, как и метод экспресс-анализа, направлен на выделение схожих ГТС в хранилище для последующего анализа экспертом, однако, предлагаемый метод предварительно осуществляет поиск формата кадра и на основании дополнительной информации строит образ ГТС, включающий как информацию о поведении параметров, так и информацию о коммутации датчиков в СТО. Метод базируется на последовательности действий (см. рисунок 2.1): 1) построить формат кадра F (2.1) с использованием последовательного пометода восстановления, описанного в разделе 3.2; 2) по полученному формату кадра F построить графовую модель ГТС (2.4) в соответствие с алгоритмом 2.4.1 в разделе 2.4.3; 3) осуществить на базе сравнения графовых моделей ГТС поиск схожих в хранилище ГТС; 4) на основании анализа схожих ГТС и их структур экспертом принимается решение о выборе структуры.
Для нахождения схожих ГТС в рамках структурных моделей ГТС (2.4) предлагается использовать расстояние редактирования на графах (graph edit distance). Данный метод является толерантным к ошибкам методом сравнения графов (inexact graph matching). Идея редакционного расстояния графов заключается в том, чтобы определить различие графов с помощью набора операций редактирования (изменений), которые необходимы для преобразования одного графа в другой. В качестве альтернативы могут быть использованы характеристики, связанные с процедурой нахождения изоморфизма графов (или подграфов) [82]. Однако, на практике всегда присутствуют шумы и искажения, которые могут вызывать изменения как в самом графе, так и в значениях атрибутов и узлов, что в конечном счете отражается на расстояниях, вычисляемых на основании изоморфизма. Дополнительные искажения в метрику расстояния вносят возможные ошибки в результате работы алгоритмов определения формата кадра. По этой причине и был выбран подход неточного сравнения на базе редакционного расстояния. В следующем разделе он будет рассмотрен более подробно.
Редакционное расстояние на графах
Одним из наиболее гибких методов для сравнения графов является редакционное расстояние. Концепция редакционного расстояния была расширена из редакционного расстояния на строках (см. раздел 3.2.5) на деревья и в конечном итоге на графы в работах [58, 59]. Аналогично, как и для редакционного расстояния для строк, ключевая идея заключается в нахождении различия, или расстояние между графами как минимального числа операций редактирования (изменений), которые потребуется для преобразования одного графа в другой. По сравнению с другими подходами к сравнению графов, подход на основании расстояния редактирования графа считается очень гибким, поскольку он может работать с произвольными графами и любыми типами меток узлов и ребер. Кроме того, в определении цены операций редактирования, концепция расстояния редактирования может быть адаптирована под конкретные особенности предметной области.
Стандартный набор операций редактирования включает в себя вставку, удаление и замену, как узлов, так и ребер. Обозначим замену двух узлов u и v как (u - v), удаление узла u через (u - e), а вставку узла v как (e - v). Для ребер мы будем использовать аналогичные обозначения. Другие операции, такие как слияния и разделения узлов [83], могут быть достаточно полезны в некоторых предметных областях, однако, в данной работе они рассматриваться не будут.
Пусть заданы два графа, граф-источник g1 и граф-приемник g2. Идея построения расстояния редактирования графа заключается в том, чтобы удалить некоторое число узлов и ребер из g1, заменить метки для некоторого числа оставшихся узлов и ребер, а также включить некоторое число узлов и ребер из g2 в g2, и таким образом, граф g1 превратить в граф g2.
