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

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

На рис. 6.2 приведен пример использования узлового способа для организации массива сообщений, каждое из которых состоит из трех элементов. Здесь, как и при цепном способе организации массивов, поле памяти ЭВМ делится на две части: А — адресную часть, Б — массив сообщений. Для записи одного сообщения отводится одна ячейка памяти (см. часть Б на рис. 5.2).

Ячейка делится на три участка. Каждый участок представляет один элемент сообщения. Участки ячеек, обозначающие одинаковые элементы сообщений, соеди­ няются между собой цепочками адресных отсылок (эти цепочки на рис. 5.2 условно изображены сплошными линиями со стрелками). Адресные отсылки к участкам, являющимся первыми элементами цепочек, указываются в части А поля памяти, а отсылки к остальным элемен­ там цепочек — в части Б. При этом отсылки к элементам ассоциативных цепочек с порядковым номером і записы­ ваются на участках, являющихся элементами этих цепо­ чек с порядковым номером і —1. На участках, отведен­ ных для последних элементов цепочек, записывается признак конца (на рис. 5.2 такие участки заштрихо­ ваны) .

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

Поиск в адресной части считается законченным, если

поиска в адресной части. Если в качестве поискового признака уңазьрңается КОД одного элемента сообщения, то

84

\ r

ч

Рис. 5.2. Узловой способ поиска.

из массива Б выбираются все сообщения, содержащие этот элемент (все сообщения, включающие элементы ассоциативной цепочки с начальным адресом Л0). Если задается несколько кодов элементов сообщений, то про­ слеживаются все соответствующие этим «одам ассоциа­ тивные цепочки и выбираются сообщения, включающие все заданное элементы,

85

При дополнении поискового массива новыми сообще­ ниями выполняются следующие операции. Сначала для элементов нового сообщения в массиве А ищутся адреса Ап. Если сообщение не содержит новых элементов, то найденные адреса записываются в первую свободную ячейку массива Б, а адреса участков этой ячейки зано­ сятся на прежние места хранения адресов Ао. Если со­ общение имеет в своем составе новые элементы, то для них вместо адресов До в свободную ячейку массива Б заносятся признаки конца ассоциативных цепочек, а ад­ реса участков этой ячейки и коды новых элементов за­ носятся в свободные ячейки массива А. Ячейки массива А подключаются к ассоциативным цепочкам, соответст­ вующим сверткам кодов новых элементов. Сообщения исключаются из поискового массива путем затирания содержимого ячеек, представляющих эти сообщения, и переноса хранившихся в них отсылочных адресов на такие участки ячеек массива Б, где ранее были записа­ ны адреса участков освобождаемых ячеек.

Способ представления массивов, приведенный на рис. 5.2, может быть обобщен для случая, когда сооб­ щения состоят из произвольного числа элементов. При этом структура адресной части останется неизменной, а в массиве сообщений для каждого узла потребуется отвести несколько рядом расположенных ячеек. Если количество элементов в сообщениях будет одинаковое, то начала и концы узлов (а следовательно, и границы сообщений) могут быть определены по адресам ячеек; если разное, то для определения границ узлов необходи­ мо ввести специальные разделительные признаки. Коды разделительных признаков должны отличаться от кодов отсылочных адресов и от кодов признаков конца ассо­ циативных цепочек. Для записи признаков начала и конца сообщений можно также выделить в каждой ячей­ ке памяти один разряд или группу разрядов, а в допол­ нение к этим признакам указывать количество ячеек в узле.

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

8 5

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

Г л а в а 6 МАШИННЫЕ СЛОВАРИ

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

В ИПС словари слов могут быть в виде словаря сло­ воформ * и в виде словаря основ слов. В первом случае основным элементом словаря является буквенный код словоформы, во втором — буквенный код основы слова. В процессе перевода сообщений с русского языка на информационный поиск в словаре осуществляется по буквенному коду словоформы или основы слова, а из словаря выбирается порядковый номер словоформы (основы слова) и сопровождающая его грамматическая информация. При переводе с информационного языка на русский из словаря по номеру словоформы или основы слова выбирается буквенный состав искомого элемента и его грамматическая информация (если она необходи­ ма). Первый вид поиска в словаре называется п р я ­ мым, а второй — о б р а т н ы м . В ИПС словарь должен быть построен так, чтобы он был удобен и для прямого и для обратного поиска.

Грамматическая информация к слову характеризует его свойства в различных контекстных окружениях и включает морфологические, синтаксические и семанти­ ческие признаки. Она может, например, содержать све­ дения о принадлежности слова к определенному грам­ матическому или семантическому классу, о характере изменения его формы в различных контекстных окруже-

* Словоформа — последовательность букв между двумя сосед­ ними пробелами.

8 7

шіях, о сочетаемости данного слова с другими словами или классами слов и т. п.

В памяти ЭВМ грамматическая информация о слове может представляться в различных формах. В работах по машинному переводу широко используется такой способ представления грамматической информации, когда за каждым признаком закрепляется определенная позиция в памяти машины, где записываются различ­ ные конкретные значения этого признака. Число раз­ личных комбинаций значений признаков ограничено, поэтому было бы нецелесообразно сопровождать каж­ дую форму или каждую основу словаря полным переч­ нем значений грамматических признаков. Лучше такое решение, когда различные наборы значений грамматиче­ ских признаков выносятся в отдельный список, нумеруют­ ся, а в словаре указываются только их номера.

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

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

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

8 8

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

Буквенные коды слов имеют различную длину и в зависимости от типа используемой ЭВМ могут быть записаны в одной или нескольких ячейках памяти. Учи­ тывая это обстоятельство, можно объединить слова в группы с одинаковой «ячеечностыо» і, а в пределах каждой группы расположить по алфавиту. Границы групп кодов слов можно отобразить в специальной т а б ­

чальный номер АѴ слова в группе.

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

мощью таблицы разделителей, так чтобы выполнялось условие N0i^ ;N < N o i+1. Поиск в словаре ведется на раз­ личных участках по разным подпрограммам, так как слова, записанные в двух, трех и большем числе ячеек, необходимо сравнивать по всей длине их буквенных кодов.

Скорость поиска в словаре может быть значительно увеличена, если увеличить объем таблицы разделителей и тем самым повысить ее разрешающую способность. Можно, например, расположить все слова по возраста­ нию их длины: сначала группу однобуквенных слов, за­ тем двухбуквенных, за ними трехбуквенных и т. д., а в пределах каждой группы упорядочить слова по ал­ фавиту. В качестве разделительных признаков можно взять длину слова, выраженную в количестве букв, и код первой буквы.

89