Результат интеллектуальной деятельности: УСТРОЙСТВО ПОИСКА ИНФОРМАЦИИ

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

Известны устройства поиска информации (см., например, патент РФ 2378691, кл. G06F 17/30, 2010 г.), которые выполняют поиск строки из восемнадцати символов в проходящем потоке символов.

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

Наиболее близким устройством того же назначения к заявленному изобретению по совокупности признаков является принятое за прототип устройство поиска информации (патент РФ 2444781, кл. G06F 17/30, 2012 г.), которое содержит запоминающее устройство объемом 2048×3 бит, синхронный двоичный счетчик и выполняет поиск двух отличающихся последним восемнадцатым символом строк в проходящем потоке символов.

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

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

Указанный технический результат при осуществлении изобретения достигается тем, что в устройстве поиска информации, содержащем запоминающее устройство объемом 2048×3 бит и синхронный двоичный счетчик, j-й выход которого соединен с (j+6)-м адресным входом запоминающего устройства, подключенного i-м адресным входом к i-му входу устройства поиска информации, тактовый вход которого соединен с тактовым входом синхронного двоичного счетчика, особенность заключается в том, что в него дополнительно введены цифровой мультиплексор, цифровой компаратор, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ, мажоритарный элемент и два двухразрядных регистра, причем четвертый вход, r-й адресный вход и инвертирующий выход цифрового мультиплексора соединены соответственно с шиной единичного потенциала, r-м выходом первого и входом записи второго двухразрядных регистров, r-й выход данных запоминающего устройства подключен к r-му входу второго двухразрядного регистра, r-му входу первой входной шины цифрового компаратора и r-му входу мажоритарного элемента, выход и r-й вход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ соединены соответственно с вторым входом первого двухразрядного регистра и объединенными r-м выходом второго двухразрядного регистра, r-м входом второй входной шины цифрового компаратора, третий вход и выход мажоритарного элемента подключены соответственно к выходу «Равно» цифрового компаратора и объединенному первому входу первого двухразрядного регистра, входу сброса синхронного двоичного счетчика, а r-й выход второго двухразрядного регистра, третий выход данных запоминающего устройства и объединенные вход записи первого двухразрядного регистра, первый, второй, третий входы цифрового мультиплексора соединены соответственно с r-м, третьим выходами и тактовым входом устройства поиска информации.

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

Устройство поиска информации содержит запоминающее устройство 1 объемом 2048×3 бит, синхронный двоичный счетчик 2, цифровой мультиплексор 3, цифровой компаратор 4, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 5, мажоритарный элемент 6, первый и второй двухразрядные регистры 7₁ и 7₂, причем j-й выход счетчика 2 подключен к (j+6)-му адресному входу запоминающего устройства 1, четвертый вход, r-й адресный вход и инвертирующий выход мультиплексора 3 соединены соответственно с шиной единичного потенциала, r-м выходом регистра 7₁ и входом записи регистра 7₂, r-й выход данных запоминающего устройства 1 подключен к r-му входу регистра 7₂, r-му входу первой входной шины компаратора 4 и r-му входу элемента 6, выход и r-й вход элемента 5 соединены соответственно с вторым входом регистра 7₁ и объединенными r-м выходом регистра 7₂, r-м входом второй входной шины компаратора 4, третий вход и выход элемента 6 подключены соответственно к выходу «Равно» компаратора 4 и объединенным первому входу регистра 7₁, входу сброса счетчика 2, а r-й выход регистра 7₂, третий выход данных, i-й адресный вход запоминающего устройства 1 и объединенные вход записи регистра 7₁, тактовый вход счетчика 2, первый, второй, третий входы мультиплексора 3 соединены соответственно с r-м, третьим выходами, i-м и тактовым входами устройства поиска информации.

