"Устройство для морфологического анализа слов естественных языков и языков "деловой прозы" Советский патент 1993 года по МПК G06F15/38 

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

Целью изобретения является повышение Окорости процессов морфологического анализа слов реальных языков, на основе логических признаков принадлежности к классам словоформ.

На фиг. 1 изображена структурная схема устройства.

На фиг. 2 представлен вариант технической реализации структуры блока поиска

вхождений,

На фиг. 3 представлен вариант технической реализации структуры блока анализа характеристического вектора.

На фиг. 4 представлен вариант технической реализации структуры блока хранения

окончаний.

00 GJ V8 ОЭ

КЭ XJ

На фиг. 5 представлен вариант технической реализации структуры блока хранения основ.

На фиг. 6 представлен вариант технической реализации структуры блока хранения признаков.

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

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

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

На фиг. 10 представлен вариант технической реализации структуры блока анализа морфологических признаков.

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

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

На фиг. 13 изображена содержательная граф-схема алгоритма работы блока управления.

На фиг, 14 изображена размеченная граф-схема алгоритма работы блока управления.

Устройство для морфологического анализа слов естественных языков и языков деловой прозы (фиг. 1} содержит блок 1 памяти слов, блок 2 регистров слов, блок 3 поиска вхождений, ключ 4, блок 5 анализа характеристического вектора, блок 6 хранения окончаний, блок 7 хранения основ, блок и ы .н ь л е т а в о н с

0

5

0

5

0

5

8 элементов ИЛИ, дешифратор 1-9, коммутатор 10, дешифратор 2-11, блок 12 хранения признаков, блок 13 регистровой памяти, блок 14 формирования адреса, блок 15 анализа морфологических признаков, блок 16 регистров символьного вхождения, блок 17 формирования результата классификации, блок 18 задержки, блок 19 управления.

Характеристическим вектором (10) называется двоичное слово, которое равно длине обрабатываемого слова и индицирует единицей в одном или нескольких разрядах позицию вхождения какой-либо буквы алфавита в слове. Например, слову катамаран при формировании вхождения буквы а будет характеристический вектор: 010101010

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

Пусть задано слово основательный. Основа слова - основ, окончание - атель- ный. Пусть также из списка окончаний извлечено окончание ук. Напоминаем, что в предлагаемом устройстве слова представляются в обратной записи. Тогда будем иметь:

ере, КОВ И ЯЗЫКОВ ДЕЛОВОЙ ПРОЗЫ Изобретение относится к техническим ствам информации и вычислительной техники и может быть использовано как под истема сложных систем лингвистического анализа и структурных методом рас- авания образов, а также для процессов, связанных с решением проблем искусствен ого интеллекта. Целью изобретения является повышение скорости процессов мороологического анализа слов реальных языков на основе логических признаков принадлежности к классам словоформ. Устройство содержит блок памяти слов, блок регистров слов, блок поиска вхождений, ключ, блок анализа характеристического вектора, блок хранения окончаний, блок хранения основ, блок элементов ИЛИ, два дешифратора, коммутатор, блок хранения признаков, блок регистровой памяти, блок формирования адреса, блок анализа морфологических признаков, блок регистров символьного вхождения, блок формирования результата классификации, блок задержки, блок элементов ИЛИ, блок управления. Новым в устройстве является то, что в нем можно реализовать скоростной анализ слов по заданному множеству формул подстановок, имеющих алфавитно и семантически различные правые и левые части, что позволяет исключить возврат на предыдущие формулы, а также быстро устанавливать отсутствие вхождения одних слов в другие обрабатываемые слова. 3 з.п. ф-лы, 14 ил. -г Ё

К

ооооооооооооо.

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

йыньлетавонсо

й

1 000000000000

йыньлетавонсо

ы

о Гооооооооооо

1-й шаг поиска вхождения

1-й шаг поиска вхождения

2-й шаг поиска вхождения

1 000000000000 01 О О О О О О .0 О О О О

010000000000 О

йыньлетавонсо

Н

0010000000100

0100000000100 0010000000000

001000000000 О

Очевидно, что при просмотре для опре- делиния вхождения всех оставшихся букв (сил волов) окончаний и обрабатываемого в

ем примере, мы будем получать харакH3U

тер

тогда, когда вхождение имеется.

стический вектор с единственной еди-

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

раз ..„.-.

полняется между 1-ым и 1+1-м разрядами соогветствующих характеристических векторов дает, при длинных основах и окончания:;, существенный выигрыш во времени.

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

промежуточный характеристический вектор

3-й шаг поиска вхождения

промежуточный характеристический вектор

0

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

Содержательная граф-схема алгоритма работы блока 19 управления устройства для морфологического анализа слов естествениых языков и языков деловой прозы приведена на фиг. 13. Для описания работы устройства используются следующие идентификаторы:

0 27, САП - команда разрешения записи

морфологических признаков в регистр 2

блока анализа морфологических признаков.

28, АОК - линия адреса блока хранения

окончаний,

5 29. ДОС - линия адреса блока хранения основ,

5 34. СхВ - команда разрешения хранения информации, поступающая из Рг1 в Рг2, подаваемая на С входы триггеров Рг2.

