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

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

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

Известно также "Устройство для сортировки чисел" (а.с. № 1277091, 1986 г., Бюл. № 46), позволяющее упорядочить числа в возрастающем и в убывающем порядке.

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

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

Задача заключалась в следующем: 1) расширить функциональные возможности поискового устройства; 2) упростить алгоритм блока управления; 3) повысить надежность работы поискового устройства произвольных вхождений.

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

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

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

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

КОМ - служит для сравнения символов обрабатываемого слова с буквами вхождения.

БАФС - блок служит для анализа сигнала компаратора по обнаружению вхождений и формирования сигналов сдвига, а также по определению адреса (позиции) вхождений в обрабатываемом слове.

БХАВ - блок служит для хранения в памяти адресов вхождений.

БУ - блок служит для управления устройством.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

смитааааатромммм - обрабатываемое слово

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

57. СИУ - информационный сигнал, состоящий из сигналов управления УПР и УРР оперативного запоминающего устройства ОЗУ ППОД и оперативного запоминающего устройства ОЗУ ПС.

58. АДР - информационный сигнал, состоящий из адресных сигналов АДС и АДЕ оперативного запоминающего устройства ОЗУ ППОД и оперативного запоминающего устройства ОЗУ ПС.

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

60. СУПР - информационный сигнал, состоящий из сигналов управления СГУ, СУР и СИГ (сигналы записи, приема, выдачи данных) регистров буфера Рг БУФ, обрабатываемых слов Рг СОБ и подстановок Рг ПОД.

Работа алгоритма управления устройства.

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

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

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

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

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

В блоке 8 алгоритма происходит загрузка подстановок в оперативную память ПООД для проведения операции замены из блока управления. В память подстановок ОЗУ ППОД DD15 записывается символьная информация, состоящая из цепочки букв - ДАН. По команде ППОД:=УПР происходит подача на вход оперативно-запоминающего устройства (ОЗУ) ППОД DD15 блока 3 памяти слов и подстановок (БПСП) сигналов управления для записи информации в ОЗУ. По команде ППОД:=АДС подаются адресные входы для записи данных в ОЗУ. По команде ППОД:=ДАН происходит подача на входы ОЗУ данных для записи (фиг.3). По выходу из блока 8 алгоритма осуществляется переход на блок 13 алгоритма.

В блоке 9 алгоритма происходит подача сигналов управления СУР из блока управления на вход регистра слов РгСОБ DD13 по команде РгСОБ:=СУР. По команде РгБУФ:=СГУ на вход регистра - буфера РгБУФ DD11 подаются управляющие сигналы СГУ из блока управления для разрешения записи информации из памяти ПС и ППОД соответственно (фиг.3).

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

В блоке 11 алгоритма по командам СДВ:=0 и СДС:=0 формируются сдвиги влево на один разряд информации, находящейся в регистрах соответственно РгВ DD7 и РгСОБ DD13 блоков 1 и 3 (фиг.2, 3).

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

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

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

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

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

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

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

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

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

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

В блоке 22 алгоритма по командам СДС:=0, СДВ:=0, СДВП:=0 формируется сдвиг влево информации, находящийся в регистрах соответственно РгСОБ DD13 блока 3 памяти слов и подстановок, РгВ DD7 блока 1 памяти вхождений, РгПОД DD12 - регистр подстановок блока 3 памяти слов и подстановок. При этом осуществляется переход на блок 26 алгоритма.

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

В блоке 24 алгоритма подается сигнал управления СГУ из блока управления на вход регистра-буфера РгБУФ DD11 по команде РгБУФ:=СГУ для записи символов из регистра обрабатываемых слов РгСОБ DD13 (фиг.3).

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

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

В блоке 27 алгоритма по команде РгБУФ:=СГУ подаются сигналы управления СГУ из блока управления на вход регистра-буфера РгБУФ DD11 для записи символов из регистра подстановок РгПОД DD12. По команде РгПОД:=СИГ происходит подача сигналов управления СИГ из блока управления на вход регистра подстановок РгПОД DD12 для выдачи символов из регистра подстановок РгПОД в регистр-буфер РгБУФ. По команде ССД:=0 из блока управления формируется управляющий сигнал, при котором осуществляется сдвиг влево информации в регистре РгБУФ DD11 на один разряд влево для записи очередного символа из регистра подстановок РгПОД DD12. По команде СДВП:=0 формируется сдвиг влево информации, находящийся в регистре РгПОД DD12 блока 3 памяти слов и подстановок. В результате выполнения этих команд вся информация из регистра подстановок РгПОД будет переписана в регистр-буфер РгБУФ (фиг.3).

