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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Если образец имеет повторение своих начальных фрагментов, то его форма записи будет иметь вид:
S = {G}F, (1)
где S - образец:
G - начальный повторяющийся фрагмент;
F - собственное окончание образца;
{} - обозначение операции "итерация".

Очевидно, что при существовании итерации фрагмента в середине образца при следующей форме его записи:
S = G{H}F, (2)
не влечет за собой пропуска позиции вхождения образца в обрабатываемое слово. Также безопасной структурой образца является следующая его форма представления:
S = G{F}, (3)
В случае общего положения структура образца может принимать вид
S = {G}H{F}, (4)
Вместе с тем существует еще одна структура образца, которая порождает необходимость в выполнении отступа в пространстве обрабатываемого слова с целью предотвращения аварийного пропуска позиции вхождения. Такая структура образца имеет вид:
S = GFGP, (5)
т.е. начальный фрагмент образца входит в его собственную структуру более одного раза.

В выражениях (1), (2), (3), (4) и (5) S, G, F, Н и Р произвольные непустые слова.

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

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

Адрес ячейки может определяться либо ее местоположением в пространстве, как это имеет место в статических запоминающих устройствах, либо ее положением (очередностью) во времени - в динамических устройствах. Соответственно различают два способа поиска: места (или S-поиск) и времени (или Т-поиск).

При S-поиске имеется возможность произвольного обращения за одинаковое время к любой запоминающей ячейке. При Т-поиске после обращения к некоторой k-й ячейке наименьшее время требуется для обращения к (k+1)-й ячейке и т.д. Такой характер обращения называют последовательным.

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

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

Параллельная система информационного поиска состоит из однотипных блоков поиска вхождений. Эти блоки имеют одинаковую структуру, одинаковые алгоритмы поиска вхождений. Достаточно описать работу одного блока, другие блоки работают аналогично описанному. Алгоритм функционирования блока поиска вхождений системы заключается в следующем. В сдвигающем регистре находится вхождение (цепочка символов). В ассоциативно-запоминающем устройстве (АЗУ) записываются слова-образцы. Количество слов зависит от объема АЗУ. Режим работы АЗУ устанавливается на равенство входных величин. Задача системы заключается в определении вхождений в обрабатываемых словах. Если вхождение найдено, то ее адрес записывается в оперативно-запоминающее устройство (ОЗУ) и формируется сдвиг регистра вправо на один разряд, предполагая, что вхождение начинается с вторых букв обрабатываемых слов. Если вхождение не найдено, то также в сдвигающем регистре формируется сигнал сдвига на один разряд вправо. Вхождение, находящиеся в регистре сдвига, постоянно сдвигается вправо на один разряд по приходу управляющих сигналов из блока управления. Сравнение в системе происходит параллельно и пофрагментно. Длина фрагмента определяется количеством символов вхождения. Все символы вхождения сравниваются по совпадению сразу со всеми обрабатывающими слова. Следует сказать, что предлагаемая система осуществляет поиск фрагментов в текстовой информации. Параллельная информационно-поисковая система работает в двух форматах. Первый формат работы заключается в определении вхождений, имеющих общие части. Это означает, что предыдущие вхождение и последующие имеют общие части. Например, вхождением являются символы ТТТ. Обрабатываемым словом-образцом является слово ТТТТТИМС. При первом режиме работы результатом является три вхождения, в ОЗУ будут записаны три адреса. Первый адрес - с первого по третий, второй - со второго по четвертый, третий - с третьего по пятый. Работу системы при первом формате наглядно иллюстрирует схема 1 (см. в конце описания схемы 1 и 2).

В результате определяем третий адрес.

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

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

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

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

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

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

На фиг.6 изображена функциональная схема канала передачи информации.

На фиг. 7 представлен вариант технической реализации блока оперативно-запоминающего устройства.

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

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

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

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

Параллельная система информационного поиска (фиг. 1) содержит блок 1 памяти вхождений, блок 2 памяти слов, n-блоков определения вхождений, блок управления. Блок определения вхождений (фиг. 3) содержит блок 9 регистра сдвига и определения адреса, ассоциативно-запоминающее устройство 10, блок 11 блокировки, блок 12 хранения адреса вхождений, блок 13 управления работой блока определения вхождений.

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

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

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

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

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

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

9. КСМ - команда, определяющая количество символов в вхождении, поступающая из блока БРСА на вход двоичного счетчика СчРг канала передачи информации.

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

11. СОВ - сигнал результата сравнения в АЗУ между входными величинами.

12. ВХВ - данные (двоичные коды букв) блока памяти вхождений.

13. АД - команда адресов вхождений, поступающая с выхода шинного формирователя.

14. АРР - выходная информация, поступающая с выходов электронных ключей.

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

16. УСО - команда обнуления двоичного счетчика СчАд блока регистра сдвига и определения адреса.

17. УПР - сигналы управления оперативно-запоминающих устройств (обнуление, выбор кристалла, считывание/запись, тактовые импульсы).

18. СЗЩ - команда разрешения записи в триггер Тр D.29 выходного сигнала с соответствующих выходов АЗУ.

19. КН1 - команда константа единицы, поступающая из блока управления работой блока на входы шинных формирователей.

