Устройство параллельного поиска и замены вхождений в обрабатываемых словах

Устройство параллельного поиска и замены вхождений в обрабатываемых словах

Иллюстрации

Показать все

Реферат

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

Известна "Информационно-поисковая система" (з-ка RU, патент №2199778 от 27.02.2003 г.), выполняющая поисковую операцию вхождений в словах [9].

Известно "Устройство поиска произвольных вхождений" (з-ка RU, патент №2202823 от 20.04.2003 г.), определяющая произвольные вхождения в обрабатываемых словах [10].

Известна (з-ка RU, "Поисковое устройство произвольных вхождений" (патент №2209465 от 27.07.2003 г.), осуществляющая поиск произвольных вхождений в обрабатываемых словах.

В качестве прототипа выбрано "Устройство поиска и замены произвольных вхождений в словах текста" (з-ка RU, патент №2250493 20.04.2005 г.), которое выполняет функцию поиска и замены произвольных вхождений в словах текста.

Задача заключалась в следующем:

1) расширить функциональные возможности устройства,

2) повысить скорость выполнения поисковых операций,

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

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

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

Решение задачи осуществляется тем, что устройство параллельного поиска и замены вхождений в обрабатываемых словах, содержащее блок памяти вхождений, блок управления, отличается тем, что дополнительно введены: блок памяти обрабатываемых слов, блок анализа поиска, блок памяти замены, блок замены, блок хранения результата, причем с первого по третий информационные выходы блока управления, на которых соответственно формируются сигналы управления оперативным запоминающим устройством, адреса столбцов и строк оперативного запоминающего устройства и данные, записанные в оперативное запоминающее устройство, соединены соответственно с первым по третий информационными входами блока памяти вхождений, информационный выход которого соединен с первым информационным входом блока анализа поиска, второй информационный вход которого соединен с информационным выходом блока памяти обрабатываемых слов, с первого по третий информационные входы которого соединены соответственно с четвертым по шестой информационными выходами блока управления, на которых соответственно формируются сигналы управления оперативным запоминающим устройством блока памяти обрабатываемых слов, адреса столбцов и строк оперативного запоминающего устройства и данные, записанные в оперативное запоминающее устройство, с третьего по пятый управляющие входы которого соединены соответственно с первым по третий управляющими выходами блока анализа поиска, на которых формируются сигналы, характеризующие соответственно результат сравнения символов вхождения и обрабатываемого слова, режим работы устройства поиска вхождений в обрабатываемом слове без общих частей и признак конца символов обрабатываемого слова, с третьего по пятый информационные входы блока анализа поиска соединены соответственно с седьмого по девятый информационными выходами блока управления, на которых формируются сигналы установки в нулевое состояние двоичных счетчиков, управляющие сигналы, формирующие режимы работы регистров блоков регистров вхождений и обрабатываемых слов соответственно, первый и второй управляющие выходы блока управления, на которых соответственно формируются сигналы признака работы устройства с общими частями и отпирающий импульс соединены соответственно с первым и вторым управляющими входами блока анализа поиска, второй информационный выход которого соединен с первым информационным входом блока замены, третий и четвертый информационные входы которого соединены соответственно с десятым и одиннадцатым информационными выходами блока управления, на которых формируются сигналы управления блоком регистров замены и блоком регистра результата замены, входящих в состав блока замены, третий управляющий выход блока управления соединен с управляющим входом блока замены, второй информационный вход которого соединен с информационным выходом блока памяти замены, с первого по третий информационные входы которого соединены соответственно с двенадцатого по четырнадцатый информационными выходами блока управления, на которых формируются сигналы управления оперативным запоминающим устройством, адреса столбцов и строк оперативного запоминающего устройства и данные, записанные в оперативное запоминающее устройство блока памяти замен, с четвертого по девятый управляющие выходы блока памяти соединены соответственно с первым по шестой управляющими входами блока хранения результата, второй информационный вход которого соединен с первым информационным выходом блока анализа поиска, информационный выход блока замены соединен с первым информационным входом блока хранения результата, первый и второй управляющие входы "СБРОС" и "ПУСК" блока управления являются внешними входами устройства.

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

