Параллельная система поиска и замены

Параллельная система поиска и замены

Иллюстрации

Показать все

Реферат

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

Известно "Устройство для реализации подстановок с двухкомпонентными вхождениями" (а.с. N 1667097, 1991 г., Бюл. N 28), позволяющее определить вхождения в представленном слове.

Известно "Устройство для морфологического анализа слов естественных языков и языков "деловой прозы" (а.с. N 1837327, 1993 г., Бюл. N 32), которое позволяет проводить морфологический анализ слов реальных языков на основе логических признаков принадлежности к классам словоформ.

Известно "Устройство поиска вхождений" (патент N 2150740, 2000 г.), которое позволяет осуществлять поиск вхождений, представленных в четырех видах.

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

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

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

2) упростить алгоритм блока управления,

3) повысить надежность работы поисковой системы.

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

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

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

Процессы поиска вхождений образца в обрабатываемом слове адекватно описываются в терминах языка регулярных выражений путем использования операций итерации и конъюнктивного следования (конкатенация) [1].

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

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

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

2) повтор одинаковых букв есть в середине обрабатываемого слова, пример - "тимааааро", при этом принято обозначение V{C}M;

3) итерация существует в конце слова, пример - "тирмииии", обозначение V{C};

4) итерация в обрабатываемом слове существует в начале слова, примером может служить вхождение "ллллмавр", обозначение {C}Z;

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

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

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

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

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

1) только итерации, т.е. часть, состоящая из одинаковых символов;

2) остальная часть вхождения, но без итераций в начале обрабатываемого слова.

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

Необходимо рассмотреть случаи, когда под итерацией понимается не только одна буква, но несколько чередующихся символов, например обрабатываемое слово имеет вид: абабабабабпртоо. В начале слова записаны итерации, состоящие из разных букв аб, и таких повторов в примере будет - 5. Такие итерации назовем двухбуквенные. Легко привести примеры трех, четырех, пяти и n-буквенных итераций. В конце обрабатываемое слово заканчивается также итерацией, но из одинаковых букв. В конце слова тоже могут быть многобуквенные итерации. Для осуществления поиска различных видов слов, состоящих из различных вариантов итераций необходимо, очевидно, разработать сложные схемы селекции, определяющие вид итераций. Затем в зависимости от вида итерации выбирается алгоритм, осуществляющий поисковую операцию. Целью предлагаемого изобретения является создание поискового устройства, осуществляющего поиск вхождения в обрабатываемом слове с любым видом итераций без сложных схем селекции, а также функционирующим в двух независимых режимах работы с выполнением операции замены.

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

К У М И Р И И И И И П Р О С Т - обрабатываемое слово

И И - вхождение.

После проведения поисковой операции в режиме поиска с общими частями, имеем четыре вхождения, рис.1.

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

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

Если необходимо произвести операцию замены, скажем, для примера на подстановку – М И Р, то в результате имеем преобразованное обрабатываемое слово, рис.3.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

На фиг.14 - размеченная ГСА работы блока управления параллельной системы.

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

1. ПРКВ - признак конца вхождения. Это может быть двоичный код, равный 11...1.

2. ПРКС - признак конца слова, равный 11...1.

3. КР - команда, определяющая конец работы устройства.

4. СУ - сигналы управления сдвигающим регистром блока памяти вхождений (сигналы записи, приема, выдачи данных).

5. СУР - сигналы управления сдвигающим регистром слова Рг СОБ блока регистра обрабатываемого слова (установки в "0", приема, синхронизации).

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

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

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

9. УРР - команды управления записью, выдачей, хранения данных в ОЗУ памяти слов блока памяти слов.

10. АД - адреса данных в ОЗУ - выдачи и записи блока памяти вхождения.

11. АДЕ - адреса данных в ОЗУ - выдачи и записи блока памяти слов.

12. ДН - данные, записанные в ОЗУ (двоичные коды букв) блока памяти вхождений.