В блоке 28 алгоритма по команде РгБУФ:=РгПОД в регистр-буфер РгБУФ символы будут перенесены из регистра подстановок РгПОД. По этим командам будет осуществлена перезапись информации из РгПОД в РгБУФ (фиг.3).

В блоке 29 анализируется состояние двоичного счетчика Сч1 DD20 блока 4 анализа и формирования сигналов сдвига. Если состояние счетчика меньше или равно единицы, то осуществляется переход на блок 33 алгоритма. Если условие выполняется, т.е. значение счетчика Сч1 больше единицы, то происходит переход на блок 30 алгоритма.

В блоке 30 алгоритма формируется подача прямоугольных импульсов из блока 6 управления - ПРИ на вычитающий вход двоичного счетчика Сч1 DD20 блока 4 анализа и формирования сигналов сдвига. По команде СВП:=1 в счетчике происходит алгебраическое вычитание единицы до тех пор пока состояние этого счетчика не будет равно единичному значению Сч1:=ПРИ (фиг.4).

В блоке 31 алгоритма формируется сдвиг вправо и переписывание информации из регистра РгБУФ в регистр РгСОБ блока 3 памяти слов и подстановок. Командами из блока управления СДС:=1 и ССД:=1 информация из регистра РгБУФ сдвигается на один разряд вправо в регистр РгСОБ. По команде РгСОБ:=СУР происходит разрешение осуществления операций сдвига в блоке 3 памяти слов и подстановок. Информация из регистра РгБУФ сдвигается в регистр РгСОБ до тех пор пока состояние счетчика Сч1 DD20 не будет равно единице (фиг.4).

В блоке 32 алгоритма по команде РгСОБ:=РгБУФ в регистр обрабатываемого слова РгСОБ DD13 будут перенесены символы из регистра-буфера РгБУФ DD11. По этим командам будет осуществлена перезапись информации из РгБУФ в РгСОБ (фиг.3).

Блоки 29, 30, 31, 32 алгоритма формируют цикл. Выходом из цикла является условие, при котором значение счетчика Сч1 будет равно единице. По выходу из блока осуществляется переход на блок 33 алгоритма.

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

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

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

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

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

В блоке 38 алгоритма по команде РгПОД:=СИГ происходит подача сигналов управления СИГ из блока управления на вход регистра подстановок РгПОД DD12 для записи символов из памяти подстановок ППОД DD15. По команде РгПОД:=ПОД регистр подстановок РгПОД DD12 записывает буквы подстановки из памяти подстановок ППОД (фиг.3). В результате выполнения этих команд в регистр подстановок РгПОД будет записана информация из памяти подстановок ППОД.

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

В блоке 40 алгоритма по команде РгБУФ:=РгПОД происходит запись информации в регистр-буфер РгБУФ DD11 из регистра подстановок РгПОД DD12. В результате выполнения этих команд блоков 38, 39, 40 вся информация из регистра подстановок РгПОД будет переписана в регистр-буфер РгБУФ. Тем самым будет осуществлена подстановка символов ПОД на место обнаруженного вхождения ВДС (фиг.3). Операция поиска и замены осуществляется только тогда, когда устройство работает в режиме поиска вхождений без общих частей. По выходу из этого блока осуществляется переход на блок 42 алгоритма.

В блоке 41 алгоритма происходит запись адреса в блок хранения адреса вхождений. На управляющий вход электронного ключа Кл DD24 блока 4 анализа и формирования сигналов сдвига поступает разрешающий сигнал из блока 6 управления - СВА, Кл:=СВА. Информация с выхода двоичного счетчика Сч2 DD23 через открытый ключ Кл DD24 поступает на вход оперативно-запоминающего устройства ОЗУ DD30 (фиг.4, 5). Сигнал разрешения для записи информации поступает из блока 6 управления Сч/Зп:=0, ВК:=0. На управляющие входы поступают нулевые значения, что соответствует режиму записи в ОЗУ устройства входной информации, т.е. адреса вхождения - АВХ ОЗУ:=АВХ.

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

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

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

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

