Файл: Левковиц, Д. Структуры информационных массивов оперативных систем.pdf

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

ПРИЛОЖЕНИЕ 2

АВТОМАТИЧЕСКАЯ КЛАССИФИКАЦИЯ ДЛЯ ПРОЦЕССОВ ПОИСКА

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

Основой для машинной классификации служит не априорная классификация знаний, а описание документа. Таким образом, каж­ дая подборка документов создает свою собственную классификацию, основанную на всех описаниях документов в библиотеке. Когда добавляются новые документы, классификация перестраивается.

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

Возьмем в качестве основной модели структуру дерева, показан­ ную иа рис. П2-1. На практике дерево может содержать любое количество уровней и произвольно ветвиться в каждой вершине.

ставляется в виде набора дескрипторов и ассоциируется с одной из терминальных вершин.

189

Уровни

ся классификационное дерево, описывается множеством дескрипторов

априорных предположений относительно семантических связей. Одна­ ко дескрипторы в множестве Si используются вместе с дескриптора­

нии дескрипторов из вершинболее низких уровней.

С каждой терминальной вершиной связывается часть машинной памяти, называемая сектором. Внутри секторов размещаются записи документа с дескрипторами (ключами) m множеств тех вершин, лежащих «а путях, которые заканчиваются в терминальной вер­ шине.

Возможно, что множество дескрипторов документа Sd может лежать па пути, имеющем несколько терминальных вершин, к кото-

190

"рым он может прийти. Нужно решить, какой терминальной першнне может соответствовать документ. Например, Sd может полностью содержаться в Si (J Su. Позднее будет объяснено, как решается поставленная задача. Таким образом, каждое описание документа ассоциируется с некоторой терминальной вершиной, которая в свою очередь ассоциируется с некоторой частью памяти, называемой сектором. На практике сектор может быть цилиндром дискового фай­ ла, серией дорожек, обслуживаемых одной головкой диска, полоской или картон магнитной памяти или сегментом магнитной ленты.

/. Поиск с помощью конъюнкции ключей

Созданная структура дерева используется для поиска документов следующим образом.

Сначала вершины дерева нумеруются так, что число групп в но­ мере представляет собой номер уровня вершины, а каждая группа подсчитывает число ветвей от порождающей вершины (номер ко­ торой в свою очередь приписан к очередной группе слева). Вершины на рис. П2-1 пронумерованы именно таким способом.

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

является. Поиск ответа на запрос, содержащий конъюнкцию клю­ чей, производится по следующему алгоритму.

1. Используя ТКВ, формируем таблицу, которая размещает все вершины с наименьшим количеством цифр (групп) в колонку I, все вершины со следующим, большим-количеством цифр — в колонку II и т. д. Дополнительно, кроме номера вершины, в скобках помещается номер ключа. Например, предположим, что запрос содержит конъ­

191

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

Если существует один или более путей, то для каждого пути производится поиск в соответствующем секторе. Эти сектора на­ ходятся следующим образом: для каждого пути выбирается послед­

1.1.3.4.118

1.2.1.119

1.2.220

1.2.4.6.1.7.121

1.2.4.6.1.7.222

1.3.7.6.23

1.3.7.8.24

1.3.8.5.2.1.1.25

1.3.8.5.2.1.3.28

1.3.9.7.29

Из просмотра ТТВ видно, что вершина 1.3.8.5.2.1 не терминаль­

в нем расположены либо последовательно, либо имеют списковую структуру (см. § 7-4).

2. Строение классификационного дерева Тс

2-1. Строение промежуточного дерева 7\. Непосредственный путь построения дерева был бы следующим. Найти группы документов, имеющих максимальное (в некотором смысле) пересечение дескрип­ торов. Эти группы образовали бы сектора, а объединение всех дескрипторов в каком-либо секторе стало бы нижней вершиной дерева. Далее пари (или тройки, или более высокие объединения) этих вершин объединялись бы в соответствии с наибольшим коли­ чеством пересечений дескрипторов для того, чтобы сформировать вершины следующего, более высокого уровня, а дескрипторы из пе­ ресечения включались бы в более высокую (родительскую) вершину

192