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

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

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

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

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

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

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

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

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

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

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

АЗУ - служит для обеспечение режима сравнения по совпадению входных величин.

БЛБ - блок служит для формирования двух режимов работы системы.

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

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

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

Особый интерес представляет структура образцов, поскольку при последовательном поиске позиции вхождения образца в обрабатываемое слово может быть аварийный пропуск вхождения в случае существования повторяющегося фрагмента в начале образца и соответственно 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, Н и Р произвольные непустые слова.

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

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

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

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

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

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

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

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

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

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

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

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

Информационно-поисковая система (фиг.1) содержит блок 1 памяти вхождений, блок 2 памяти слов, блок 3 регистра сдвига и определения адреса, ассоциативно-запоминающее устройство 4, блок 5 блокировки, блок 6 хранения адреса вхождений, блок 7 управления.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В блоке 5 алгоритма происходит подача на вход оперативно-запоминающего устройства памяти слов ПС блока БПС сигналов управления СУ2 ПС:=СУ2 из блока управления. По этой команде из оперативно-запоминающего устройства можно считывать слова для поиска в них определенной цепочки символов - вхождений.

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

В блоке 7 алгоритма происходит подача на вход оперативно-запоминающего устройства памяти вхождений ПВ блока БПВ сигналов управления СУ1 ПВ:=СУ1 из блока управления. По этой команде из оперативно-запоминающего устройства можно считывать вхождения для поиска их в словах.

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

В блоках 9, 10, 11, 12, 13, 14 алгоритма сформирован цикл записи информации в ОЗУ системы в случае обнаружения совпадения вхождения с фрагментами слов в АЗУ и дальнейшие действия системы в случае отсутствия совпадения.

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

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

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

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

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

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

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

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

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

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

В блоке 19 алгоритма осуществляется анализ сигнала РАС-выхода с логического элемента ИЛИ DD.30. Если сигнал РАС равен нулю, то происходит переход на блок 20 алгоритма. В этом случае в счетчике СчКi имеется информация и процесс вычитания из счетчика продолжается. Если сигнал РАС равен единице, то осуществляется переход на блок 21 алгоритма. В этом случае значение двоичного счетчика СчКi принимает значение нуля.

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

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

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

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

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

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

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

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

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

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

Блок 2 регистра слов и определения адреса БРСА состоит из реверсивного регистра сдвига вхождений РгВх DD.12, двоичного счетчика СчАд DD.15, логического элемента ИЛИ DD.13, логического элемента И DD.14 (фиг.3). Работа этого блока заключается в следующем: осуществлении операций сдвига вправо информации в регистре сдвига РгВх, определении сигнала признака конца сдвига ПКС, формировании адреса вхождения АДР. На вход регистра вхождения РгВх DD.12 поступает информационный сигнал управления СУП из блока управления. По приходу этого сигнала осуществляются операции: обнуления регистра, разрешения записи информации в регистр, подачи синхроимпульсов. Перед началом работы системы, в регистр вхождений РгВх записывается вхождение ВХВ - цепочка символов. Двоичный счетчик адреса СчА DD.15 обнулен сигналом установки в 0 - УС0. Управляющий сигнал ПКС принимает значение нуля. Выходом регистра вхождений является информационный сигнал ВХД, который поступает на вход ассоциативно-запоминающего устройства АЗУ. После загрузки информации в регистр, совершается операция сравнения на равенство в АЗУ системы. Если сравнения дало положительный результат, то происходит запись адреса в соответствующий i-й блок ОЗУ. Затем на вход регистра вхождений поступает сигнал сдвига вправо на один разряд - СДП. Информация регистра РгВх перемещается на один разряд вправо. После этого в АЗУ также осуществляется операция сравнения на равенство. Сигнал сдвига вправо СДП поступает на управляющий вход логического элемента И DD.14. На информационный вход указанного элемента поступают прямоугольные импульсы ГИ из блока управления. Выход элемента И DD. 14 соединен с суммирующим входом двоичного счетчика СчАд DD.15, который подсчитывает количество прямоугольных импульсов. При поступлении очередного сигнала сдвига СДП через схему И на суммирующий вход счетчика поступают прямоугольные импульсы. По приходу синхроимпульса СИН происходит суммирование прямоугольных импульсов в двоичном счетчике. Счетчик подсчитывает количество импульсов ГИ. На выходе этого счетчика формируется двоичный код, соответствующий количеству сдвига вправо информации в регистре вхождений (фиг.3). В случае равенства входных величин в АЗУ. в счетчике будет сформирован адрес вхождения - АРД. Полученный адрес записывается в ОЗУ системы. После операций сдвига информация в регистре перемещается вправо, при достижении крайне правого положения вхождения в регистре происходит установка логического элемента ИЛИ DD.13 в единичное состояние. Это означает, что первый цикл поиска вхождений завершен.

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

