Запретный плод "дерева"

Элементы иерархических структур

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

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

В такой структуре могла бы ориентироваться без всяких проблем любая программа, в которой заложены соответствующие ресурсы управления. Но чтобы такие ресурсы заложить, их нужно еще разработать в соответствие с теми свойствами, которыми обладает иерархия как универсальная структура любых объектов. Одно из поистине волшебных свойств иерархии связано со степенной зависимостью общего количества позиций объекта от длины вертикали. Если, скажем, количество уровней будет равно 10, а среднее количество позиций в одном списке - 20, то общее количество позиций в таком объекте будет порядка 2010, т.е. при соответствующей организации данных, максимум, за 10 шагов обеспечивается доступ к любой из 10 трлн. (!!!) позиций объекта. Однако в традиционных компьютерных технологиях иерархии существуют только в номинальном, т.е. неуправляемом виде, поскольку такие их элементы, как позиции, уровни, вертикали и т.д., если и присутствуют, то только как образы или аналогии (деревья, родословные списки, цепная реакция и т.п.), а не как параметры, которые доступны для изменения или вычисления.

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

Позиции отдельных записей располагаются таким образом, что каждая из них может быть связана с несколькими подчиненными и только одной вышестоящей позициями. Например, запись, содержащая ключевое слово, будет вышестоящей позицией по отношению к позициям, содержащим его возможные значения. Позиция, для которой вышестоящая отсутствует, является вершиной иерархии (словарь как единый объект). Позиции, не имеющие подчиненных, образуют контур иерархии (например, отдельные фразы или значения слов, не имеющие устойчивых словосочетаний), а цепочка связей, соединяющая позицию контура с вершиной, - иерархическую вертикаль (например, словарь - карта - географическая - контурная).

Позиции, отстоящие на равное число отрезков вертикали от вершины, образуют уровни (например, уровень 1 - ключевые слова, уровень 2 - возможные значения слов, уровень 3 - фразы), состоящие из локальных списков, каждый из которых подчинен только одной вышестоящей позиции (например, к слову "карта" относятся: географическая, игральная, электронная). Место каждой позиции в локальном списке соответствует ее порядковому или списочному номеру.

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

Таким образом, номер уровня - это единственный (!) параметр иерархии, который нужно сохранять в качестве необходимого ресурса управления для однозначного воспроизведения данных и их связей. Однако при этом мобильность системы, определяемая показателями производительности, экономичности, гибкости и т.п., будет минимальной. Чтобы поднять их до максимального уровня, можно ввести дополнительные ресурсы управления, аналогичные тем, которые применяются для управления жесткими дисками через таблицу размещения файлов FAT. Применительно к иерархии, в таблице размещения данных, кроме номера уровня, нужно сохранять также смещение от начала объекта и длину записи в байтах, а также бинарные переключатели (флажки) для обозначения состояния каждой позиции (активной, помеченной, удаленной и др.). Конкретные значения ресурсов управления в байтах могут выглядеть, например, так:

Параметры Ресурс
Номер уровня 1
Смещение 4
Длина записи 2
Флажки 1
Всего 8

В этом случае возможности иерархических объектов ограничиваются следующими показателями: максимальное число уровней иерархии - 256, максимальный объем текстового ядра объекта - 4 Гб, максимальная длина одной позиции - 64К, количество флажков - 8, объем основных ресурсов управления на 1 позицию данных - 8 байт. В отличие от табличных записей, фиксировать их длину в иерархических позициях не требуется, и записи на носителе занимают ровно столько места, сколько необходимо. Насколько велик потенциал таких объектов с точки зрения их применения в компьютерных технологиях - это отдельная тема. А вот практическая польза от применения в КТ иерархических ресурсов управления вполне очевидна.

Если бы основной ресурс управления - номер уровня - был задействован в существующих форматах данных, то вполне возможно, что стратегическое направление развития КТ в сторону единого формата данных могло пойти совсем другим путем. Преимущества иерархических форматов данных могли бы проявляться в более явном виде. Например, функция поддержки иерархических списков в MS Word, в отличие от сегодняшней, работала бы как часы. Ведь для надежной работы этой функции сохранять конкретные списочные номера позиций не нужно, а для управления ими с текущей позиции существует всего четыре возможных варианта: создать следующий номер по списку (как сейчас), создать первую позицию на следующем уровне, (добавить к текущему номеру точку и единицу), создать следующую позицию на столько-то уровней выше и удалить/отменить текущую позицию. В этом случае эта функция могла бы очень эффективно использоваться, например, в текстах постановок задач для программирования, где описания модулей и функций имеют многочисленные разветвления и ссылки. Ошибки в нумерации пунктов в рамках даже очень большого списка были бы полностью исключены, а их редактирование существенно облегчалось бы за счет автоматической поддержки, причем независимо от дополнительных ненумерованных вставок текстов, таблиц, рисунков и т.д. между нумерованными абзацами. Но пока разработчики MS Word усиленно трудятся в направлении дальнейшего усложнения формата данных и функций его поддержки, вместо того, чтобы за счет иерархий существенно и, может быть, даже радикально его упростить!

Юрий КРАСКОВ,
c_city2000@mail.ru

Версия для печатиВерсия для печати

Номер: 

39 за 2002 год

Рубрика: 

Новые технологии
Заметили ошибку? Выделите ее мышкой и нажмите Ctrl+Enter!