13. ДНС - данные, записанные в ОЗУ (двоичные коды букв) блока памяти слов.

14. ССР - сигнал сравнения, поступающий из компаратора.

15. СИН - команда синхронизации, поступающая на вход двоичного счетчика Сч1 блока анализа и формирования сигналов сдвига из блока управления блоком.

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

17. СВА - команда выдачи адреса вхождения из блока анализа и формирования сигналов сдвига в блок хранения адреса вхождений.

18. СЗЩ - команда разрешения записи в триггер Тр блока анализа и формирования сигналов сдвига выходного сигнала из компаратора.

19. СДЛ - команда, поступающая из блока управления блоком, открывающая или запирающая электронный ключ И DD25 блока анализа и формирования сигналов сдвига.

20. СН - команда синхронизации двоичного счетчика Сч2 блока анализа и формирования сигналов сдвига.

21. СО - команда обнуления двоичного счетчика Сч2 блока анализа и формирования сигналов сдвига.

22. ПИМ - прямоугольные импульсы, поступающие на информационный вход электронного ключа И DD25 блока анализа и формирования сигналов сдвига.

23. АдСТ - адреса столбцов для записи вхождений в блок хранения адреса вхождений.

24. АдСТР - адреса строк для записи вхождений в блок хранения адреса вхождений.

25. ДАВ - данные адресов вхождений.

26. АВХ - адрес вхождения.

27. ВДВ - выходные данные вхождения блока памяти вхождений.

28. ВДС - выходные данные слова блока памяти слов и подстановок.

29. ДС - данные - обрабатываемые слова.

30. ДВ - данные вхождений.

31. ПРИ - прямоугольные импульсы, поступающие из бока управления блоком на информационный вход логического элемента И DD25 блока анализа и формирования сигналов сдвига.

32. ТАК - тактовые прямоугольные импульсы, поступающие на информационный вход логического элемента И DD29.

33. СВП - команда, определяющая количество сдвигов вправо регистра слова РгСОБ DD41 блока регистра обрабатываемого слов.

34. ДШЕ - команда, определяющая двоичный код 0001 (единицу) на выходе двоичного счетчика Сч1 DD30.

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

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

37. СБР - команда обнуления двоичного счетчика СчСт DD37 блока хранения адреса вхождений.

38. СБО - команда обнуления двоичного счетчика СчСтр DD38 блока хранения адреса вхождений.

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

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

41. РР - команда признака режима работы системы.

42. ПСП - признак "пустого (отсутствие данных)" оперативного запоминающего устройства обрабатываемых слов блока памяти слов.

43. СРР - команда признака работы системы в различных режимах.

44. ПЗ признак работы устройства - поиска и замены или только поиска.

45. ПУС - признак "пустого (отсутствие данных)" оперативного запоминающего устройства подстановок блока подстановок.

46. ППП - информационный сигнал, состоящий из сигналов ПУС и ПСП - признаков "пустых" оперативных запоминающих устройств ОЗУ подстановок и обрабатываемых слов.

47. ССД - управляющий сигнал сдвига информации влево или вправо регистра буфера РгБУФ блока регистра буфера.

48. СДВП - управляющий сигнал сдвига информации влево регистра подстановок РгПОД блока регистра подстановок.

49. ПОД - данные подстановки - выходная информация из памяти ОЗУ подстановок.

50. ЗАМ - данные замены - выходная информация регистра подстановок РгПОД, замена осуществляется в том случае, когда устройство работает в режиме поиска и замены.

51. СИМС - выходная информация регистра буфера РгБУФ, поступает на вход регистра слова РгСОБ блока регистра обрабатываемого слова.

52. УПР - команды управления записью, выдачей, хранения данных в ОЗУ подстановок блока подстановок.

53. АДС - адреса данных в ОЗУ подстановок - выдачи и записи информации блока подстановок.