0 управляющие входы первой группы элементов И.

0 40. PS - информационный выход слова блока памяти слов,

0 46. ВИКЛ - выходная информация ключа.

чер|

НИИ

тир

вхоАов блока регистровой памяти.

Работа алгоритма управления устройства.

Содержательная ГСА управления приведена на фиг. 13 и отражает работу блока управления (фиг, 1).

По сигналам УОО и Пуск (блоки 2, 4 - граф-схемы алгоритма) происходит уста- нов са в нуль всех элементов памяти устрой- ствг, кроме блока хранения основ, блока хранения окончаний, блока хранения признаков и блока памяти слов, по команде СБРОС: Г (блок 3).

В блоке 5 алгоритма по команде СЗ нов бло ков,

ходит указанная загрузка этого регистра, т.е. все Д -триггеры регистра 1 блока 15 анализа морфологических признаков будут усте новлены в единицу,

В блоке 6 алгоритма по команде СЗ происходит запрет на прием информации в триггеры регистра 1 блока 15 анализа морфологических признаков, при этом данный регистр переходит в режим хранения информации. По команде сигнал принимает значение нуля (блок 6).

В блоке 7 алгоритма по команде про 1сходит разрешение на выдачу из блока 1 памяти слов информации и разрешения

происходит разрешение уста- си в единицы Д -триггеров регистра 1 :а 15 анализа морфологических признало команде (блок 5) происз блок 18 задержки на прием этой же

информации в блок 22 регистра слов. По комзнде происходит прием информации (очередного слова) из блока 1 памяти слов в блок 2 регистра слов. По команде происходит просмотр

блока 6 хранения окончаний (блок 7 алгоритма).

В блоке 8 алгоритма происходит проверка признака СЛП. Если СПП-1, то это

означает просмотр блока 6 хранения окончаний. Если , то это означает просмотр блока 7 хранения основ.

В блоке 9 алгоритма происходит проверка признака СПБ. Если СПВ-1, то это

0 означает просмотр блока 7 хранения основ. Если СПВНГ, то это означает прекращение работы устройства и осуществляется переход на блок 39 алгоритма.

В блоке 10 алгоритма по команде

5 происходит считывание окончаний из блока 6 хранения окончаний до тех пор, пока все окончания не будут просмотрены, либо в случае нахождения требуемого окончания. По команде происхо0 дит запрет на считывание основ из блока 7 хранения основ. По команде происходит коммутация выхода блока 6 хранения окончаний на вход блока регистровой памяти. По команде происходит

5 запрет коммутации выхода блока 7 хранения основ на вход блока 13 регистровой памяти (фиг. 7).

В блоке 11 алгоритма по команде: НАПО: 0 происходит запрет на считывание

0 окончаний из блока 6 хранения окончаний;. По команде происходит считывание основ из блока 7 хранения основ до тех пор, пока все основы не будут просмотрены, либо в случае нахождения требуемой осно5 вы. По команде происходит запрет коммутации выхода блока 6 хранения окончаний на вход блока 13 регистровой памяти (фиг, 7).

В блоке 12 алгоритма по команде При0 ем 1 осуществляется формирование сигнала разрешения в блок 13 регистровой памяти (фиг. 1) для приема очередного сигнала. По команде (блок 12) происходит прием группы символов из блоков

5 хранения окончаний (основ) в блок 13 регистровой памяти (фиг. 8).

В блоке 13 алгоритма по команде Выдача происходит выдача очередного символа из блока 13 регистровой памяти в

0 блок 16 регистров символьного вхождения (фиг. 1). Команда Выдача формируется блоком управления.

В блоке 14 алгоритма по команде Прием происходит разрешение на прием

5 информации из блока 13 регистровой памяти в блок 16 регистров символьного вхождения, по команде СИ2: 1 (блок 14) происходит подача синхро-импульсов из блока 19 управления в блок 16 символьного вхождения, по команде БРСВ:РДГ (блок

14) происходит прием в блок 16 регистров символьного вхождения информации из блока 13 регистровой памяти (фиг. 1).

В блоке 15 по команде Выдача2: Г происходит разрешение на выдачу информации из блока 16 регистров символьного вхождения в блок 3 поиска вхождения (фиг.

t).

В блоке 16 происходит проверка признака состояния блока 16 регистров символьного вхождения СОГГ. Если СОГЬО, то это соответствует тому, что в блоке 16 регистров символьного вхождения имеется не пустая информация (есть очередной символ). При этом выполняется проверка признака РРП (блок 17 алгоритма). Если (это означает, что в блоке 16 регистров символьного вхождения находится пустая запись, то есть конец слова-вхождения), то выполняется переход на блок 29 алгоритма.

В блоке 17 происходит проверка признака РРП. Если (это означает, что символа, который находится в блоке 16 регистров символьного вхождения нет в обрабатываемом слове). Вхождение при этом не обнаруживается. При этом осуществляется переход на блок 12 алгоритма и организуется цикл на блок 12 алгоритма поиска символа вхождения до тех пор, пока не будет обнаружено совладение буквы в блоке 16 регистров символьного вхождения и в блоке 2 регистров слов (фиг. 1). Выход из цикла организуется тогда, когда будет обнаружено вхождение, будет найдена буква в блоке 2 регистров слов, т.е. РРЛ-1 (блок 17).