20. СИМ - команды синхронизации двоичных счетчиков СчРг DD.32 каналов передачи информации.

21. СБР - команда обнуления двоичного счетчика СчРг DD.32 канала передачи информации.

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

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

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

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

26. РАС - сигнал определения нулевого состояния двоичного счетчика СчК.

27. СУР - сигналы управления работой блока блокировки (сигналы защелки, синхроимпульсы, тактовые импульсы, сигналы обнуления).

28. КЛБ - информационный сигнал, соответствующий количеству символов в вхождении.

29. ТАИ - тактовые импульсы, поступающие на вычитающий вход двоичного счетчика СчК.

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

31. АРД - информационный сигнал, формирующийся на выходе двоичного счетчика СчАд DD.19, соответствующий количеству сдвигов вправо регистра сдвига РгВх.

32. ПКС - команда признака конца сдвига, определяющая завершение подачи сигналов сдвигов вправо на вход регистра вхождений РгВх.

33. СОБ - команда обнуления двоичного счетчика СчК DD.33.

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

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

36. СБР - команда обнуления двоичного счетчика СчСт DD.35.

37. СБО - команда обнуления двоичного счетчика СчСтр DD.36.

38. Сч/Зп - команда считывания/записи оперативно-запоминающего устройства.

39. ВК - команда выбора кристалла оперативно-запоминающего устройства.

40. ВХД - выходной информационный сигнал, поступающий с выхода регистра вхождений РгВх (двоичный код вхождений).

41. W/R - сигнал считывания/записи АЗУ.

42. МО - 0-й входной сигнал маски в АЗУ.

43. M1 - 1-й входной сигнал маски в АЗУ.

44. М2 - 2-й входной сигнал маски в АЗУ.

45. М3 - 3-й входной сигнал маски в АЗУ.

46. СД - сигнал дешифрации, выходящий из блока управления.

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

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

49. ВСЛ - информационный сигнал, соответствующий словам-образцам, поступающий из блока управления.

50. ACT - адреса столбцов, поступающие на вход блока памяти вхождений.

51. АСР - адреса строк, поступающие на вход блока памяти вхождений.

52. AC - адреса столбцов, поступающие на вход блока памяти слов.

53. АР - адреса строк, поступающие на вход блока памяти слов.

54. ВК1 - сигнал разрешения выбора кристалла блока памяти вхождений.

55. ВК2 - сигнал разрешения выбора кристалла блока памяти слов.

56. Сч/Зп1 - сигнал считывание/записи блока памяти вхождений.

57. Сч/Зп2 - сигнал считывание/записи блока памяти слов.

58. СБРОС - сигнал обнуления всех элементов системы.

59. ПУСК - сигнал начала работы всех элементов системы.

Работа алгоритма блока управления работы блока (БУРБ).

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

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

В блоке 3 по команде "СДi:=1" блок поиска вхождений получает сигнал разрешения на работу из блока управления системы.

В блоках 4, 5 алгоритма происходит запись из памяти слов ПС в ассоциативно-запоминающее устройство АЗУ системы информации в виде нескольких слов текста. Из памяти вхождений ПВ осуществляется загрузка в регистр вхождений РгВх символов для осуществления поисковых операций.

В блоке 4 алгоритма происходит разрешение записи и запись информации в ассоциативно-запоминающее устройство системы. По сигналу W/Ri:=0 осуществляется запись в i-е АЗУ информации, т.е. слов для дальнейшей обработки. По командам: АЗУi: = ВХДi происходит подача из регистра вхождений РгВх блока регистра сдвига и определения адреса очередного вхождения на вход ассоциативно-запоминающего устройства АЗУ. По команде АЗУi:=ОСЛi осуществляется подача слов из памяти слов в АЗУ для проведения операций сравнения (фиг.3, 4). На управляющий вход шинного формирователя ШФi (фиг.6) канала передачи информации подается значение константы, равной единицы КН1:=1, для осуществления передачи информации через шинный формирователь.

В блоке 5 алгоритма по команде РгВхi:=СУПi происходит подача сигналов управления на вход регистра РгВх для разрешения записи в этот регистр блока БРСА информации (фиг.3). По команде PrBxi:=BXBi происходит прием очередного вхождения в регистр вхождений PrBxi. По команде СчРгi:=КСМi происходит подача прямоугольных импульсов на суммирующий вход двоичного счетчика СчРг канала передачи информации КНП1 (фиг.6). По этой команде осуществляется подсчет количества символов в вхождении. При каждом считывании буквы из памяти вхождений ПВ после очередного синхроимпульса, поступающего на вход памяти вхождений из блока управления определения вхождений, происходит подсчет количество прямоугольных импульсов. В счетчике СчРг DD.32 формируется двоичный код, соответствующий количеству букв в вхождении. По команде СчКi:=КЛБi на входы двоичного счетчика-регистра СчК DD.33 поступает информация, соответствующая количеству символов (фиг.6).

В блоках 6 - 11 алгоритма сформирован цикл записи информации в БОЗУi системы в случае обнаружения совпадения вхождения с фрагментами слов в АЗУi и дальнейшие действия системы в случае отсутствия совпадения.