54. ДАН - данные, записанные в ОЗУ подстановок (двоичные коды букв) блока подстановок.

55. СИГ - сигналы управления сдвигающим регистром РгПОД блока регистра подстановок (установки в "0", приема, синхронизации).

56. СГУ - сигналы управления сдвигающим регистром РгБУФ блока регистра буфера (установки в "0", приема, синхронизации).

57. ВыхИн - выходная информация с выхода электронного ключа ЭКЛ блока регистра обрабатываемого слова.

58. УП - управляющий сигнал электронного ключа КЛ блока регистра буфера.

59. УР - управляющий сигнал электронного ключа ЭКЛ блока регистра обрабатываемого слова.

60. СТР - управляющий сигнал электронного ключа КЛЧ блока регистра подстановок.

61. КП - команда пуска работы блока поиска и замены параллельной системы.

62. УПР - команды управления записью, выдачей, хранения данных в ОЗУ блока подстановок.

63. АДС - адреса строк и столбцов, по которым данные записываются в ОЗУ блока подстановок.

64. ДАН - данные, записанные в ОЗУ (двоичные коды букв) блока подстановок.

65. ВхИн - выходная информация с выхода электронного ключа КЛ блока регистра буфера.

66. ВыхИнф - выходная информация с выхода электронного ключа КЛЧ блока регистра подстановок.

67. УСТ "0" - управляющий сигнал установки в нуль регистра буфера блока регистра буфера.

68. СИНХ - управляющий сигнал синхронизации работы регистра буфера блока регистра буфера.

69. ПРИМ - управляющий сигнал приема информации регистра буфера блока регистра буфера.

70. УСН "0" - управляющий сигнал установки в нуль регистра слова блока регистра обрабатываемого слова.

71. СНХ - управляющий сигнал синхронизации работы регистра слова блока регистра обрабатываемого слова.

72. НРБ - управляющий сигнал приема информации регистра слова блока регистра обрабатываемого слова.

73. УС "0" - управляющий сигнал установки в нуль регистра подстановок блока регистра подстановок.

74. СИН - управляющий сигнал синхронизации работой регистра подстановок блока регистра подстановок.

75. РБТ - управляющий сигнал приема информации регистра подстановок блока регистра подстановок.

Описание алгоритма работы блока управления поиска и замены (БПЗ).

Содержательная ГСА управления приведена на фиг.9 и отражает работу блока поиска и замены (БПЗ) (фиг.3).

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

В блоке 3 по команде "КП:=1" блок поиска и замены получает сигнал разрешения на работу из блока управления параллельной системы.

В блоке 4 алгоритма анализируется режима работы устройства - команда ПЗ. Если устройство работает в режиме обработки символьной информации поиска и замены - выход ДА, то в этом случае осуществляется переход на блок 9 алгоритма. Если устройство работает только в режиме поиска выход из блока - НЕТ, то в этом случае осуществляется переход на блок 5 алгоритма.

В блоке 5 алгоритма происходит подача сигналов управления СУР из блока 16 управления на вход регистра слова РгСОБ DD41 по команде РгСОБ:=СУР. По команде РгБУФ:=СГУ на вход регистра - буфера РгБУФ DD24 подаются управляющие сигналы СГУ из блока 16 управления. По этой команде осуществляется разрешение для записи информации из памяти слов ПС DD10 в регистр слова РгСОБ, а также для передачи информации из регистра слова РгСОБ в регистр буфер РгБУФ (фиг.2, 6, 9).

В блоке 6 алгоритма происходит запись в регистр слова из памяти слов обрабатываемого слова РгСОБ:=ДС, в регистр вхождений записывается из памяти вхождений последовательность букв (вхождение) РгВ:=ДВ.D - Триггер Тр DD26 блока анализа и формирования сигналов сдвига устанавливается в "0" ТР:=0. По этим командам происходит предварительная загрузка устройства (фиг.4, 7, 9).

