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

Скачать файл (8,49Мб)

Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 19.10.2024

Просмотров: 62

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

и уничтожались бы из низшей вершины. Таким образом формиру ются вышеупомянутые терминальные вершины.

Описанный алгоритм приводит к решению, однако большое время переработки н большая затрата памяти вызывают трудности использования этого алгоритма. Эта задач? решалась с помощью программы па вычислительной машине IBM 7094 [Л. 14]. Однако такая переработка должна производиться в оперативной памяти, и поэтому рассматриваемая программа работает со словарем при близительно в 900 дескрипторов, что резко ограничивает использо вание программы, так как на практике встречаются словари с 10—20

тыс. дескрипторов. Имеется другой метод, который и был запро граммирован на IBM 7040 [Л. 15].

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

что процедура	начинается	с Si и кончается на Si.i.i,	Si.1.2 и т. д.
В результате	получим дерево, которое имеет ту же		форму, что и
дерево на рис. П2-1, но		множества дескрипторов, расположенные

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

ров дерева Ті в соответствующие	вершиньг дерева Тс	(рис. П2-1).
2-2. Общее описание процесса	построения дерева	Ті. Сначала

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

торого	количества N вершин следующего (более низкого) уровня.
На	рис. П2-2 N=2 на этом	уровне,	а дескрипторы	из Ni рас
пределяются по вершинам JVI.I		и Л^ . 2 .	Распределение	происходит
согласно следующим трем правилам:
13—88				193

1.Каждое описание документа должно быть представлено по крайней мере в одной из групп (вершин).

2.Количество дескрипторов в каждой группе должно быть при близительно равно.


3. Распределение				дескрипторов			по группам		должно	быть та
ким, чтобы документ				мог попасть			в возможно		меньшее	количество
групп	в соответствии			со вторым		правилом		(очевидно, что если бы
были	введены первое			и третье	правила бгэ второго, то в качестве
решения можно			было бы поместить все документы в одну группу).
Когда		дескрипторные группы				Ni.i и N1.2 сформированы, доку
менты,	которые		охватываются		дескрипторами				из этих	отдельных
групп,	должны		быть	приписаны		к этим вершинам. Если документ
должен быть приписан к более чем одной								вершине, то он приписы
вается	к одной		из этих вершин,				стремясь	уравнять		количество
документов в вершинах. Поэтому,						когда процесс закончится, каждый
документ		будет	приписан точно			к одной		вершине, а объединение

всех документов дескрипторов вершины представляет собой мно жество дескрипторов данной вершины. Отсюда Nu соответствует набору документов Оі.і, а множество дескрипторов, т. е. объедине ние всех дескрипторов в документах Du, будем называть Nu.

Аналогично вершина JVi.2 имеет набор документов Di.г, а объ единение дескрипторов этих документов называется #1.2. Если Dt

есть набор документов, соответствующих Ni, то согласно выше сказанному имеют место следующие соотношения:

А . . и о . . * = о ,	(П2-і)
А . і Г\ Di.2=0;	(П2-2)
Nui U #і.г = N1;	(П2-3)
Ni.i С\ М\-гФ & (в общем случае).	(П2-4)

Дерево Ті может быть теперь построено расчленением каждой вершины Nu и Ni.2 на некоторое количество N вершин, где /V может быть, а может и не быть таким же, как и ранее. Тогда как дескрипторы (например, Nu) и документы Du будут распределены между N LU и УѴі.і.2 и между Di.i.i и Оі.і.: в соответствии с тремя

правилами. Будут снова выполняться четыре отношения:

	A . I . I U O I . I . 2 = O I . , ;		(П2-5)
	f)Du , . 2 = 0 ;		(П2-6)
	# , . i . , U # . . i . 2 = #..i;		1П2-7)
	Wi.i.i П ^і.і.г Ф 0 (в общем случае).		(ПЗ-8)
