Устройство для обработки текстовой информации

 

пц 52690!

ОП ИСА НИ Е

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Союз Саввтскик

Социалистических

Рвслублнн (61) Дополнительное к авт. свид-ву (22) Заявлено 12.02.74 (21) 1995904, 24 (51) М. Кл, G 06F 15/06

G 06F 15/40 с присоединением заявки №

Госуларственный комитет

Совета Министров СССР ло делам изобретений и открытий (23) Приоритет

Опубликовано 30.08.76. Бюллетень № 32

Дата опубликования описания 20.10.76 (53) УДК 681.323(088.8) (72) Авторы изобретения

Г. М. Адельсон-Вельский, В. Л. Арлазаров, P. Э. Асратян, А. Ф. Волков, В. Н. Деза, Е. А. Диниц, Н. В. Дагурова, Н. Е. Емельянов, Н. Г. Зенкина, В. Т. Лысиков и И. А. Фараджев (71) Заявитель

Ордена Ленина институт проблем управления (54) УСТРОЙСТВО ДЛЯ ОБРАБОТКИ ТЕКСТОВОЙ ИНФОРМАЦИИ

Изобретение относится ас области вычислительной Tax HHIKH, в чаcllHocTIH к такому использова нию 3ВМ, в которых преобладает обработка нечисловых дан ных: моделирование, ком пиляция, т ра нсляция, информационный поиок и всякого рода, информационно-логические задачи.

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

Цель изобретения — повышение быстродействия устройства и расширение класса решаемых задач.

Это:достигается тем, что устройство содержит счетчик формирования информационных частей, вход которого соединен с вторым инфор мацио нным выходом блока заголовков текстов, счетный вход — с первым выходом блока увтравления, выход — с первым входом блока управления, счетчвк формирования адреса, счетный вход которого, подключен ас пер вому выходу блока управления, информационный вход — к первому и нфэрмационному выходу блока упр авления, выход — ж первому входу блока управления, первый счетчик последовательного доступа, сче.пный вход которого соединен с первым выходом блока управления, выход lIIipHBHBIKB —.с первым входом блока управления, информационный выход под1о ключен к второму управляющему входу блока заголовков текстов, блэк приема слов из главной памяти, управляющий вход .которого соединен с управляющим выходом:регистра адреса, информационный вход — с информа15 ционным входом устройства. К роме того, в уст ройство введены блок формирования адресов связи и информационных частей, первый вход которого связая с выходом блока приема слов из главной памяти,,второй вход подlKJIHwGH K

20 информационному входу блэка приема слов из главной памяти, блок адресов текстов, адресный выход которого, соединен с адреоным входом регистра адреса, пер вый адресный вход— с адресным выходом блока фо|рмирования ад25 ресов связи и информационных частей, второй адресный вход — с информационным входом устройства, первый управляющий вход подключен 1к третьему выходу блока управления, второй управляющий вход — к информационЗО ному выходу первого счетчика последователь526901

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

Блок-схема устройства представлена на чертеже, где 1 —.регистр адреса; 2 — сумматор;

3 — бло к за голов кон текстов; 4 — блок приема слоев из главной памяти; 5 — блок формиро вания адресов связи и и нформационных частей; 6 — бло к адресов текстов; 7 — бланк управления; 8 — счетчик формирования информацион ных частей; 9 — счетчик формирования адреса; 10, .11 — счетчики последовательного доступа; 12 — блок текстов; 13 — блок определения первого вхождения; 14 — информацио|нный вход; 15 — адресный выход устройства.

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

У|стройство пред назначено для работы с текстами, которые могут быть п редста влены в двух формах: несписоч ной, при которой инфо|рмация размещается в последовательно ра. споIJIоженныx ячейках па мяти, и списочной.

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

У каждого списка свой заголовок (описание), в кото ром указываются параметры элементаа описка, т. е. н ач алло и н ф oip м а цио н н ой части, длина и нформацио н ной части, начало адресной ссыл ки, а также начальный адрес текста, 10

Зо

4

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

Основными текстовыми кома идами устроиств а я в л я ются сл еду ющие.

К о м а нд а «Найти первое вхождение .какого-ли бо текста из набора в заданный текст».

Е сли о боз начить на бор текстов SI (i = 1, 2, ..., Й), а заданный текст L, то действие команды состоит в нахождении самого;первого от начала элемента 1 qL такого, в котором существует |кусок текста L, и начинающийся с l (где 1 называется на чалом вхождения), и полHoIcTb1o совпадающий с KBIKHM-либо текстом из набора текстов. В ко|маиде указывается адрес заголовка текста L и адреса заголовков всех текстов и их количество. Концы текстов заданы неявно. Ко ма нда может распросDpaiHHTbся на тексты, представленные в несписочной форме.

К о м а н д а «Найти текст из на бора текстов, совпадающий с зада н ным».

Эта команда, а налогична п редыдущей.

Ко м аида «Найти первое вхождение ка кого-либо, символа из набора символов в заданный текст».