В блоке 7 алгоритма по командам СДВ:=0 и СДС:=0 формируются сдвиги влево на один разряд информации, находящейся в регистре РгВ DD17 и регистре слова РгСОБ DD41 блоков 11 БРВХ (фиг.4) и 22 БРгСОБ (фиг.9).

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

В блоке 9 алгоритма по команде СРР:=0 выходной сигнал логического элемента DD35 блока анализа и формирования сигналов сдвига устанавливается в нулевое состояние. В этом случае логические элементы DD28 и DD32 указанного блока будут закрыты. На выходах этих элементов будут нулевые состояния.

В блоке 10 алгоритма по команде СДС:=0 на вход регистра слова РгСОБ DD41 блока 22 регистра обрабатываемого слова подается сигнал из блока 16 управления работой блока памяти и замены, равный нулевому значению. При этом осуществляется сдвиг информации в этом регистре на один разряд влево.

В блоке 11 алгоритма по команде СРР:=1 выходной сигнал логического элемента DD36 блока анализа и формирования сигналов сдвига устанавливается в единичное состояние. В этом случае логические элементы DD35 и DD28 указанного блока будут открыты. На выходах этих элементов будет сигнал ПРИ - прямоугольные импульсы, поступающие из блока 16 управления работой блока памяти и замены.

В блоке 12 алгоритма по команде СДС:=СВП на вход регистра слова РгСОБ DD41 блока 22 регистра обрабатываемого слова подаются прямоугольные импульсы СВП, количество которых на единицу меньше количества сигналов, поступивших на суммирующий вход счетчика СЧ1 DD30 блока 14 анализа формирования сигналов сдвига. При этом по приходу каждого импульса СВП осуществляется сдвиг информации в этом регистре вправо на один разряд.

В блоке 13 алгоритма происходит анализ сигнала сравнения ССР, поступившего с выхода компаратора КОМ DD12 (фиг.4). Если ССР=1, то произошло совпадение буквы вхождения с буквой обрабатываемого слова. В этом случае осуществляется переход на блок 14 алгоритма. Если ССР=0, то совпадения не произошло и переход произошел на блок 19 алгоритма.

В блоке 14 алгоритма на вход D - Т триггера DD26 блока 14 анализа и формирования сигналов сдвига поступает сигнал ССР из компаратора КОМ DD12 (фиг.4) ТР:=ССР. Триггер устанавливается в единичное состояние. Это означает, что входные символы на входе компаратора равны между собой.

В блоке 15 алгоритма по команде СЗЩ:=1 из блока 16 управления происходит разрешение на запись в D-триггер информации с выхода компаратора. По команде ТР:=1 D-триггер блока 14 анализа и формирования сигналов сдвига устанавливается в единицу. На суммирующий вход двоичного счетчика СЧ1 DD30 этого же блока поступают тактовые импульсы СЧ1:=ТАК. Счетчик подсчитывает количество совпадений в компараторе (фиг.7).

В блоке 16 алгоритма происходит подача сигналов управления СИГ из блока 16 управления на вход регистра подстановок РгПОД DD43 по команде РгПОД:=СИГ для записи символов из регистра обрабатываемого слова РгСОБ (фиг.9, 10).

В блоке 17 алгоритма происходит запись в регистр подстановок РгПОД DD43 из регистра обрабатываемого слова РгСОБ символов ВДС по команде РгПОД:=ВДС (фиг.9, 10). В этом случае произошло совпадение входных величин на входе компаратора.

В блоке 18 алгоритма по командам СДС:=0, СДВ:=0, СДВП:=0 формируется сдвиг влево информации, находящийся в регистрах соответственно РгСОБ DD41 блока 22 регистра обрабатываемого слова, РгВ DD17 блока 11 регистра вхождений, РгПОД DD43 – регистр подстановок блока 20 регистра подстановок. При этом осуществляется переход на блок 32 алгоритма.

