Scientific journal
Modern problems of science and education
ISSN 2070-7428
"Перечень" ВАК
ИФ РИНЦ = 0,940

FAST SYMBOLIC INFORMATION PROCESSING IN DOCUMENTS CONTROL AND DECISION MAKING SYSTEMS: HARDWARE REALISATION

Korolkov O.F. 1 Apalkov V.V. 1 Chaplygin A.A. 1 Korolkova V.O. 1
1 South-west state university
Realization variants and production kinds with variables in symbolic information computing devices with modified production algorithmic Markov’s system, their work principles and production realization with alphabetic variables and also variable pattern and modificator length, such memory organization, that there will be no garbage are considered. Production algorithms may be used for high speed document processing, structured pattern recognition methods and database organization with fast access. The process of one algorithm’s production begins with the symbol by symbol search in processing word and matching with the pattern for retaining of its position in processing word. The obtained results in this work may be used in the further symbolic information processing units development.
productions with alphabetic variables
production of pattern and modification variable size
computing speed.

Введение

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

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

Принципы реализации устройств символьных вычислений

Основные положения теории обработки символьной информации приведены в работах [1–5], а важные для данной статьи положения теории нормальных модифицированных алгоритмов рассматриваются в [1; 4].

Рассмотрим продукцию с алфавитными переменными, которая представлена словом, имеющим следующий вид:

agyb®dyga, (1)

где символ «®»– метасимвол, не принадлежащий рабочему алфавиту, отделяющий образец от модификатора; g, y алфавитные переменные; «a» и «b» и «d» – конкретные символы рабочего алфавита.

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

Введем продукцию с переменной длиной образца и модификатора, которая представлена словом, имеющим следующий вид:

а#b®d#g, (2)

где символ «#» в образце означает то, что в ОС между символами «а» и «в» имеется цепочка символов переменной длины, в том числе и пустая. Этот же символ «#» в модификаторе означает то, что он может формироваться как из символов «b» и «g», так и из цепочки, полученной при обнаружении позиции вхождения образца в ОС. Для того чтобы осуществить поиск позиции вхождения образца в ОС и модификацию, аналогичную формуле (2), необходимо применить эквивалентный алгоритм из продукции с алфавитными переменными. Такой алгоритм представляется конечным списком слов, имеющим следующий вид:

agyβ b®dgyβ g ,

agy b®dgy g ,

ag b®dg g . . (3)

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

Правила работы продукционных устройств с одним и двумя блоками памяти для ОС, реализующих продукцию канонического вида [4], описаны в работах [1]. Структурная схема устройства с двумя блоками памяти для ОС представлена на рисунке 1.

 

Рис. 1. Структурная схема устройства с двумя блоками памяти для обрабатываемого слова: УУ – устройство управления; БПП – блок памяти продукций;

БП1сл, БП2сл – блоки памяти обрабатываемого слова;

Ком – коммутатор; БлСрсим – блок сравнения символов;

Буф – буфер; БпрПоАлг – блок перехода по продукциям в алгоритме.

Работа с одной продукцией алгоритма заключается в просмотре (сопоставлении) посимвольно ОС и образца продукции для обнаружения позиции его вхождения в ОС. Такое сопоставление осуществляется в блоке «БлСрсим» (рис. 1) во время перезаписи символов ОС из одного блока памяти в другой, причем считанный символ образца записывается во второй блок. В случае обнаружения позиции вхождения образца в ОС на место совпавшего фрагмента во второй блок памяти ОС записывается модификатор.

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

М1:γi®βj :М2 , (4)

где γi, βj – цепочки символов заданного рабочего алфавита, несущие тот же смысл, как и у продукции (1), М1, M2 – метки (натуральные числа) перехода на определенные номера продукции из списка; М1 – если продукция не обнаружила своего вхождения при просмотре слова, М2 – соответственно если обнаружила, такой алгоритм заканчивает свою работу если продукция имеет специальный признак заключительной продукции, или не срабатывает последняя в списке продукция.

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

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

abg®cccc , (5)

abg®cc . (6)

На рисунке 2 схематически представлены два блока памяти для ОС.

 

Рис. 2. Схемы расположения символов ОС в блоках памяти для устройства с двумя блоками памяти: а – блок памяти «БП1сл», из которого считывается ОС; б – блок памяти «БП2сл», в который записывается ОС, соответствует моменту обнаружения позиции вхождения образца в ОС; в – блок памяти «БП2сл», окончательный результат обработки для продукции вида (4) при образце по длине меньше модификатора; г – блок памяти «БП2сл», окончательный результат обработки для продукции вида (5) при образце большем по своей длине, чем модификатор.

Продукция (1), реализуемая на устройстве с двумя блоками памяти для ОС, представляется словом, имеющим следующий вид:

a**b$d*2*1a$, (7)

где символ «*» в образце является признаком алфавитной переменной; «$» – признаки конца образца и модификатора; символы «*1» и «*2» в модификаторе – порядковый номер алфавитной переменной в образце.

Продукция (1), с ограничением на алфавит, будет иметь следующий вид:

 a{ C1C2}*d$β$, (8)

где «a, d» – конкретные символы рабочего алфавита; символ «*» – алфавитная переменная; скобки {} указывают на область изменения значений алфавитной переменной (любой символ алфавита, который располагаются в нем между символами «C1» и «C2»); β модификатор.

