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

резерва

по Л а н д а у е р у

адекватно, по-видимому, д л я боль­

шинства

систем.

В т а б л . 6-1

и на

рис.

6-1 изображен декодер с

усе­

чением

имен.

П о д о б н а я

стратегия не подходит для

ре­

имущество такой иерархии состоит в

том, что фрагмент

Имени

не надо

повторять с к а ж д ы м

фрагментом

Вели­

чины.

Кроме

того, к а ж д о е дерево

Величин

может

фрагменты

внутри

одного и того ж е

дерева

одинаковы

по длине.

К р о м е

быстрого

декодирования

больших

справочни­

иск ключа

в диапазоне от

AGE/21 до AGE/30. Системе

з а р а н е е

не

известно',

есть

ли в

файле действительные

значения

ключевого

имени

AGE,

поэтому желательно

написать

программу, которая

будет декодировать

дере­

во И м е н

(в данном

случае она

будет декодировать

AGE)

и направлять

его в

дерево

Величин. З а т е м она

опреде­

лит .границу

наименьшей величины (21) и просмотрит

дерево снизу

вверх,

начиная

с этой точки и кончая

верх­

ней границей

(30). Все величины, полученные при этом

просмотре, декодируются в

соответствующие

адресные

ссылки. Кроме того, для

к а ж д о й из них

проводится

по­

иск по списку.

В конце этой главы

будут выведены

формулы, с

по­

слова, д а ю щ е е

однозначно

закодированный фрагмент.

Набор правил кодирования приведен во втором

и

треть­

ем

столбцах табл .

6-1. К а к

и в

случае справочника

с по­

стоянными

(по длине) словами, ключевые

слова

вначале

упорядочивают

в

алфавитном

порядке

(это

показано

в

левом

столбце

т а б л и ц ы ) .

З а т е м

