УСТРОЙСТВО ДЛЯ ОБЪЕДИНЕНИЯ ЛЕКСИЧЕСКИХ МНОЖЕСТВ Российский патент 1994 года по МПК G06F15/38 

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

Целью изобретения является упрощение устройства.

Цель достигается тем, что в устройство для объединения лексических множеств, содержащее дешифратор, первый блок памяти, блок формирования данных, блок управления, два счетчика, две схемы сравнения, причем информационный вход дешифратора соединен с входом кода слова устройства, управляющий вход дешифратора соединен с первым выходом блока управления, второй выход которого соединен с входом сброса первого счетчика, выходы m разрядов дешифратора подключены к информационному входу блока формирования данных, информационный выход которого подключен к первому информационному входу первого блока памяти, выход которого является выходом характеристик слова устройства, адресный вход первого блока памяти соединен с выходом второго счетчика, с первым входом первой схемы сравнения, выход которой соединен с первым входом блока управления, второй, третий и четвертый входы которого соединены соответственно с первым, вторым и третьим входами задания режима устройства, выходы (m+1)-го и (m+2)-го разрядов дешифратора подключены соответственно к счетному входу первого счетчика и к пятому входу блока управления, входы чтения и записи первого блока памяти подключены к третьему и четвертому выходам блока управления, введены второй блок памяти, коммутатор, регистр, третья схема сравнения и два сумматора, причем информационный выход блока формирования данных подключен к первому информационному входу коммутатора, второй информационный вход которого соединен с входом кода слова устройства, а управляющий вход - с пятым входом блока управления, выход коммутатора соединен с адресным входом второго блока памяти, первый выход которого соединен с вторым информационным входом первого блока памяти и с первым входом первого сумматора, второй вход и выход которого соединены соответственно с входом единицы устройства и с первым информационным входом второго блока памяти, второй информационный вход которого соединен с первым входом второй схемы сравнения и с выходом второго сумматора, первый вход которого соединен с третьим информационным входом первого блока памяти и с вторым выходом второго блока памяти, третий выход которого соединен с первым входом третьей схемы сравнения, выход которой соединен с вторым входом второго сумматора, а второй вход - с третьим информационным входом второго блока памяти и с выходом первого счетчика, выход коммутатора соединен с адресным входом второго блока памяти, вход сброса которого соединен с вторым выходом блока управления, шестой выход которого соединен с входом записи второго блока памяти и с первым управляющим входом блока формирования данных, второй и третий управляющие входы которого соединены соответственно с выходом второй схемы сравнения и седьмым выходом блока управления, шестой вход которого соединен с управляющим выходом блока формирования данных и с синхровходом регистра, информационный вход которого соединен с выходом второго счетчика, а выход - с выходом количества слов устройства, и с вторым входом первой схемы сравнения, причем блок формирования данных содержит первую группу элементов И, первые, вторые прямые и инверсные входы которых подключены соответственно к второму, первому управляющим и информационному входам блока формирования данных, при этом выходы элементов И первой группы подключены к единичным входам триггеров группы, нулевые входы которых подключены к выходам элементов И второй группы, к первым и вторым входам которых подключены соответственно третий управляющий вход блока формирования данных, и входы шифратора, выход которого является информационным выходом блока формирования данных, управляющий выход которого соединен с инверсным выходом элемента ИЛИ, входы которого соединены с выходами триггеров группы, выход первого триггера группы соединен с первым входом шифратора, m-1 входов которого соединены соответственно с выходами m-1 элементов И группы, выход i-го триггера группы (i = 1 - (m-1)) подключен к i-м инверсным входам m-1 элементов И группы, к (i+1)-м входам которых подключены соответственно выходы триггеров группы, кроме первого, восьмой и девятый выходы блока управления подключены соответственно к входу сброса и счетному входу второго счетчика.

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

На фиг. 1 приведена структурная схема устройства для объединения лексических множеств; на фиг. 2 - структурная схема блока управления; на фиг. 3 - структурная схема блока формирования данных.

