Теоретические сведения. В некоторых задач основной характеристикой образа служит последовательность символов или чисел

В некоторых задач основной характеристикой образа служит последовательность символов или чисел. Понятие сходство между ними и оценка расстояния базируются на работе Кендала, где введена мера сравнения порядка списков.

Пусть имеем две реализации

Коэффициент сравнения определяют следующим образом:

где l < k

Расстояние по Кендалу вычисляется:

Если компоненты обоих векторов упорядочены однотипно, то и результат суммирования равен половине числа размещений из n по 2.

Но поскольку , то

пример 1: ;

; ; ; n=3

; ;

Максимальная величина расстояния между векторами получается в том случае, когда их компоненты упорядочены в противоположном порядке.

Другой подход к определению расстояний между двумя списками состоит в учете последовательности составляющих в каждом списке. В этом случае учитывается структура последовательности.

Каждый список состоит из символов, входящих в один и тот же алфавит. Они могут быть представлены в виде типографских знаков (например, букв) или других элементов, образующих конкретный текст.

Пусть заданы два списка:

и

В общем случае n и m могут быть не равны друг другу. Задача заключается в том, чтобы определить такую функцию, которая выражала бы степень сходства этих двух списков.

Из рассмотрения двух последовательностей видно, что одна из них может быть преобразована в другую. Например, для того, чтобы перейти от ряда АВС к ряду АВДЕ, следует сохранить первый и второй символы, заменить третий и добавить четвертый. Введя пустой символ , можно эти три варианта преобразований записать в виде трех операций:

SUBstitution (подстановка)

DEStruction (уничтожение)

CREation (создание)

Каждому преобразованию соответствует своя цена для SUB, для DES, для CRE.

Для оценки расстояния между двумя списками вводят понятие полной цены последовательности преобразований как наименьшей из всех возможных цен, которые следует “уплатить” за переход от исходного списка к конечному. Расстояние , соответствующее полной цене, является минимальным.

Схема преобразований носит название пути, обычно изображаемого стрелками.

Например, :

:

Путь можно записать в виде ряда операций :

, , , ,

, , .

Каждой операции приписывают определенную цену, и расстоянию между списками соответствует минимум цены.

Рассмотрим

Положим , , тогда,

например,

,

Положим

Для перехода от D(l-1, k-1) к D(l,k) имеются три возможности:

- путем подстановки и , цена которой соответствует цене подстановки последних элементов в каждом списке;

- путем создания последнего элемента в списке j , за что придется уплатить цену ;

- если рассматривать пару и , то цена будет , что соответствует стоимости уничтожения последнего элемента в списке i.

Минимальная цена соответствует оптимальному пути.

Дата добавления: 2014-12-09; просмотров: 170; Нарушение авторских прав

Мы поможем в написании ваших работ!