БПОС - блок памяти обрабатываемых слов служит для записи, хранения и выдачи обрабатываемых слов, с которыми необходимо проводить поисковые операции.

БАП - блок анализа поиска служит для анализа поисковой операции, определения способа поиска вхождений в обрабатываемом слове, а также определения адреса вхождения.

БПЗМ - блок памяти замены служит для записи, хранения и выдачи замены в регистры блока регистров результата замены.

БЗАМ - блок замены служит для выполнения операций: 1) записи символа обрабатываемого слова в случае отрицательного сравнения, 2) записи замены в регистры блока регистров результата замены, если произошло положительное сравнение в блоке компараторе.

БХР - блок хранения результатов служит для записи и хранения в нем адресов вхождений в обрабатываемых словах и результатов выполнения операций замены.

БУ - блок управления служит для генерации управляющих сигналов устройства.

Процессы поиска вхождений в обрабатываемом слове можно выполнить как в последовательном, так и в параллельном режимах символьной обработки. Формировать новое слово возможно с помощью операций замены, а также левой или правой конкатенаций [1].

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

Поиск вхождений в обрабатываемом слове может быть осуществлен в двух режимах работы устройства: 1) определение вхождений, имеющих общие части, 2) определение вхождения без общих частей [7]. Такая процедура поиска, которая удовлетворяет поставленным требованиям, называется корректной.

В устройстве применяются оперативные запоминающие устройства, в которых хранится информация [2]. Вхождение, обрабатываемое слово и замена переписываются из памяти в сдвигающие регистры. Процессы записи и считывание информации в регистры могут быть следующие: параллельный ввод - параллельный вывод, используется в регистре для хранения вхождений, последовательный ввод - последовательный вывод, используется для в регистре для хранения замены, а также последовательный ввод - параллельно-последовательный вывод, используется для хранения в регистре обрабатываемого слова [3], [5]. В устройстве применяются элементы нейронной и пороговой логики [4].

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

1) нет повтора одинаковых букв (итерации) в обрабатываемом слове;

2) повтор одинаковых букв есть в середине обрабатываемого слова, при этом принято обозначение W{A}P;

3) итерация существует в конце слова, обозначение Н{А};

4) итерация в обрабатываемом слове существует в начале слова, обозначение {A}R;

5) итерация в обрабатываемом слове присутствует и в начале слова и в конце, обозначение {A}S{A}.

6) обрабатываемое слово состоит полностью из итераций, обозначение {А}.

В зависимости от вида итераций применяется алгоритм, осуществляющий поисковую операцию вхождения в обрабатываемом слове [7, 8].

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

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

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

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

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

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

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

На фиг.7 показана функциональная схема блока замены.

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

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

На фиг.10 показана функциональная схема блока хранения результата.

На фиг.11а, 11б, 11в - содержательная ГСА работы устройства.

На фиг.12а, 12б, 12в - размеченная ГСА работы устройства.

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

Для описания алгоритма работы блока 7 управления используются следующие идентификаторы.

1. УВХ - сигналы управления оперативным запоминающим устройством блока памяти вхождений: обнуление, выбор кристалла, режим записи/считывания.

2. АдВХ - адреса столбцов и строк оперативного запоминающего устройства блока памяти вхождений.

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

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

5. УОС - сигналы управления оперативным запоминающим устройством блока памяти обрабатываемых слов: обнуление, выбор кристалла, режим записи/считывания.

6. АдОС - адреса столбцов и строк оперативного запоминающего устройства блока памяти обрабатываемых слов.

7. ДОС - данные, записанные в оперативное запоминающее устройство блока памяти обрабатываемых слов.

8. ОС - выходные данные из оперативного запоминающего устройства блока памяти обрабатываемых слов.

9. УЗМ - сигналы управления оперативным запоминающим устройством блока памяти замен: обнуление, выбор кристалла, режим записи/считывания.

10. АдЗМ - адреса столбцов и строк оперативного запоминающего устройства блока памяти замен.

11. ДЗМ - данные, записанные в оперативное запоминающее устройство блока памяти замен.

12. ЗМ - выходные данные из оперативного запоминающего устройства блока памяти замен.

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