Блок 4 ассоциативно-запоминающее устройство АЗУ представляет собой элемент памяти, в котором реализуются несколько функций: поиск максимального значения, поиск минимального значения. сравнение на равенство и так далее. В представленной системе применяется только один режим работы АЗУ - сравнение на равенство входных величин. Этот режим обеспечивается входными сигналами W/R, М0, M1, M2, М3 [6,7,8]. На вход АЗУ поступает информация из регистра вхождений РгВх - вхождение (цепочка символов). В памяти перед поиском происходит загрузка слов, с которыми необходимо произвести операцию на сравнение с вхождением. Количество слов зависит от емкости АЗУ. Предположим, что их будет - n. Количество разрядов в каждой строке исчисляется - m. Операция сравнение в АЗУ происходит по столбцам, сразу во всех строках. Все символы вхождения сравниваются с буквами слов-образцов по столбцам. Если обнаружено равенство хотя бы в одной строке, при этом выходной сигнал СОВi будет равен единице, то в блок ОЗУi блока 6 хранения вхождений записывается адрес вхождения, т.е. место положение самого вхождения в регистре вхождений. Затем формируется сдвиг информации в регистре вхождений на один разряд вправо. После этого в АЗУ также реализуется операция сравнение на равенство. Если обнаружено совпадение с входной величиной, то адрес вхождения записывается в соответствующий блок ОЗУi. Процесс поиска вхождения в обрабатываемых словах продолжается до тех пор, пока информация в регистре не переместится в самое крайнее положение в регистре вхождений. Выходные сигналы СОВi с выхода АЗУ поступают на вход блока 5 блокировки (фиг.1, 4).

Блок 5 блокировки состоит из n каналов передачи информации КНПi. На входы всех каналов поступает управляющий сигнал, определяющий режим работы PP. На входы каналов поступают сигналы управления СУРi. Структура сигнала СУР1 и сигнала СУРi представлена на фиг.5. По своей структуре информационные сигналы СУР1 и СУРi отличаются. На фиг.2 показана структура обоих информационных сигналов СУР1 и СУРi. В состав информационного сигнала СУР1 входят управляющие сигналы СЗЩ1, СИМ, СБР, ТАИ1, СОБ1, КН1, КСМ. В состав информационного сигнала СУРi входят управляющие сигналы СЗЩi, ТАИi, СОБi, KHi Каналы передачи информации обеспечивают 2 режима работы системы и передают информацию от АЗУ к блокам ОЗУ (фиг.4). На фиг.5 представлен вариант технической реализации канала передачи информации КНП1. В состав первого канала входят: электронный ключ Кл DD.23, шинный формирователь ШФ DD.24, Д-триггер Тр DD.25, логический элемент с инверсным входом И DD.26, логический элемент И DD.27, двоичный счетчик СчРг DD.28, счетчик-регистр СчК DD.29, логический элемент ИЛИ-НЕ DD. 30. В начале работы системы двоичный счетчик СчРг DD.28 обнулен управляющим сигналом СБР, поступающим из блока управления. Счетчик-регистр СчК DD.29 также обнулен управляющим сигналом СОБ1, поступающим из блока управления. Д-триггер TpDD.28 находится первоначально в нулевом состоянии. Управляющий сигнал КН1 всегда находится в единичном состоянии, что обеспечивает рабочий режим шинного формирователя ШФ DD.24 во время все работы системы. Поисковая система работает в двух режимах. При первом режиме, когда вхождения имеют общие части, управляющий сигнал РР равен нулю. Логический элемент И DD.27 принимает значения нуля. Шинный формирователь всегда открыт для передачи информации. Ели в АЗУ системы произошло сравнение на равенство, т. е. обнаружено вхождение в первой строке, то в этом случае электронный ключ Кл DD.23 управляющим сигналом СОВ1, равным единице, будет открыт.