В блоке 18 алгоритма по команде происходит разрешение приема характеристического вектора, поступившего из блока 3 поиска вхождения в ключ 4 (фиг. 1). По команде (блок 18} происходит загрузка характеристического вектора в ключ 4.

В блоке 19 алгоритма происходит проверка признака СПТ. Если , то формируется СЗАЩ: 1 (блок 24). На синх- ровходы триггеров регистра 1 блока 5 анализа характеристического вектора подан единичный сигнал и регистр подготовлен к приему очередного характеристического вектора и в этот регистр принимается характеристический вектор (блок 24). При этом осуществляется переход на блок 25 алгоритма. Если (это означает, что загружен регистр 1 блока 5 анализа характеристического вектора) и по команде (блок 20) СЗАЩ: 0 устанавливается режим хранения этого вектора в указанном регистре.

В блоке 21 алгоритма выходная информация регистра 1 блока 5 анализа характеристического вектора (ВИ Рг1) обрабатывается с помощью поразрядной

операции коньюнкция, с выходной информацией ключа 4 (ВИКЛ), так, что каждый 1+1 разряд выходной информации ключа (ВИКЛ) коньюнктируется с 1-ым разрядом выходной информации ВИ РП регистра 1

0 блока 5, а первый разряд ключа 4 коньюнктируется с последним разрядом регистра 1 блока 5 анализа характеристического вектора, т.е. коньюнкция выполняется по косой линии ВГЭИ: ВИКЛ ВИ Рг1. Результат

5 операции коныонкции поступает на вход второй группы элементов И (ВГЭИ).

В блоке 22 алгоритма происходит проверка признака СИЛ. Если , то осуществляется переход на блок 26 алгоритма.

0 Если , то в блоке 23 алгоритма по команде СЗАЩ: 1 происходит подача сигнала разрешения для приема информации из ключа 4 в регистр 1 блока 5 анализа характеристического вектора. По команде

5 ЭлИЛИ (блок 23) происходит загрузка вектора в регистр 1 блока 5 анализа характеристического вектора выходкой информации элементов ИЛИ (фиг. 3).

В блоке 25 алгоритма по команде

0 СЗАЩ: 0 происходит подача на синхро- входы триггеров регистра 1 блока 5 анализа характеристического вектора сигнала запрета на прием информации и регистр переводится в режим хранения. При этом

5 осуществляется переход на блок 13 алгоритма, т.е. организуется цикл поиска нужного вхождения.

В блоке 26 алгоритма происходит проверка признака АПС. Если АПОО, то

0 осуществляется переход на блок 12. Если , то в блоке 27 алгоритма по команде СЗАЩ: 1 происходит подача сигнала разрешения для приема информации из регистра 2 блока 5 анализа характеристиче5 ского вектора (фиг. 3). По команде РВ:-1 происходит подача на управляющие входы первой группы элементов И блока 5 анализа характеристического вектора (фиг. 3) разрешающего сигнала. По команде

0 ЭлИЛИ происходит прием характеристического вектора выходной информации элементов ИЛИ в регистр 1 блока 5 анализа регистра характеристического вектора. В блоке 28 алгоритма по команде

5 происходит подача на управляющие входы первой группы элементов И блока 5 (фиг. 3) запрещающего сигнала, т.е. нуля. При этом регистр 2 блока 5 анализа характеристического вектора хранит инфор- мацию характеристического вектора, получе

нного при просмотре блока 6 хранения

окончании.

В блоке 29 алгоритма по команде +СчАПП: -1 происходит считывание очередного адреса из блока 12 хранения признаков (фиг. 6).

В блоке 30 алгоритма по команде

С/

шения для приема информации в регистр 2 блока 15 анализа морфологических признаков По команде (блок 30) происходит загрузка в регистр 2 блока 15 анализа морфологических признаков очередного

происходит подача сигнала разреMOf

СЗ

1 происходит подача сигнала разрешения для записи информации в регистр 1 блска 15 анализа морфологических призна- кощ. По команде Рг1: Рг1 & Рг2 (блок 31) происходит загрузка в регистр 1 блока 15

фологического признака.

В блоке 31 алгоритма по команде

ан, фор

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

конъюнкции (фиг. 10).

В блоке 32 алгоритма по команде происходит подача на регистр 1

блс|ка 15 анализа морфологических признаков

запрещающего сигнала для приема информации (режим хранения). По команде БОРК: РМ (блок 32) происходит передача и прием информации из блока 15 анализа

М0| МИ|

тесан;RE

фологических признаков в блок 17 фор- ювания результата классификации. За- в блоке 33 алгоритма производится лиз признака результата REZ. Если (это означает, что решение найде-

но однозначно и слово классифицируется по морфологическому признаку), то в блоке 34 алгэритма по команде входнослову в блоке 2 регистров слов, в специ- но отведенные для кода признака

му ал

регистры записывается двоичный код, например, соответствующей части речи входного слова. Если , то в блоке 35 алгоритма происходит анализ признака AIjlO. Если АПОЮ, то осуществляется