В блоке 6 алгоритма происходит анализ сигнала сравнения COBi, поступившего с выхода ассоциативно-запоминающего устройства (фиг.5, 6). Если COBi= 1, то произошло совпадение вхождения, находящегося в регистре РгВх, с фрагментом одной или нескольких строк АЗУ. Это означает, что вхождение найдено в каком-то слове или словах текста и после этого необходимо записать адрес или адреса вхождения (вхождений) по соответствующему (соответствующим) адресу (адресам) записи в оперативно-запоминающие устройства системы. Если совпадения не произошло, то процесс поиска вхождений продолжается. По алгоритму в этом случае осуществляется переход на блок 10.

В блоке 7 алгоритма происходит процесс формирования сигналов из блока управления (БУРБ) для записи информации в ОЗУi системы. По команде ШФi:=АРРi на вход i- ого шинного формирователя поступает адрес вхождения. По команде СЗЩi: = 1 происходит подача из блока управления (БУРБ) разрешающего сигнала, равного единице, на вход триггера Трi для разрешения в него записи (фиг.6). Триггер Tpi устанавливается в единичное состояние соответствующего канала передачи информации по команде Tpi:=l (фиг.6). Сигнал разрешения для записи информации поступает из блока управления (БУРБ) BKi:=0, Сч/Зпi:=0. На управляющие входы поступают нулевые значения что соответствует режиму записи в блок ОЗУi системы входной информации т.е. адреса вхождения (фиг.7).

В блоке 8 алгоритма по командам: БОЗУi:=Ад CTi, БОЗУi:=Ад CTPi происходит подача на входы i-го блока оперативно-запоминающего устройства адресов строк и адресов столбцов с выходов двоичных счетчиков СчСт и СчСтр (фиг.7).

В блоке 9 алгоритма по команде БОЗУi:=АДРi происходит запись в блок ОЗУi системы соответствующего адреса вхождения.

В блоке 10 алгоритма по команде РгВхi:=СДПi на вход регистра вхождений PrBxi поступают сигналы сдвига СДПi. Вся информация в регистре при этом сдвигается на один разряд вправо. По команде СчАдi:=ГИi происходит подача на вход логического элемента И DD.18 из блока управления (БУРБ) прямоугольных тактовых импульсов (фиг.4).

В блоке 11 алгоритма по команде СЗЩi:=1 происходит подача из блока управления (БУРБ) разрешающего сигнала, равного единице, на вход триггера Tpi для разрешения в него записи. Триггер Tpi устанавливается в нулевое состояние соответствующего канала передачи информации по команде Tpi:=0 (фиг.6). С выхода блока 11 осуществляется переход на блок 10 алгоритма.

В блоке 12 алгоритма происходит анализ признака завершения подачи сигналов сдвига вправо на один разряд на вход регистра вхождений РгВх. Если признак завершения подачи сигналов - ПКСi равен единице, то это означает, что вхождение в регистре вхождений находится в самом правом крайнем положении. При этом процесс сравнения данного вхождения со словами текста АЗУ завершен. В этом случае осуществляется переход по алгоритму на блок 20. Если признак завершения подачи сигналов сдвига равен нулю, то работа системы продолжается по определению в словах данного вхождения.

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

В блоке 14 алгоритма по команде РгВхi:=СДПi на вход регистра вхождений РгВх (фиг. 4) подаются сигналы сдвига вправо на один разряд. В этом случае информация регистра перемещается на один разряд вправо.

В блоке 15 алгоритма по команде СчКi:=КЛБi на счетчик-регистр СчК на входы предварительной установки поступает информация, соответствующая количеству символов в вхождении. Информация поступает с выхода двоичного счетчика СчРг (фиг. 6). По команде СчКi: =ТАИi на вычитающий вход i-ого счетчика-регистра поступают тактовые импульсы из блока управления (БУРБ). Операция вычитания будет продолжаться до тех пор, пока на выходе этого счетчика-регистра СчК не будет получено значение нуля (фиг.6). По команде PACi: = 0 выходной сигнал с логического элемента ИЛИ DD.34 устанавливается в нулевое значение.

В блоке 16 алгоритма осуществляется анализ сигнала РАСi-выхода с логического элемента ИЛИ DD.34. Если сигнал РАСi равен нулю, то происходит переход на блок 17 алгоритма. В этом случае в счетчике СчК имеется информация и процесс вычитания из счетчика продолжается. Если сигнал РАСi равен единице, то осуществляется переход на блок 18 алгоритма. В этом случае значение двоичного счетчика СчК принимает значение нуля (фиг.6).

В блоке 17 алгоритма по команде РгВхi:=СДПi на вход регистра вхождений РгВх подаются сигналы сдвига вправо на один разряд. В этом случае информация регистра перемещается на один разряд вправо. По команде СчКi:=ТАИi на вычитающий вход i-ого счетчика-регистра поступают тактовые импульсы из блока управления (БУРБ). Операция вычитания будет продолжаться до тех пор, пока на выходе этого счетчика-регистра СчК не будет получено значение нуля (фиг.6). По команде АДРi: на выходе i-ого шинного формирователя ШФ DD.28 будет установлено третье высокоимпедансное состояние. При этом на выходе устанавливается большое сопротивление, данный шинный формирователь отключен от цепи передачи информации на вход БОЗУi. Включение шинного формирователя и восстановление цепи произойдет при сигнале РАСi, равным единичному значению. С выхода этого блока формируется переход на блок 16 алгоритма. Блоки 16 и 17 образуют цикл.