14. УПРС - управляющие сигналы: обнуления, синхроимпульсы, сигналы, формирующие режимы работы регистров, блока регистров обрабатываемых слов блока анализа поиска.

15. СВ - сигнал сдвига влево на один разряд информации блока регистров вхождений блока анализа поиска.

16. СО - сигнал сдвига влево на один разряд информации блока регистров обрабатываемых слов блока анализа поиска.

17. РСР - выходной двоичный сигнал из блока анализа поиска, который определяет результат сравнения символов вхождения и обрабатываемого слова.

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

19. ПОЧ - признак работы устройства с общими частями, двоичный сигнал блока анализа поиска, определяющий режим работы устройства: 1) поиск вхождений с общими частями, 2) поиск вхождений без общих частей в обрабатываемом слове.

20. ОБС - информационный сигнал, поступающий из блока управления на входы R1, R2, R3 - установки в нулевое состояние двоичных счетчиков блока анализа поиска.

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

22. БОЧ - двоичный сигнал блока анализа поиска, определяющий режим работы устройства поиска вхождений в обрабатываемом слове без общих частей.

23. CMi - входной информационный сигнал - символ вхождения блока регистров вхождений.

24. СИМi - выходной информационный сигнал блока регистров вхождений.

25. ОС1 - символ обрабатываемого слова первого регистра Рг1 блока регистров обрабатываемого слова.

26. OCi - выходной информационный сигнал - символы обрабатываемого слова блока регистров обрабатываемого слова.

27. ПКОС - признак конца символов обрабатываемого слова, нулевая информация 00...0.

28. УКЛ - управляющий сигнал блока управления, поступающий на управляющие входы схем И блока замены.

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

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

31. ОСЗМ - информационный сигнал - символы обрабатываемого слова или замены, поступающий на информационный вход блока регистров результата замены.

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

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

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

35. АД СТЛ - адреса столбцов оперативного запоминающего устройства для записи результата замены или адреса вхождения в блок хранения результата.

36. АД СТР - адреса строк оперативного запоминающего устройства для записи результата замены или адреса вхождения в блок хранения результата.

37. ГИ - генератор импульсов, поступающий из блока управления на суммирующий вход (+) двоичного счетчика Сч1 блока хранения результата.

38. ТИ - тактовые импульсы, поступающие из блока управления на суммирующий вход (+) двоичного счетчика Сч2 блока хранения результата.

39. ОБ - команда обнуления двоичного счетчика Сч1 блока хранения результата.

40. УС "0" - команда обнуления двоичного счетчика Сч2 блока хранения результата.

41. ВК - команда выбора кристалла оперативного запоминающего устройства ОЗУ блока хранения результата.

42. Сч/Зп - команда считывания/записи оперативного запоминающего устройства ОЗУ блока хранения результата.

43. РЕПЗ - выходные данные оперативного запоминающего устройства блока хранения результата - результаты замен или адреса вхождений в обрабатываемом слове.

44. СБРОС - сигнал сброса - обнуление элементов памяти устройства выполнения параллельного поиска и замены.

45. ПУСК - сигнал начало работы устройства.

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

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

В блоке 2 алгоритма по сигналу "СБРОС" происходит установка в нуль всех элементов памяти устройства (фиг.1).

В блоке 3 алгоритма по команде "СБРОС:=1" происходит установка в единичное состояние сигнала СБРОС.

В блоке 4 алгоритма анализируется признак работы устройства "ПУСК". По выходу блока "единица" начинается работа устройства параллельного поиска и замены вхождений в обрабатываемых словах.

В блоке 5 алгоритма по команде ПВХ:=УВХ происходит подача информационного сигнала на вход блока памяти вхождений. Информационный сигнал УВХ состоит из управляющих сигналов: выбора кристалла, сигналов разрешения записи и считывания информации из ОЗУ блока. По команде ПОС:=УОС происходит подача аналогичного информационного сигнала УОС из блока управления на вход блока памяти обрабатываемых слов. По команде ПЗМ:=УЗМ на управляющие входы оперативного запоминающего устройства замены поступают управляющие сигналы: выбор кристалла, сигналы разрешения записи и считывания информации из ОЗУ блока (фиг.1, 2).