еход в блок 39 алгоритма. Если , в блоке 36 алгоритма по команде происходит подача на выходы С -триггеров регистра 2 блока 5 анализа

nef

то

Qi

„д,

характеристического вектора разрешающе- го с игнала для приема информации характеристического вектора. По команде

Рг1

происходит прием информации характеристического вектора разрешающего сигнала

для

приема информации характеристического

вектора. Эта информация характеристического гектора получена после просмотра блока 6 хранения окончаний.

В блоке 37 алгоритма по команде происходит подача на С входы

0

5

0

5

0

5

0

5

0

5

О -триггеров регистра 2 блока 5 анализа характеристического вектора нулевого сигнала. При этом регистр переходит в состояние хранения полученной информации.

В блоке 38 по команде СПП:-0 происходит запрет на выдачу информации из блока б хранения окончаний. Результат в этом случае еще не получен, поэтому необходимо перейти к просмотру блока 7 хранения основ для дальнейшего определения классификации слова. По команде СПВ:-1 происходит подача разрешающего сигнала на считывание информации из блока 7 хранения основ, т.е. разрешение на просмотр блока 7.

В блоке 39 алгоритма по команде Стоп происходит остановка устройства и анализ обрабатываемого слова.

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

Работа устройства для морфологического анализа слов естественных языков и языков деловой прозы заключается в следующем.

Внешние управляющие сигналы Пуск и Сброс поступают в блок 19 управления. Из блока 19 управления в блок 6 хранения окончаний поступает управляющий сигнал СПП. По этому сигналу происходит начало работы устройства. Блок 6 хранения окончаний содержит постоянное запоминающее устройство (ПЗУ), счетчик адресов, схему И, генератор импульсов, D-триггер (фиг. 4). По приходе сигнала прямоугольные импульсы генератора импульсов через схему И поступают на вход счетчика, который формирует адрес считывания из ПЗУ блок 6. Сигнал является разрешающим сигналом для считывания информации из ПЗУ блока 6 хранения окончаний. Так же этот единичный сигнал установит D-триггер блока 6 хранения окончаний в единичное состояние (фиг. 4). Итак, по приходе сигнала из блока управления происходит считывание адреса первой группы символов из ПЗУ блока 6 хранения окончаний (фиг. 4).

В ПЗУ блока б хранения окончаний вначале (по первому адресу) записываются окончания, которые имеют максимальное количество букв. Затем записываются окончания, имеющие меньшую длину и т.д. Последнее окончание, которое будет записано в ПЗУ окончаний будет иметь минимальную длину, т.е. содержать одну букву. При этом все окончания будут предварительно разбиты на группу символов. В одну группу символов входит одно окончание. В конце группы в ПЗУ записывается единичная информация. Этот код нужен для того, чтобы определить конец группы символов. По приходу из блока 19 управления сигналов и на вход коммутатора (фиг. 7) происходит коммутация выхода блока б хранения окончаний с входом блока 13 регистровой памяти. Блок 10 коммутатор содержит схемы И, схему ИЛИ. На информационные входы схем И1.1...И1.8 поступает информация из блока б хранения окончаний. Управляющим сигналом для этих схем И является сигнал УОК(фиг. 7). На информационные входы схем И2.1...И2.8 поступает информация из блока 7 хранения основ. Управляющим сигналом для этих И является сигнал УОС (фиг. 7). При УОК-Г и на выходе коммутатора будет информация, полученная из блока 6 хранения окончаний (фиг. 7). При УОК°0 и УООГ на выходе коммутатора будет информация, полученная из блока 7 хранения основ (фиг. 7).

Из блока 19 управления поступили сигналы , УОКИ, , при этом из ПЗУ блока б хранения окончаний считывается первое окончание (фиг. 4) и поступает на вход блока 13 регистровой памяти.

Из блока 19 управления поступает управляющий сигнал ПРИЕМ1 в блок 13 регистровой памяти (фиг. 9). Блок 13 регистровой памяти содержит дешифратор 1 записи, дешифратор 2 выдачи, регистры общего назначения, мультиплексор, инвертор. По приходу сигнала ПРИЕМ 1 дешифратор 1 записи организует очередь записи группы символов одного окончания или основы, подавая разрешающий сигнал на входы регистров общего назначения. Буква, которая вошла первой, выходит первой при считывании из блока 13 регистровой памяти. Адрес памяти при постановке в очередь задается блоком формирования адреса и блоком 13 регистровой памяти (фиг. 8). В первый регистр блока 13 регистровой памяти (фиг. 9) записывается последняя буква окончания или основы, во второй предпоследняя и т.д. Считывание происходит побук- венно. Как только будет считана группа символов окончания (основы) в регистры общего назначения, дешифратор 2 выдачи, по приходу из блока 19 управления сигнала ВЫДАЧА1 формирует адреса считывания из регистров общего назначения. Адреса поступают на управляющие входы мультиплексора. Согласно очереди считывания содержимое регистров общего .назначения поочередно считывается в блок 16 регистров символьного вхождения (фиг. 11) побук- венно. Блок 19 управления формирует сигнал Прием 2 в блок 16 регистров символьного вхождения. Блок 16 регистров символьного вхождения состоит из ключей приема КП, ключей выдачи KB и регистра хранения символа (фиг. 11). Сигнал Прием