Устройство для объединения лексических множеств (фиг. 1) содержит дешифратор 1, первый и второй счетчики 2 и 3, коммутатор 4, первый и второй блоки 5 и 6 памяти, схемы 7-9 сравнения с первой по третью, первый и второй сумматоры 10 и 11, блок 12 формирования данных, регистр 13, блок 14 управления, вход 15 кода слова, вход 16 выбора режима работы устройства, вход 17 единицы, выход 18 характеристик слова, выход 19 количества слов, входы 20-25 соответственно с первого по шестой блока 14 управления, выходы 26-34 соответственно с первого по девятый блока 14, выходы 35₁-35_m дешифратора 1.

Блок 14 управления (фиг. 2) содержит генератор 36 тактовых импульсов, элементы И 37-41 соответственно с первого по пятый, первый и второй элементы ИЛИ 42 и 43, первый и второй элементы 44 и 45 задержки, первый и второй формирователи 46 и 47 импульсов, первый и второй триггеры 48 и 49.

Блок 12 формирования данных (фиг. 3) содержит первую группу 50 из m элементов И, вторую группу элементов И 5₁₁-51_m, группу триггеров 52, группу элементов И 53₁-53_m-1, шифратор 54, элемент ИЛИ 55, выходы 56 триггеров 52 группы, выходы 57 элементов И 53 группы.

Вербальное описание принципа работы устройства.

Процесс формирования объединения множеств имеет три этапа: формирование промежуточных результатов и их запись в блок 6 памяти; запись значений и характеристик слов в блок 5 памяти; выдача результатов на внешнее устройство.

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

Устройство в зависимости от режима работы либо производит объединение лексических множеств, либо формирует словарь.

В первом режиме, задаваемом значением "О" на входе 16, осуществляется объединение лексических множеств и определяются такие характеристики слов, как ранг (число текстов, в которых встречается данное слово) и повторяемость (общее число вхождений данного слова во всех текстах).

Пусть имеется три лексических множества (некоторых текста):
Т1 = { Д, А, Б, А};
Т2 = {В, Г, А, В, Д};
Т3 = { В, Е, А, В, Е, Е}, где А, Б, В Г, Д, Е - некоторые абстрактные слова.

При объединении данных множеств получается некоторое множество Т, в котором все элементы расположены в алфавитном порядке, встречаются только один раз и имеют характеристики - ранги и повторяемости:
Т = {А.3.4, Б.1.1, В.2.4, Г.1.1, Д.2.2, Е.1.3}, т.е. слово А встречается в трех текстах четыре раза (ранг равен 3, повторяемость - 4), слово Б - один раз в одном тексте и т.д.

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

В описанном случае соответствующее множество имеет вид:
ТС = {А.3.4, В.2.4, Д.2.2}.

Определение характеристик слов производится совокупностью блоков 2, 6, 9, 10 и 11 устройства.

При подаче на вход 16 устройства различных кодов легко перестраивать уровень достоверности словаря (так, при подаче кода "2" в состав словаря входят лишь те слова, которые встречаются не менее чем в трех текстах и т. д.).

Устройство работает следующим образом.

На первом этапе работы на вход 22 подается положительный потенциал (высокий). При наличии низкого потенциала с выхода триггера 49 открывается элемент И 37 в блоке 14 управления, и на его выход поступают тактовые импульсы с генератора 36. Эти импульсы с инверсного выхода элемента И 37 поступают на вход разрешения дешифратора 1, на информационный вход 15 которого поступают анализируемые слова. На выходе дешифратора 1 для каждого анализируемого слова формируется обратный унитарный код: каждому слову соответствует наличие нулевого сигнала в строго определенной позиции совокупности выходов 35. Этот код поступает в блок 12 формирования данных. Номер текста определяется числом разделителей текста, при поступлении которых на вход 15 устройства формируется единичный сигнал на (m + 1)-м выходе дешифратора 1.

Исходное состояние счетчиков 2, 3, ячеек памяти блоков 5 и 6, регистра 13, триггеров 48 и 49, а также триггеров 52 группы нулевое. Соответствующие цепи начальной установки не показаны на фигурах. В зависимости от режима работы устройства подается потенциал на вход 16: в режиме объединения множеств нулевой код, в режиме словаря код с единицей в младшем разряде (или другой код, как указано выше). На вход 17 сумматора 10 также подается в течение всего сеанса работы устройства код "Единицы". На первом этапе работы на входы 21 и 23 подаются нулевые потенциалы.