В блоке 18 алгоритма по команде ШФi:=АРРi происходит подача информационного сигнала с выхода i-го электронного ключа Кл DD.27 на вход i-го шинного формирователя ШФ DD.28 (фиг.6). В этом случае цепь передачи информации восстановлена. Процесс поиска вхождений продолжается.

В блоке 19 алгоритма по команде СчКi:=КЛБi на счетчик-регистр СчК на входы предварительной установки поступает информация, соответствующая количеству символов в вхождении. Информация поступает с выхода двоичного счетчика СчРг (фиг.6). По команде PACi:=0 выходной сигнал с логического элемента ИЛИ DD.34 устанавливается в нулевое значение. При этом осуществляется переход на блок 6 алгоритма.

В блоке 20 алгоритма происходит анализ признака конца работы системы КРС. Если КРС= НЕТ, то процесс поиска будет продолжен и при этом осуществляется переход на блок 4 алгоритма. Если обнаружен признак конца слов КРС= ДА, то осуществляется переход на блок 21 алгоритма.

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

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

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

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

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

В блоке 5 алгоритма происходит запись вхождений в ОЗУ блока памяти вхождений. По командам: ВК1:=0, Сч/Зп1:=0 на управляющие входы оперативно-запоминающего устройства из блока управления подаются сигналы управления: сигнал выбора кристалла ВК1 и сигнал считывание/запись Сч/Зп1, равными нулю. Эти сигналы соответствуют режимам выбора микросхемы и режиму записи в ОЗУ информации. Сигналы управления оперативно-запоминающего устройства ОЗУ DD.37 считывание/запись и выбора кристалла соответственно при записи принимают значения Сч/Зп1= 0, ВК1=0. Выходом ОЗУ1 является информационный сигнал ДАВ1 (фиг. 7). По сигналу ПВ:=АСР на адресный вход строк ОЗУ поступает двоичный код, формирующий адреса строк для записи входного сигнала в ОЗУ. По сигналу ПВ: = АСТ адресный вход столбцов ОЗУ поступает двоичный код, формирующий адреса столбцов для записи входного сигнала в ОЗУ. По команде ПВ:=ВВХ на входную шину ОЗУ подается входная информация из блока управления т.е. вхождения.

В блоке 6 алгоритма происходит запись вхождений в ОЗУ блока памяти слов. По командам: ВК2:=0, Сч/Зп2:=0 на управляющие входы оперативно-запоминающего устройства из блока управления подаются сигналы управления: сигнал выбора кристалла ВК2 и сигнал считывание/запись Сч/Зп2, равными нулю. Эти сигналы соответствуют режимам выбора микросхемы и режиму записи в ОЗУ информации. По сигналу ПС: =АС на адресный вход строк ОЗУ поступает двоичный код, формирующий адреса строк для записи входного сигнала в ОЗУ. По сигналу ПС:=АР адресный вход столбцов ОЗУ поступает двоичный код, формирующий адреса столбцов для записи входного сигнала в ОЗУ. По команде ПС:=ВСЛ на входную шину ОЗУ подается входная информация из блока управления т.е. слова-образцы.

В блоке 7 алгоритма счетчики i, j, k принимают единичные значения. Счетчик i изменяет свое значение от единицы до n, что соответствует количеству блоков определения вхождений (БОПВ). Счетчик j изменяется от единицы до определения признака конца слов (ПРКС), что соответствует количеству слов-образцов. Счетчик k изменит свое значение от единицы до определения признака конца вхождений (ПРКВ), что соответствует количеству вхождений. По командам: i:=1, j:=1, k:=1 счетчики устанавливаются в начальные единичные значения.

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

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

В блоке 9 алгоритма по команде Б0ПВi:=СДi происходит подача разрешающего сигнала СДi на управляющие входы блоков определения вхождений на осуществление поисковой операции. Эта команда соответствует команде ПУСК конкретному блоку. По команде БОПВi: =РРi происходит подача управляющего сигнала РР - выбора режима работы БОПВ, на вход блока определения вхождений. Определения вхождений, имеющих общие части и определение вхождений, не имеющих общих частей.

В блоке 10 алгоритма по команде: БОПВi:=ВХВj происходит подача очередного вхождения из блока памяти вхождений на один из блоков определения вхождений. По команде БОПВi:=ОСЛk осуществляется процесс записи блоком определения вхождений очередных массивов слов из блока памяти слов для проведения поисковой операции.

В блоке 11 алгоритма по команде i:=i+1 происходит изменение счетчика i на единицу.

В блоке 12 алгоритма по команде j:=j+l происходит изменение счетчика j на единицу.

В блоке 13 алгоритма по команде k:=k+l происходит изменение счетчика k на единицу. При этом осуществляется переход выходов блоков 12 и 13 на вход блока 10 алгоритма.

В блоке 14 алгоритма происходит анализ признака конца слов ПРКС (признаком является двоичный код, равный всем единицам 11...1). Если ПРКС= НЕТ, то процесс поиска будет продолжен и при этом осуществляется переход на блок 12 алгоритма. Если обнаружен признак конца слов ПРКC=ДА, то осуществляется переход на блок 15 алгоритма. В этом случае все слова, находящиеся в памяти слов, просмотрены.