5 2 поступает на входы ключей приема и тем самым отпирает их, Блок 19 управления формирует сигнал СИ2. Это синхроимпульсы, поступающие на С-входы триггеров регистра хранения символа. Символ,

0 считанный из блока 13 регистровой памяти, через ключи приема и по заднему фронту синхроимпульсов, записывается в регистр хранения символа (фиг, 11).

Слова, с которыми производится мор5 фологический анализ, находятся в блоке 1 памяти слов. Блок 1 памяти слов - это запоминающее устройство, которое имеет по каждому адресу запись длиной , где п - длина обрабатываемого слова. ЗУ хранит

0 все слова обрабатываемого текста (сложные слова декомпозируются на составные и анализируются независимо), на каждую букву отводится 8 бит.

По приходу из блока 19 управления сиг5 нала СР (сигнала разрешения) из блока 1 памяти слов в блок 2 регистров слов считывается одно слово. Сигнал СР (сигнал разрешения) является сигналом разрешения для записи в блок 2 регистров слов при считыва0 нии слова из блока 1 памяти слов, он поступает одновременно из блока 19 управления, но через блок задержки. По приходу сигнала СР (сигнала разрешения) слово записывается следующим образом: - последняя буква

5 слова записывается в первый регистр блока 2 регистров слов, предпоследняя буква слова записывается во второй регистр блока 2 регистров слов и т.д. В итоге в блоке 2 регистров слов входное слово записано в обрат0 ном порядке. Пример: входное слово необходимый записано йымидохбоен. Блок 2 регистров слов состоит из статистических восьмиразрядных регистров. Все сигналы регистров разрешения записи сое5 динены между собой и по приходу сигнала СР (сигнала разрешения) все регистры готовы принять информацию из блока 1 памяти слов, В каждом регистре блока 2 регистров слов содержится одна буква. В блоке 2 ре0 гистров слов в один из( регистров записывается двоичный код ПРС - признак принадлежности к одному из классов частей речи обрабатываемого слова. Информация из блока 2 регистров слов поступает в

5 блок 3 поиска вхождений (фиг. 2). По приходу из блока 19 управления сигнала ВЫДА- ЧА2 в блок 16 регистра символьного вхождения на управляющие входы ключей выдачи (KB) из блока 16 регистра символьного вхождения выдается одна буква оконnat ия (основы) в блок 3 поиска вхождений. Блок 3 поиска вхождения состоит из компа- ра оров (на равенство) букв. Происходит сравнение восьмиразрядного (байт) слова- 6yi вы, считанного из блока 16 регистра символьного вхождения, со всеми буквами, ка; сдая из которых представлена также одни и байтом, поступившим из блока 2 регистров слов. Если вхождение найдено, т.е. пр изошло совпадение, то формируется характеристический вектор, состоящий из нулей и одной или более единиц, соответствующих выходам компараторов (.2).

Если совпадение буквы из блока 16 ре- ги тра символьного вхождения и буквы блока 2 регистра слов не произошло то из блока 19 управления по сигналу Прием 1 считывается следующее окончание. Процесс счи- ты ания из блока б хранения окончаний и пе едачи в блок 13 регистровой памяти, а та1же передачи в блок 16 регистров символьного вхождения происходит аналогично описанному выше. Все выходы компараторов блока 3 поиска вхождения соединены с информационными входами ключа 4. Также выходы компараторов соединены с входами схемы дизъюнкции (ф1 г. 2). Выходы схемы дизъюнкции соеди- Hei ы с управляющими входами ключа 4. Ее ли произошло хотя бы одно совпадение в блоке 3 поиска вхождений, то на выходе схемы дизъюнкции появляется единица (фу г. 2). Этот единичный сигнал РРП, поступи 1ший на управляющие входы ключа 4 р зрешит запись получившегося характеристического вектора в ключ 4 (фиг. 3). Блок 19 управления сформирует единичный сигнал, разрешающий сигнал СЗАЩ, который поступит на С-входы триггеров блока 5 знали; ia характеристического вектора (фиг. 3). Бл ж 5 анализа регистра характеристиче- скс го вектора состоит из D-триггеров. Входы D-триггеров соединены с выходами эл ментов ИЛИ этого блока. Один из входов эл ментов ИЛИ блока 5 анализа характери- CTI чес кого вектора соединены с выходами схс м коньюнкции ключа 4. Вторые входы ка сдого из элементов ИЛИ соединены с выходами второй группы элементов И так, что 1-й выход второй группы элементов И соединен со входом 1+1 элементов ИЛИ (нумера- ци t идет по разрядам характеристического ве тора слева-направо). Прямые выходы D- Tpi ггеров регистра 1 блока 5 анализа харак- те истического вектора соединены с вх дами второй группы элементов И для оп еделения сопряженности букв в блоке 5, а также соединены с D-входами триггеров регистра 2 блока 5 анализа характеристического вектора. Последняя связь необходима для хранения информации характеристического вектора, полученного после просмотра блока 6 хранения окончаний и будет

применена при определении сопряженности букв при просмотре блока 7 хранения основ. Регистр 2 блока 5 анализа характеристического вектора состоит из D-триггеров. Прямые выходы D-триггеров регистра 2 со0 единены с информационными входами первой группы элементов И блока 5 анализа характеристического вектора. На управляющие входы первой группы элементов И подан сигнал РВ, поступающий из блока 19

5 управления. Выходы первой группы элементов И блока 5 соединены с третьими входами элементов ИЛИ блока 5 анализа характеристического вектора.

После приема характеристического век0 тора блоком 19 управления формируется сигнал СЗАЩ, равный нулю, и блок 5 анализа характеристического вектора переходит в режим хранения. Блоком 19 управления формируется сигнал Выдача 1 - считыва5 ния следующей буквы из блока 13 регистровой памяти.

Процесс загрузки из блока 13 регистровой памяти в блок 16 регистров символьного вхождения очередной буквы окончания или

0 основы аналогичен и описан выше. В блоке 3 поиска вхождения вторая считанная буква окончания или основы компарируется также со всеми буквами входного слова. Если произошло совпадение в одном компараторе

5 блока 3 поиска вхождения, то сигнал РРП принимает значение единицы. На управляющие входы ключа 4 подается разрешающий сигнал. Характеристический вектор из блока 3 поиска вхождения подается на ключ

0 4. Регистр 1 характеристического вектора блока 5 при этом находится в режиме хранения, т.е. хранит первый характеристический вектор. На входы второй группы элементов И блока 5 поступает первый характеристи5 ческий вектор из регистра 1 блока 5 и второй (полученный) характеристический вектор из ключа 4. Если в одной из схем второй группы элементов И блока 5 на входе была получена единица (единичный выход сигнала схемы

0 дизъюнкции 2 блока 5 анализа характеристического вектора). Единица на выходе одной из схем второй группы элементов И индицирует о том. что первая буква группы блока 16 регистров символьного вхождения

5 и вторая буква окончания (основы) во входном слове 1 блока 2 регистров слов расположены рядом (фиг. 3). Если блок 6 хранения окончаний будет просмотрен, но результат не будет получен (т.е. однозначное опреде- ление части речи обрабатываемого слова),

то полученный в результате просмотра блока 6 хранения окончаний характеристический вектор, который хранится в регистре 1 блока 5 анализа характеристического вектора, будет передан на хранения в регистр 2 блока 5. При приходе сигнала характеристический вектор из регистра 1 блока 5 анализа характеристического вектора перепишется в регистр 2 блока 5, и при будет храниться для дальнейшей работы устройства. После этого будет просматриваться блок 7 хранения основ (фиг. 5). Из блока 19 управления в блок 7 хранения основ поступает управляющий сигнал СПВ. По этому сигналу происходит начало работы устройства. Блок 7 хранения основ содержит постоянное запоминающее устройство, счетчик адресов, схему И, генератор импульсов (фиг. 5). По приходе сигнала и при этом сигнала пря- моугольные импульсы генератора импульсов через схему И поступают на вход счетчика, который формирует адрес считывания из ПЗУ блока 7. Сигнал является разрешающим сигналом для считывания информации из ПЗУ блока 7 хранения основ (фиг. 5). По приходе сигнала ) из блока 7 хранения основ происходит считывание адреса первой группы символов из ПЗУ блока 7 хранения основ (фиг. 5). При этом запись информации в ПЗУ блока 7 хранения основ аналогична записи информации в ПЗУ блока 6 хранения окончаний и описана выше, По приходе из блока 19 управления сигналов и происходит коммутация выхода блока 7 хранения основ с входом блока 13 регистровой памяти (фиг. 7), при этом . В случае получения сигнала , т.е. не сработало, косая линия будет просмотрена, в блоке 7 основ следующая группа основ, но при этом предварительно в регистр 1 блока 5 анализа характеристического вектора будет записана информация характеристического вектора из регистра 2 блока 5, полученная при просмотре блока 6 хранения окончаний. Информация перепишется при команде , подаваемой на управляющие входы первой группы элементов И блока 5 анализа характеристического векто- ра.