На первом этапе работы нулевой потенциал с выхода триггера 49 устанавливает коммутатор 4 таким образом, что на его выходы поступают сигналы с входом 15 устройства. Для каждого анализируемого слова код с выхода коммутатора 4, совпадающий с кодом слова, определяет адрес ячейки памяти блока 6, в котором хранятся характеристики данного слова. Для каждого слова на первом этапе требуются три характеристики: последний номер текста, в котором встретилось данное слово (этот параметр записывается в блок 6 со счетчика 2, а его значение снимается с блока 6 в схему 9), ранг слова (его значение записывается в блок 6 с выхода сумматора 11 и снимается с блока 6 также на сумматор 11), повторяемость слова (записывается в блок 6 с выхода сумматора 10 и снимается с выходов блока 6, соединенных с сумматором 10). Номер последнего текста, в котором встречалось данное слово, служит вспомогательной информацией для формирования ранга данного слова.

В начале работы на входы 15 поступает первый разделитель текстов. Сигналом с выхода m + 1 дешифратора 1 счетчик 2 устанавливается в единичное состояние. Затем на входы 15 подаются слова первого текста. При поступлении очередного слова на адресные входы блока 6 памяти код повторяемости слова поступает на вход сумматора 10, на котором инкриминируется. Код ранга слова поступает на сумматор 11, на второй вход которого поступает (в младший разряд) код с выхода схемы 9 сравнения. Если текущий номер текста совпадает с номером текста, записанным для данного слова в блоке 6, т.е. данное слово не впервые встречается в данном тексте, то на выходе схемы 9 нулевой сигнал, если коды не совпадают - единичный (выход типа "Не равно"). Таким образом, схема 9 и сумматор 11 реализуют инкриминирование ранга слова при его первом вхождении в каждом тексте.

Тактовый импульс с выхода элемента И 37 поступает на формирователь 46, реализующий задержку на время, необходимое для формирования сигнала на выходах счетчика 2 и сумматоров 10, 11. Затем короткий импульс с выхода формирователя 46 поступает на вход записи в блок 6, записывая новые характеристики входного слова в блок 6. Этот же сигнал поступает в блок 12, открывая элементы И 50. По второму (инверсному) входу в этот момент открыт элемент И 50, номер которого соответствует унитарному коду входного слова (общее число различных слов m). Если для данного слова сработала схема 8 сравнения, то устанавливается в "единицу" соответствующий триггер 52 (в данном режиме - при первом же появлении данного слова в совокупности текстов), в режиме формирования словаря - при превышении рангом слова заданного кодом на входе 16 значения).

Таким образом осуществляется накопление данных и определение промежуточной информации. Каждый разделитель текстов инкриминирует содержимое счетчика 2. По окончании ввода последнего текста уникальный код "Конец ввода" формирует сигнал на (m + 2)-м выходе дешифратора 1, устанавливая триггер 49 в единичное состояние. При этом триггер 49 закрывает элемент И 37, завершая первый этап работы устройства, открывает элемент И 38 и переключает выходы коммутатора 4 к выходам блока 12. С поступлением следующего тактового импульса начинается второй этап работы.

На втором этапе ключевую роль играет блок 12. Установленные на первом этапе работы триггеры 52 определяют совокупность слов, которые должны быть выведены на выход устройства. Эти слова с соответствующими характеристиками записываются в блок 5 памяти, что осуществляется следующим образом. Сигналы с выходов 56 триггеров 52 поступают на входы элементов И 53, на выходах которых в совокупности формируется унитарный код, единственная "единица" которого находится в позиции, соответствующей наименьшему индексу триггера 52, среди триггеров 52, установленных в единичное состояние (единичный сигнал с выхода этого триггера закрывает все элементы И 53 с большими индексами). Этот же унитарный код в шифраторе 54 преобразуется в двоичный код (эквивалент данного слова). Этот код слова поступает на адресные входы блока 6 через коммутатор 4 и задает соответствующую ячейку памяти, в которой записаны ранг и повторяемость данного слова.