В блоке 15 алгоритма происходит анализ признака конца вхождения ПРКВ (фиг.2). Если ПРКВ=ДА, то в памяти вхождений обнаружен двоичный код 11..1. В этом случае все вхождения, находящиеся в памяти вхождений, просмотрены. Процесс поиска заканчивается. В этом случае осуществляется переход на блок 8 алгоритма. Если ПРКВ=НЕТ, то это означает, что процесс поиска продолжается, не все вхождения еще просмотрены, при этом осуществляется переход на 13 блок алгоритма.

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

Блок 16 алгоритма является конечным блок-схемой алгоритма.

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

Внешние управляющие сигналы "Сброс" и "Пуск" и поступают в блок 6 управления.

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

Блок 1 памяти вхождений содержит оперативно-запоминающее устройство (ОЗУ) - память вхождений DD.7. (фиг.2). На вход этого блока поступают сигналы из блока управления для осуществления операций выбора кристалла ВК1, операции считывания/записи Сч/Зп1, а также адреса строк и столбцов ACT и АСР. Входными данными ОЗУ памяти вхождений являются вхождения ВВХ, которые поступают из блока управления. Вхождения записываются заранее перед осуществлением операции поиска. При считывании вхождений с выхода памяти вхождений формируется информационный сигнал ВХВ, соответствующий двоичному коду каждой буквы вхождения. Выходным сигналом является управляющая команда - соответствующая признаку конца вхождения ПРКВ. Этот сигнал поступает на вход блока управления. Память вхождений ПВ служит для хранения цепочки символов-вхождений.

Блок 2 памяти слов содержит оперативно-запоминающее устройство (ОЗУ)- память слов DD. 8. (фиг.2). На вход этого блока поступают сигналы из блока управления для осуществления операций выбора кристалла ВК2, операции считывания/записи Сч/Зп2, а также адреса строк и столбцов АС и АР. Входными данными ОЗУ памяти слов являются слова-образцы ВСЛ, которые поступают из блока управления. Слова записываются заранее перед осуществлением операции поиска. При считывании слов с выхода памяти слов формируется информационный сигнал ОСЛ, соответствующий двоичному коду каждой буквы слова. Выходным сигналом является управляющая команда - соответствующая признаку конца слова ПРКС. Этот сигнал поступает на вход блока управления. Память слов ПС служит для хранения слов-образцов.