Именно первое правило, выражаемое формально в виде отно
шений (П2-1)	или (П2-2), утверждает, что Тс	будет	обладать свой
ством I классификационного дерева.
Кроме того, когда процесс заканчивается,		т. е. не происходит
дальнейшего	разбиения вершин, каждый документ		будет отнесен

к одной и только одной терминальной вершине дерева (на рис. П2-2 это Ni.n, /Ѵі.і.2, Ni.i.i, /Ѵі.2.2.1, #i.z.2.2, #1.2.2.3). Отсюда видно, что

требование, чтобы каждый документ был привязан к какой-либо терминальной вершине Тс, выполняется потому, что терминальные вершины Тс такие же, как и у Ти а отличия имеются только в пе ресечении дескриптороз, которые возникают в вершинах более высо ких уровнен.

194

Решение о прекращении давлении вершины Nh может быть принято тогда, когда документы в Du и все относящиеся к ним данные заполняют реальную память, отведенную под сектор.

Этим замечанием завершается общее описание построения дере ва Гі и поясняется, как выполняются все требования к конструкции дерева Тг и привязки документов к секторам.

2-3. Построение Тв из 7Л. Граф дерева Тс идентичен трафу де рева 7"і; единственное различие заключается в составе дескрипторов вершин. Множество вершин Тс образуете.! пересечением соответ ствующих множеств вершин 7Л и удалением из вершин Ті всех дес крипторов при пересечении. Оставшиеся дескрипторы образуют вер шины дерева Тс. Общие дескрипторы становятся вершиной более


высокого	уровня. Этот	процесс		затем повторяется для вершин более
высоких	уровней. Весь	процесс		начинается с терминальных вершин
и продолжается до верхушки			дерева.
2-4.	Формальное описание		алгоритма построения Ті. Дескрипто

ры в вершине Nk должны ібыть разделены на N подгрупп. Описания документов Du содержатся на магнитной ленте, которая называется входной лентой. Предполагается, что дескрипторы закодированы целыми числами. В дополнение к входной ленте требуются одна про межуточная и одна выходная ленты. Разделение состоит из трех этапов.

Э т а п I

Описания документов рассматриваются по одному в порядке рас

положения их на входной лейте. Рассмотрим добавления					описания
D. Подгруппы нумеруются по порядку 1, 2, 3,..., N.
1. Найти группу, которая содержит			наибольшее	число	дескрип
торов пз Л'. Обозначим		эту группу і. •
2. Если	таких групп	две или более,	то выберем	из них группу
с меньшим	количеством	дескрипторов и ее обозначим		і.
3. Если и таких групп две или более, то выберем				из них группу

снаименьшим номером и обозначим ее і.

4.Пусть количество дескрипторов з группе і будет л,-, а количе ство дескрипторов из D, которые не вошли в группу, обозначим а,-. Пусть е будет положительным целым числом 0 . 1 . 2 . . .

Тогда,	если	имеет место соотношение (/ІІ + ДІ) ^ («j+czj) + е для
/ = 1 , 2 , . . . ,	/V, ]фі, дескрипторы из D,		не попавшие в группу I,
добавляются к		группе і. В противном	случае дескрипторы добав
ляются к группе		/, где n,+aj есть минимум по всем /.

Эт а п 2

1.Входная лента перематывается.

2. Если описание D появляется только в одной группе, дескрип

торы	из D в этой группе	отмечаются, а	описания	записываются
на выходную ленту вместе с присвоенным			им номером группы.
3.	Если D появляется	более чем в одной группе *,		описание за

писывается на промежуточную ленту, а дескрипторы не отмечаются. При этом образуется избыточность, которая позднее может быть

устранена	исключением	некоторых	дескрипторов из одной или более
групп.
* Заметим, что в		соответствии	с	п. 1 каждое	описание будет
помещено	по крайней	мере в одной		группе во	время этапа 1.
(Прим. пер.)
13*					195

Э т а п 3

1.Промежуточная лента перематывается.