Наоор символов задается в виде текста.

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

Ком а нд а «Перекодировка».

В ко ма яде задается адрес saiIoловка текста или адрес начала текста (для .несписочной формы) и а|дрес начала таблицы. Каждая строка таблицы со держит по два символа: исходный и соответствующий ему код. Действие команды состоит в замене символов задан ного текста на другие |в соответствии с таблицей перекодирования. Символы, не при надлежащие таблице перекодирования, остаются без изменения.

К о м а н д а «Раопа ковка».

В ко ма нде задается адрес начала исходного текста и адрес, iIIO которому хранится затоJIoBoIK «ñïèoêà свободных мест», нужного фо рмата, куда требуется, распаковать да ичный текст.

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

К о и а iH д а «Упаковка».

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

Ко,м ан д а «Замена».

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

В ко ма и де указывается ар!рес элемента, предшествующего первому элементу заменяемой части, адрес последнего элемента заменя52690!

50

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

Будем считать, что в блоке 3 заголовков текстов уже находится и нформа ция о формате списка, т. е. его,заголовок. При форми ровании и нфо рмацион ных ча стей адрес начала исходного текста пе редаетея из блока 6 адресов текстов в регистр 1 адреса, а содержимое отдельных ча стей заголовка 1блока 3 распределяется следхттощим образом: длина информациоННоН части — в счетчик 8 для формирования инФормационной части, начало информационной части — в сумматор 2.

Результат суммирования передается в регистр 1, по которому из глав ной памяти в блок 4 приема слов считывается инфо рма ционная часть. В дальнейшем она передается в бло к 5 форми рова ния и нформаттионньтх ча тей, где инфовма ция уже представляется в виче строки. После этого содепжимое с "мматора 2 увеличивается на 1, а содержимое счетчика 8 для Фо рмиро в агония и нформаттион ньтх частей уменьшается на 1 и по сигналу из блока 7 происходит чтение инфор маттионной части элемента по следующему адрест. Так прочолжается до тех пор, пока содержимое счетчика 8

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

После окончания формиоования и нформаттиoiHiHoH части. о чем свидетельствует сигнал в блок 7 управления (содегжимое счетчика 8 ра вно нулю), начинается Формирование адресной ссылки. К началыномт адресу исходного текста приба|вляется уже величина, равная iHaчалу адресной ссылки, а ganbIIIe процесс фо|рмирования а налогичен описанному. Отличие лишь в том, что длина адреса связи (фи ксирова н ная. 2 байта) загружается в счетчик 9 для формирования адресной ссылки. Концом формирования адресной ссылки служит сигнал из счетчика 9 (содержимое счетчика 9 равно нулто) в блок управления. Сфо рми рова нная адттесная ссылка передается пз блока 5 в блок

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

Рассмотрим работу устпойства на првмере выполнения команды «Найти первое вхождение какого-ли|бо текста из набора в заданный текст».

Первоначально а д реса за го ло в ков всех текстов и их количество k переписываются из главной памяти в блок 6 адресов текстов.

Первый счетчик 10 последовательного доступа

6 к блокам 3. 6, 13 загружается величиной k— количеством текстов. По сигналу из блока 7 управления заголовки текстов переписываются из главной памяти в блок 3 заголовков текстов, а в блок 6 адресов текстов записываются адреса первых элементов всех текстов.

Выполнение команды за ключается в том, что по отношению к каждому элементу тек. ста J, проводится проверка — не является ли этот элемент началом вхождения. Упрощенно проверка состоит в следующем. Проверяемый элемент текста L подается на шины оп роса блока 13 определения перьвого вхождения, основным элементом которого служит ассоциатив ное запоминающее устройство (АЗУ), а в регистры АЗУ заносятся первые элементы всех текстов из блока 5 (по одному в каж дьтй регистр) и происходит сравнение информапион ньтх частей по сигналу из блока 7 упра вления. Регистры, в которых не произошло совпа дения, помечаются, например запттсьтвается

«1» в опведелеттньтй разряд. По сигналу совпатте нття из блока 13 определения первого вхождения в блок 7 упра влeнття, в регистры, в которых IIQQH301II10 совпадение, заносятся вторые элементы соответствутощих текстов по канал .. связьтватотцем блок 5 и блок 13 опрсде. ения первого вхождения, а iHa шины опроса

АЗУ подается следующий за проверяемым элемент текста и вновь проводятся cpalBEIåíIIå и пометка несовпавших текстов и т. д. В помеченно т,регистре уже не может произойти говна ения. Если на каком-нибудь шаге проверки о кажется. что все регистры помечены (т. е. нет ни одного совпадения), то проверяемый элемент не является началом вхо жде нття и можно приступить к проверке на вхождение слодлотттего элемента.

Если же на каком-нибудь шаге окажется. что в непомеченном (совпавшем) регттстре находится последний "-.ëeìeíò текста, то вхождение найдено.