Блок 3 определения вхождений БОПВ состоит из блока регистра сдвига и определения адреса БРСА. ассоциативно-запоминающего устройства АЗУ, блока блокировки БЛБ, блока хранения адреса вхождений БХАВ и блока управления работой блока БУРБ (фиг.3). Блок регистра сдвига и определения адреса БРСА состоит из реверсивного регистра сдвига вхождений РгВх DD.14, двоичного счетчика СчАд DD.19, логического элемента ИЛИ DD.15, логического элемента И DD.18, логического элемента ИЛИ DD.16, логического элемента DD.17. (фиг.4). На вход этого блока поступают информационные сигналы из блока памяти вхождений БПВ - ВХВ1, из блока управления работой блока БУРБ - сигналы управления СУП1, а также управляющие сигналы: сигнал сдвига вправо СДП1, прямоугольные импульсы ГИ1, сигнал синхронизации СИН1, сигнал установки в нуль УС01 из блока управления работой блока БУРБ, выходным управляющим сигналом блока БРСА является сигнал-признак конца сдвига ПКС1, выходными информационными сигналами блока являются сигналы: адреса АД1 и сигнал ВХД1 - вхождение. Работа этого блока заключается в следующем: осуществление операций сдвига вправо информации в регистре сдвига РгВх, определении сигнала признака конца сдвига ПКС, формировании адреса вхождения АД1. На вход регистра вхождения РгВх DD.14 поступает информационный сигнал управления СУП1 из блока управления работой блока БУРБ. По приходу этого сигнала осуществляются операции: обнуления регистра, разрешение записи информации в регистр, подача синхроимпульсов. Перед началом работы системы в регистр вхождений РгВх записывается вхождение ВХВ1 - цепочка символов. Двоичный счетчик адреса СчАд DD.19 обнулен сигналом установки в 0 - УС01. Управляющий сигнал ПКС1 принимает значение нуля. Выходом регистра вхождений является информационный сигнал ВХД1, который поступает на вход ассоциативно-запоминающего устройства АЗУ. После загрузки информации в регистр совершается операция сравнения на равенство в АЗУ системы. Если сравнение дало положительный результат, то происходит запись адреса в соответствующий i-й блок ОЗУ данного блока определения вхождений БОПВ1. Затем на вход регистра вхождений поступает сигнал сдвига вправо на один разряд - СДП1. Информация регистра РгВх перемещается на один разряд вправо. После этого в АЗУ также осуществляется операция сравнения на равенство. Сигнал сдвига вправо СДП1 поступает на управляющий вход логического элемента И DD. 18. На информационный вход указанного элемента поступают прямоугольные импульсы ГИ1 из блока управления работой блока. Выход элемента И DD.18 соединен с суммирующим входом двоичного счетчика СчАд DD.19, который подсчитывает количество прямоугольных импульсов. При поступлении очередного сигнала сдвига СДП1 через схему И на суммирующий вход счетчика поступают прямоугольные импульсы. По приходу синхроимпульса СИН1 происходит суммирование прямоугольных импульсов в двоичном счетчике. Счетчик подсчитывает количество импульсов ГИ1. На выходе этого счетчика формируется двоичный код, соответствующий количеству сдвига вправо информации в регистре вхождений (фиг.4). В случае равенства входных величин в АЗУ в счетчике будет сформирован адрес вхождения - АРД1. Полученный адрес записывается в соответствующее ОЗУ системы. После операций сдвига информация в регистре перемещается вправо, при достижении крайне правого положения вхождения в регистре происходит установка логического элемента ИЛИ DD.15 в единичное состояние. Это означает, что первый цикл поиска вхождений завершен. Логический элемент ИЛИ DD.16 определяет считывание очередного символа из ОЗУ для подсчета количества всех символов в вхождении. На выходе этого элемента формируется единица, если на входе будет двоичный код буквы. Нулевое состояние на выходе этого элемента означает завершение считывания символов очередного вхождения. Выход этого элемента поступает на управляющий вход логического элемента И DD.17, который работает в режиме электронного ключа. На второй вход элемента И поступают прямоугольные импульсы ГТИ1 из блока управления работой блока БУРБ. Количество импульсов, поступивших на вход логического элемента И DD.17, соответствует количеству букв в вхождении. Считывание каждого символа из памяти вхождений происходит после подачи синхроимпульса из блока управления работой блока (фиг.4). Ассоциативно-запоминающее устройство АЗУ 10 представляет собой элемент памяти, в котором реализуются несколько функций: поиск максимального значения, поиск минимального значения, сравнение на равенство и так далее. В представленной системе применяется только один режим работы АЗУ - сравнение на равенство входных величин. Этот режим обеспечивается входными сигналами W/R1, М01, M11, M21, М31 [7,8,9]. На вход АЗУ поступает информация из регистра вхождений РгВх - вхождение (цепочка символов). В памяти перед поиском происходит загрузка слов, с которыми необходимо произвести операцию на сравнение с вхождением. Количество слов зависит от емкости АЗУ. Предположим, что их будет - m. Количество разрядов в каждой строке исчисляется - k. Операция сравнение в АЗУ происходит по столбцам, сразу во всех строках. Все символы вхождения сравниваются с буквами слов-образцов по столбцам. Если обнаружено равенство хотя бы в одной строке, при этом выходной сигнал COBi будет равен единице, то в блок ОЗУi блока 12 хранения вхождений записывается адрес вхождения, т.е. место положение самого вхождения в регистре вхождений. Затем формируется сдвиг информации в регистре вхождений на один разряд вправо. После этого в АЗУ также реализуется операция: сравнение на равенство. Если обнаружено совпадение с входной величиной, то адрес вхождения записывается в соответствующий блок ОЗУi. Процесс поиска вхождения в обрабатываемых словах продолжается до тех пор, пока информация в регистре не переместится в самое крайнее положение в регистре вхождений. Выходные сигналы COBi с выхода АЗУ поступают на вход блока 11 блокировки (фиг.5, 13). Блок 11 блокировки состоит из n каналов передачи информации КНПi. На входы всех каналов поступает управляющий сигнал, определяющий режим работы РР1. На входы каналов поступают сигналы управления СУРi. Структура сигнала СУР1 представлена на фиг.6. В состав информационного сигнала СУР1 входят управляющие сигналы СЗЩ1, СИМ1, СБР1, ТАИ1, СОБ1, КН1, КСМ1. Каналы передачи информации обеспечивают 2 режима работы системы и передают информацию от АЗУ к блокам ОЗУ (фиг.5). На фиг. 6 представлен вариант технической реализации канала передачи информации КНП1. В состав первого канала входят: электронный ключ Кл DD.27, шинный формирователь ШФ DD. 28, Д-триггер Тр DD.29, логический элемент с инверсным входом И DD. 30, логический элемент И DD.31, двоичный счетчик СчРг DD.32, счетчик-регистр СчК DD.33, логический элемент ИЛИ-НЕ DD.34. Вначале работы системы двоичный счетчик СчРг DD.32 обнулен управляющим сигналом СБР1, поступающим из блока управления работой блока. Счетчик-регистр СчК DD.33 также обнулен управляющим сигналом СОБ1, поступающим из блока управления работой блока. Д-триггер Тр DD.29 находится первоначально в нулевом состоянии. Управляющий сигнал КН1 всегда находится в единичном состоянии, что обеспечивает рабочий режим шинного формирователя ШФ DD.28 во время всей работы системы. Поисковая система работает в двух режимах. При первом режиме, когда вхождения имеют общие части, управляющий сигнал РР1 равен нулю. Логический элемент И DD.31 принимает значения нуля. Шинный формирователь всегда открыт для передачи информации. Ели в АЗУ системы произошло сравнение на равенство, т.е. обнаружено вхождение в первой строке, то в этом случае электронный ключ Кл DD. 27 управляющим сигналом СОВ1, равным единице, будет открыт. Входная информация АРД1 через открытый ключ Кл. DD.27 поступит на вход шинного формирователя ШФ DD. 28. Входная информация АРР1, поступающая на вход шинного формирователя, через открытый элемент поступает на вход блока ОЗУ1 (фиг.6). В блоке ОЗУ1 по сформированным адресам входная информация АДР1 записывается в оперативно-запоминающее устройство ОЗУ1. По описанному выше алгоритму работают все каналы передачи информации КНПi поисковой системы при установлении первого режима работы. В случае положительного результата сравнения на равенство в АЗУ записывается адрес вхождения в ОЗУi. Второй режим работы устанавливается управляющим сигналом РР1, равным единице. Работа поисковой системы в этом режиме заключается в следующем: в двоичном счетчике СчРг DD.32 (фиг. 6) формируется двоичный код, соответствующий количеству символов в вхождении. На суммирующий вход счетчика поступают прямоугольные импульсы КСМ1. Один прямоугольный импульс поступает на вход счетчика при считывании одного символа вхождения из памяти вхождений. В результате считывания всех символов очередного вхождения на выходе счетчика будет сформирован двоичный код КЛБ1, эквивалентный количеству букв в вхождении. Этот код поступает на входы всех счетчиков-регистров блоков КНП1. В нашем случае на вход СчК DD.33 (фиг.6) поступает код КЛБ1 и записывается в счетчик-регистр. На выходе счетчика-регистра СчК будет сформирован двоичный код, соответствующий количеству символов в вхождении. На входе логического элемента ИЛИ-НЕ DD.34 имеется хотя бы одна единица, на выходе элемента управляющий сигнал РАС1 равен нулю. Этот сигнал поступает на инверсный вход логического элемента И DD.30. Если выходной сигнал из АЗУ СОВ1 равен единице, то по приходу сигнала "защелки" СЗЩ1 на вход триггера Тр DD.29 из блока управления работой блока БУРБ, триггер устанавливается в состояние единицы. Электронный ключ Кл DD.27 при отпирающем сигнале СОВ1 "открыт". Информация через ключ проходит на вход шинного формирователя ШФ DD.28. Шинный формирователь на этот момент "открыт", выходной сигнал АД1 при этом поступает на вход блока ОЗУ1. В результате этой операции адрес вхождения АРД1 через "открытые" электронный ключ и шинный формирователь будет записан в блок ОЗУ1. После записи на выходе логического элемента И DD.30 будет единичное состояние. На выходе логического элемента И DD.31 также будет единица. Эта единица установит шинный формирователь ШФ DD. 28 в третье импедансное состояние (практически разомкнуто) [9,10]. В дальнейшем это состояние шинного формирователя будем называть цепь "разомкнута". Второй режим работы системы характеризуется тем, что найденные вхождения не имеют общих частей в словах-образцах. Допустим в примере вхождение имеет пять символов. Это вхождение было обнаружено в первой строке АЗУ. По алгоритму работы системы при обнаружении вхождения адрес будет записан в блок ОЗУ1. После записи адреса необходимо "отключить" цепь передачи информации от электронного ключа к блоку ОЗУ1. Это состояние формируется подачей на второй вход шинного формирователя единичного состояния. Цепь передачи информации восстанавливается после того, как будет сделано s сдвигов вправо вхождения, где s - количество символов в вхождении. В нашем примере надо сделать пять сдвигов вправо, чтобы первая буква вхождения совместилась с шестой буквой слова-образца. В этом случае цепь передачи информации восстанавливается, процесс поиска на равенство в АЗУ продолжается. Цепь восстанавливается при подачи на второй управляющий сигнал шинного формирователя нуля. В регистре-счетчике СчК DD.33 записано количество символов в вхождении. На вычитающий вход этого элемента поступает прямоугольный сигнал ТАИ1 из блока управления работой блока БУРБ. Каждый раз, как только происходит сдвиг информации вправо на один разряд в регистре вхождений, происходит подача сигнала ТАИ1 на вычитающий вход счетчика-регистра СчК DD.33. Как только на выходе счетчика-регистра СчК DD.33 будет получен нуль, то на выходе логического элемента ИЛИ DD.34 будет единичное состояние. Сигнал РАС1 принимает значение единицы. В результате этого на выходе логического элемента И DD.30 будет нуль. На выходе логического элемента И DD.31 также будет нуль. На вход шинного формирователя ШФ подается значение нуля, что формирует рабочее состояние этого элемента. В результате этого шинный формирователь ШФ DD.28 будет "открыт" (фиг. 6). Цепь передачи информации восстановится. После этого в счетчик-регистр СчК DD.33 вновь будет записана информация о количестве символов в вхождении из счетчика СчРг DD.32. Процесс сравнения на равенство входных величин будет продолжен, но уже с определенной позиции, на которой находится вхождение в регистре вхождений в результате сдвигов. На фиг. 6 представлен один вариант технической реализации канала передачи информации КНП1. Остальные каналы КНПi имеют аналогичную структуру. Работают они по такому же описанному выше алгоритму. Блок 12 хранения адреса вхождений БХАВ содержит блоки оперативно-запоминающих устройств БОЗУn. Количество блоков БОЗУ зависит от количества строк в АЗУ. Каждый канал передачи информации КНПi имеет свой блок оперативно-запоминающих устройств БОЗУ. Каждый блок БОЗУi работает совместно с двумя двоичными счетчиками. Эти счетчики формируют адреса столбцов и адреса строк. По этим адресам информация записывается в оперативно-запоминающее устройство. На фиг.7 представлен вариант технической реализации первого блока БОЗУ1 и показаны связи с двоичными счетчиками СсСт и СчСтр. Все остальные блоки БОЗУ имеют аналогичную структуру. На фиг.7 представлено оперативно-запоминающее устройство ОЗУ1 DD37, двоичный счетчик, формирующий адреса столбцов ОЗУ - СчСт DD35, двоичный счетчик, формирующий адреса строк ОЗУ - СчСтр DD36. Двоичные счетчики вначале работы устройства обнулены управляющими сигналами СБР1, СБ01, поступающие из блока управления работой блока БУРБ (фиг.3, 7). На входы счетчиков поступают прямоугольные импульсы ГИ1, ТИ1 из блока управления работой блока. Счетчики формируют адреса строк и столбцов, по которым будут записаны адреса вхождений, поступающие на вход оперативно-запоминающего устройства ОЗУ DD37. Входным сигналом АДР1 является информация об адресе обнаруженного вхождения системой. Входной сигнал поступает на входную шину ШВх1 ОЗУ1. Сигналы управления оперативно-запоминающего устройства ОЗУ DD37 выбора кристалла и считывания/запись соответственно при записи принимают значения ВК1=0, Сч/Зп1=0. Выходом ОЗУ1 является информационный сигнал ДАВ1 (фиг.7).

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

