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

при

рандомизации

входных

терминов

(ключей)

будет

выделяться

б л и ж а й ш е е

целое

число бит

из

[ogzN

в

сто­

рону

увеличения.

Н а

рисунке

показан

входной

ключ

(например,

тер­

мин

естественного

я з ы к а ) , обозначенный

как

ключ X.

Этот

ключ

надо

рандомизировать

в

число

х,

л е ж а щ е е

в диапазоне 1—N.

О б р а щ а ю т с я

к

области

памяти

Обл.

X. Внутри этой области содержится адрес

данных

Ах, соответствующих ключу X (Обл.

1 — Обл.

п

могут

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

З У П Д в

зависи­

мости от величины п, наличия места в оперативной

па­

мяти

и

заданной

скорости

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

Д р у г и м и

словами, Ах

является косвенной адресной ссылкой

к

вы­

соответствующей ключу X. Внутри этой записи

(в

обла ­

сти Ах) находится заголовок

записи

данных

ключа X,

затем .длина списка ключа X,

а потом

идет нулевое

поле,

у к а з ы в а ю щ е е в данном случае местонахождение

дан ­

ных ключа X внутри рассматриваемой записи.

Структура данных внутри

этой

записи переменной

ются адресом связи с первой

записью. Б о л е е того, если

подполе

ключа X

(заголовка)

имеет 'постоянную

длину,

то

выход

декодера

в целом (т. е. все д а н н ы е в

записи

Ах)

можно передвинуть в Обл.

х. В этом случае

уровень

косвенных адресов не нужен .

Тогда, если

выходная

запись в целом содержит w слов, то Обл.

x=wx.

Если ф а й л имеет структуру

инвертированного

спис­

ка, то д а н н ы е ключа X являются

инвертированным

спис­

К а к показано в верхней части

рисунка, д в а

ключа

Yi

и Yz рандомизируются в одно

и то ж е число у

и

соответ­

ственно

(с помощью

области у) — в область Аѵ,

которая

хранится в

З У П Д .

В области

Ау

содержится

поле

за ­

головка, определяющее полную ссылку д л я

ключа

Уь

длину

списка ключа

Уі (Lvi)

и

адрес

связи

Ау2.

Этот

адрес

указывает,

что в ф а й л е

имеется

д р у г а я

запись

с ключевым

словом

(в данном случае это Yz),

рандоми-

зируемым в то ж е

самое число

(у),

что и ключ

Уі. М о ж ­

но без труда определить, является ли найденная

запись

искомой.

Д л я этого

н а д о сравнить входной

ключ

(Уі

или Yz)

со ссылкой

в начале

поля

заголовка . Если срав-

8—88

113

нения

не произошло,

т. е. был

декодирован ключ У2, то

о б р а щ а ю т с я к записи,

хранимой

в области Аѵ% и сравни­

вают

заданный ключ

с первым

подполем поля заголовка

мент времени добавить в этот файл

другой

ключ, ска­

жем,

ключ

Уз,

который

т а к ж е

будет рандомизирован

в

число

у,

то цепь будет

расширена

на

один элемент,

а

третье

подполе

заголовка Л у 2

будет

содержать

адрес

связи Ауз.

Этот

адрес

будет д а в а т ь

ссылку

на

запись

данных

ключа У3 . П о л е

заголовка записи,

соответствую­

щей

ключу У3, будет иметь вид ключ

У з Д . у 3 / 0 .

Если требуются более простые (по сравнению

с

по­

казанными

в табл . 3-1)

информационные

структуры,

то

обобщенный рандомизатор

(рис. 6-4)

упрощается

и при­

если

записи ф а й л а . содержат

только

по одному

ключу

(т. е.

имеется система запросов с единственными

ключа­

ми,

подобная

банковскому

примеру,

рассмотренному

в гл.

1) и если

длины записей

постоянные, то промежу­

записи

равен wx. При

этом зацепление ключей т а к ж е

необходимо.

Н а

рис. 6-5 показана другая модификация, которую

можно

использовать для

файлов со структурой связного

писях файла . Н а

рис.

6-5

показано,

что

записи

файла

хранятся

в областях Ах,

Ау1

и АУ2,

а заголовок,

содер­

ж а щ и й с я

только

в головной

записи списка,

обозначается

со звездочками,

т а к

и без

них. Ключи

со

звездочками

обозначают заголовок ключей списка. Подполе

этого

объединенного

заголовка

справочника

и

поле

ключа

записи следующие:

полный ключ/длина

списка/адрес

Т а'б лиifa

6-3

Параметры~о5ъемов памяти декодера

Декодер*

Символ

Значение

V T

R

F T

HOB слов.

Поэтому можно ожидать,

что д л я

хранения

таблиц требуется в основном память

прямого

доступа.

Хранение части таблиц в оперативной

памяти

требуется

лишь при

повышенных требованиях

к времени

ответа.

При этом экономится одно обращение

к З У П Д .

Конечно,

мяти

экономит приблизительно 1 / я Х І 0 0 % общего

вре­

мени

доступа.

Р а с с м а т р и в а е м ы е ниже формулы предназначены

д л я

раметрами декодера

(например, глубиной

дерева) и

средней длиной цепи

рандомизатора, а т а к ж е

временем

ного

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

вей,

выходящих из к а ж д о й вершины дерева . Этот пара­

метр

называется

фактором

ветвления т.

В соответст­

вии

с принципом

упаковки

максимально

возможного

ной физической записи,

хранимой

в

З У П Д

(которая

соответствует размеру буфера

оперативной

п а м я т и ) , и

от объема памяти, требуемого

д л я

хранения

декодирую­

щей тройки ключ (фрагмент)/адрес/длина списка.

Д л я

простоты положим, что д л я хранения

физической

записи

требуется одна

д о р о ж к а

(для

любого

другого

блока

па­

мяти читатель

может использовать

в

этих рассуждениях

вместо понятия

дорожки

понятие

б л о к а ) .

m,

Md

Необходимо

вычислить

значения

параметров

и M с, а т а к ж е

выразить

их

через

целые числа

Nt

и

Nti.