В блоке 19 алгоритма анализируется содержимое D-триггера Тр DD26 (фиг 7). Если Тр=0, то это означает, что совпадения на предыдущем шаге не было, в этом случае формируется сигнал сдвига влево на один разряд в регистре слова РгСОБ DD41 блока 22 регистра обрабатываемого слова. Если Тр=1, то осуществляется переход на блок 23 алгоритма.

В блоке 20 алгоритма подается сигнал управления СГУ из блока 16 управления на вход регистра буфера РгБУФ DD24 по команде РгБУФ:=СГУ для записи символов из регистра слова РгСОБ DD41 (фиг.9).

В блоке 21 алгоритма формируется командой СДС:=0 сдвиг влево на один разряд информации из регистра слова РгСОБ в регистр РгБУФ блока 21 блока регистра буфера БРгБУФ (фиг.6). При этом РгБУФ:=ВДС выходная информация ВДС из регистра слова РгСОБ переписывается в регистр РгБУФ через открытый ключ КЛ DD23. На освободившиеся место в регистр слова РгСОБ записывается очередной символ обрабатываемого слова из блока 3 памяти слов РгСОБ:=ДС (фиг.2, 5, 9).

В блоке 22 алгоритма по команде ССД:=0 из блока 16 управления формируется управляющий сигнал, при котором осуществляется сдвиг влево информации в регистре РгБУФ DD24 на один разряд влево блока 21 регистра буфера для записи очередного символа из регистра слова РгСОБ DD41 (фиг.5, 9). При этом осуществляется переход на блок 36 алгоритма.

В блоке 23 алгоритма по команде РгБУФ:=СГУ подаются сигналы управления СГУ из блока 16 управления на вход регистра буфера РгБУФ DD24 для записи символов из регистра подстановок РгПОД DD43. По команде РгПОД:=СИГ происходит подача сигналов управления СИГ из блока 16 управления на вход регистра подстановок РгПОД DD43 для выдачи символов из регистра подстановок РгПОД в регистр буфер РгБУФ. По команде ССД:=0 из блока 16 управления формируется управляющий сигнал, при котором осуществляется сдвиг влево информации в регистре РгБУФ DD24 на один разряд влево для записи очередного символа из регистра подстановок РгПОД DD43. По команде СДВП:=0 формируется сдвиг влево информации, находящийся в регистре РгПОД DD43 блока 20 подстановок. В результате выполнения этих команд вся информация из регистра подстановок РгПОД будет переписана в регистр буфер РгБУФ (фиг.5, 6, 10).

В блоке 24 алгоритма по команде РгБУФ:=РгПОД в регистр буфер РгБУФ DD24 блока 21 регистра буфера символы будут перенесены из регистра подстановок РгПОД DD43. По этим командам будет осуществлена перезапись информации из РгПОД в РгБУФ (фиг.5, 6, 10).

В блоке 25 анализируется состояние двоичного счетчика СЧ1 DD30 блока 14 анализа и формирования сигналов сдвига. Если состояние счетчика меньше или равно единице, то осуществляется переход на блок 29 алгоритма. Если условие выполняется, т.е. значение счетчика СЧ1 больше единицы, то происходит переход на блок 26 алгоритма.

В блоке 26 алгоритма формируется подача прямоугольных импульсов из блока 16 управления - ПРИ на вычитающий вход двоичного счетчика СЧ1 DD30 блока 14 анализа и формирования сигналов сдвига. По команде СВП:=1 в счетчике происходит алгебраическое вычитание единицы до тех пор, пока состояние этого счетчика не будет равно единичному значению СЧ1:=ПРИ (фиг.7).

