5.1. Расстояние по виду структуры

Пусть нам даны две иерархии  и  с числом уровней  и  соответственно. Будем рассматривать иерархию  как (упорядоченное) множество уровней с  по , а каждый уровень — как совокупность  расположенных на нем  вершин (таксонов) :

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

Затем для вершины  находится самая похожая на нее вершина , т. е. такая, редакционное расстояние  до которой минимально. Величина  добавляется в счетчик суммарного расстояния  между данными уровнями, и эта пара самых похожих вершин из дальнейшего рассмотрения исключается. Среди оставшихся вершин снова ищется самая похожая пара, величина их редакционного расстояния  добавляется к счетчику , а эта пара также исключается из дальнейшего анализа. Такая процедура нахождения на каждом (-м) шаге самой похожей пары, добавления к счетчику  величины  и исключения -й пары выполняется  раз. В итоге получается величина редакционного расстояния между двумя этими уровнями:

Проведя сравнение всех  уровней первой иерархии со всеми  уровнями второй, мы получим матрицу  с номерами строк  и номерами столбцов . На пересечении строки  и столбца  будет стоять величина (частного) редакционного расстояния  между уровнями  и  сравниваемых иерархий (см. табл. 16).

Таблица 16. Редакционное расстояние между уровнями иерархий  и

Редакционным расстоянием  между иерархиями  и  называем стоимость не любого, а оптимального перевода уровней иерархии  в соответствующие уровни иерархии . Этот перевод будем искать с помощью метода динамического программирования [13,30]. В результате находим путь на матрице , соединяющий клеточку  с клеточкой  и проходящий через соседние клеточки либо по горизонтали слева направо, либо по вертикали сверху вниз, либо по диагонали вправо вниз. На каждом шаге прибавляем к счетчику расстояния  величину , взятую из той клеточки, через которую проходит путь. Весовой коэффициент  равен единице при переходе по диагонали и двум при переходе по горизонтали или вертикали (схема динамического программирования 2-1-2). Наша цель состоит в поиске такого пути , который набирает минимальную сумму  стоимостей частных взвешенных редакционных расстояний. Этот путь показан в табл. 16. Он дает величину .

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

Матрица частных редакционных расстояний для сочетания всех уровней иерархий  и  приведена в табл. 17, а, для иерархий  и  — в табл. 17, б.

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

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