Блок 13 управления работой блока БУРБ (фиг.3) синтезируется на основе ГСА алгоритма управления блоком (фиг.3) известным способом [6]. Размеченная ГСА работы блока 13 управления работой блока приведена на фиг.9, где обозначено:
Логические условия:
Х1: "СДi"
Х2: "СОВi"
Х3: "ПКСi"
Х4: "РРi"
Х5: "РАСi"
Х6: "КРС"
Операторы:
У1: "Сдi:=1"
У2: "W/Ri:=0"
У3: "АЗУi:=ВХДi"
У4: "АЗУi:=ОСЛi"
У5: "КНi:=1"
У6: "РгВХi:=СУПi"
У7: "РгВХi:=ВХВi"
У8: "СчРгi:=КСМi"
У9: "СчКi:=КЛБi"
У10: "ШФi:=АРРi"
У11: "СЗЩi:=1"
У12: "Трi:=1"
У13: "ВКi:=0"
У14: "Сч/Зпi:=0"
У15: "БОЗУi:=АдСТi"
У16: "БОЗУi:=АдСТРi"
У17: "БОЗУi:=АДРi"
У18: "РгВХi:=СДПi"
У19: "СчАдi:=ГИi"
У20: "Трi:=0"
У21: "СчКi:=ТАИi"
У22: "РАСi:=0"
У23: "АДРi:
Блок 6 управления системой синтезируется на основе ГСА алгоритма управления (фиг.10) известным способом [6]. Размеченная ГСА работы блока 6 управления системой приведена на фиг.11, где обозначено:
Логические условия:
Х1: "УОО"
Х2: "ПУСК"
Х3: "i≤n"
Х4: "ПРКС"
Х5: "ПРКВ"
Операторы:
У1: "СБРОС:=1"
У2: "ВК1:=0"
У3: "Сч/Зп1:=0"
У4: "ПВ:=АСР"
У5: "ПВ:=АСТ"
У6: "ПВ:=ВВХ"
У7: "ВК2:=0"
У8: "Сч/Зп2:=0"
У9: "ПС:=АС"
У10: "ПС:=АР"
У11: "ПС:=ВСЛ"
У12: "i:=1"
У13: "j:=1"
У14: "k:=1"
У15: "БОПВi:=СДi"
У16: "БОПВi:=РРi"
У17: "БОПВi:=ВХВj"
У18: "БОПВi:=ОСЛk"
У19: "i:=i+1"
У20: "j:=j+1"
У21: "k:=k+1"
ИСТОЧНИКИ ИНФОРМАЦИИ
1. Кудрявцев В.Б., Подколзин А.С., Ушчумлич Ш. Введение в теорию абстрактных автоматов. М.: Изд-во МГУ, 1985, 174 с.

2. Крайзмер Л. П. Кибернетика: Учеб. пособие для студ. с-х. вузов по экон. спец. - 2-е изд., перераб. и доп. - М.: Агропромиздат, 1985, - 255 с.

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

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

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

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

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

8. Большие интегральные схемы запоминающих устройств: Справочник/ А.Ю. Гордонов, Н. В. Бекин, В.В.Цыркин и др..; Под ред. А.Ю.Гордонова и Ю.Н.Дубкова. - М.: Радио и связь, 1990, - 288 с.: ил.

9. Применение интегральных микросхем в электронной вычислительной технике: Справочник/ Р.В.Данилов, С.А.Ельцова, Ю.П.Иванов и др.; Под. ред. Б.Н. Файзулаева, Б.В.Тарабрина. - М.: Радио и связь, 1987, - 384 с.: ил.

10. Популярные цифровые микросхемы: Справочник. 2-е изд., испр. - Челябинск: Металлургия, Челябинское отд., 1989, - 352 с.: ил.

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

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

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

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

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

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