Продукцию (2) можно представить словом, имеющим следующий вид:

 а#b$®d#g$, (9)

где символ «#» в образце означает то, что в ОС между символами «a» и «b» может находиться цепочка символов любой конечной длины; «$» – признаки конца образца и модификатора.

Сопоставление для символа «*» всегда завершается успешно, а символ ОС, соответствующий этой переменной, записывается как во второй блок памяти ОС, так и в буфер. Замена совпавшей части ОС с образцом осуществляется из символов модификатора продукции, считываемого из блока памяти продукций и записываемого посимвольно во второй блок памяти. Если в модификаторе встречается символ «*», то из блока памяти продукций считывается следующий символ модификатора «2», являющийся порядковым номером, по которому в буфере записан символ из ОС, конкретизирующий алфавитную переменную образца. Этот символ из буфера затем записывается следующим во второй блок памяти ОС вслед за предыдущим.

Структурная схема устройства с одним блоком памяти для ОС представлена на рисунке 3.

 

Рис. 3. Структурная схема устройства с одним блоком памяти для ОС: УУ – устройство управления; БПП – блок памяти продукций (Ич – информационная часть, Уч – управляющая часть); ПлПсл – блок памяти ОС (Ич – информационная часть, Уч – управляющая часть);

БлСрсим – блок сравнения символов; Буф – буфер.

 Рассмотрим структурную организацию варианта устройства, при котором ОС размещено в одном блоке памяти (рис. 3).

 

Рис. 4. Схемы расположения ОС в памяти для устройства с одним блоком памяти ОС: а – исходное слово; б – окончательный результат, случай, когда длина модификатора больше длины образца; в – окончательный результат, случай, когда длина модификатора меньше длины образца.

Блок памяти для продукций и ОС двухбайтные (информационный и управляющий байты). Признаки концов слова образца и слова модификатора представлены дополнительным управляющим байтом, который записывается в памяти продукции над позициями их последних символов соответственно.

Размещение слова в памяти при различных длинах образцов и модификаторов представлены рис 4. Если длина модификатора больше длины образца, то в управляющей части слова модификатора ставится специальный признак в позиции, равной длине образца, уменьшенной на единицу (рис. 4), продукция (1), признак Пр1. Другой признак Пр2 ставится в конце модификатора (рис. 4), продукция (1), признак Пр2. Если длина модификатора меньше длины образца, то в конце образца в управляющем байте ставится специальный признак Пр3, показывающий, что это признак окончания модификатора (рис. 4), продукция (2), признак Пр3.

Теперь из блока памяти продукций считываются символы модификатора со своими управляющими байтами и записываются в блок памяти ОС на место символов совпавшего фрагмента образца в ОС. Если в управляющем байте определяется один из признаков Пр1, Пр2 или Пр3, то он будет записан в управляющий байт ОС, а в следующие по порядку два байта в ОС будет записан адрес перехода (рис. 4). Если длина модификатора больше длины образца, то таких адресов в ОС будет два: первый адрес – переход в свободный фрагмент памяти, второй адрес – возврат на символ ОС, следующий за позицией окончания совпавших фрагментов ОС и образца (рис. 4б). Если длина модификатора меньше длины образца, то такой адрес один (рис. 4в).

Для реализации на устройстве с одним блоком памяти для ОС продукция (1) будет иметь следующий вид (таблица 1)

Таблица 1 – Побайтное представление продукции

 

 

 

1

 

 

 

1

 

 

1

 

 

2

1

 

а

*

*

в

в

*

*

а

Первые две строки таблицы 1 представляют управляющие байты (четыре бита – первая, четыре бита – вторая строки). Третья строка (байт) – символы продукции. Признак «1» в первой строке означает конец образца или модификатора. В этом варианте реализации устройства появляется новая возможность определять равные значения разных алфавитных переменных при их конкретизации при работе продукции. Признак «1» во второй строке в образце указывает, что первая и вторая алфавитные переменные имеют равные значения при их конкретизации. Цифровые символы в позиции записи модификатора в таблице 1 обозначают номера алфавитных переменных в образце, которые считываются из буфера в процессе модификации. Продукция (1) с ограничением на алфавит для этого устройства будет иметь следующий вид (таблица 2).

Таблица 2 – Побайтное представление продукции

 

 

 

 

1

1

 

 

 

2

2

 

 

 

 

 

а

C1

C2

*

d

β

 

 

Признак «1» в верхней строке обозначает конец образца и конец модификатора. Признак «2» в следующей строке указывает на то, что код символа, соответствующий «*», может быть любым в диапазоне кодов между C1 и C2 .

При аппаратной реализации продукций вида (2) на устройстве с одним блоком памяти для ОС (рис. 2) с дополнительным байтом для каждого ее символа организация памяти продукций иллюстрируется таблицей 3.

Таблица 3 – Побайтное представление продукции

 

 

1

 

 

1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

а

#

в

b

#

g

 

 

 

 

Две первые строки таблицы 3 по аналогии с таблицей 1 представляют собой управляющие байты (четыре бита – первая строка, четыре бита – вторая). Третья строка (байт) – символы рабочего алфавита продукции.

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

Заключение

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

Рецензенты:

Зотов И.В., д.т.н., профессор кафедры «Информационные системы и технологии», Юго-Западный государственный университет, г. Курск.

Дегтярев С.В., д.т.н., профессор кафедры «Информационные системы и технологии», Юго-Западный государственный университет, г. Курск.