В блоке 6 алгоритма по команде ПВХ:=АдВХ на вход оперативного запоминающего устройства блока памяти вхождений подаются адреса строк и столбцов для записи вхождений в ОЗУ. По команде ПОС:=АдОС на вход ОЗУ блока памяти обрабатываемых слов подаются адреса строк и столбцов для записи в память обрабатываемых слов. По команде ПЗМ:=АдЗМ на вход оперативного запоминающего устройства блока памяти замены подаются адреса строк и столбцов для записи замен в ОЗУ (фиг.1, 2).

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

В блоке 8 алгоритма анализируется признак работы устройства поиска и замены вхождений в обрабатываемых словах - РПЗ. По выходу НЕТ осуществляется переход на 51 конечный блок алгоритма работы устройства. По выходу ДА выполняется переход на блок 9 алгоритма.

В блоке 9 алгоритма анализируется признак левой конкатенации - ЛЕК, т.е. присоединения вхождения к обрабатываемому слову слева. Такая операция имеет вид {S}P, где S - вхождение, а Р - обрабатываемое слово. По выходу НЕТ осуществляется переход на блок 14 алгоритма. По выходу ДА выполняется переход на блок 10 алгоритма.

Блоки 9, 10, 11, 12, и 13 организуют цикл, в котором выполняется операция левой конкатенации. Цикл позволят получить одно или неоднократное присоединение вхождения к обрабатываемому слову слева, это можно записать как {{S1}...{Sn}}Р.

В блоке 10 алгоритма по команде УКЛ:=1 на управляющий вход блока замены - БЗАМ из блока управления подается управляющий сигнал УКЛ, равный единице (фиг.7). В результате этой операции данные блока регистра замены через открытые электронные ключи с прямыми управляющими входами и схемы ИЛИ поступают на вход блока регистра результата замены. При этом осуществляется операция левой конкатенации.

В блоке 11 алгоритма по команде БРгЗМ:=УЗАМ на входы блока регистров замены поступают управляющие сигналы из блока управления. Это сигналы: разрешения выдачи данных, синхроимпульсы (фиг.7). По команде БРгРЗ:=УРЗМ из блока управления подаются управляющие сигналы, по которым происходит запись с выходов схемы ИЛИ в блок регистров результата замены. Это сигналы: разрешение записи данных и синхроимпульсы (фиг.7).

В блоке 12 алгоритма по команде ОСЗМ:=ЗМ на вход данных блока регистров результата замены поступают данные из блока регистров замены.

В блоке 13 алгоритма по команде БРгРЗ:=ЗМ в блок регистров результата замены записывается вхождение из блока регистров замены (фиг.7).

В блоке 14 алгоритма анализируется признак правой конкатенации - ПРК, т.е. присоединения вхождения к обрабатываемому слову справа. Такая операция имеет вид P{S}, где, Р - обрабатываемое слово, a S - вхождение. По выходу НЕТ осуществляется переход на блок 20 алгоритма. По выходу ДА выполняется переход на блок 15 алгоритма.

Блоки 14, 15, 16, 17, и 18 организуют цикл, в результате, которого выполняется операция правой конкатенации. Цикл позволят получить одно или неоднократное присоединение к обрабатываемому слову вхождение справа, это можно записать как P{{S1}...{Sm}}.

В блоке 15 алгоритма по команде УКЛ:=0 на управляющий вход системы электронных ключей блока замены - БЗАМ из блока управления подается управляющий сигнал УКЛ равный нулю (фиг.7). В результате этой операции данные блока регистров обрабатываемого слова через открытые электронные ключи с инверсными управляющими входами и схемы ИЛИ поступают на вход блока регистра результата замены. При этом осуществляется операция записи символов обрабатываемого слова в блок регистров результата замены.

В блоке 16 алгоритма по команде БРгОС:=УПРС на входы блока регистров обрабатываемого слова поступают управляющие сигналы из блока управления. Это сигналы: разрешения выдачи данных, синхроимпульсы (фиг.6, 7). По команде БРгРЗ:=УРЗМ из блока управления подаются управляющие сигналы, по которым происходит запись с выходов схемы ИЛИ в блок регистров результата замены. Это сигналы: разрешение записи данных и синхроимпульсы (фиг.7, 9).