Внешние управляющие сигналы "ПУСК" и "СБРОС" поступают в блок 6 управления. В оперативно-запоминающем устройстве блока БПСП записаны слова произвольного текста, в которых необходимо обнаружить вхождения. Под вхождениями подразумевается символ или цепочка символов (включая слова), которые нужно найти в словах блока БПСП. Вхождения находятся в оперативно-запоминающем устройстве блока БПВ. В блоке сравнения (компараторе) происходит последовательное сравнение каждой буквы вхождения с символами обрабатываемого слова. В блоке 4 анализа и формирования сигналов сдвига обрабатывается сигнал сравнения символов, поступивших из блоков БПСП и БПВ, а также анализируется сигнал из блока управления, устанавливающий режим работы устройства - PP. Если вхождение обнаружено в слове, то формируется адрес (позиция) этого вхождения в слове. Обнаруженное вхождение находится в регистре РгПОД DD12 блока 3 памяти слов и подстановок. В случае, если пользователем выбран режим поиска и замены, то в регистр РгПОД из памяти подстановок записывается вместо вхождения подстановки - цепочка символов. После проведения операции подстановки, информация из регистра РгПОД DD12 переписывается в регистр РгБУФ DD11 блока 3 памяти слов и подстановок. Регистр РгПОД при этом освобождается для дальнейшего поиска вхождений в обрабатываемом слове. Если выбран режим только поиска, то адрес вхождения записывается в ОЗУ блока 5 хранения адреса. Адрес хранится в блоке 5 хранения адреса. Если сравнение не произошло, то формируются сигналы сдвига СДС, ССД в блоке БУ, поступающие на вход блоков БПСП и БПВ. Если при работе устройства возникает ситуация, при которой были получены вначале положительные результаты сравнения в компараторе, а затем отрицательный признак конца вхождения еще необнаружен. В этом случае будут найдены только несколько символов вхождения, но не все вхождение полностью. При положительном результате в компараторе происходит сдвиг влево на одну позицию информации регистра РгСОБ DD13, в котором находится слово. Слово из регистра РгСОБ DD13 по-буквенно переходит в регистр РгПОД DD12. Двоичным счетчиком подсчитывается положительная серия сравнений в компараторе. В случае отрицательного результата при сравнении происходит переписывание информации из регистра подстановок РгПОД DD12 в регистр-буфер РгБУФ DD11. Затем из регистра РгБУФ DD11 символы переписываются в регистр слов РгСОБ DD13. Количество сдвигов вправо будет меньше на один, чем количество сдвигов влево. Процесс поиска вхождений будет продолжен, но со второй буквы фрагмента, где было обнаружена положительная серия совпадений в обрабатываемом слове. Первая буква в этом случае как бы "вычеркивается". Процесс продолжается до тех пор пока не будут обнаружены все вхождения и осуществлены операции замены в обрабатываемом слове.

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

Компаратор 2 представляет собой устройство сравнения на равенство входных величин: выходных данных вхождений ВДВ блока 1 БПВ и выходных данных слов ВДС блока 3 БПСП (фиг.1). Если входные сигналы равны, то на выходе компаратора формируется единичный сигнал ССР. В противном случае ССР будет равен нулю. Выходной сигнал компаратора поступает на вход блока 6 управления и на вход блока 4 анализа и формирования сигналов сдвига (фиг.1).

