Файл: Левковиц, Д. Структуры информационных массивов оперативных систем.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 19.10.2024
Просмотров: 96
Скачиваний: 0
15 фрагментов) . Здесь |
используется |
принцип отдельной |
||||||
дорожки, |
показанный |
на рис. 6-1; следовательно, |
фраг |
|||||
ментация |
15 ключей |
в |
начальный |
момент |
проводится |
|||
так, как показано |
в третьем |
столбце |
табл . 6-1. Усечение |
|||||
каждого |
набора |
из |
четырех |
фрагментов |
выполняется |
|||
однозначно, независимо |
от других наборов. |
Эти |
фраг- |
|||||
|
І1/В£Ш/Г00 |
|
|
Ѵ/Е/Тю |
|
|
|
|
|
|
7—: — |
|
|
|
|
|
|
№*fo, |
II WBELM/T0Z |
V////////////mt% |
\ |
|
|
|||
|
|
VWVTn |
II VWn |
І |
^ |
Ш |
^ |
^ |
Ш |
||||
Д . |
|
|
\ |
|
V |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
j |
|
„ |
i |
|
|
|
|
|
|
|
|
|
\ 16.l/BUICKW/H5/ls\\iJ/CflRT/fls/Le |
|
J! IZ/C/fy/Li/B/Ag/lB |
|||||||||
|
|
L |
2J/BE/A„/L„ |
Ѵ/в/А,г/£,2 |
|
|
|
|
|||||
ü/QEaS/Ra/lg, y/BELM/R,0/L,o |
|
|
|
|
|||||||||
|
|
ІФУ/Я,/І, |
II |
|
Iß/E/flz/Lz/m/Ls/C/flj/lJMZ^ |
||||||||
Рис. 6-2. Дерево |
однозначно |
усеченных ключевых |
слов |
переменной |
|||||||||
|
|
|
|
длины. |
|
|
|
|
|
|
|
|
|
менты хранятся на д о р о ж к а х |
третьего |
уровня: Т\% Tu, |
|||||||||||
Toi и Foi (рис. 6-2). Последний в алфавитном |
|
порядке |
|||||||||||
фрагмент |
д о р о ж к и третьего |
уровня |
помещается |
( т а к ж е |
|||||||||
в алфавитном |
порядке) |
на д о р о ж к у |
второго |
уровня, т. е. |
|||||||||
фрагмент Е на д о р о ж к е Ті2 помещается |
в виде |
последне |
|||||||||||
го фрагмента |
на д о р о ж к у |
второго уровня |
Tw |
с |
адресной |
||||||||
ссылкой |
Ті2. |
Аналогично |
фрагмент |
CART |
|
дорожки |
|||||||
Гн входит |
в д о р о ж к у Ті0, |
з а в е р ш а я ее (фактор |
ветвления |
||||||||||
второго уровня равен 2) . Последним |
фрагментом |
Тю |
|||||||||||
является Е\ он входит в запись |
первого |
уровня |
|
(хранит |
|||||||||
ся в оперативной памяти) с адресной |
ссылкой Гю. |
|
|||||||||||
Это дерево декодируется аналогично дереву ключе |
|||||||||||||
вых слов |
постоянной |
длины. |
Особенность |
заключается |
|||||||||
в применении |
к последнему |
уровню |
правил |
декодирова |
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
ло?. |
ния однозначных |
усечений |
ключевых |
слов переменной |
|
длины на отдельной дорожке, рассмотренных выше. |
||||
Н а п р и м е р , |
при декодировании B A K E R сравнение на |
|||
первом уровне |
показывает, |
что |
|
|
|
|
B A K E < B E L M . |
|
|
Сравнение |
с дорожкой |
7'оо показывает: |
||
В А К Е > В А І ; |
|
|
||
B A K E < B E L M . |
|
|||
П р а в и л а декодирования |
последнего |
уровня в приме |
||
нении к д о р о ж к е |
Т02 дают: |
|
|
|
B A K E R # . B E L L S ;
|
|
В А К Е = £ B E L M ; |
|
|
|
|
|
|
ВА |
=И=.ВЕ; |
|
|
|
|
|
В |
= В . |
|
|
|
В |
результате декодирования |
получается |
адрес |
связи |
||
Л і 2 с длиной |
списка L i 2 . |
|
|
|
||
К |
этому |
дереву |
применимы |
правила |
оперативного |
|
обновления постоянного дерева. |
Однако при этом |
про |
||||
цедура обновления |
д о л ж н а обеспечивать |
возможность |
||||
генерации нового однозначного фрагмента и регенерации дорожки в целом.
6-3. ДЕРЕВО ПОЛНЫХ КЛЮЧЕВЫХ СЛОВ ПЕРЕМЕННОЙ ДЛИНЫ
Сохранение полного ключевого слова гарантирует одно значность декодирования . Существуют два способа де кодирования с сохранением полных ключевых слов. Тре бующий больших з а т р а т памяти, но более простой в от
ношении программирования способ состоит в |
примене |
нии к полному ключу правил создания дерева |
перемен |
ной длины, приведенных выше. Другой подход, требую
щий |
более сложного программирования, |
но |
экономный |
||
в отношении памяти, состоит в применении |
процедуры |
||||
грамматического |
разбора . |
Объем требуемой памяти |
|||
в этом случае зависит от степени общности |
начальных |
||||
букв |
ключей. Д л я |
словарей |
дескрипторов |
обычного есте |
|
ственного языка эта общность не столь высока, следо вательно, требуется больший объем памяти, чем при
ПО
|
|
|
|
E Eyers |
|
el |
lac |
ar |
гогіег unlap yson |
/ К |
/ К |
Л |
|
Л |
Ъ Hey her |
I Ison man |
к кшеіі |
der |
ton |
Л
bet son Рис. 6-3. Грамматический разбор имен табл. 6-1.
однозначном усечении, но несколько меньший, чем при хранении полного ключа. Грамматический разбор 15 имен (табл. 6-1) иллюстрируется па рис. 6-3.
6-4. МЕТОД РАНДОМИЗАЦИИ
При использовании метода рандомизации [Л. 13], иногда называемого кодированием с преобразованием *, ключе вые термины естественного языка постоянной или пере менной длины преобразуются в ключи постоянной длины из заданного диапазона целых чисел. Д л я этого над исходными ключевыми терминами выполняются опреде
ленные математические действия. Например, |
если |
за |
||||
дан диапазон целых чисел |
0 — 1023, то |
из ключевого |
тер |
|||
мина, представленного |
в |
коде BCD **, |
можно |
выделить |
||
10 бит и использовать их |
как фрагмент |
(ключевую ссыл |
||||
ку) постоянной длины. |
|
В |
результате |
могут, |
конечно, |
|
получаться дублированные ссылки, как это бывает при усечении дерева ключевых слов постоянной длины . Дей
ствительно, если |
в |
рассматриваемом |
примере система |
|||
содержит более |
1 024 |
ключей, то |
получается |
дублирова |
||
ние |
(несколько |
полных ключей |
могут |
преобразовывать |
||
ся |
в одну ключевую |
ссылку) . Если отображение ключей |
||||
в ключевые ссылки |
сделать по |
возможности |
равномер |
|||
ным, то количество |
дублирований можно |
уменьшить. |
||||
(Равномерное отображение означает, |
что д л я |
заданного |
||||
набора ключей отклонение от среднего количества дуб лированных ссылок минимально.)
* Английский термин hash coding. (Прим. пер.)
** Американский двоично-десятичный код. (Прим. пер.)
П р о щ е |
всего выполнить |
одну или несколько арифме |
||
тических |
операций либо |
над |
всем |
закодированием |
в BCD ключом, либо н а д |
его частью, |
а затем провести |
||
операцию |
выделения . Это |
удалит |
из кода регулярность, |
|
присущую некоторым комбинациям букв в естественном языке (например, повторения некоторых последователь-
КлючХ ключУ. ключУг
|
А |
і |
L |
|
|
Рандомиаировать в: |
|
||
|
1 |
& |
У |
|
|
\ |
|
||
Обл.1 |
Облх |
^Обл.у |
Обл.п |
|
|
Обл. 2 |
Яу |
— f>„ |
|
Я,. |
я2 |
ях |
||
Я^Ключ X/Lx/0
[Данные 1 к'лючах\
Яу:ключУ,/1.уі}яУі
Данные ' ключа YA
\Яу:ключ
[Данные"] ключа £j
Рис. 6-4. |
Декодирование справочника ключей с помощью |
|
|||||
|
|
метода рандомизации. |
|
|
|||
ностей |
букв |
в приставках, |
корнях и с у ф ф и к с а х ) . |
Так, |
|||
к а ж д о е |
машинное слово, |
с о д е р ж а щ е е |
закодированное |
||||
в BCD |
ключевое" слово, |
можно |
возвести |
в к в а д р а т и |
|||
выделить из |
результата |
к а ж д ы й |
четвертый бит. Если |
ло- |
|||
статочного количества знаков не получилось, то можно
выделить к а ж д ы й четвертый бит, отсчитанный |
от |
второго |
||
бита, |
и т. д. П о д о б н а я операция выполняется |
до |
выде |
|
ления |
нужных п бит. П р и этом ключевая ссылка |
|
посто |
|
янной длины будет находиться в диапазоне 0 — |
2П—1. |
|||
Н а |
рис. 6-4 и з о б р а ж е н процесс декодирования |
спра |
||
вочника |
ключей методом рандомизации . В верхней части |
|||||||
рисунка |
показана последовательность областей памяти, |
|||||||
обозначенных Обл. |
1, |
Обл. |
2, |
Обл. |
х, |
..., Обл. у, ... |
||
..., Обл. |
п. Количество |
этих |
областей |
соответствует за |
||||
данному |
диапазону |
постоянных |
ключей. |
Следовательно, |
||||
112