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

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

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

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

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

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

198

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

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

выражение вида Fi-i-Fh обозначает последовательность ячеек, начинающуюся с ячейки Fi и оканчивающуюся ячейкой Fk\ выражения вида (С*), (D), (F{-i-Fh) обозна­ чают коды, записанные по адресам С;, D, F\-i-Fk.

Алгоритм автоматического составления словаря словоформ

1.Положить Ei = Eh.Ri = Ru Si = Si.

2.Проверить ( Е і ) на наличие признака конца текста. При поло­ жительном результате проверки — конец работы алгоритма, при от­ рицательном — перейти к п. 3.

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

199

6.Перенести (С,) в ячейку D . Перейти к п. 7.

7.Проверить для (D ) выполнение условия А = 0. Если условие

кп. 9.

9.Положить R i = R i + k. Перейти к п. 2.

10. Проверить коды (Ej-bEj,) и (A -^ -A + k — 1) на совпадение. При положительном результате прсіверки перейти к п. 2, при отри­

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

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

Составление словарей словоформ и словарей основ слов на ЭВМ с ограниченной емкостью оперативной памяти

Если объем словаря превосходит емкость оператив­ ной памяти машины, то при его составлении приходится прибегать к специальным приемам. Существо этих прие­ мов заключается в том, что в памяти машины в оконча­ тельном виде формируется не весь словарь, а лишь от­ дельные его участки, которые по мере готовности выда­ ются на печать. Рассмотрим три таких приема: 1) состав­ ление словаря по участкам; 2) двухступенчатое состав­ ление словаря; 3) составление словаря способом «пере­ полнения».

20«

Идея составления словаря по участкам заключается

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

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

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

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

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

201 *

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

Составление словарей наименований понятий на ЭВМ

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

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

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

2 0 2

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

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

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

основ слов на номера их смысловых эквивалентов, то будут учтены и трансформации с изменением основ слов.

Описанные процедуры автоматического составления словаря наименований понятий основаны на серийной обработке всего исходного списка словосочетаний. Они неудобны для пополнения словарей и для внесения в них изменений. Более удобными в этом отношении являются ассоциативно-адресные- методы, и в частности узловой способ, описанный в гл. 5 и 6. Этот способ позволяет составлять словарь наименований понятий «с нуля» и вносить в него любые изменения.

Требования, предъявляемые к словарю наименований понятий в процессе кодирования и декодирования ин­ формации, противоречивы. В процессе кодирования ре­ шается задача распознавания терминов-,' и здесь требу­ ется приводить трансформационные варианты словосо­ четаний к канонической форме. При этом может теряться информация о порядке следования Ң 9 формах слов

§ 0 3