Блок 3 памяти слов и подстановок содержит оперативно-запоминающее устройство (ОЗУ) - память слов DD14, реверсивный регистр сдвига РгСОБ DD13 (регистр слов), в котором будет хранится обрабатываемое слово, оперативно-запоминающее устройство (ОЗУ) - память подстановок DD15, реверсивный регистр сдвига РгПОД DD12, в котором будут храниться символы обрабатываемого слова в случае положительного сравнения, реверсивный регистр сдвига РгБУФ DD11, логический элемент И DD10 предназначен для обнаружения признака конца слова ПРКС. По сигналам управления УРР происходит разрешение записи информации, по адресным входам АДЕ записываются данные ДНС в ОЗУ (память слов) из блока 6 управления (фиг.3). С выхода памяти слов информация ДС поступает на вход реверсивного регистра слов РгСОБ DD13, по сигналам управления СУР из блока 6 управления происходит запись слова в реверсивный регистр слов РгСОБ DD13. Сигнал сдвига слов СДС из блока 6 управления поступает на вход реверсивного регистра слов РгСОБ DD13 (фиг.3). Выходная информация из реверсивного регистра слов РгСОБ DD13 поступает на вход логического элемента И DD10, а также на второй вход компаратора КОМ DD2, на информационный вход регистра подстановок РгПОД, на информационный вход регистра-буфера РгБУФ. На информационный вход регистра обрабатываемых слов РгСОБ DD13 поступает выходная информация с регистра-буфера РгБУФ DD11. Элемент И DD10 формирует сигнал признака конца слова ПРКС, равный единице (все единицы на входе). Перед началом работы устройства в памяти слов ПС DD14 записаны все слова, в регистре обрабатываемых слов РгСОБ находится первое слово, сигнал признака конца слова ПРКС равен нулю. Если на выходе компаратора КОМ будет сформирован сигнал сравнения ССР, равный единице, то сигнал сдвига СДС будет равен нулю, в этом случае будет сформирован сигнал сдвига влево информации на один разряд. Информация из регистра РгСОБ DD13 сдвинется на один символ влево. Этот символ перейдет по информационным сигналам СИГ в регистр РгПОД DD12. Процесс сдвига влево будет продолжаться до тех пор, пока не будет получен отрицательный результат сравнения в компараторе КОМ DD2 или не будет обнаружено вхождение в слове. Предположим, что было зафиксировано 5 сдвигов влево, а затем получен отрицательный сигнал сравнения ССР, равный нулю. В этом случае вся информация из регистра подстановок РгПОД перепишется в регистр-буфер РгБУФ, под управлением сигналов сдвига: СДВП и ССД, равных нулю. После этого блоком управления 6 будут сформированы сигналы сдвига вправо при этом сигналы сдвига СДС и ССД будут равны единице. Информация из регистра РгБУФ DD11 будет сдвинута вправо на один символ меньше чем влево, в нашем случае 4. В этом случае вторая буква обрабатываемого слова будет первой в регистре РгСОБ DD13, процесс поиска вхождений будет продолжен. Четыре буквы из регистра РгПОД DD12 перейдут вначале в регистр РгБУФ DD11, а затем перепишутся в регистр РгСОБ DD13, если выбран режим работы устройства поиска и замена. Если выбран режим работы только поиска вхождений с запоминанием адресов в ОЗУ DD30, то в этом случае информация из регистра РгСОБ DD13 будет переписываться в регистр-буфер РгБУФ DD11. Режимы работы устройства будут формироваться управляющими сигналами: СУР, СИГ, СГУ из блока управления.