При более подробном рассмотрении можно отметить. что в действтттельносттт каждою тексту в АЗУ блска 13 определения первого вхождения соответств, ют подрядлежащие регистры с чет ньтхт II нечетным номером. В первых постоянно хранятся начальные символы соответств .тощих текстов (столько, сколько пометцается в ячейку), а во вторые peTHCTры последовательно заносятся вторые, третьи п другие ттнформацттсттньте части текстов.

Блок 12 текстов является своего рода буфсро», для хранения последутощпх информационных частей. Для последовате IbEI010 доступа к ячейкам блока 12 текстов служит счетчик 11.

Счетчик 11 устанавливается в иуль при смене начала приложения, .п этот адрес запоминается в блошке 13 определения первого вхождения. Содержимое счетчпка 11 увеличивается па единицу каждый раз при записи очеред ной и-ой части текста. После записи k а-х частей текста переходят к записи k (и+1) -х частей до тех пор. пока память не исчерпается.

526901

При абра щения за очеред ной частью текста, в начале происходит обра щение к блоку 12 текстов, если нужной части там нет (на что i хазывает спсциальный разряд в:блоке 12), то из блока 7 уп!равления подается сигнал на об ращение к гла в ной памяти и, п рочита н ная часть н нфо рмации помещается в блок текстов, если там есть место.

Ф о ip м у л а и з о.б 1р е т е н и я

Устройство для эбработки текстовой н нфо рмации, содержащее блэк уп равле ния,,су1мма:тар, регистр адреса, выход которого соединен с адресным выходам устройства и,llppabIIM входам сум|матэра,,выход которого подключен к входу perHCTipa ailrpeca, yrlipaBляющий вход под.ключен к первому выходу блока управления, блок заголовков текстов, инфоомационный вход Ко Tolpoão соединен с и нфор мационным входом у строй ства,,первый управляющий вход подключен к второму выходу блока у1правления, первый и нформацио н ный выход соединен с вторым входом сумматора, о тл и ч а ю щ е ес я тем, что, с целью повышения быспродействия устройства и расши|рения класса решаемых задач, в него введены счетчик фэрми рования информациoHiHblx частей, вход которого со единен с вторым информа цHQIHIHbIM выходом блока за головков текстов, счетный вход подключен к

rIeipBoMó выходу блэка управления, выход соеди нен с перовым .входом блока управления, счетчик фор миро вания адреса, счетный вход котэрэгэ пэдключен к первому выходу блока управления, инфар мацион ный вход соединен с первым инфар мацио н ным выходо м блока у1пра вления, выход соединен с первым входом блока управления, пер вый счетчик последовательного доступа, счетный вход которого подключен к первому выходу блэка yrripaaления, выход приз на к à соединен с пер|в ы м входом блока уш|равления, и нформа циэн ный выход подключен к IBTopQMv упра вляю щему вхэду

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

Зо

45 адреса, инфэр|мациэн ный вход — с информационным входом устройства, блэк формирования адресов связи и информационных частей, первый вход которого соединен с выходом блока приема слов из главной памяти, второй вход подключен к информационному входу блока приема слав из гла вной памяти, бло к адресов текстов, адресный выход которого соединен с адресным входом регистра agipeca, первый ад реciHbIH |вход подключен к адресному выходу блэка фор мирова ния адресов связи и и нформацио нных ча стей, второй адреоный вход соедине н с информационным входом устройства, первый управляющий вхо д под ключен к третьему выходу блока у1правлен ия, второй управляющий вход соединен с информационным выходом пе р вого счетчика последовательного досту1па, и нфор мациан ный выход соединен с информацион ным входом, первого счетчика последовательного доступа, блок текстов, информационный вход которого соединен со вторым информацио нным выходом блока формирования адресов, связи и информационных частей, выход, подключен к втэрому входу блока управлен1ия, первый управляюпвий вход соединен с четвертым выходом блэка управления, второй счетчик последователь ного доступа, управляющий вход которого соединен с первым выходом блока управления, и нфор мационный вход подключен к второму инфэрмацион ному выходу блока управления, выход соединен с вторым управляющим входом блока текстов, блок определения первого вхождения, управляющий вход котэрого соеди|нен с информационным,выходом первого счетчика последовательного доступа, вход п ризнака соединен с од ноименным выходом блока упра вления, выход признака соединен с третьим входом блока управления,,первый и второй и нформацианный

Bxogbl соединены соответственно с информацио иHbIM выходом блока текстав и с вторым инфо р,мационным выхэдо м блока формирования адресов связи и информационных частей, инфо рма цион ный выход соединен с и нформацио н ным,входам блэка приема слов из глаэной памяти, 526901

Составитель А. Жеренов

Техред 3. Тараненко

Корректор О. Тюрина

Редактор И. Грузова

Типографии, лр. Сапунова, 2

Заказ 2180/12 Изд. № 1655 Тираж 864 Подписное

ЦНИИПИ Государственного комитета Совета Министров СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., л. 4/5