2.Если дескрипторы из D все отмечены, по крайней мере в од ной группе, то D записывается на выходную ленту в группу с любым

пз дескрипторов, входящих в D. Промежуточная лента продвигается


к следующему		списанию.
3. Если	условие из п. 2		не	выполнено,	то	выбираем группу
с наименьшим		количеством неотмеченных дескрипторов из D.
4. Когда		промежуточная	лента	пройдет,	все	неотмеченные де
скрипторы	исключаются.

Выходная лента может теперь быть отсортирована по присвоен ным номерам групп, т. е. все описания, находящиеся в группе 1, со

бираются в отдельный блок, в группе		2 — в другой блок	и т. д.
Если описание документа появляется более чем в одном блоке,
оно убирается	из всех блоков, за	исключением самого	короткого,
в котором оно	находится.

Каждое множество документов Du, соответствующее вершине Nk, теперь находится в одном блоке, отсортировано и готово к расчле нению, если документы Dh и связанные с ними данные все еще пре вышают емкость сектора.

Если дерево Т± получено таиим образом, то добавление .новых описаний в файл и обновление классификаций можно выполнять без просмотра всей ленты.

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

3. Пример построения деревьев Т\ и Тс

Дескрипторы документальных файлов, приведенные в табл. П2-1, должны быть классифицированы в соответствии с принципами вклю-

			Т а б л и ц а П2-1
	Документный	файл
Номер документа	Описание		документа
1	1	2
2	1	3	4
3	1	3	6
4	1	5	6
5	2	4	11
6	2	3
7	4	13	14
8	4	11
9	6	7	8
10	9	10
11	10	11
12	9	11
13	11	12	15
14	13	14	15

196

чаемых разбиений для того, чтобы образовать 7'і (дескрипторы пред ставлены в виде целых чисел).

Первый, или верхний, уровень Гі содержит одну группу, состоя щую из всех 15 дескрипторов. Группа первого уровня будет разбита

на две включаемые группы			с помощью		трехэтапного процесса.		Каж-
					Т а б л и ц а		П2-2
Деление	группы первого		уровня	на	две вкиючаемые группы
			для	е = 0
Группы	1	2	Промежуточная		Группы	1	2
Группы	1	2	лента		Группы	1	2
	1	1	1	2		1	1
	2	3	9	10		2	3
	5	4	О)			5	4
	5	6	О)			6	6
	4	2				4	2
	11	13				11	13
	7	14				7	14
	8	9				8	15
	10	10				10
	9	15				9
	12					12

а) в)

дая группа второго уровня будет затем разделена на две включаемые группы, в результате чего формируется третий уровень.

табл. П2-2,а показано

деление

включаемой пруіп.пы

первого

уровня

на две

группы

для

е = 0 после этапа 1.

На этапе

2, показан

ном

табл. іП2-2,6", создается

промежуточная

лента

из

избыточных

Т а б л и ц а

П2-3

Лента,

содержащая

описания,

разбитые на блоки

соответствии с

включаемыми

группами табл. П2-2, в

•

1 1

описаний, а

на

этапе

исключаются несущественные

дескрипторы 9

и 10

из

второй группы,

после

чего

производится окончательное

раз-

• биение

(та'бл. П2-2,е).

табл. П2-3 показаны

блоки

ленты, образуемые

на

этапах

2 и

3, в которых записаны описания из табл. П2-1 вместе с обозначением той группы, к которой они приписаны.

197

Смотрите также файлы

Лифенцев, О. М. Крашение и печатание тканей путем синтеза пигментов на волокне.pdf

Максимов, М. М. Русскому золоту 250 лет.pdf

Мартинсон, Г. Г. Загадки пустыни Гоби.pdf

Марчук, Г. И. Численное решение задач динамики атмосферы и океана.pdf

Махров, Н. В. Параметры разработки современных автоматизированных систем управления предприятиями.pdf

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

Смотрите также файлы

Информация

Списки файлов

Дополнительно