§ 5. Расстояние между иерархиями

Как определить расстояние между подобными иерархическими структурами? В работах [18,19,136] предлагается мера близости между такими графами с поименованными вершинами, списки вершин в которых совпадают или мало различаются. Здесь мы попытаемся предложить решение проблемы измерения расстояний между иерархиями с объектами произвольного состава.

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

Перейдем к математической постановке задачи нахождения характеристик расстояния  и .