Блок 4 анализа и формирования сигналов сдвига содержит компаратор КОМ DD2, D - триггер Тр DD16, двухвходовый логический элемент И DD17 с инверсным входом, двухвходовый логический элемент И DD19, двухвходовый логический элемент И DD22, трехвходовый логический элемент И DD18 с инверсным входом, четырехвходовый элемент И DD21 с инверсными входами, трехвходовый элемент И DD27 с инверсным входом, электронный ключ DD24, двоичный счетчик Сч1 DD20, двоичный счетчик Сч2 DD23, двухвходовый элемент ИЛИ с инверсными входами DD26, двухвходовый элемент И DD25. Перед началом работы устройства двоичные счетчики DD20, DD23, а также D - триггер Тр установлены в нулевое состояние. Блок 4 анализа и формирования сигналов сдвига обрабатывает выходной сигнал ССР с компаратора КОМ DD2. Если сигнал ССР равен единице, то это означает что произошло совпадение двоичного кода символа вхождения с двоичным кодом буквы слова. В этом случае D - триггер Тр DD16 по приходу из блока 6 управления разрешающего сигнала СЗЩ, равного единице, устанавливается в единичное состояние. Логический элемент И DD19, выполняющий функцию электронного ключа, отпирается, тактовые импульсы ТАК из блока 6 управления поступают на суммирующий (+) вход двоичного счетчика Сч1 DD20. В двоичном счетчике Сч1 DD20 происходит суммирование тактовых импульсов, количество которых соответствует количеству совпадений в компараторе КОМ. На выходе двоичного счетчика Сч1 DD20 формируется двоичный код, соответствующий количеству положительных совпадений в компараторе. При каждом положительном совпадении в компараторе происходит формирование сигналов сдвига влево СДВ и СДС, равных нулю, и осуществляется сдвиг на один символ влево в регистрах РгВ DD7 блока 1 памяти вхождений и регистре РгСОБ DD13 блока 3 памяти слов и подстановок. Регистр РгБУФ DD11 блока памяти слов и подстановок записывает каждый символ, поступающий из регистра РгСОБ DD13, если сравнения не произошло. В случае обнаружения признака конца вхождения ПРКВ, равным единице, логических элементов И DD9 блока 1 памяти вхождений происходит определение адреса вхождения и записывание по соответствующему адресу записи в оперативно-запоминающее устройство ОЗУ DD30 блока 5 хранения адреса вхождений. Если признак конца слова не обнаружен ПРКС=0 (равен нулю), то предыдущее вхождение восстанавливается, т.е. переписывается заново из памяти вхождений и процесс поиска вхождений в слове продолжается (в случае наличие нескольких вхождений в одном слове). Если совпадений в компараторе КОМ не происходит, выходной сигнал ССР равен нулю, то формируется только сигнал СДС, равным нулю, и происходит сдвиг влево на одну позицию информации, находящейся в регистре слов РгСОБ DD13 блока 3 памяти слов и подстановок. При каждом сдвиге влево и отрицательном результате совпадения в компараторе из памяти слов ПС переписывается (дописывается) символ в регистр памяти слов РгСОБ DD13 блока 3 памяти слов и подстановок. Возможна ситуация в поисковой операции, когда был получен положительный результат сравнения символов, тогда формируется сдвиг влево на один разряд регистров РгСОБ DD.13 и РгПОД DD12. После сдвига получен второй раз положительный результат, третий и так далее, но признака конца вхождения еще нет. Допустим на n шаге получен отрицательный результат сравнения, а вхождение полностью не обнаружено. В этом случае D - триггер Тр DD16 был установлен в состояние единицу, т.е. на выходе элемента единица. На следующем этапе сигнал сравнения равен нулю ССР=0. На выходе логического элемента И DD17 будет сформирован единичный сигнал. Логический элемент И DD18 также будет открыт, прямоугольные импульсы из блока 6 управления ПРИ будут поступать на вычитающий вход двоичного счетчика СЧ1 DD20. Вычитание происходит до тех пор пока на выходе счетчика не будет двоичный код, равный единице. На положительный вход счетчика прямоугольные импульсы из блока 6 управления поступать не будут, т.к. логический элемент И DD19, выполняющий функцию электронного ключа будет заперт, установившимся в нулевое состояние D - триггером DD16. Логический элемент И DD21 выполняет роль дешифратора единицы. Выход этого элемента равен единице в случае получения на выходе счетчика Сч1 DD20 двоичного кода 0001. При всех других комбинациях на выходе данного элемента будет состояние нуль. При единице на выходе этого элемента логический элемент И DD18 запирается, т.к. единица поступает на инверсный вход. Прямоугольные импульсы на вычитающий вход счетчика Сч1 DD20 не поступают. Счетчик Сч1 DD20 обнуляется командой ОБН, поступающей из блока 6 управления. Логический элемент И DD27 выполняет роль своеобразного "клапана", формирующего количества сдвигов вправо регистра РгСОБ DD13. Каждый раз, когда происходит вычитание единицы из содержимого счетчика Сч1 DD20, происходит перемещение вправо информации из регистра РгБУФ DD11 в регистр РгСОБ DD13. Количество сдвигов вправо будет на один меньше, чем количество сдвигов влево. В нашем примере n-1. Вторая буква из полученной серии положительных сдвигов будет первой в регистре РгСОБ DD13. Вхождение будет заново переписано из памяти вхождений в регистр вхождений РгВ DD7. Процесс поиска будет продолжен. Логический элемент ИЛИ DD26 выполняет функцию распознавания режима работы. Как известно система работает в двух независимых режимах: определения вхождений с общими частями и определения вхождений и без (пересечений) общих частей. В первом случае признак режима работы РР будет равен нулю. Во втором случае признак РР равен единице. Логический элемент И DD25 выполняет функцию электронного ключа. В случае, когда признак работы системы РР равен нулю, на выходе элемента ИЛИ DD26 всегда будет единица. Электронный ключ DD25 будет открыт. Прямоугольные импульсы ПРИ из блока 6 управления работой блока через открытый ключ поступают на третий вход логического элемента И DD18. Этот режим характеризуется перемещением информации из регистра РгБУФ DD11 в регистр РгСОБ DD13 на n-1 разрядов, т.е. будет сформирован возврат информации, где n - количество положительных сдвигов, всякий раз, когда будет обнаружено вхождение в обрабатываемом слове при этом признак конца вхождения ПРКВ будет равен единице. Если режим работы системы будет установлен как поиск вхождений без общих частей, то в этом случае РР равен единице. В случае обнаружения вхождения, при этом признак вхождений ПРКВ равен так же единице. На выходе логического элемента ИЛИ DD26 установить нулевое значение. Электронный ключ И DD25 будет заперт. Прямоугольные импульсы ПРИ из блока 6 управления работой блока не будут поступать на вход элемента И DD18 (фиг.4). Информация из регистра РгБУФ DD11 не переместиться в регистр РгСОБ DD13. В этом случае будет сформирован сдвиг влево символов из регистра РгСОБ DD13 в регистр РгПОД DD12, т.е. возврата информации не будет (фиг.3).

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

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

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