В блоке 27 алгоритма формируется сдвиг вправо и переписывание информации из регистра буфера РгБУФ DD 24 в регистр слова РгСОБ DD41 блока 22 регистра обрабатываемого слова. Командами из блока 16 управления СДС:=1 и ССД:=1 информация из регистра буфера РгБУФ сдвигается на один разряд вправо в регистр слова РгСОБ. По команде РгСОБ:=СУР происходит разрешение осуществления операций сдвига в блоке 22 регистра обрабатываемого слова. Информация из регистра буфера РгБУФ сдвигается в регистр слова РгСОБ до тех пор, пока состояние счетчика СЧ1 DD30 не будет равно единице (фиг.4, 5, 6, 7, 9).

В блоке 28 алгоритма по команде РгСОБ:=РгБУФ в регистр слова РгСОБ DD41 будут перенесены символы из регистра буфера РгБУФ DD24. По этим командам будет осуществлена перезапись информации из РгБУФ в РгСОБ (фиг.5, 6, 9).

Блоки 25, 26, 27, 28 алгоритма формируют цикл. Выходом из цикла является условие, при котором значение счетчика СЧ1 будет равно единице. По выходу из блока осуществляется переход на блок 29 алгоритма.

В блоке 29 алгоритма на вход регистра вхождения РгВ DD17 блока 11 регистра вхождений из блока 16 управления поступают управляющие сигналы РгВ:=СУ. В результате этого в регистр вхождений записывается информация из памяти вхождений РгВ:=ДВ (фиг.4).

В блоке 30 алгоритма регистр слова РгСОБ принимает информацию из регистра буфера РгБУФ РгСОБ:=РгБУФ (фиг.5, 6, 9). Обрабатываемое слово сдвигается вправо на n-1 разрядов, где n количество сдвигов влево этого же слова.

В блоке 31 алгоритма по команде ОБН:=1 происходит обнуление счетчика СЧ1 DD30 блока 14 анализа и формирования сигналов сдвига. Двоичный счетчик СЧ1 DD30 принимает нулевое значение СЧ1:=0. По выходу из блока формируется переход на блок 32 алгоритма.

В блоке 32 алгоритма происходит анализ признака конца вхождения ПРКВ (фиг.4). Если ПРКВ=1, то в регистре вхождения РгВ обнаружен двоичный код 11...1. В этом случае вхождение обнаружено в обрабатываемом слове и в блок хранения адреса вхождений записывается адрес вхождения (фиг.8) Если ПРКВ=0, то это означает что процесс сравнения идет побуквенно, но не все буквы вхождения еще просмотрены, при этом осуществляется переход на 38 блок алгоритма.

В блоке 33 алгоритма анализируется режима работы устройства - команды ПЗ. Если устройство работает в режиме обработки символьной информации поиска и замены - выход ДА, то это означает, что при обнаружении вхождения в обрабатываемом слове будет осуществлена замена в регистре подстановок РгПОД на заранее записанную в регистр подстановку - цепочку символов. В этом случае осуществляется переход на блок 34 алгоритма. Если устройство работает только в режиме поиска выход из блока - НЕТ, то это означает, что адрес обнаруженного в процессе поиска вхождения будет записан по соответствующим адресам строк и столбцов в оперативную память устройства (фиг.8). В этом случае осуществляется переход на блок 37 алгоритма.

В блоке 34 алгоритма по команде РгПОД:=СИГ происходит подача сигналов управления СИГ из блока 16 управления на вход регистра подстановок РгПОД DD43 для записи символов из блока памяти подстановок БПО - ОЗУ подстановок ПОД DD9. По команде РгПОД:=ПОД в регистр подстановок РгПОД DD43 записываются буквы подстановки из памяти подстановок ПОД (фиг.2, 5, 10). В результате выполнения этих команд в регистр подстановок РгПОД будет записана информация из блока БПО памяти подстановок - ПОД.