Если при этом в блок 16 регистров символьного вхождения пришел символ конца группы, это означает, что окончание слова найдено и чтобы получить результат, необ- ходимо проанализировать морфологические признаки в блоке 15 анализа морфологических признаков (фиг. 10). Блок 15 анализа морфологических признаков содержит группу элементов ИЛИ, два регистра и группу элементов И, выходы элементов ИЛИ группы соединены с информационными входами первого регистра, выходы которого образуют выход блока и соединены с первыми входами элементов И группы, вторые входы которых соединены с выходами второго регистра, информационный вход И синхровход которого является соответственно информационным входом и вторым управляющим входом блока, выходы элементов И группы соединены с первыми входами элементов ИЛИ группы, вторые входы которых соединены между собой и подключены к первому управляющему входу блока, третьим управляющим входом которого является синхровход первого регистра. В начале работы устройства блок 19 управления формирует сигнал СЗ Г (сигнал записи), этот сигнал является разрешающим для записи единичной информации в регистр 1 блока 15 анализа морфологических признаков (фиг, 10). Сигнал СЗ 1 поступает на входы С D-триггеров регистра 1 блока 15 анализа морфологических признаков. D- триггеры готовы принять информацию, поступившую из группы схем ИЛИ. Блок 19 управления формирует единичный сигнал ИН 1. Единичная информация через группу схем ИЛИ поступает на информационные D-входы триггеров регистра 1. Все D-тригге- ры регистра 1 блока 15 анализа морфологических признаков находятся в единичном состоянии. Работа блока 15 анализа морфологических признаков заключается в следующем. В регистр 2 из блока 12 хранения признаков записываются морфологические признаки по приходу сигнала САП из блока 19 управления после того, как будет найде но в слове окончание (основа).