Работа предлагаемого устройства поиска информации осуществляется следующим образом. На его первый, ..., шестой и тактовый входы подаются соответственно 6-разрядный код очередного символа и импульсный сигнал (см. фиг. 2), причем этот сигнал должен удовлетворять условиям ,, где , , , , и есть длительности задержек, вносимых счетчиком 2, запоминающим устройством 1, мультиплексором 3, регистром 7₂, компаратором 4 и мажоритарным элементом 6. В исходном состоянии имеем q₁=…=q₅=0 и z₁=0. Если в процессе работы на входе сброса счетчика 2 установлен ноль, то передний фронт (переход из нуля в единицу) очередного импульса импульсного сигнала f обнуляет выходные сигналы счетчика 2, то есть q₁=…=q₅=0. Когда на входе сброса счетчика 2 действует единица, указанный фронт увеличивает значение кода (q₅…q₁)₂ на единицу. Загрузка данных в регистр 7₁ (7₂) происходит по перепаду из нуля в единицу сигнала на его входе записи, а выходные сигналы мультиплексора 3 и компаратора 4 определяются выражениями и , где есть символы операций И, ИЛИ, НЕ. Отметим, что счетчик 2, регистр 7₁ (7₂), мультиплексор 3 и компаратор 4 могут быть аппаратно реализованы на основе ИМС К555ИЕ18, К531ИР19, К155КП5 и К555СП1. В представленной ниже таблице приведено содержимое ячеек запоминающего устройства 1, необходимое для распознавания строки следующих символов: _JOHN_DOE_AT6374NM* или строки _JANET_CANE_M376KL*, где символ * обозначает конец строки. Все остальные не указанные в таблице ячейки содержат код 000₂.

Предположим, что на первый, …, шестой входы устройства поиска информации поступил 6-разрядный код Х₁=001100₂, который соответствует символу _. Следовательно, 11-разрядный адрес на адресных входах устройства 1 равен 00000001100₂. Как видно из таблицы, в ячейке с таким адресом записан код 011₂. Два младших разряда этого кода загрузятся в регистр 7₂ по первому перепаду из единицы в ноль импульсного сигнала f. Сигналы на выходах элементов 5 и 6 будут равны соответственно нулю и единице. По первому перепаду «↑» (из нуля в единицу) сигнала f код 01₂ загрузится в регистр 7₁, а счетчик 2 сформирует код 00001₂, который служит для задания пяти старших разрядов следующего адреса. Пусть вслед за кодом 001100₂ на первый, …, шестой входы предлагаемого устройства поступает код 010110₂. С учетом сформированных счетчиком 2 данных 11-разрядный адрес на адресных входах устройства 1 равен 00001010110_2. В ячейке с этим адресом находится код 011₂, два младших разряда которого загрузятся в регистр 7₂ по второму перепаду из единицы в ноль импульсного сигнала f. На выходах элементов 5 и 6 имеем ноль и единицу соответственно. В момент второго перепада «↑» сигнала f код 01₂ загрузится в регистр 7₁, а счетчик 2 формирует пять старших разрядов 00010₂ следующего адреса. Допустим, что после кода символа J на первый, …, шестой входы устройства поиска информации подается код 011011₂ (001101₂). В этом случае на адресных входах устройства 1 и на его выходах соответственно имеем 00010011011₂ (00010001101₂) и 001₂ (010₂). По третьему перепаду из единицы в ноль сигнала f код 01₂ (10₂) загрузится в регистр 7₂. На выходах элементов 5, 6 получим единицы. В момент третьего перепада «↑» сигнала f код 11₂ загрузится в регистр 7₁, при этом счетчик 2 сформирует старшие разряды 00011₂ следующего адреса. Предположим далее, что на первый, …, шестой входы предлагаемого устройства поступил код 010100₂ (011010₂). Следовательно, на адресных входах устройства 1 и на его выходах соответственно получим 00011010100₂ (00011011010₂) и 001₂ (010₂). Поскольку z₁=z₂=1, то m=0 и загрузка данных в регистр 7₂ не производится. На выходах элементов 5, 6 имеем единицы, которые запишутся в регистр 7₁ в момент четвертого перепада «↑» сигнала f. По этому же перепаду счетчик 2 сформирует код 00100₂ для задания пяти старших разрядов следующего адреса и т.д. Если одна из искомых последовательностей символов найдена, то на конечном этапе поиска (см. последнюю строку таблицы) в старшем разряде кода, выбранного из устройства 1, появится единица, сигнализирующая об успешном исходе поиска, при этом код (y₂y₁)₂=01₂ ((y₂y₁)₂=10₂) является идентификатором найденной последовательности символов. Когда на любом этапе поиск окажется неудачным, выходной сигнал элемента 6 будет равен нулю и очередной перепад «↑» сигнала f установит предлагаемое устройство в исходное состояние, в котором, как указывалось выше, q₁=…=q₅=0 и z₁=0.

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