В блоке 35 алгоритма по команде РгБУФ:=СГУ подаются сигналы управления СГУ из блока 16 управления на вход регистра буфера РгБУФ DD24 для записи символов из регистра подстановок РгПОД DD43. По команде СДВП:=0 формируется сдвиг влево информации, находящийся в регистре подстановок РгПОД DD43 блока 20 регистра подстановок. По команде ССД:=0 из блока 16 управления формируется управляющий сигнал при котором осуществляется сдвиг влево информации в регистре буфере РгБУФ DD24 на один разряд влево для записи очередного символа из регистра подстановок РгПОД DD43.

В блоке 36 алгоритма по команде РгБУФ:=РгПОД происходит запись информации в регистр буфер РгБУФ DD24 из регистра подстановок РгПОД DD43. В результате выполнения этих команд блоков 34, 35, 36 вся информация из регистра подстановок РгПОД будет переписана в регистр буфер РгБУФ. Тем самым будет осуществлена подстановка символов ПОД на место обнаруженного вхождения ВДС (фиг.5, 6, 10). Операция поиска и замены осуществляется только тогда, когда устройство работает в режиме поиска вхождений без общих частей. По выходу из этого блока осуществляется переход на блок 38 алгоритма.

В блоке 37 алгоритма происходит запись адреса в блок хранения адреса вхождений. На управляющий вход электронного ключа Кл DD34 блока 14 анализа и формирования сигналов сдвига поступает разрешающий сигнал из блока 16 управления - СВА, Кл:=СВА. Информация с выхода двоичного счетчика СЧ2 DD33 через открытый ключ Кл DD34 поступает на вход оперативно-запоминающего устройства ОЗУ DD39 (фиг.7, 8). Сигнал разрешения для записи информации поступает из блока 16 управления Сч/Зп:=0, ВК:=0. На управляющие входы поступают нулевые значения, что соответствует режиму записи в ОЗУ устройства входной информации т.е. адреса вхождения - АВХ ОЗУ:=АВХ.

В блоке 38 алгоритма происходит анализ признака конца слова ПРКС (признаком является двоичный код, равный всем единицам 11...1). Если ПРКС=0, то процесс поиска будет продолжен и при этом осуществляется переход на блок 13 алгоритма. Если обнаружен признак конца слова ПРКС=1, то осуществляется переход на блок 39 алгоритма.

В блоке 39 алгоритма происходит анализ признака "пустого" ОЗУ слов - ПСП блока 3 памяти обрабатываемых слов. Если ПСП равен нулю, то осуществляется переход на блок 5 алгоритма. В этом случае в памяти слов блока 3 памяти слов имеется информация (слова), с которыми необходимо будет провести поисковые операции и операции замены, т.е. процесс обработки будет продолжен. Если ПСП равен единице, то это означает, что все слова в памяти слов блока 3 памяти обрабатываемых слов просмотрены (фиг.2). В этом случае осуществляется переход на конечный блок 40 алгоритма. В работе поискового устройства происходит останов.

Блок 40 алгоритма является конечным блоком.

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

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

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

В блоке 5 алгоритма происходит загрузка вхождений из блока памяти вхождений (фиг.2) для проведения поисковых операций. По команде ПВ:=СУП происходит подача на вход оперативного запоминающего устройство (ОЗУ) ПВ DD.8 блока памяти вхождений (БПВ) сигналов управления для записи и считывания информации в ОЗУ. По команде ПВ:=АД подаются адресные входы строк и столбцов для записи и чтения данных в ОЗУ. По команде ПВ:=ДН происходит подача на входы ОЗУ данных (вхождений) для записи в оперативное запоминающее устройство (фиг.2).

В блоке 6 алгоритма происходит загрузка информации в блок памяти слов для проведения поисковых операций. По команде ПС:=УРР происходит подача на вход оперативного запоминающего устройство (ОЗУ) ПС DD.10 блока памяти слов (БПС) сигналов управления для записи информации в ОЗУ. По команде ПС:=АДЕ подаются адресные входы строк и столбцов для з