В блоке 17 алгоритма по команде ОСЗМ:=ОС на вход данных блока регистров результата замены поступают данные из блока регистров обрабатываемого слова (фиг.6, 7, 9).

В блоке 18 алгоритма по команде БРгРЗ:=ОСЗМ в блок регистров результата замены записывается обрабатываемое слово из блока регистров обрабатываемого слова (фиг.6, 7).

В блоке 19 алгоритма анализируется признак присоединения - конкатенация КОН левая или правая. По выходу ДА блока осуществляется переход на блок 9 алгоритма, в этом случае процесс присоединений продолжается или осуществляется переход на блок 20 алгоритма. По выходу НЕТ происходит переход на блок 43 алгоритма для записи результата конкатенаций в оперативное запоминающее устройство блока хранения результатов.

В результате выполнения этих циклов возможны следующие композиции вхождения и обрабатываемого слова: {S}P - одна левая конкатенация, {{S1}...{Sn}}P - n левых конкатенаций, а также P{S} - правая конкатенация и Р{{S1}...{Sm}} - m правых конкатенаций.

В блоке 20 алгоритма по команде БРгВХ:=УПРВ на управляющие входы регистров блока регистров вхождений из блока управления подаются управляющие сигналы: разрешения записи информации, синхроимпульсы, установки в нулевое состояние регистров (фиг.1, 5). Управляющие сигналы подаются одновременно на все входы регистров блока. По команде БРгОС:=УПРС на управляющие входы регистров блока регистров обрабатываемого слова из блока управления подаются управляющие сигналы: разрешения записи слова, синхроимпульсы, обнуления регистров (фиг.1, 6). По команде ОТИ:=1 на управляющие входы электронных ключей из блока управления подается отпирающий сигнал, равный единичному значению. Через открытый электронный ключ, схема И с прямым управляющим входом, количество импульсов сдвига поступают на вход схемы ИЛИ (фиг.4). По команде СчА:=СВ на суммирующий вход двоичного счетчика СчА поступают сигналы сдвига СВ из блока регистров вхождений. Количество импульсов сдвига СВ определяет количество символов в вхождении (фиг.3, 4).

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

В блоке 22 алгоритма анализируется признак конца обрабатываемого слова ПКОС. В случае управляющего сигнала ПКОС, равного нулевому значению - выход НЕТ блока, это означает, что все символы обрабатываемого слова просмотрены и регистр обрабатываемого слова пуст (фиг.6). В этом случае осуществляется переход на блок 43 алгоритма. Если сигнал ПКОС равен единичному значению - выход ДА блока, то поиск в обрабатываемом слове продолжается (фиг.6). В этом случае осуществляется переход на блок 23 алгоритма.

В 23 алгоритма по команде КОМ:=ВХ на первые входы компаратора поступают символы вхождения ВХ. По команде КОМ:=ОС на вторые входы компаратора поступают символы обрабатываемого слова ОС. В компараторе выполняется операция сравнение символов вхождения и обрабатываемого слова. Операция сравнения в блоке анализа поиска осуществляется в параллельном режиме посимвольно (фиг.3).

В блоке 24 алгоритма анализируется признак результата сравнения на равенство символов вхождения и обрабатываемого слова - РСР. Если сравнение произошло положительно, сигнал при этом РСР равен единичному значению - выход блока "единица", то осуществляется переход на блок 31 алгоритма. В случае отрицательного сравнения на равенство входных величин - выход "нуль" блока, сигнал РСР равен нулевому значению, при этом выполняется переход на блок 25 алгоритма.

В блоках 25, 26, 27, 28 выполняется операция записи символа обрабатываемого слова в регистр блока регистров результата замены, если произошло отрицательное сравнение символов обрабатываемого слова и вхождения (фиг.3, 7, 9).

В блоке 25 алгоритма по команде УКЛ:=0 управляющий сигнал из блока управления поступает на входы электронных ключей с инверсными управляющими входами, тем самым, отпирая электронные ключи. В результате этого на входы схем ИЛИ поступает символ обрабатываемого слова, который запишется в регистр блока регистров результата замены. Этот характеризуется отрицательным сравнением символов вхождения и обрабатываемого слова (фиг.7).