Входная информация АДР через открытый ключ Кл. DD.23 поступит на вход шинного формирователя ШФ DD.24. Входная информация АРР1, поступающая на вход шинного формирователя, через открытый элемент, поступает на вход блока ОЗУ1 (фиг. 4). В блоке ОЗУ1 по сформированным адресам входная информация АДР1 записывается в оперативно-запоминающее устройство ОЗУ1. По описанному выше алгоритму работают все каналы передачи информации КНПi поисковой системы при установлении первого режима работы. В случае положительного результата сравнения на равенство в АЗУ, записывается адрес вхождения в ОЗУi. Второй режим работы устанавливается управляющим сигналом РР, равным единице.

Работа поисковой системы в этом режиме заключается в следующем: в двоичном счетчике СчРг DD.28 (фиг.5) формируется двоичный код, соответствующий количеству символов в вхождении. На суммирующий вход счетчика поступают прямоугольные импульсы КСМ. Один прямоугольный импульс поступает на вход счетчика при считывании одного символа вхождения из памяти вхождений. В результате считывания всех символов очередного вхождения на выходе счетчика будет сформирован двоичный код КЛБ, эквивалентный количеству букв в вхождении. Этот код поступает на входы всех счетчиков-регистров блоков КНПi. В нашем случае на вход СчК DD.29 (фиг.5) поступает код КЛБ и записывается в счетчик-регистр.

На выходе счетчика-регистра СчК будет сформирован двоичный код, соответствующий количеству символов в вхождении. На входе логического элемента ИЛИ DD.30 имеется хотя бы одна единица, на выходе элемента управляющий сигнал РАС1 равен нулю. Этот сигнал поступает на инверсный вход логического элемента И DD. 26. Если выходной сигнал из АЗУ СОВ1 равен единице, то по приходу сигнала "защелки" СЗЩ1 на вход триггера Тр DD.25 из блока управления, триггер устанавливается в состояние единицы. Электронный ключ Кл DD.23 при отпирающем сигнале СОВ1 "открыт". Информация через ключ проходит на вход шинного формирователя ШФ DD. 24. Шинный формирователь на этот момент "открыт", выходной сигнал АДР1 при этом поступает на блока ОЗУ1. В результате этой операции адрес вхождения АРД через "открытые" электронный ключ и шинный формирователь будет записан в блок ОЗУ1.

После записи на выходе логического элемента И DD.26 будет единичное состояние. На выходе логического элемента И DD.27 также будет единица. Эта единица установит шинный формирователь ШФ DD.24 в третье импедансное состояние (практически разомкнуто) [8,9]. В дальнейшем это состояние шинного формирователя будем называть цепь "разомкнута". Второй режим работы системы характеризуется тем, что найденные вхождения не имеют общих частей в словах-образцах. Допустим в примере вхождение имеет пять символов. Это вхождение было обнаружено в первой строке АЗУ. По алгоритму работы системы при обнаружении вхождения, адрес будет записан в блок ОЗУ1.

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

Каждый раз как только происходит сдвиг информации вправо на один разряд в регистре вхождений, происходит подача сигнала ТАИ1 на вычитающий вход счетчика-регистра СчК DD.29. Как только на выходе счетчика-регистра СчК DD. 29 будет получен нуль, то на выходе логического элемента ИЛИ DD.30 будет единичное состояние. Сигнал РАС1 принимает значение единицы. В результате этого на выходе логического элемента И DD.26 будет нуль. На выходе логического элемента И DD.27 также будет нуль. На вход шинного формирователя ШФ подается значение нуля, что формирует рабочее состояние этого элемента. В результате этого шинный формирователь ШФ DD.224 будет "открыт" (фиг.5). Цепь передачи информации восстановится. После этого в счетчик-регистр СчК DD.29 вновь будет записана информация о количестве символов в вхождении из счетчика СчРг DD.28. Процесс сравнения на равенство входных величин будет продолжен, но уже с определенной позиции, на которой находится вхождение в регистре вхождений в результате сдвигов. На фиг.5 представлен один вариант технической реализации канала передачи информации КНП1. Остальные каналы КНПi имеют аналогичную структуру. Работают они по такому же описанному выше алгоритму.

Блок 6 хранения адреса вхождений БХАВ содержит блоки оперативно-запоминающих устройств БОЗУn. Количество блоков БОЗУ зависит от количества строк в АЗУ. Каждый канал передачи информации КНПi имеет свой блок оперативно-запоминающих устройств БОЗУ. Каждый блок БОЗУi работает совместно с двумя двоичными счетчиками. Эти счетчики формируют адреса столбцов и адреса строк. По этим адресам информация записывается в оперативно-запоминающее устройство.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

13. А.с. СССР N 1277091 (аналог).

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

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