Иерарахические числа – это числа вида [s] a0 . a1 . a2 . … . ai. … .an , где ai– целые положительные числа из множества N = {0, 1, 2, 3…}.
s– символ знака «+» или «-», положительный знак может не указываться.
Например, иерархические числа могут выглядеть так:
0.0.12.48.0 или -2.33.0.0.4 .
Символом, обозначающим множество иерархических чисел, является H.
Прикладное определение. Иерархические числа – это раздел математической теории чисел, который позволяет адекватно оперировать основными характеристиками таксономий.
В теории представления знаний искусственного интеллекта иерархические числа позволяют:
- определять семантическое сходство понятий;
- вычислять индексы гиперонимов и гипонимов;
- получать регулярные структуры знаний;
- верифицировать деревья родовидовой и причинно-следственной классификаций.
Эти числа так или иначе уже используются в практике классификации или адресации, например: универсальный десятичный код или IP-адрес компьютера в глобальной сети. Однако, введение алгебраической системы иерархических чисел позволяет совершать с ними операции, схожие с формальной арифметикой, и выделять бинарные отношения для их сравнения и анализа нетривиальных свойств операций и отношений.
Пусть N – множество целых положительных чисел с элементами ni ϵ N, пусть также есть выделенный символ «.».
Множество A = N ᴗ «.» ᴗ ᴧ определяется как алфавит с целыми числами n, где «ᴗ» – операция объединения множеств, а ᴧ – пустой символ.
Тогда грамматика:
ĥ → ᴧ,
ĥ → h,
ĥ → - h,
h → < n >,
h → < n > . <h>
описывает множество иерархических чисел Ĥ с элементами ĥ.
Рассмотрим алгебру бинарных иерархических чисел.
Пусть B – множество чисел с элементами {0, 1}, n ϵ B (n = 0 или n = 1), пусть также есть выделенный символ «.».
Множество A = B ᴗ «.» ᴗ ᴧ определяется как алфавит с целыми числами из B, где «ᴗ» – операция объединения множеств, а ᴧ – пустой символ. Тогда грамматика:
ĥ → ᴧ, ĥ → h, ĥ → -h,
h → < n >, h → < n > . <h>
описывает множество бинарных иерархических чисел H с элементами h.
Можно привести примеры бинарных иерархических чисел: 0.1.0.0.1 или 1.0.-1.0 .
Бинарные иерархические числа представляют собой численные индексы вершин двух
двоичных деревьев: положительного и отрицательного с одной общей вершиной 0.
Порождение вершины влево от 0 производится бинарной операцией 0+0 = 0.0, порождение вершины вправо - бинарной операцией 0 + 1 = 0.1.
Порождение отрицательных вершин выполняется операцией «-» соответственно:
0-0 = -0.0, 0-1 = -0.1.
Графически это можно представить деревом, распространяющимся в положительную или отрицательную сторону:
Впрочем, использование отрицательных элементов может сделать смысл операций более сложным. Например, порождения трассы «+» может выглядеть так:
0.1 + 1.1 = 0.1.1.1, 0 + 0.1 = 0.0.1
Однако пример 0.0.-1 + 1.1 = 0.0.-1.1.1 свидетельствует о наличии более сложных трасс путешествия по дереву, использующих не только спуск но и локальные подъемы (рисунок 2). Такое применение иерархических чисел будет рассмотрено далее на конкретных примерах.
Операция, обратная порождению, удаление терминальной вершины «--», является унарной:
0.1.1.1-- = 0.1.1, 0.1.0-- = 0.1, 0.-1.-1 -- = 0.-1.-1 .
В графической интерпретации число можно считать абсолютным индексом какой-либо вершины, т.е.начинающимся с вершины дерева 0 или относительным, отображающим путь по дереву от одной из любых вершин к другим вершинам вверх и вниз. Абсолютный индекс всегда начинается с символа 0.
При решении практических задач можно рассматривать только положительную часть алгебры бинарных иерархических чисел. В этом случае операции, претендующие на получение отрицательного индекса, будут иметь результатом 0.
Можно привести еще одну довольно популярную операцию «º», а именно вычисление наиболее общей вершины, что интерпретируется как поиск общего предка двух вершин - аргументов:
0.1.1.1 º 0.1.0 = 0.1.0 º 0.1.1.1 = 0.1
Эта операция генерализации/умножения коммутативна, т.е. a º b = b º a.
Умножение положительного числа на отрицательное всегда равно 0.
Важной операцией является «Ù»
0.1.0 Ù 0.1.1.1 Ù 0.1.0. 0.1. 0.1.1. 0.1.1.1 @ 0.1.1.1 0.1.1. 0.1 0.1.0
Здесь @ - отношение равенства длин двух иерархических чисел.
Однако, такое вычисление приводит к излишне сложному результату.
Заметим, что общим предком для 0.1.1.1 и 0.1.0 является 0.1, с которого начинаются оба числа - аргумента. Вследствие этого, при вычислении операции Ù эти фрагменты опускаются для всех вершин пути из первой вершины во вторую. Это необходимо для получения представления о сложности пути из первой вершины во вторую, не смотря на глубину дерева.
Тогда правильная операция Ù получается так:
0.1.0 Ù 0.1.1.1 = [0.1.]0. [0.1.] [ 0.1.]1. [ 0.1].1.1 = 0.1.1.1
0.1.1.1 Ù 0.1.0 = [0.1.]1.1 [0.1.]1. [0.1] [0.1.]0 = 1.1.1.0
0.1.1.1 @ 1.1.1.0
После рассмотрения семантики приведенных операций можно задать универсальную арифметическую алгебру иерархических чисел H:
H = < H, Ω >, Ω = {+, -, --, º , Ù, ⊕ },
где Ω – сигнатура алгебры, т.е. множество операций. Все операции бинарны, за исключением «--», которая является одноместной. Смысл операции «⊕ » будет рассмотрен позже, на соответствующих примерах.
Рассмотренную алгебру можно дополнить до алгебраической системы H = <H,Ω,R>, введя множество отношений R = {< , >, @ , = }, где отношения « a> b» и « b< a» соответственно «число a сложней числа b» и «число b короче числа a».