В блоке 26 алгоритма по команде ОСЗМ:=ОС на информационные входы регистра блока регистров результата замены поступает символ обрабатываемого слова ОС для дальнейшей записи его в регистр блока (фиг.7).

В блоке 27 алгоритма по команде БРгРЗ:=УРЗМ на управляющие входы регистров блока регистров результата замены поступает информационный сигнал из блока управления УРЗМ. В результате этой операции регистры блока устанавливаются в нулевое состояние, на входы регистров поступают синхроимпульсы и происходит разрешение записи информации в регистры блока (фиг.9).

В блоке 28 алгоритма по команде БРгРЗ:=ОС1 на входы регистра блока регистров результата замены поступает символ обрабатываемого слова ОС1. Эта операция осуществляется в случае отрицательного сравнения в блоке компаратора символов обрабатываемого слова и вхождения (фиг.7, 9).

В блоке 29 алгоритма по команде БРгОС:=СО на управляющий вход регистров блока регистров обрабатываемого слова поступает сигнал сдвига СО. В результате этой операции обрабатываемое слово сдвигается на один разряд влево для выполнения поисковой операции (фиг.6).

В блоке 30 алгоритма по команде ОТИ:=0 из блока управления поступает управляющий сигнал ОТИ, равный нулевому значению. Сигнал поступает на инверсный вход схемы И - электронного ключа. В результате этого электронный ключ будет открыт, через него и схему ИЛИ сигнал сдвига влево поступит на суммирующий вход двоичного сумматора СчА (фиг.3, 4). По команде СчА:=СО на суммирующий вход счетчика поступает сигнал сдвига влево СО для подсчета количества сигналов сдвига влево обрабатываемого слова для формирования адреса вхождения в обрабатываемом слове (фиг.4).

По выходу из блока 30 алгоритма осуществляется переход на блок 22 алгоритма для выполнения операции сравнения символов вхождения и сдвинутым влево на один разряд обрабатываемым словом. В результате образуется цикл, в котором будут просмотрены все символы обрабатываемого слова. Циклическая операция будут продолжаться до обнаружения признака конца обрабатываемого слова ПКОС.

В блоке 31 алгоритма анализируется признак операций: 1) поиск, 2) поиска и замены - ПЗ. Если устройство работает в режиме только поиска - выход НЕТ, то в этом случае осуществляется переход на блок 43 алгоритма. В случае работы в режиме поиска и замена - выход ДА алгоритма, то выполняется переход на блок 36 алгоритма.

В блоках алгоритма 32, 33, 34, и 35 определяется способ обработки информации: 1) поиск, 2) поиск и замена. Существуют два вида комбинаций вхождений в обрабатываемом слове: 1) с общими частями символов вхождений, 2) без общих частей символов вхождений. Первый вид это когда между предыдущим вхождением в обрабатываемом слове и последующим есть общие части - символы. В этом случае поиск вхождения в обрабатываемом слове осуществляется сразу же на следующем сдвиге обрабатываемого слова, после положительного сравнения символов вхождения и обрабатываемого слова. Второй вид это когда сравнение символов осуществляется через n сигналов сдвига влево обрабатываемого слова, где n - количество символов вхождения.

В блоке 32 анализируется признак работы устройства с общими частями - выход ДА и без общих частей - выход НЕТ - сигнал ПОЧ. В случае выбора режима работы устройства с общими частями осуществляется переход на блок 22 алгоритма. Если устройство работает в режиме поиска без общих частей, то выполняется переход на блок 33 алгоритма.

Блоки 33, 34 и 35 формируют цикл, в котором выполняется сдвиг влево обрабатываемого слова на один разряд до тех пор, пока сигнал БОЧ - признак работы устройства без общих частей не будет равен нулевому значению.

В блоке 33 алгоритма анализируется двоичный сигнал - признак без общих частей БОЧ (фиг.4). Если сигнал уже равен нулевому значению - выход блока "нуль", то осуществляется переход на блок 22 алгоритма. В случае равенства единичному значению этого сигнала - выход "единица" блока, то выполняется переход на блок 34 алгоритма.

