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

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

Известно устройство поиска информации (см., например, рис.13.7 на стр.609 в книге: Озкарахан Э. Машины баз данных и управление базами данных. Пер. с англ. - М.: Мир, 1989), которое выполняет поиск (распознавание) строки из пяти символов в проходящем потоке символов.

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

Наиболее близким устройством того же назначения к заявленному изобретению по совокупности признаков является принятое за прототип устройство поиска информации (рис.6.32 на стр.286 в книге: Шевкопляс Б.В. Микропроцессорные структуры. Инженерные решения. Справочник. - М.: Радио и связь, 1990), которое содержит запоминающее устройство, регистр и выполняет поиск строки из восемнадцати символов в проходящем потоке символов.

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

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

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

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

Устройство поиска информации содержит запоминающее устройство 1 и регистр 2, причем первый, второй и третий выходы данных запоминающего устройства 1 соединены соответственно с последовательным входом данных регистра 2, входом разрешения параллельной загрузки регистра 2 и выходом устройства поиска информации, подключенного тактовым и i-м входами соответственно к входу записи регистра 2 и i-му адресному входу запоминающего устройства j-й адресный вход которого соединен с (j-6)-м выходом регистра 2, подключенного (j-6)-м параллельным входом данных к шине нулевого потенциала.

Работа предлагаемого устройства поиска информации осуществляется следующим образом. На его первый, …, шестой входы подается 6-разрядный код очередного символа распознаваемой строки, а на его тактовый вход подается импульсный сигнал f∈{0,1}, период Т которого должен удовлетворять условию Т>τ_P+τ_ЗУ, где τ_Р и τ_ЗУ есть длительности задержек, вносимых регистром 2 и запоминающим устройством 1. В исходном состоянии в регистр 2 записан нулевой код. Если на входе разрешения параллельной загрузки регистра 2 действует логическая «1», то с помощью импульсного сигнала f в регистр 2 будет записан код 00000₂, то есть Q₁=0, …, Q₅=0. Когда на входе разрешения параллельной загрузки регистра 2 действует логический «0», сигнал f запишет в младший разряд регистра 2 бит z₁, сдвигая на один разряд предыдущее содержимое указанного регистра в направлении от Q₁ к Q₅. Отметим, что регистр 2 может быть построен на основе ИМС К555ИР16. В представленной ниже таблице приведено содержимое ячеек запоминающего устройства 1, необходимое для распознавания строки следующих символов: _JOHN_DOE_AT6374N_. Все остальные не указанные в таблице ячейки содержат код D₁=0, D₂=1, D₃=0.

Символ x₁₁, …, x₇ x₆, …, x₁ Адрес ячейки z₁ z₂ у _ 00000 001100 12 1 0 0 J 00001 010110 86 1 0 0 О 00011 011011 219 1 0 0 Н 00111 010100 468 1 0 0 N 01111 011010 986 1 0 0 _ 11111 001100 1996 0 0 0 D 11110 010000 1936 0 0 0 О 11100 011011 1819 0 0 0 Е 11000 010001 1553 1 0 0 _ 10001 001100 1100 0 0 0 А 00010 001101 141 1 0 0 Т 00101 100000 352 0 0 0 6 01010 000110 646 1 0 0 3 10101 000011 1347 1 0 0 7 01011 000111 711 0 0 0 4 10110 000100 1412 0 0 0 N 01100 011010 794 1 0 0 _ 11001 001100 1612 0 1 1

Предположим, что на первый, …, шестой входы устройства поиска информации поступил 6-разрядный код 001100₂, который соответствует символу «пробел» (_). Следовательно, 11-разрядный адрес на адресных входах устройства 1 равен 00000001100₂, или в десятичном представлении 12₁₀. Как видно из таблицы, в ячейке с адресом 12₁₀ записан код 001₂, старший разряд (у) которого равен нулю. С помощью импульсного сигнала f, действующего на тактовом входе предлагаемого устройства, в регистре 2 формируется код 00001₂, который служит для задания пяти старших разрядов следующего адреса. Предположим далее, что вслед за кодом 001100₂ на первый, …, шестой входы предлагаемого устройства поступает код 010110₂. С учетом сформированных ранее в регистре 2 данных 11-разрядный адрес на адресных входах устройства 1 равен 00001010110₂=86₁₀. В ячейке с этим адресом находится код 001₂, под управлением которого с помощью очередного импульса сигнала f в регистре 2 сформируется код для задания пяти старших разрядов следующего адреса и т.д. Если искомая последовательность символов найдена, то на конечном этапе поиска (см. последнюю строку таблицы) в старшем разряде кода, выбранного из устройства 1, появится единица, сигнализирующая об успешном исходе поиска. Когда на любом этапе поиск окажется неудачным, в регистр 2 запишется код 00000₂ исходного состояния предлагаемого устройства. Таким образом, данные, приведенные в таблице, показывают, что предлагаемое устройство выполняет поиск строки из восемнадцати символов в проходящем потоке символов.

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

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

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