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

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

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

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

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

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

178

место хранения относительного адреса соответствующей группы номеров подчиненных понятий. После этого по относительному адресу выбираются элементы группы. Конец группы определяется по относительному адресу группы, следующей за искомой. Если группы номеров понятий хранятся в памяти машины в виде непрерывного массива, то в качестве относительных адресов можно использовать порядковые номера начальных элементов групп в массиве. Местоположение этих элементов можно определить по формулам вида (10.1).

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

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

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

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

При независимом установлении связей между поня­ тиями одни связи иногда являются следствием других. Например, если между понятиями А, В и С зафиксиро­ ваны связи А ^ В , В~^С и Л—>-С (->— знак подчинения), то связь А-^~С является следствием двух первых связей. Такая связь может быть исключена из словаря, так как она восстанавливается при объединении результатов, по­ лученных на всех этапах поиска.

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

Связи подчинения между понятиями иногда изобра­ жают в виде иерархических деревьев. Такие деревья до­ статочно наглядны и могут являться исходным материа­

180

лом для построения экономичной системы парных связей между понятиями с целью ее ввода в машину и оформ­ ления в виде классификационного словаря. Но при боль­ ших объемах списков наименований понятий (несколько тысяч или несколько десятков тысяч единиц) построение деревьев классификации оказывается чрезвычайно труд­ ным, в особенности если список понятий богат синони­ мами и требуется большая степень полноты отражения смысловых связей. Гораздо легче установить парные от­ ношения между понятиями и ввести их в машину, а за­ тем исключить избыточные связи.

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

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

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

в классификационном словаре производится цепным спо­ собом.

181