В блоке 34 алгоритма по команде БРгОС:=СО на управляющие входы регистров блока регистров обрабатываемого слова поступают сигналы сдвига влево на один разряд для выполнения операции сдвига данных обрабатываемого слова влево (фиг.6).

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

Блоки 36-42 алгоритма выполняют операцию записи замены в регистры блока регистров результата замены. Если устройство работает в режиме поиска и замены и при этом обнаружено вхождение в обрабатываемом слове, то в регистры блока регистров результата замены записывается цепочка символов замены (фиг.2, 7, 9).

В блоке 36 алгоритма по команде БРгЗМ:=УЗАМ на входы блока регистров замены поступают управляющие сигналы из блока управления. Это сигналы: разрешения выдачи данных, синхроимпульсы (фиг.1, 7).

В блоке 37 алгоритма по команде БРгЗМ:=ЗМ в блок регистров замены записывается замена из блока памяти замены (фиг.2, 7).

В блоке 38 по команде УКЛ:=1 на управляющий вход блока замены - БЗАМ из блока управления подается управляющий сигнал УКЛ равный единице. По выполнению этой операции данные блока регистра замены через открытые электронные ключи с прямыми управляющими входами и схемы ИЛИ поступают на вход блока регистров результата замены (фиг.7).

В блоке 39 алгоритма по команде БРгЗМ:=УЗАМ из блока управления на входы блока регистров замены поступают управляющие сигналы: разрешения выдачи данных, синхроимпульсы (фиг.1, 7).

В блоке 40 по команде БРгРЗ:=УРЗМ из блока управления подаются управляющие сигналы, по которым происходит запись с выходов схемы ИЛИ в блок регистров результата замены. Это сигналы: разрешение записи данных и синхроимпульсы (фиг.1, 7).

В блоке 41 алгоритма по команде ОСЗМ:=ЗМ на информационный вход данных блока регистров результата замены поступают данные из блока регистров замены (фиг.7).

В блоке 42 алгоритма по команде БРгРЗ:=ОСЗМ выполняется запись замены в регистры блока регистров результата замены (фиг.7, 9). По выходу из этого блока выполняется переход на блок 49 алгоритма.

В блоке 43 алгоритма анализируется выполнения устройством операций: 1) поиска, 2) поиска и замены, 3) конкатенаций левой или правой - (П) или (ПЗ) или (КОН). Результат выполнение функций определяется с помощью логической операции ИЛИ. Если не выполнялось ни одной из этих операции устройством - выход НЕТ блока, то осуществляется переход на блок 8 фиг.11a. В случае выполнения хотя бы одной из этих операций - выход ДА блока, то осуществляется переход на блок 44 алгоритма.

В блоке 44 алгоритма по команде АВД:=СчА определяется адрес вхождения в обрабатываемом слове, который вычисляется с помощью двоичного счетчика СчА блока анализа поиска. Адрес вхождения формируется по количеству сигналов сдвига влево, поступивших на суммирующий вход счетчика СчА, вначале вхождения, затем обрабатываемого слова (фиг.4).

В блоке 45 алгоритма по команде РЕЗ:=(АДВ)или(РЗ) определяется результат РЕЗ с помощью логической операции ИЛИ. Результат поиска - адрес вхождения, или в результате поиска и замены или после неоднократных замен, полученное новое слово из блока регистров результата замены, поступает на информационный вход оперативного запоминающего устройства блока хранения результата (фиг.7, 10).

В блоке 46 алгоритма по командам ВК:=0, Сч/3п:=0 сигналы: выбор кристалла и запись/считывание, поступившие из блока 7 управления, устанавливают режим записи информации в ОЗУ блока хранения результата. На управляющие входы поступают нулевые значения, что соответствует режиму записи в ОЗУ устройства входной информации (фиг.10).

В блоке 47 алгоритма по командам ОЗУ:=АдСТЛ и ОЗУ:=АдСТР на адресные входы оперативного запоминающего устройства блока хранения результата поступают адреса столбцов - АдСТЛ и строк - АдСТР. Адреса столбцов и строк определяют двоичные счетчики Сч1 и Сч2 блока. По этим адресам данные записываются в ОЗУ блока (фиг.10).

В блоке 48 алгоритма по ко