В регистре 1 блока 15 анализа морфологических признаков находится единичная информация. В группе схем И происходит обнуление некоторых позиций в регистре 1 блока анализа морфологических признаков. После прихода сигнала СЗ равным единице из блока 19 управления, полученная информация в группе схем И записывается в регистр 1 блока 15 анализа морфологических признаков. Информация из регистра 1 блока анализа морфологических признаков поступает в блок 17 формирования результата классификации,°

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

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

иск

Дл на: фо 12

ке, то результат получен. При приходе из блфка 19 управления сигнала +СЧАПП происходит разрешение на считывание морфологических признаков из ПЗУ блока 12 (ранения признаков. Вся область хране- ни информации в ПЗУ блока 12 разделена на 2 части. Первая часть - это часть, где хранится информация о морфологических npiзнаках окончаний. Вторая часть - это часть, где хранится информация о морфологических признаках основ. Обращение к ПЗ f по одинаковым адресам из блока 6 хра- неь ия окончаний и блока 7 хранения основ

пючено, так как адреса будут различны. этого в блоке 6 хранения окончаний

лис

(фИ1

сиф

тат;

(ваемому

слову

эдится D-триггер, который участвует в мировании адреса считывания из блока

ранения признаков. Поэтому адреса обращения блоков б и 7 к блоку 12 хранения признаков будут различны. Пример: пусть по адресу 1.0001 в блоке 12 хранения при- знасов записан морфологический признак око чаний, тогда по адресу 0.0001 будет заан морфологический признак основ

.4,5).

Блок 17 формирования результата клас-

икации состоит из дешифратора, элемен га ИЛИ, шифратора и группы элементов И, выход элемента ИЛИ соединен с первыми f ходами элементов И группы и является вых( дом признака результата блока, инфор- мацюнный выход которого образован выходами элементов И группы, вторые входы коте рых соединены с выходами шифраторов, входы которого соединены с входами элемента ИЛИ и выходами дешифратора, вхо/ которого подключен к входу блока, На инф фмационные входы схем группы эле- мен- ов И поступает информация от шифратора, на управляющие входы сигнал REZ - выход элемента ИЛИ. На выходе группы элег ентов И образуется двоичный код - при: нак принадлежности к одному из классов частей речи. При этот двоичный код юступает в блок 2 регистров слов. Таким бразом, происходит присвоение обра- бат при фор

признака

адлежности в виде двоичного кода, шруемого шифратором, аботу блока 17 формирования резуль- классификации поясняет таблица истинности. Количество групп элементов И соответствует, например, количеству частей речи. Количество входов в группу элементов И также соответствует количеству, например, частей речи.

XL X2, хз. хп - логические переменные

Например:

xi - существительное

ха - глагол и т.д.

F - выходная функция - результат.

Пример приводится для четырех переменных.

особое состояние

F XI Х2 ХЗ Х4 V Х1 Х2 ХЗ Х4 V XI Х2 ХЗ Х4 V Х1 Х2 ХЗ Х4

Единичное значение функции F определено тогда, когда единице равна только одна переменная, т.е. однозначно определена, например, часть речи (существительное, глагол, наречие и т.д.) или другие лингвистические классы и структурные признаки образов.

Из блока 15 анализа морфологических признаков информация морфологических признаков поступает в блок 17 формирования результата классификации, в котором формируется сигнал REZ результата. Сигнал REZ поступает в блок 19 управления.

Сигнал ПРИЕМ 1 вырабатывается блоком 19 управления в том случае, когда вхождение не обнаружено или тогда, когда в блок 19 управления поступили сигналы: , СНЛ, равные нулю.

Блок 14 формирования адреса (фиг. 8) состоит из двух счетчиков. Счетчик 1 записи и счетчик 2 считывания информации из регистровой памяти. По приходу из блока 19 управления сигнала ПРИЕМ 1, счетчик формирует адрес для записи (A3) окончания (основы) из блоков 6, 7 хранения окончаний (основ).

Счетчик 2 по сигналу Выдача Г из блока 19 управления формирует текущий адрес считываемого символа, подающегося на блок 16 регистров символа вхождения. Другими словами, счетчик 1 подсчитывает сигналы ПРИЕМ Г, а счетчик 2 - сигналы ВЫДАЧА 1 и формирует на своих выходах адреса записи и считывания соответствен- но. Перед работой счетчики 1 и 2 устанавливаются е нуль-состояние.

По приходе из блока 19 управления происходит разрешение работы дешифратора 1 (фиг. 7). Дешифратор 1 со- стоит из дешифратора 1 и схемы ИЛИ, Основана функция дешифратора 1 состоит в определении конца просмотра информации блока хранения окончаний. Выходной сигнал дешифратора 1 АПО является опреде- ляющим сигналом работы блока б хранения окончаний. Если , то происходит процесс считывания информации из блока 6 хранения окончаний. Если , то это означает, что блок 6 хранения окончаний просмотрен. Сигнал АПО является выходом схемы ИЛИ. На выходе дешифратора нулевая информация, если на его входе также нули, при этом . Если на входе дешифратора ненулевая информация, то на его выходе будет унарный код (одна единица), при этом .

Работа дешифратора 2 аналогична работе дешифратора 1, Сигнал СТР 2 также является разрешающим сигналом работы дешифратора 2, а сигнал АПС является признаком работы блока 7 хранения основ. Дешифратор 2 состоит также из дешифратора и схемы ИЛИ.

Блок 19 управления синтезируется на основе ГСА алгоритма управления (фиг. 13) известным способом. Размеченная ГСА работы блока 19 управления приведена на фиг. 14, где обозначено:

Логические условия:

хз: СИЛ

Х4: АПС

xs:

АПО

Операторы:

Yi:nCBPOC: 1 Уз: YB:

У2з: ВЫДАЧА Y24: Y25: Y26: СЗАЩ: 0 Y27: ВГАИ: ВИКЛ&ВИРгГ У2а: СЗАЩ: Г

Г

Узо: ЛИЛИ Y3i: PB:-1 Y32: Узз: +СчАПП:-Г Ys4: САП:-Г Y3s: Узб: РП: Рг2&РгГ BOPK: RN ВИРгГ Уад: Y4i: У4з: Y44: СТОП

5 0 5 0

5

0

5

0

5

Формул а изо бретени я 1. Устройство для морфологического анализа слов естественных языков и языков деловой прозы, содержащее блок памяти слов, блок регистров слов, блок регистровой памяти, коммутатор, блок формирования адреса, блок поиска вхождения и блок управления, причем выход блока памяти слов соединен с первым информационным входом блока регистра слов, выход которого соединен с первым информационным входом блока поиска вхождения, с первого по третий выходы блока управления соединены соответственно с входом управления считыванием блока памяти слов и первым и вторым управляющими входами блока формирования адреса, первый и второй управляющие входы коммутатора соединены соответственно с четвертым и пятым выходами блока управления, входы пуска и сброса которого являются одноименными входами устройства, отличающееся тем, что, с целью повышения скорости процессов морфологического анализа реальных языков на основе логических признаков принадлежности к классам словоформ, оно дополнительно содержит ключ, блок хранения окончаний, блок хранения основ, блок хранения признаков, блок анализа характеристического вектора блок анализа морфологических признаков, блок регистров символьного вхождения, блок формирования результата классификации, блок задержки два дешифратора и блок элементов ИЛИ, причем адресные выходы блока хранения окончаний и блока хранения основ через блок элементов ИЛИ соединены с адресным входом блока хранения признаков, выход которого соединен с информационным входом блока анализа морфологических признаков, выход которого соединен с входом блока формирования результата классификации, информационный выход которого соединен с вторым информационным входом блока регистров слова, вход управления записью которого через блок задержки соединен с первым выходом блока управления, шестой, седьмой и восьмой выходы которого соединены с входами уп- рг вления считыванием соответственно бло- хранения окончаний, блока хранения о4нов и блока хранения признаков, выход

ока хранения окончаний соединен с ин- формационным входом первого дешифрз- тс ра и первым информационным входом кс ммутатора, выход которого соединен с

формационным входом блока регистрои памяти, выход которого соединен с ин-

фэрмационным входом блока регистров символьного вхождения, информационный внход которого соединен с вторым информационным входом блока поиска вхожде- 1я, информационный и управляющий 1ходы которого соединены с одноименными входами ключа, выход которого соеди- н эн с информационным входом блока анализа характеристического вектора, первый, второй и третий управляющие входы которого соединены соответственно с девя- т4м, десятым и одиннадцатым выходами ока управления, выход блока хранения нов соединен с вторым информационным одом коммутатора и информационным одом второго дешифратора, стробируюв:в; ший вход которого соединен с девятнадца

IM выходом блока управления, семнадцатый выход которого соединен со ррбирующим входом первого дешифрато- 35 , выход которого и выход второго дешифратора подключены соответственно.к п зрвому и второму входам логических условий блока управления, третий вход логических условий которого соединен с выходом 40

п

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

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

РЯ2

Ц

SPf

выходами элементов И группы, вторые входы которых соединены с выходами шифратора, входы которого соединены с входами элемента ИЛИ и выходами дешифратора, вход которого подключен к входу блока.

фи&.1

SP

зЈ

л

SPz

г

сре/е.2

V)

tTj

tptse.S

Ш .

&А/

Ч U

;I:

+

:

I

iZeAEQl

X

№ У

7

p#c.ff

срме.12

$7Ј/&./f

I

5;

1837327 (iи ; Q„

а,