ПАРАЛЛЕЛЬНАЯ СИСТЕМА ПОИСКА И ЗАМЕНЫ Российский патент 2005 года по МПК G06F17/30 

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

Известно "Устройство для реализации подстановок с двухкомпонентными вхождениями" (а.с. 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 блока памяти слов (БПС) сигналов управления для записи информации в ОЗУ. По команде ПС:=АДЕ подаются адресные входы строк и столбцов для записи данных в ОЗУ. По команде ПС:=ДНС происходит подача на входы ОЗУ данных для записи в оперативное запоминающее устройство (фиг.2).

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

В блоке 8 счетчик блоков поиска и замены - i устанавливается в единичное состояние по команде i:=1.

В блоке 9 алгоритма анализируется текущее значение счетчика блоков i. Если i<=N, где N общее количество блоков поиска и замены в поисковой системе, то процесс загрузки блоков для символьной обработки продолжается. В этом случае происходит переход на блок 10 алгоритма. Если условие в блоке 9 алгоритма не выполняется, т.е. все блоки загружены, то осуществляется переход на блок 12 алгоритма.

В блоке 10 алгоритма по команде БПЗi:=КГП на блоки поиска и замены параллельной системы подаются команды пуска - КП, для начала работы системы.

В блоке 11 алгоритма по команде i:=i+1 происходит изменение значения счетчика блоков (БПЗ) на единицу. При этом осуществляется переход на блок 9 алгоритма.

В блоках 9, 10, 11 сформирован цикл загрузки и работы всех блоков поиска и замены параллельной системы, начиная с первого и по N-ый.

В блоке 12 счетчик блоков поиска и замены - i устанавливается в единичное состояние по команде i:=1.

В блоке 13 алгоритма анализируется текущее значение счетчика блоков i. Если i<=N, где N общее количество блоков поиска и замены в поисковой системе, то работа блоков поиска и замены параллельной системы еще продолжается. В этом случае происходит переход на блок 14 алгоритма. Если условие в блоке 13 алгоритма не выполняется, т.е. все блоки системы остановлены, то осуществляется переход на блок 16 алгоритма.

В блоке 14 алгоритма по команде БУ:=ПРКВi из блоков поиска и замены параллельной системы поступают сигналы признака конца вхождений - ПРВК, которые означают конец работы очередного блока. В этом блоке алгоритма происходит подсчет количества блоков, выполнивших задачу по символьной обработке информации и в связи с этим сформировавшими сигнал останова работы.

В блоке 15 алгоритма по команде i:=i+1 происходит изменение значения счетчика блоков (БПЗ) на единицу. При этом осуществляется переход на блок 13 алгоритма.

В блоках 13, 14, 15 сформирован цикл подсчета всех блоков поиска и замены параллельной системы, которые закончили работу, начиная с первого и по n-ый.

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

Внешние управляющие сигналы "ПУСК" и "СБРОС" поступают в блок 7 управления.

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

В оперативное запоминающее устройство блока 3 БПС записаны обрабатываемые слова, в которых необходимо обнаружить вхождения. Под вхождениями подразумевается символ или цепочка символов (включая слова), которые нужно найти в словах блока БПС. Вхождения записываются в оперативное запоминающее устройстве блока 1 БПВ. В блок 2 подстановок БПО записываются подстановки. Это отдельные символы, цепочка символов или целые слова на которые необходимо заменить обнаруженные вхождения в обрабатываемых словах текста. По команде ПУСК из ОЗУ блоков памяти вхождений и слов в блоки поиска и замены системы записываются соответственно вхождения и слова.

В каждом блоке поиска и замены операция сравнения на компараторе происходит последовательно, каждая буква вхождения сравнивается с символами обрабатываемого слова. В блоке 14 анализа и формирования сигналов сдвига обрабатывается сигнал сравнения символов, поступившего из компаратора КОМ DD12. Обрабатываемое слово из ОЗУ блока 3 памяти слов записывается в регистр обрабатываемого слова РгСОБ DD41 блока поиска и замены. Вхождение записывается в регистр вхождений РгВ DD7. В каждом блоке поиска и замены анализируется сигнал из блока управления блоком, устанавливающий режим работы устройства - PP. Если вхождение обнаружено в слове, то формируется адрес (позиция) этого вхождения в слове. Обнаруженное вхождение находится в регистре подстановок РгПОД DD43 блока 20 регистра подстановок. В случае, если пользователем выбран режим поиска и замены, то в регистр подстановок РгПОД из памяти подстановок записывается вместо вхождения подстановка - цепочка символов. После проведения операции подстановки, информация из регистра подстановок РгПОД DD43 переписывается в регистр буфер РгБУФ DD24 блока 21 регистра буфера. Регистр РгПОД при этом освобождается для дальнейшего поиска вхождений в обрабатываемом слове. Если выбран режим только поиска, то адрес вхождения записывается в ОЗУ блока 15 хранения адреса. Адрес хранится в блоке 15 хранения адреса. Если сравнение не произошло, то формируются сигналы сдвига СДС, ССД в блоке 16 управления блоком, поступающие на вход блоков БРСП. Если при работе устройства возникает ситуация, при которой были получены вначале положительные результаты сравнения в компараторе, а затем отрицательный, но признак конца вхождения еще не обнаружен. В этом случае будут найдены только несколько символов вхождения, но не все вхождения полностью. При положительном результате в компараторе происходит сдвиг влево на одну позицию информации регистра слова РгСОБ DD41, в котором находится слово. Слово из регистра слова РгСОБ DD41 побуквенно переходит в регистр подстановок РгПОД DD43. Двоичным счетчиком подсчитывается положительная серия сравнений в компараторе. В случае отрицательного результата при сравнении происходит переписывание информации из регистра подстановок РгПОД DD43 в регистр буфер РгБУФ DD24. Затем из регистра буфера РгБУФ DD24 символы переписываются в регистр слова РгСОБ DD41. Количество сдвигов вправо будет меньше на один, чем количество сдвигов влево. Процесс поиска вхождений будет продолжен, но со второй буквы фрагмента, где была обнаружена положительная серия совпадений в обрабатываемом слове. Первая буква в этом случае как бы "вычеркивается". Процесс продолжается до тех пор, пока не будут обнаружены все вхождения и осуществлены операции замены в обрабатываемом слове.

Блок 1 памяти вхождений содержит оперативное запоминающее устройство (ОЗУ) - память вхождений ПВ DD8, в котором будут записаны вхождения.

Блок 2 подстановок содержит оперативное запоминающее устройство (ОЗУ) - память подстановок ПОД DD9, в котором будут хранится подстановки.

Блок 3 памяти слов содержит оперативное запоминающее устройство (ОЗУ) - память слов ПС DD10, в котором будут записаны обрабатываемые слова.

Блок 7 управления генерирует информационные и управляющие сигналы, поступающие на вход блоков системы.

Блок 4 поиска и замены БПЗ содержит: блок регистра вхождения - БРВХ DD11, компаратор - КОМ DD12, блок регистра слов и подстановок - БРСП DD13, блок анализа и формирования сигналов - БАФС DD14, блок хранения адреса вхождений - БХАВ DD15.

Блок 11 регистра вхождений - БРВХ содержит реверсивный регистр сдвига РгВ DD17 (регистр вхождений), в котором будет хранится вхождение, логический элемент И DD18 для обнаружения признака конца вхождения. По сигналам управления СУП происходит разрешение записи информации, по адресным входам АД записанные данные ДН в ОЗУ (память вхождений) из блока 7 управления (фиг.1, 2, 4). С выхода памяти вхождений информация ДВ поступает на вход реверсивного регистра вхождений РгВ DD17, по сигналам управления СУ из блока 16 управления блоком, происходит запись буквы вхождения в регистр вхождений. Сигнал сдвига вхождений СДВ из блока 16 управления блоком поступает на вход реверсивного регистра вхождений - РгВ (фиг.4). Выходная информация из реверсивного регистра вхождений ВДВ поступает на вход компаратора КОМ 12 (фиг.3, 4). Реверсивный регистр РгВ DD17 выполняет сдвиг в любом направлении: слева направо или наоборот. Сдвиг вправо выполняется при значении сигнала СДВ=1, сдвиг влево - при СДВ=0, т.е. направление сдвига осуществляется одним управляющим сигналом [3, 4]. Элемент И DD18 формирует сигнал признака конца вхождений ПРКВ, равный единице (все единицы на входе). В памяти вхождений формируется сигнал КР - конец работы, если ОЗУ будет пусто. Перед началом работы устройства в памяти вхождений записаны все вхождения, в регистре вхождений находится первое вхождение, сигнал признака конца вхождений ПРКВ равен нулю, сигнал сдвига вхождений СДВ равен нулю.

Компаратор КОМ DD12 представляет собой устройство сравнения на равенство входных величин: выходных данных вхождений ВДВ блока 11 БРВХ и выходных данных слов ВДС блока 13 БРСП (фиг.4, 5). Если входные сигналы равны, то на выходе компаратора формируется единичный сигнал ССР. В противном случае ССР будет равен нулю. Выходной сигнал компаратора поступает на вход блока 16 управления блоком и на вход блока 14 анализа и формирования сигналов сдвига (фиг.4, 7).

Блок 13 регистров слов и подстановок содержит: блок регистра подстановок БРгПОД DD20, блок регистра буфера БРгБУФ DD21, блок регистра обрабатываемого слова - БРгСОБ DD22, логический элемент И DD19 предназначен для обнаружения признака конца слова ПРКС.

Блок регистра подстановок БРгПОД DD20 содержит: реверсивный регистр сдвига РгПОД DD43 (регистр подстановок), в котором будут хранится символы обрабатываемого слова в случае положительного сравнения в компарторе и электронный ключ КЛЧ DD42. Блок регистра буфера БРгБУФ DD21 содержит: реверсивный регистр буфер сдвига РгБУФ DD24 для промежуточного хранения информации и электронный ключ КЛ DD23. Блок регистра обрабатываемого слова БРгСОБ DD22 содержит: реверсивный регистр сдвига РгСОБ DD41 (регистр слов), в котором будет хранится обрабатываемое слово, и электронный ключ ЭКЛ DD40.

По сигналам управления УРР происходит разрешение записи информации, по адресным входам АДЕ записываются данные ДНС в ОЗУ (память слов) из блока 16 управления блоком (фиг.2). С выхода памяти слов информация ДС поступает на входы блоков поиска и замены БПЗ параллельной системы. В каждом блоке поиска и замены входная информация ДС записывается в реверсивный регистр слова РгСОБ DD41, по сигналам управления СУР из блока 16 управления блоком (фиг.9). Сигнал сдвига слов СДС из блока 16 управления блоком поступает на вход блока регистра обрабатываемого слова БРгСОБ DD22, в котором на вход реверсивного регистра слов РгСОБ DD41 (фиг.5, 9). Выходная информация из реверсивного регистра слова РгСОБ DD41 - ВДС поступает на вход логического элемента И DD19, а также на второй вход компаратора КОМ DD12, на информационный вход электронного ключа КЛЧ DD 40, затем на вход регистра подстановок РгПОД, на информационный вход регистра буфера РгБУФ через электронный клю КЛ DD23 (фиг.5, 6, 9, 10). На информационный вход регистра слова РгСОБ DD41 поступает выходная информация с регистра буфера РгБУФ DD24. Элемент И DD19 формирует сигнал признака конца слова ПРКС, равный единице (все единицы на входе). Перед началом работы устройства в памяти слов ПС ОЗУ DD10 записаны все слова, в регистре слова РгСОБ находится первое слово, сигнал признака конца слова ПРКС равен нулю. Если на выходе компаратора КОМ будет сформирован сигнал сравнения ССР, равный единице, то сигнал сдвига СДС будет равен нулю, в этом случае будет сформирован сигнал сдвига влево информации на один разряд. Информация из регистра слова РгСОБ DD41 сдвинется на один символ влево. Этот символ перейдет по информационным сигналам СИГ в регистр подстановок РгПОД DD43. Процесс сдвига влево будет продолжаться до тех пор, пока не будет получен отрицательный результат сравнения в компараторе КОМ DD12 или не будет обнаружено вхождение в слове. Предположим, что было зафиксировано 5 сдвигов влево, а затем получен отрицательный сигнал сравнения ССР, равный нулю. В этом случае вся информация из регистра подстановок РгПОД перепишется в регистр буфер РгБУФ, под управлением сигналов сдвига: СДВП и ССД, равные нулю. После этого блоком управления 16 блоком будут сформированы сигналы сдвига вправо при этом сигналы сдвига СДС и ССД будут равны единице. Информация из регистра буфера РгБУФ DD24 будет сдвинута вправо на один символ меньше чем влево, в нашем случае 4. В этом случае вторая буква слова будет первой в регистре слова РгСОБ DD41, процесс поиска вхождений будет продолжен. Четыре буквы из регистра подстановок РгПОД DD43 перейдут вначале в регистр буфер РгБУФ DD24, а затем перепишутся в регистр слова РгСОБ DD41, если выбран режим работы устройства поиска и замена. Если выбран режим работы только поиска вхождений с сохранением адресов в ОЗУ DD39, то в этом случае информация из регистра слова РгСОБ DD41 будет переписываться сразу в регистр буфер РгБУФ DD24. Режимы работы устройства будут формироваться управляющими сигналами: СУР, СИГ, СГУ из блока 16 управления блоком.

Блок 14 анализа и формирования сигналов сдвига содержит: D - триггер Тр DD26, двухвходовый логический элемент И DD27 с инверсным входом, двухвходовый логический элемент И DD29, двухвходовый логический элемент И DD25, трехвходовый логический элемент И DD28 с инверсным входом, четырехвходовый элемент И DD31 с инверсными входами, трехвходовый элемент И DD32 с инверсным входом, электронный ключ DD34, двоичный счетчик СЧ1 DD30, двоичный счетчик СЧ2 DD33, двухвходовый элемент ИЛИ с инверсными входами DD36, двухвходовый элемент И DD35. Перед началом работы устройства двоичные счетчики DD30, DD33, а также D-триггер Тр установлены в нулевое состояние. Блок 14 анализа и формирования сигналов сдвига обрабатывает выходной сигнал ССР с компаратора КОМ DD12. Если сигнал ССР равен единице, то это означает, что произошло совпадение двоичного кода символа вхождения с двоичным кодом буквы слова. В этом случае D-триггер Тр DD26 по приходу из блока 16 управления разрешающего сигнала СЗЩ, равного единице, устанавливается в единичное состояние. Логический элемент И DD29, выполняющий функцию электронного ключа, отпирается, тактовые импульсы ТАК из блока 16 управления поступают на суммирующий (+) вход двоичного счетчика СЧ1 DD30. В двоичном счетчике СЧ1 DD30 происходит суммирование тактовых импульсов, количество которых соответствует количеству совпадений в компараторе КОМ. На выходе двоичного счетчика СЧ1 DD30 формируется двоичный код, соответствующий количеству положительных совпадений в компараторе. При каждом положительном совпадении в компараторе происходит формирование сигналов сдвига влево СДВ и СДС, равных нулю, и осуществляется сдвиг на один символ влево в регистрах РгВ DD17 блока 1 памяти вхождений и регистре слова РгСОБ DD41 блока 22 регистра обрабатываемого слова. Регистр РгБУФ DD24 блока 21 регистра буфера записывает каждый символ, поступающий из регистра слова РгСОБ DD41, если сравнения не произошло. В случае обнаружения признака конца вхождения ПРКВ равным единице логическим элементов И DD18 блока 11 регистра вхождений происходит определение адреса вхождения и записывание по соответствующему адресу записи в оперативное запоминающее устройство ОЗУ DD39 блока 15 хранения адреса вхождений. Если признак конца слова не обнаружен ПРКВ=0 (равен нулю), то предыдущее вхождение восстанавливается, т.е. переписывается заново из памяти вхождений и процесс поиска вхождений в слове продолжается (в случае наличие нескольких вхождений в одном слове). Если совпадений в компараторе КОМ не происходит, выходной сигнал ССР равен нулю, то формируется только сигнал СДС равным нулю и происходит сдвиг влево на одну позицию информации, находящейся в регистре слова РгСОБ DD41 блока 22 регистра обрабатываемого слова. При каждом сдвиге влево и отрицательном результате совпадения в компараторе, из памяти слов ПС переписывается (дописывается) символ в регистр слова РгСОБ DD41 блока 22 регистра обрабатываемого слова. Возможна ситуация в поисковой операции, когда был получен положительный результат сравнения символов, тогда формируется сдвиг влево на один разряд регистров РгСОБ DD41 и РгПОД DD43. После сдвига получен второй раз положительный результат, третий и так далее, но признака конца вхождения еще нет. Допустим, на n шаге получен отрицательный результат сравнения, а вхождение полностью не обнаружено. В этом случае D-триггер Тр DD26 был установлен в состояние единицы, т.е. на выходе элемента единицы. На следующем этапе сигнал сравнения равен нулю ССР=0. На выходе логического элемента И DD27 будет сформирован единичный сигнал. Логический элемент И DD28 также будет открыт, прямоугольные импульсы из блока 16 управления блоком ПРИ будут поступать на вычитающий вход двоичного счетчика СЧ1 DD30. Вычитание происходит до тех пор, пока на выходе счетчика не будет двоичный код равный единице. На положительный вход счетчика прямоугольные импульсы из блока 16 управления блоком поступать не будут, т.к. логический элемент И DD29, выполняющий функцию электронного ключа, будет заперт установившимся в нулевое состояние D-триггером DD26. Логический элемент И DD31 выполняет функцию дешифратора единицы. Выход этого элемента равен единице в случае получения на выходе счетчика СЧ1 DD30 двоичного кода 0001. При всех других комбинациях на выходе данного элемента будет состояние нуль. При единице на выходе этого элемента логический элемент И DD28 запирается, т.к. единица поступает на инверсный вход. Прямоугольные импульсы на вычитающий вход счетчика СЧ1 DD30 не поступают. Счетчик СЧ1 DD30 обнуляется командой ОБН, поступающей из блока 16 управления блоком. Логический элемент И DD32 выполняет роль своеобразного "клапана", формирующего количества сдвигов вправо регистра слова РгСОБ DD41. Каждый раз когда происходит вычитание единицы из содержимого счетчика СЧ1 DD30, происходит перемещение вправо информации из регистра РгБУФ DD24 в регистр слова РгСОБ DD41. Количество сдвигов вправо будет на один меньше, чем количество сдвигов влево. В нашем примере n-1. Вторая буква из полученной серии положительных сдвигов будет первой в регистре слова РгСОБ DD41. Вхождение будет заново переписано из памяти вхождений в регистр вхождений РгВ DD17. Процесс поиска будет продолжен. Логический элемент ИЛИ DD36 выполняет функцию распознавания режима работы. Как известно, система работает в двух независимых режимах: определения вхождений с общими частями и определения вхождений и без (пересечений) общих частей. В первом случае признак режима работы РР будет равен нулю. Во втором случае признак РР равен единице. Логический элемент И DD35 выполняет функцию электронного ключа. В случае когда признак работы системы РР равен нулю, на выходе элемента ИЛИ DD36 всегда будет единица. Электронный ключ DD35 будет открыт. Прямоугольные импульсы ПРИ из блока 16 управления блоком через открытый ключ поступают на третий вход логического элемента И DD28. Этот режим характеризуется перемещением информации из регистра РгБУФ DD24 в регистр слова РгСОБ DD41 на n-1 разрядов, т.е. будет сформирован возврат информации, где n - количество положительных сдвигов, всякий раз, когда будет обнаружено вхождение в обрабатываемом слове, при этом признак конца вхождения ПРКВ будет равен единице. Если режим работы системы будет установлен как поиск вхождений без общих частей, то в этом случае РР равен единице. В случае обнаружения вхождения, при этом признак вхождений ПРКВ равен также единице. На выходе логического элемента ИЛИ DD36 установить нулевое значение. Электронный ключ И DD35 будет заперт. Прямоугольные импульсы ПРИ из блока 16 управления блоком не будут поступать на вход элемента И DD28 (фиг.7). Информация из регистра РгБУФ DD24 не переместится в регистр слова РгСОБ DD41. В этом случае будет сформирован сдвиг влево символов из регистра слова РгСОБ DD41 в регистр РгПОД DD43, т.е. возврата информации не будет (фиг.5, 9, 10).

Признак конца работы устройства ПСП, равный единице, может быть сформирован тогда, когда все вхождения просмотрены, в памяти вхождений нет информации и память слов ПС также пуста. Если ПСП равен нулю, то регистр слова РгСОБ DD41 блока 22 регистра обрабатываемого слова БРгСОБ принимает новую информацию (новое слово) из памяти слов (фиг.2, 5, 9).

Блок 15 хранения адреса вхождений БХАВ содержит оперативное запоминающее устройство ОЗУ DD39, двоичный счетчик формирующий адреса столбцов ОЗУ - Сч Ст DD37, двоичный счетчик формирующий адреса строк ОЗУ - Сч Стр DD38. Двоичные счетчики вначале работы устройства обнулены управляющими сигналами СБР, СБО, поступающими из блока 16 управления блоком. На входы счетчиков поступают прямоугольные импульсы ГИ, ТИ из блока 16 управления блоком. Счетчики формируют адреса строк и столбцов по которым будет записаны адреса вхождений, поступающие на вход оперативного запоминающего устройства ОЗУ DD39, если выбран в устройстве только режим поиска вхождений. Сигналы управления оперативного запоминающего устройства ОЗУ DD39 считывания/запись и выбора кристалла соответственно при записи принимают значения Сч/Зп=0, ВК=0 (фиг.8).

Блок 16 управления блоком БПЗ синтезируется на основе ГСА алгоритма управления (фиг.11) известным способом [3,5]. Размеченная ГСА работы блока 16 управления блоком приведена на фиг.12, где обозначено:

Логические условия:X1: "КП"Х6: "СЧ1>1"Х2: "ПЗ"Х7: "ПРКВ"Х3: "РР"Х8: "ПРКС"Х4: "ССР"Х9: "ПСП"Х5: "ТР"Операторы:У1: "КП:=1"У19: "РгБУФ:=РгПОД"У2: "РгСОБ:=СУР"У20: "РгБУФ:=ВДС"У3: "РгБУФ:=СГУ"У21: "РгСОБ:=ДС"У4: "РгСОБ:=ДС"У22: "ССД:=0"У5: "РгВ:=ДВ"У23: "СВП:=1"У6: "ТР:=0"У24: "СЧ1:=ПРИ"У7: "СДВ:=0"У25: "СДС:=1"У8: "СДС:=0"У26: "ССД:=1"У9: "СРР:=0"У27: "РгСОБ:=РгБУФ"У10: "СРР:=1"У28: "РгВ:=СУ"У11: "СДС:=СВП"У29: "РгВ:=ДВ"У12: "ТР:=ССР"У30: "ОБН:=1"У13: "СЗЩ:=1"У31: "СЧ1:=0"У14: "ТР:=1"У32: "РгПОД:=ПОД"У15: "СЧ1:=ТАК"У33: "Кл:=СВА"У16: "РгПОД:=СИГ"У34: "Сч/Зп:=0"У17: "РгПОД:=ВДС"У35: "ВК:=0"У18: "СДВП:=0"У36: "ОЗУ:=АВХ"

Блок 7 управления системой синтезируется на основе ГСА алгоритма управления параллельной системой (фиг.13) известным способом [3, 5]. Размеченная ГСА работы блока 7 управления параллельной системой приведена на фиг.14, где обозначено

Логические условия:X1: "УОО"Х3: "i<=N"Х2: "ПУСК"Операторы:У1: "СБРОС:=1"У8: "ПОД:=УПР"У2: "ПВ:=СУП"У9: "ПОД:=АДС"У3: "ПВ:=АД"У10: "ПОД:=ДАН"У4: "ПВ:=ДН"У11: "i:=1"У5: "ПС:=УРР"У12: "БПЗi=КПi"У6: "ПС:=АДЕ"У 13: "i:=i+1"У7: "ПС:=ДНС"У14: "БУ:=ПРКВ1"

ИСТОЧНИКИ ИНФОРМАЦИИ

1. Кудрявцев В.Б., Подколзин А.С., Ушчумлич Ш. Ввеление в теорию абстрактных автоматов. М.: Из-во МГУ, 1985. 174 с.

2. Марков А.А., Нагорный Н.М. Теория алгорифмов. - Москва.: Наука – 318 с. Главная редакция физико-математической литературы. 1984 г.

3. Успенский В.А., Семенов А.Л. Теория алгорифмов: основные открытия и приложения. - Москва.: Наука. Главная редакция физико-математической литературы. 1987 г. - 210 с.

4. Алексенко А.Г., Шагурин И.И. Микросхемотехника: Учеб. пособие для вузов. - 2-е изд., перераб. и доп. - М.: Радио и связь, 1990. - 496 с.: ил.

5. Баранов С.И. Синтез микропрограммных автоматов. - Энергия. Ленинградское отделение. 1974 г. - 184 с.

6. Цифровые и налоговые интегральные микросхемы: Справочник под ред. С.В.Якубовского. - М.: Радио и связь, 1990. - 496 с.: ил.

7. Патент № 2195015 (прототип).

8. Патент N 2150740 (аналог).

9. А.С. СССР N 1837327 (аналог).

10. А.С. СССР N 1667097 (аналог).

Изобретение относится к техническим, средствам информатики и вычислительной техники и может быть использовано для поиска и замены произвольных вхождений в словах произвольного текста. Технический результат заключается в расширении функциональных возможностей поисковой системы. Система содержит: блок памяти вхождений, блок памяти слов, блок управления, блок подстановок, n блоков поиска и замены. 17 ил.

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