Логические условия:X1: "УОО"Х6: "ТР"Х2:"ПУСК"Х7: "Сч1>"Х3: "ПЗ"Х8: "ПРКВ"Х4: "РР"Х9: "ПРКС"Х5: "ССР"Х10: "ПСП"

Операторы:У1: "СБРОС:=1"У24: ”Cч1=TAK”У2: "ПВ:=СУП"У25: "РгПОД=СИГ"У3: "ПВ:=АД"У26: "РгПОД:=ВДС"У4: "ПВ-ДН"У27: "СДВП:=0"У5: "ПС:=УРР"У28: "РгБУФ:=РгПОД"У6: "ПС:=АДЕ"У29: "РгБУФ:=ВДС"У7: "ПС:=ДНС"У30: "РгСОБ:=ДС"У8: "ППОД:=УПР"У31: "ССД:=0"У9: "ППОД:=АДС"У32: "СВП:=1"У10: "ППОД:=ДАН"У33: "Сч1:=ПРИ"У11: "РгСОБ:=СУР"У34: "СДС:=1"У12: "РгБУФ:=СГУ"У35: "ССД:=1"У13: "РгСОБ:=ДС"У36: "РгСОБ:=РгБУФ"У14: "РгВ=ДВ"У37: "РгВ:=СУ"У15: "ТР:=0"У38: "РгВ=ДВ"У16: "СДВ=0"У39: "ОБН:=1"У17: "СДС:=0"У40: "Сч1:=0"У18: "СРР:=0"У41: "РгПОД:=ПОД"У19: "СРР:=1"У42: "Кл:=СВА"У20: "СДС:=СВП"У43: "Сч/Зп:=0"У21: "ТР-ССР"У44: "ВК:=0"

У22: "СЗЩ:=1"У45: "ОЗУ:=АВХ"У23:"ТР:=1" 

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

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

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

3. Пом А., Агравал О. Быстродействующие системы памяти. - М.: Мир, 1987. - 264 cл., ил.

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

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

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

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

8. А.С. СССР № 1837327 (аналог).

9. А.С. СССР № 1667097 (аналог).

10. А.С. СССР № 1277091 (аналог).

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

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