(как

показано

ный фрагмент. Д л я этого

используется

наименьшее,

на­

чиная

слева, количество символов

(требуемое

д л я одно­

значного различения данного полного имени

от

непо­

средственно

предшествующего

имени) .

Следовательно,

В А В В Е Т (первое имя

в

данной

последовательности)

можно однозначно закодировать просто буквой

В;

BABSON отличается от В А В В Е Т

четвертой

буквой;

сле­

довательно,

д л я

того

чтобы отличать B A B S O N

от

ВАВВЕТ, требуется закодированный фрагмент BABS *.

Аналогично,

B A I L E Y

отличается

от B A B S O N

буквами

B A I ,

a B A K E R

от B A I L E Y — б у к в а м и

ВАК .

Эта

про­

цедура применяется ко всему набору ключей;

результат

этого показан во втором столбце табл . 6-1.

Д л я иллюстрации того, как

закодированные

фрагмен­

ты переменной длины хранятся в виде дерева

в

памяти

на дисках

и к а к

это

дерево

декодируется,

будут

рас­

Распределение

отдельной дорожки

Т а б л и ц а 6-2

Номер записи

Содержание дорожкн

Комментарии

1

6,1

Ключ длимы 6 (1 ключ)

BLACKW/AI.L,

Ссылка на ключ BLACKWELL

(в области файла

/1,) с длиной

списка Z-i

2

5,1

Ключ длины 5 (1

ключ)

B E L L S / A 2 / L ,

5

2,4

D Y / A . / L ,

-

C R / A . / L ,

B L / A 1 0 / 1 I 0

B E / A . . / L , ,

6

1,4

E / A i 2 / L , 2

D / A 1 3 / L I 3

C / A , . , / L u

B / A 1 6 / L 1 5

Р а с п р е д е л е н ие

отдельной

дорожки

показано

в табл . 6-2. Таблица

состоит из

трех столбцов.

В первом

ром — содержание д о р о ж к и

внутри каждого поля запи­

си (каждое поле отмечается

при помощи разделительной

носящиеся к записям . Процедура состоит в перестанов­

ке фрагментов в порядке уменьшения

их длин. В резуль­

тате этого самый длинный фрагмент

B L A C K W , содержа­

щий шесть букв, появляется в заголовке списка; затем

идет пятибуквенный фрагмент B E L L S

и т. д. Первое поле

вида

информации

. Первый — это длина фрагмента, рав­

ная

6 д л я записи

1, а

второй — количество

фрагментов,

содержащееся в

записи

(в данном случае

1). Следова-

ственная тройка,

длина фрагмента

в

которой

равна 5.

В третьей записи содержатся три

тройки

с

длинами

фрагментов

4, а

именно

CART, B E L M

и BABS .

Таким

образом, в целом

д о р о ж к а

планируется

в порядке

умень­

шения длин

фрагментов.

Вообще

говоря,

эта

д о р о ж к а

триваемой

дорожке .

В

этом

случае физическая

запись

(т. е. д о р о ж к а )

считывается

в

оперативную

память

це­

ликом. П е р в а я

запись

указывает,

что

шесть

букв

имени B A B S O N надо

сравнить

с фрагментом

B L A C K W ,

т а к ж е состоящим

из

шести

букв, — сравнение

окажется

неудачным.

Тогда программа

удалит

одну

букву

из

фрагмента B A B S O N и сравнит

первые пять букв с пяти-

буквенньш

фрагментом

B E L L .

Сравнение опять

окажет ­

буквы В AB S с

фрагментами

CART,

B E L M и

BABS .

В итоге слово B A B S O N однозначно декодируется в со­

ответствующий

адрес связи

Ай. Неоднозначность

деко­

дирования слов

B E L L S O N и

B E L L

(в предыдущем де­

ственно как B E L L S

и

BE.

Однозначность

поиска гарантируется т а к ж е

сравне­

нием полного ключа,

хранимого в найденной

записи,

бочное

декодирование слова

B I N D E R привело

к фраг­

менту В

(соответствующему

слову В А В В Е Т ) ,

то

ошибка

обнаружится при обращении к записи файла и

сравне­

нии хранимого в ней

полного .ключевого

слова

В А В В Е Т

с з а д а н н ы м ключом

B I N D E R .

Д л я

добавления

в справочник нового

ключевого сло­

декодируется д л я обнаружения избыточного

фрагмента

(если избыточно закодированного фрагмента

нет,

то

в качестве фрагмента берется н а ч а л ь н а я

буква с л о в а ) .

Затем разыскивается избыточное ключевое слово,

у ж е

имеющееся в файле. При этом возможны

два

случая.

1.

Новое слово

алфавитно

предшествует

старому

слову.

В этом случае новому

слову ставится

в соответ­

назначается

более

длинный

фрагмент

для

отличия

его

от нового слова . Например, пусть в существующий

спра­

вочник

надо

занести

имя

B L A B .

Оно

декодируется

в фрагмент

B L , ранее назначенный слову B L A C K . Слово

B L A B алфавитно

предшествует слову

B L A C K ,

поэтому

слову

B L A B

н а з н а ч а е т с я

фрагмент

B L , а

д л я B L A C K

создается

фрагмент B L A C

(чтобы

отличать

его

от

B L A D ) . Н а

остальную

часть

списка

это

не

влияет,

пото­

му

что следующее

слово

B L A C K W E L L ,

очевидно,

не совпадает с более коротким фрагментом

слова B L A C K

и тем более не может совпасть с любым более

длинным

фрагментом .

2.

При

декодировании

обнаруживается,

что

новое

слово

алфавитно

следует

за

старым.

В этом случае

за

старого слова.

Рассмотрим

создание трехуровневого дерева

д л я 15

ключевых

слов

(рис. 6-2). Создание дерева

начинается

с правого

края .

К а ж д а я логическая

запись

отделяется

внутри д о р о ж к и

двойными линиями.

К а к и

в

случае

ответствующую запись помещается

у к а з а т е л ь

ссылки

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

З а т е м

начинается новая д о р о ж к а низшего

уровня. П р и

исполь­

зовании резервного пространства д л я дерева

ключевых

слов переменной длины требуется подсчет

количества

фрагментов ключей, помещенных

на

данную

дорожку .

самих закодированных

фрагментов,

а т а к ж е

от того,

что

закодировнные

фрагменты

одинаковой

длины

можно

сгруппировать

под

одним и

тем

ж е

заголовком .

Д л я

определенности

предположим

в этом

примере,

что

в

к а ж д о й

д о р о ж к е с о д е р ж а т с я

четыре

фрагмента .

Это

означает,

что

в случае

трехуровневого

дерева

на

первых двух уровнях требуются только две

возможности

ветвления (для

декодирования

на

третьем,

уровне