С первого тактового импульса, проходящего через элемент И 38 и (по разрешающему сигналу на входе 21 устройства) через элемент И 41 в блок 5 памяти, начиная с нулевого адреса, определяемого счетчиком 3, в соответствующие ячейки записываются значения упорядоченных слов и их параметров. После записи некоторого слова с параметрами выходной сигнал с элемента И 38, пройдя через элемент 45 задержки, поступает на входы элементов И 51 и сбрасывает триггер 52, индекс которого соответствует унитарному коду на выходах 57 блока 12. Сигналом с выхода элемента И 38 через элементы ИЛИ 43 и элемент 44 задержки по выходу 34 инкриминируется содержимое счетчика 3, задавая следующий адрес в блоке 5 памяти. Элементы 44-47 могут быть выполнены одинаково: последовательно соединенные элемент задержки и формирователь короткого импульса.

Таким образом, на втором этапе работы производится запись выбранных на первом этапе слов в блок 5 памяти. При этом за счет структуры блока 12 не приходится перебирать все множество потенциально возможных слов, а лишь достаточно перебрать имеющиеся в совокупности текстов слова.

Окончание второго этапа работы устройства происходит при обнулении последнего из триггеров 52, что вызывает появление единичного сигнала на выходе элемента ИЛИ 55, который, поступая на синхровход регистра 13, записывает в него содержимое счетчика 3 (число слов, подлежащих выдаче во внешнее устройство). Этот же сигнал устанавливает триггер 48 в единичное состояние, закрывая элемент И 38 и завершая тем самым второй этап работы устройства.

Перед третьим этапом работы устройства следует подать положительный импульс на вход 23. Этим импульсом счетчик 3 устанавливается в нулевое состояние. Затем в момент времени, удобный для пользователя, подается положительный потенциал на вход 21 устройства и поддерживается до окончания вывода слов. Этот потенциал разрешает чтение данных с блока 5 памяти на выходы 18 устройства, открывает элементы И 39 и 40 и закрывает элемент И 41, запрещая запись данных на этом этапе.

Тактовые импульсы поступают на устройство на третьем этапе через элемент И 39. Сразу после установки высокого потенциала на входе 21 устройства на выходе 18 появляется слово с параметрами, записанное в нулевой ячейке блока 5. После первого тактового импульса, прошедшего через элементы И 39, ИЛИ 43 и элемент 44, инкриминируется содержимое счетчика 3, на выходах 18 формируется следующее слово и т.д.

В момент времени, когда выведено последнее слово, очередным тактовым импульсом счетчик 3 переводится в состояние, когда его содержимое больше содержимого, записанного в регистре 13. При этом срабатывает схема 7 сравнения (по выходу "Больше") и импульс с его выхода через элементы И 40 и формирователь 47 устанавливает все узлы устройства в исходное состояние, после чего устройство готово к дальнейшей работе.

Сигнал на выходе генератора 36 может служить внешнему устройству (пользователю) на первом и третьем этапах работы при вводе текстов и выводе слов в качестве синхросигнала. Выход 19 информирует пользователя об общем числе выводимых слов. Сигнал с выхода схемы 7 может быть использован для оповещения об окончании работы устройства.

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

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

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

