Файл: Белоногов Г.Г. Автоматизированные информационные системы.pdf

Система разделителей, используемая при такой 'ор­ ганизации словаря, представлена в табл. 6.1. Строки этой

Т а б л и ц а 6.1

таблицы обозначены буквами русского алфавита, столб­ цы — числами, выражающими количество букв в слове, а в клетках записаны начальные номера слов для каж­ дого участка словаря, соответствующего сочетанию при­ знаков «длина слова» и «код первой буквы». Поиск на участке словаря может производиться последовательным просмотром буквенных кодов слов или способом «деле­ ния пополам». Попутно по адресам ячеек памяти опре­ деляются номера просматриваемых слов.

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

номеров слов, где М — длина ячейки в двоичных разря­ дах; г — длина кода номера слова; Е — оператор выделе­ ния целой части числа.

90

Форма записи разделителей в памяти ЭВМ для слу­ чая, когда в одной ячейке помещается три номера слова, иллюстрируется табл. 6.2. Обозначения строк и столбцов в этой таблице приведены для наглядности. В действи­ тельности они нигде не записываются.

91

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

Участок таблицы разделителей определяется но

в которой Ао — адрес ячейки, предшествующей первой

А0, а позицию номера слова в ячейке определяют по формуле

где символ Res обозначает операцию вычисления остатка при делении одного числа на другое. При прямом и об­ ратном поиске в словаре адрес буквенного кода слова определяется по его номеру с помощью формулы (6.1). Объем таблицы разделителей определяется согласно вы­ ражению

записывается по три номера слова, то под таблицу раз­ делителей необходимо отвести около трехсот ячеек. При этом для каждого сочетания признаков «длина слова» и «код первой буквы» отводится место под начальный но­ мер группы слов независимо от того, имеются ли в дей­ ствительности в словаре слова, обладающие этими приз­ наками.

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

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

92

в которой разделительным признаком служит длина сло;- ва. Полное исключение пустых клеток из таблицы приве­

адресам участков словаря производится по сверткам ко­ дов слов (код свертки образуется из кода первой буквы и кода длины слова). Поиск на выделенном участке словаря производится последовательным просмотром буквенных кодов слов.

В ячейках) к которым адресуются по сверткам кодов слов, могут записываться не начальные адреса участков словаря, а начальные адреса групп адресных отсылок к отдельным словам этих участков. После обращения по свертке к группе адресных отсылок поиск в словаре про­ изводится последовательным сравнением соответствую­ щих этим отсылкам буквенных кодов слов с буквенным кодом искомого слова. Такой способ представления сло­ варя позволяет записывать буквенные коды новых слов

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

впроцессе включения новых слов здесь требуется раз­ двигать 'Массив адресных отсылок. Этого можно избе­ жать, если применить цепной способ поиска (см. гл. 5),

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

кода (я+1)-го слова участка.

Поиск в словаре ведется среди группы слов, имею­ щих такой же код свертки, что и искомое слово. При этом адрес буквенного кода первого слова выбирается

93