Параллельная система информационного поиска

Параллельная система информационного поиска

Реферат

 

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

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

Известно "Устройство для реализации подстановок с двухкомпонентными вхождениями" (а. с. 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, in. Если количество 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, операции считывания/записи Сч