1. УСТРОЙСТВО ДЛЯ ОБЪЕДИНЕНИЯ ЛЕКСИЧЕСКИХ МНОЖЕСТВ, содержащее дешифратор, первый блок памяти, блок формирования данных, блок управления, два счетчика, две схемы сравнения, причем информационный вход дешифратора соединен с входом кода слова устройства, управляющий вход дешифратора соединен с первым выходом блока управления, второй выход которого соединен с входом сброса первого счетчика, выходы m разрядов дешифратора подключены к информационному входу блока формирования данных, информационный выход которого подключен к первому информационному входу первого блока памяти, выход которого является выходом характеристик слова устройства, адресный вход первого блока памяти соединен с выходом второго счетчика, с первым входом первой схемы сравнения, выход которой соединен с первым входом блока управления, второй, третий и четвертый входы которого соединены соответственно с первым, вторым и третьим входами задания режима устройства, выходы (m + 1) - и (m + 2) - го разрядов дешифратора подключены соответственно к счетному входу первого счетчика и к пятому входу блока управления, входы чтения и записи первого блока памяти подключены к третьему и четвертому выходам блока управления, отличающееся тем, что, с целью упрощения, оно содержит второй блок памяти, коммутатор, регистр, третью схему сравнения и два сумматора, причем информационный выход блока формирования данных подключен к первому информационному входу коммутатора, второй информационный вход которого соединен с входом кода слова устройства, а управляющий вход - с пятым выходом блока управления, выход коммутатора соединен с адресным входом второго блока памяти, первый выход которого соединен с вторым информационным входом первого блока памяти и с первым входом первого сумматора, второй вход и выход которого соединены соответственно с входом единицы устройства и с первым информационным входом второго блока памяти, второй информационный вход которого соединен с первым входом второй схемы сравнения и с выходом второго сумматора, первый вход которого соединен с третьим информационным входом первого блока памяти и с вторым выходом второго блока памяти, третий выход которого соединен с вторым входом второго сумматора, а второй вход - с третьим информационным входом второго блока памяти и с выходом первого счетчика, выход коммутатора соединен с адресным входом второго блока памяти, вход сброса которого соединен с вторым выходом блока управления, шестой выход которого соединен с входом записи второго блока памяти и с первым управляющим входом блока формирования данных, второй и третий управляющие входы которого соединены соответственно с выходом второй схемы сравнения и седьмым выходом блока управления, шестой вход которого соединен с управляющим выходом блока формирования данных и с синхровходом регистра, информационный вход которого соединен с выходом второго счетчика, а выход - с выходом количества слов устройства и с вторым входом первой схемы сравнения, причем блок формирования данных содержит первую группу элементов И, первые, вторые прямые и инверсные входы которых подключены соответственно к второму, первому управляющим и к информационному входам блока формирования данных, выходы элементов И первой группы подключены к единичным входам триггеров группы, нулевые входы которых подключены к выходам элементов И второй группы, к первым и вторым входам которых подключены соответственно третий управляющий вход блока формирования данных и входы шифратора, выход которого является информационным выходом блока формирования данных, управляющий выход которого соединен с инверсным выходом элемента ИЛИ, входы которого соединены с выходами триггеров группы, выход первого триггера группы соединен с первым входом шифратора (m - 1) входов которого соединены соответственно с выходами (m - 1) элементов И группы, выход i-го триггера группы i = 1 ÷ (m - 1) подключен к i-м инверсным входам (m - 1) элементов И группы, к (i + 1)-м входам которых подключены соответственно выходы триггеров группы, кроме первого, восьмой и девятый выходы блока управления подключены соответственно к входу сброса и счетному входу второго счетчика. 2. Устройство по п.1, отличающееся тем, что блок управления содержит генератор тактовых импульсов, два триггера, два элемента задержки, два формирователя импульса, пять элементов И, два элемента ИЛИ, причем выход генератора тактовых импульсов подключен к тактовому выходу устройства, первым прямым входам соответственно первого, второго и третьего элементов И, второй вход которого соединен с первым входом четвертого элемента И, с инверсным входом пятого элемента И и с третьим выходом блока, третий вход блока соединен с вторым прямым входом первого элемента И, инверсный выход которого является первым выходом блока, а прямой выход через первый формирователь импульсов подключен к шестому выходу блока, четвертый вход блока соединен с первым входом первого элемента ИЛИ, выход которого подключен к восьмому выходу блока, а второй вход - к выходу второго формирователя импульсов, к нулевым входам первого и второго триггеров и к второму выходу блока, выход третьего элемента И соединен с первым входом второго элемента ИЛИ, выход которого через первый элемент задержки соединен с девятым выходом блока, а второй вход - с выходом второго элемента И, через второй элемент задержки - с седьмым выходом блока и с прямым входом пятого элемента И, выход которого является четвертым выходом блока, первый вход блока соединен с вторым входом четвертого элемента И, выход которого соединен с входом второго формирователя импульсов, шестой вход блока соединен с единичным входом первого триггера, выход которого соединен с инверсным входом второго элемента И, второй прямой вход которого соединен с инверсным входом первого элемента И, с пятым выходом блока и выходом второго триггера, единичный вход которого соединен с пятым входом блока.