RU2549525C2 - Method and apparatus for searching for composite sample in sequence - Google Patents

Abstract

FIELD: physics, computer engineering.

SUBSTANCE: invention relates to computer engineering. A method of searching for a composite sample in an analysed sequence, characterised by combining parallel bitwise processing of elements in the diagonals of a characteristic matrix, the length of which is equal to the length of the composite sample in the analysed sequence, with row-wise computation of start values search cells of the characteristic matrix, which enables to take into account the positionally irregular arrangement of symbols of the composite sample in the analysed sequence and join into a single search object the positionally irregular arrangements of symbols of the composite sample in the analysed sequence.

EFFECT: broader functional capabilities owing to modernisation of links of cells of the characteristic matrix and input of additional elements into the characteristic matrix.

2 cl, 5 dwg

Description

The invention relates to the field of computer engineering and informatics, can be used in information retrieval and expert systems, in high-frequency trading systems, in data transmission systems, in specialized devices and systems for processing symbolic information, etc.

The problem of searching for a composite sample in the analyzed sequence (text, data stream) is considered. In the general case, the composite sample and the analyzed sequence represent one-dimensional data structures (rows) made up of the letters of the working alphabet. Let a composite pattern x with a length of m-characters be given containing z substrings x ₁ , x ₂ ... x _z with lengths t ₁ , t ₂ , ... t _z such that (t ₁ + t _2, + ... + t _z ≤m , and the text is n-character long, where n> 0, m> 0 and m≤n. It is required to find the position of occurrence of substrings from x to y, that is, to determine such smallest addresses i ₁ , i ₂ ... i _z , for which is fair

,

.

,

.

In the particular case, for patterns that include only one substring, the search problem is formulated as an entry search. With scrap, the best part of condition (1) is written as

.i ₁ + 1 = i ₂ ; i ₂ + 1 = 1i ₃ ;

.

By default, expressions (2) are implied; they determine the physically adjacent nature of the arrangement of occurrences of individual substrings from x in the structure of the text y.

The most important practical case for symbol information processing systems is the search for a composite sample x containing z substrings x ₁ , x ₂ ... x _z with lengths equal to one symbol each, i.e. t ₁ = t ₂ = ... t _z = 1. In fact, in the analyzed sequence y, a character-by-character search is performed from x, for each element of which condition (2) is not necessarily satisfied, but condition (1) is surely fulfilled.

A known method of pipelined search of occurrences [Kulik, B.A. Search systems in arbitrary text / B.A. Kulik // Programming. 1987. No. 1 - C.6-10.], Based on a parallel comparison of the current character of the sample with the analyzed sequence and on the calculation, storage and processing of two binary (characteristic) vectors with the number of bits equal to the number of characters in the text. The algorithmization of this method consists in cyclic processing of the previous and current characteristic vectors based on the hardware-oriented operation “oblique conjunction”, which is a bitwise multiplication of two binary vectors, with the bits of the previous vector shifted by one position to the beginning of the vector. The disadvantage of this method is the need for additional time spent on checking positions “1” in binary vectors in accordance with the distribution of the characters of the composite sample in the text.

A known method of a matrix search for occurrences of a string pattern [Titenko, EA A method parallel to the search for a pattern and a matrix device for its implementation / K.A. Titenko // Information Systems and Technologies. Number 4. - 2011 P.24-30.], Based on a two-dimensional representation of operand words to take into account the positional and temporal relationships between the characters of two lines and consisting in organizing calculations along the diagonals of the binary (characteristic) matrix. Parallel processing of a matrix consists in bitwise processing of row and column elements in k (k = mn-1) diagonals of the matrix. Sequences of adjacent "1" in each diagonal matrix describe the structural relationship of occurrence. When organizing the search for a composite sample, the disadvantage of this method is the inability to take into account the position of the irregular distribution of the characters of the composite sample in the text and, as a consequence, the excessive time spent for sequential processing of each symbol of the composite sample and additional verification of the current and previous addresses of single-character occurrences pa condition i _j-1 <i _j , where j = 1 ... z.

A device is known [A.S. 1485254 USSR, MKI G06F 12/00. A device for addressing the contents of the memory block /.A. Kulik, E.V. Rakhov, N.N. Vostrov, T.P. Kopets - No. 4313200 / 24-24, declared 10/05/87; publ. 06/07/89, Bull. No. 21. 10 pp., Ill.] For addressing by the contents of a memory block, consisting of two blocks of associative features, a logical vector memory block and an operation block that performs, among other things, an identification operation based on processing of binary stolon vectors (column search). At the same time, the limitations of the identification operation are associated with a set-theoretic interpretation of the initial data. As a result of this, the structural relationships of succession in characteristic vectors are not taken into account, which does not allow directly using the operation unit to search for occurrences of a compound pattern in the text.

A parallel information retrieval system is known [RF Patent 2195015, IPC G06K 17/30. Parallel information retrieval system / V.M. Dovgal, S.S. Shevelev; applicant and patent holder Kursk, state. tech. un-t - No. 2001 120172/09: declared 07/18/2001; publ. 12/20/2002, Bull. No. 12], which contains an occurrence memory block, a word memory block, a control block, an array of occurrence determination blocks working simultaneously and incorporating a shift register for storing text and associative memory for snoring a substring of a pattern. The operation of the system consists in parallel matching in the associative memory of the substring of the pattern and the text. If there is no entry, the text is shifted by one police and a new iteration of the search. The disadvantage of this system is the inability to take into account structural relations of ordering occurrences of substrings of a composite sample in the analyzed text.

The prototype device is a device for parallel search and data processing [Patent 72771 Russian Federation, IPC G06F 12/00. Device for parallel search and data processing E.A. Titenko, L.A. Lisitsin, V.M. Dovgal; applicant and patent holder Kursk, state. tech. un-t - No. 2007149075/22: declared 12/25/2007; publ. 04/27/2008, Bull. No. 12.], Which consists of two blocks for storing and comparing associative features, a logical vector memory block, an operation block, and a matrix search block that performs parallel processing of a set of characteristic vectors combined into a two-dimensional search matrix. The disadvantage of this device is its limited functionality - the device allows you to only search for occurrences of a sample consisting of only one substring. The characteristic search matrix has the geometric shape of a parallelogram, and the connections between adjacent elements of the diagonals are local in nature, which does not allow this device to solve the problem of searching for a composite sample in the analyzed sequence.

An object of the invention is to expand the functionality by modernizing the relationships of the cells of the characteristic matrix and introducing additional elements into the characteristic matrix, which will solve the problem. The essence of the modernization of the characteristic matrix consists in combining parallel bitwise processing of elements in the composition of the diagonals of the matrix, the length of which is equal to the length of the sample, with a line-by-line calculation of the starting values of the cells of the characteristic matrix.

The solution to the technical problem is achieved by the fact that in the device for searching for a composite sample in a sequence containing the first and second blocks for storing and comparing associative signs, a memory block of logical vectors and an operation block, the information inputs of the first and second blocks for storing and comparing associative signs are respectively the first and second information inputs of the device, and the outputs of the storage units and comparison of associative features are connected respectively to the first and second address inputs mi of the logical vector memory block, the input of the regimes of the first and second blocks for storing and comparing associative signs, and the write-read input of the logical vector memory block are the first, second, and third inputs of the device modes, and the fourth, fifth, sixth device mode inputs, respectively connected to three inputs of operation unit operation codes, the first output of which is the first output of the device, the first input of the initial installation of the device is connected to the input initially installation of the operating unit, the second input of the initial installation - to the inputs of the initial installation of the first and second blocks for storing and comparing associative features, the first and second outputs of the logical vector memory block are connected respectively to the first and second information inputs of the operating unit, an additional one-bit output of the operating unit is introduced, which is the second output of the operating unit, and the composite sample search unit having four inputs and one output, and the first input of the initial installation The property is connected to the first input of the composite sample search unit, the second input of which is connected to the second output of the operation unit, the third and fourth inputs of the composite sample search unit are the third and fourth information inputs of the device, and the output of the composite sample search unit is the second output of the device, while the composite sample search unit contains a delay element, n registers for snoring the codes of the symbols of the composite sample with a bit size of p bits each, m registers for storing symbol codes in the text, each bit has p bits, k position triggers, as well as a characteristic matrix consisting of search cells and having a parallelogram geometric shape, matrix size is n × k search cells (km-n + 1 is the number of diagonals in the matrix) and (n- 1) × k two-input OR elements for line-by-line calculation of starting values, with each register for storing composite character codes and each register for storing text character codes, respectively, with three inputs (the first and second control inputs and the third information p-p row input) and one p-bit output, each position trigger has three inputs (first and second control inputs and third information input) and one p-bit output, each search cell has three information inputs (first and second p bit bits each, the third is a one-bit input) and one output, each search cell contains a two-input comparison scheme for the equality of p-bit codes of characters of a composite sample and text and a two-input element And, with the first and second p-bit inputs of the search cell are connected respectively to the first and second p-bit inputs of the two-input comparison circuit for equality, respectively, the output of which is the first input of the two-input element And, the output of which is the output of the search cell, the second input of the two-input element And is connected to the third input of the search cell, the first p-bit the inputs of all the search cells of the i-th row of the matrix (i = 1-n) are connected to the p-bit output of the i-th register for storing a compound pattern symbol, p-bit output of the j-th register for storing the tex character code that (j = 1-m) is connected respectively to the second p-bit inputs of all the search cells included in the j-th column of the matrix, the output of the (i, j) -th search cell, except for i = n (the last row of the matrix), is connected with the first input of the (i, j) -th two-input OR element, the second input of which is connected to the output of the (i, j-1) -th two-input OR element, except for the first two-input OR element in the current matrix row, the output (i, j) - of the two-input OR element is connected to the second input (ij + 1) of the two-input OR element and to the third input (i + 1, j + 1) of the search cell, except i = n, on the second the input of the first two-input OR element in each row of the matrix, a logical “0” value is supplied, the output of the search cell located in the last row of the matrix is connected to the third input of the j-th position trigger, to the third input of each search cell located in the first row of the matrix, a logical value of “1” is applied, the first input of the composite pattern search block is connected respectively to the first inputs of n registers for storing the character codes of the composite pattern, as well as with the first inputs of m registers for storing the character codes text and the first inputs k of position triggers, the second input “Recording strings” of the composite pattern search unit is connected to the input of the delay element and to the second inputs of n registers for storing the character codes of the composite pattern and the second inputs of m registers for storing text character codes, respectively, the output of the delay element is connected with second inputs of k position triggers, the outputs of which form the information k-bit output of the composite sample search block, the third input of the matrix search block consists of n groups of p bits each group, symbols of the composite sample, and the i-th group of bits (i = 1-n) is fed to the third p-bit input of the i-th register to store the code of the symbol of the composite sample, the fourth input of the composite sample search block consists of m groups of bits of p bits each group encoding characters of the text, and the j-th group of bits (j = 1-m) is fed to the third p-bit input of the j-th register to store the code of the characters of the text, each two-input equality comparison scheme in the search cell consists of p -input element And, as well as from p two-input the output elements of the sum modulo two with inversion, the first inputs of which will receive the corresponding bit from the i-th p-bit group of the third input of the composite sample search unit, and the pa second inputs of the two-input elements of the sum modulo two with inversion are the corresponding bit from the jth p-bit group of the fourth input of the composite sample search unit, the outputs of all two-input elements of the sum modulo two with inversion are connected to the p-input element And, the output of which is a one-bit output of the two-input comparison circuit for equality.

The invention is illustrated by drawings, where Fig. 1 shows a functional diagram of a device for searching a composite sample in a sequence, Fig. 2 is a functional diagram of a unit for searching a composite sample, Fig. 3 is a functional diagram of a search cell of a characteristic matrix, Fig. 4 is an example search composite sample, figure 5 is a timing diagram of the operation "SEARCH COMPOSITION" ("PSO").

The essence of the proposed method consists in combining parallel bitwise processing of diagonally located elements of the characteristic matrix, the length of which is equal to the length of the composite sample, with line-by-line calculation of starting values for the search cells of the characteristic matrix. The organization of line-by-line calculation of the initial value of the search cells of the characteristic matrix allows you to take into account the irregular nature of the location of the individual substrings of the composite sample in the structure of the analyzed sequence. The initial value within a single row of the matrix is formed as an iterative function OR the results of character-by-symbol matching within the analyzed sequence. The calculated starting values of “1” at the positions of the current row of the characteristic matrix initiate parallel search processes along the diagonals of the matrix, which makes it possible to combine positionally irregular arrangements of characters of a composite sample into one search object.

The device for searching for a composite sample in the sequence (Fig. 1) contains blocks 1 ₁ and 1 ₂ for storing and comparing associative signs, a block 2 for logical vector memory, an operation block 3, a block 4 for searching for a composite sample, information inputs 4 ₁ , 4 ₂ , 4 ₃ and 4 ₄ , information outputs 5 ₁ -5 ₂ , inputs 6 ₁ -6 _{6 of} setting the operating mode, inputs 7 ₁ and 7 _{2 of the} initial installation.

The structure of blocks 1 ₁ , 1 ₂ , 2, 3 strictly corresponds to the prototype device in a circuit and in functional terms, consists of matching elements and the connections between them.

Block 4 for searching a composite sample contains two control inputs: “Initial installation” 7 ₁ (first input) and input “Recording lines” (second input), third and fourth inputs for supplying characters of a composite sample and text in parallel code through information inputs 4 ₃ , and 4 ₄ devices, as well as one information output, which is the second output of 5 ₂ devices. In this case, the second control input of unit 4 is connected to the second output of the operation unit 3.

The composite sample search unit 4 contains a delay element 31, consisting of n pairs of inverters, n registers 32 ₁ -32 _n for storing the character codes of the composite sample, m registers 33 ₁ -33 _m for storing the character codes of the text, the characteristic matrix of the search cells 34 ₁₁ - 34 _nm. and (n-1) × k two-input elements 40 OR for line-by-line calculation of starting values, k triggers 37 positions, and register 32 _i (i = 1-n) and register 33 _j (j = 1-m) contain the first and second control inputs, the third p-bit information input and one output, respectively. The first and second inputs of n registers 32 for storing composite character codes and the first and second inputs of m registers 33 for storing text character codes are respectively connected to the first and second control inputs of the composite pattern search unit 4, the third input of which is p × n bit wide parallel recording of the composite sample in registers 32 ₁ -32 _n and consists of n groups of bits of p bits each group encoding the characters of the composite sample, and the i-th group of bits (i = 1-n) is fed to the third p-bit input of register 32 _i (i = 1-n), the fourth input of block 4 for searching for a composite sample with a bit size of p × m bits is intended for parallel writing of text into registers 33 ₁ -33 _m and consists of m groups of bits of p bits each group encoding text characters, and j-th group of bits (j = 1-m) is fed to the third p-bit input of the register 33 _j (j = 1-m). The second control input of the composite sample search unit 4 is also connected to the input of the delay element 31.

The characteristic matrix of search cells 34 ₁₁ -34 _nm has a size n × k cells (k = m-n + 1 is the number of diagonals in the matrix), and each search cell 34 _ij has three inputs and one output and contains a two-input comparison circuit 35 _ij for equality of p-bit character codes of the composite image and the text and the two-input element 36 I, each two-input equality comparison circuit 35 _ij in the search cell 34 _ij consists of the p-input element 39 I, as well as p two-input elements 38 ₁ -38 _p sum modulo two with inversion, the first inputs of which are supplied respectively etstvuyuschy discharge of the i-th group of p-bit unit 4 sample the composite input search the third, and the second inputs of two-input elements 38 ₁ -38 _p modulo two sum with inversion - the corresponding bit of the j-th group of p-bit input of the fourth block 4 searching for a composite sample, all outputs of two-input elements 38 ₁ -38 _p sum modulo two with inversion in the two-input equality circuit 35 _ij connected to the p-input element 39 And, the output of which is the output of the two-input equality comparison circuit 35 _ij . The first and second p-bit inputs of the search cell 34 _{ij are} respectively connected to the first and second p-bit inputs of the two-input equality comparison circuit 35 _ij , the output of which is the first input of the two-input element 36 AND, the second input of which is the third input of the search cell 34 _ij , the output of which is the output of the two-input element 36 I. Also, each row of the characteristic matrix, except for the last row, includes two-input elements 40 OR.

The characteristic matrix of search cells 34 ₁₁ -34 _nm has a geometric parallelogram shape in which each row contains k search cells shifted 1 position to the right from the next row of cells, starting from the cells of the first row 34 ₁₁ -34 _1k . This form of the matrix provides the direction of the search along the diagonals passing through the cells from the first row to the last row inclusive. Also, each row of the characteristic matrix, except the last row, includes k two-input elements 40 OR. The first p-bit inputs of k search cells of the i-th row of the matrix (i = 1-n) are connected to the p-bit output of register 32 _i . The p-bit output of the register 33 _j (j = 1-m) is connected to the second p-bit inputs of all the search cells included in the j-th column of the matrix. The output of each search cell 34 _ij , except i = n (the last row of the matrix), is connected to the first input of the (i, j) -th two-input element 40 OR, the second input of which is connected to the output of the (i, j-1) -th two-input element 40 OR, except for the first two-input OR element 40 in each row of the matrix, the output of the (i, j) -th two-input OR element 40 is connected to the second input (i, j + 1) of the two-input OR element 40 and to the third input (i + 1, j + 1) of the search cell, except for i = n, pa the second input of the first two-input element 40 OR in each row of the matrix, the value of the logical "0" is supplied, you the course of the search cell located in the last row of the matrix is connected to the third input of the j-th position trigger. On the third input of each cell located in the first row of the matrix, a logical value of “1” is supplied, thereby setting the direction of the search along the corresponding diagonal from the first row of the matrix to the last row inclusive.

The trigger 37 ₁ -37 _k positions store the search result in the form of a k-bit code, in which the logical “1” value marks the position of the beginning of occurrences of the composite pattern in the text. The trigger 37 _i position (i = 1-k) contains three inputs (first and second control, the third one-bit information input) and one output. The first input of the composite sample search unit 4 is connected respectively to the first inputs of k position triggers 37, the second inputs of the position triggers 37 are connected to the output of the delay element 31. The outputs of the triggers 37 ₁ -37 _k positions form a k-bit information output of the block 4 search composite sample.

This device, like the prototype device, works in the “Record” and “Operation” modes. The Record mode strictly corresponds to the algorithm described in the prototype device.

In the algorithm of the "Operation" mode, in addition to the operations performed in the prototype device, an operation is designated, designated as "PSO" and having its own operation code, which is supplied to the corresponding input of the operation mode. Given the appearance of block 4, in comparison with the prototype device, the following additions are made to the algorithm of the "Operation" mode.

Let the device perform the "Operation" mode with the operation code "PSO". Input 7 ₁ “Initial setting” of the operation unit 3 and unit 4 for searching the composite sample is supplied with a pulse signal of the initial installation, which resets the register 22 of the commands at its input 1, register 30 at its input 1, and also k triggers 37 positions at their input 1, n registers 32 at their input 1 and m registers 33 at their input 1. After the signal of the initial installation expires at input 6 ₆ , the operating mode of operation unit 3, the operation code "PSO" is detected, which is detected by the decoder 23 commands and with second output of the operating unit 3 a second input of 'Writing strings "unit 4 composite sample search supplied with the pulse signal. This pulse signal at the “Record strings” input of the composite sample search unit 4 is supplied respectively to the second write enable inputs of n registers 32 for storing the character codes of the composite sample and to the second write enable inputs of m registers 33 for storing text character codes, thereby recording n characters of a composite sample and m characters of text in parallel code from inputs 4 ₃ and 4 _{4 of the} device. Also, the pulse signal at the input “Recording lines” of the composite sample search unit 4 through the delay element 31 is supplied respectively to the second recording permission inputs of k triggers 37 positions. The delay element 31, made in the form of n pairs of inverters, is necessary to complete the search for a composite sample along the diagonals of the characteristic matrix, consisting of search cells 34 ₁₁ -34 _nm . The search begins with the cells of the first row of the characteristic matrix. The initial k-bit characteristic vector, equal to 11 ... 1, is fed to the third inputs of the search cells of the first row of the matrix and thereby determines the direction of parallel search on all diagonals of the characteristic matrix from the search cells of the first row to the search cells of the last row, inclusive. The search time for a composite sample is determined by the value T = mτ _И , where τ _И is the delay time in the element 36 I. Upon completion of the search processes, the pulse signal from the output of the delay element 31 after the time T = m2τ _inv (2τ _inv is the delay time on the inverter chain) records The k-bit composite pattern search result in trigger 37 ₁ -37 _k positions. The outputs of the triggers 37 ₁ -37 _k positions are the k-bit output of the block 4 search for a composite sample and form the second output of the device 5 ₂ .

The execution of the algorithm in the "Operation" mode on the remaining operations strictly corresponds to the prototype device.

Thus, the expansion of the functionality of the composite sample search device in the sequence is achieved due to the modernization of the links of the cells of the characteristic matrix and the introduction of additional elements into the characteristic search matrix.

Claims (2)

1. The method of searching for a composite sample in the analyzed sequence, characterized by combining parallel bitwise processing of the elements in the diagonals of the characteristic matrix, the length of which is equal to the length of the composite sample in the analyzed sequence, with line-by-line calculation of the starting values of the search cells of the characteristic matrix, which allows you to take into account the positionally irregular arrangement of the characters of the composite sample in the analyzed sequence and combine in one search object positionally the linear arrangement of the characters of the composite sample in the analyzed sequence. 2. A device for searching for a composite sample in the analyzed sequence, containing the first and second blocks for storing and comparing associative signs, a memory block of logical vectors and an operation block, the information inputs of the first and second blocks for storing and comparing associative signs are the first and second information inputs of the device, and the outputs of the blocks for storing and comparing associative signs are connected, respectively, with the first and second address inputs of the logical vector memory block c, the inputs of the job modes of the first and second blocks for storing and comparing associative signs and the write-read input of the logical vector memory block are the first, second, and third inputs of the device modes, and the fourth, fifth, and sixth inputs of the device modes are respectively connected to three inputs operating unit operation codes, the first output of which is the first output of the device, the first input of the initial installation of the device is connected to the input of the initial installation of the operating unit, T swarm input of the initial installation - to the inputs of the initial installation of the first and second blocks of storage and comparison of associative signs, the first and second outputs of the logical vector memory block are connected respectively to the first and second information inputs of the operational block, characterized in that, firstly, it is introduced into it an additional one-bit output of the operating unit, which is the second output of the operating unit, and secondly, a unit for searching for a composite sample in the analyzed sequence, having four inputs and one you a move, and the first input of the initial installation of the device is connected to the first input of the composite sample search unit in the analyzed sequence, the second input of which is connected to the second output of the operation unit, the third and fourth inputs of the composite sample search unit in the analyzed sequence are the third and fourth information inputs of the device, and the output of the composite sample search unit in the analyzed sequence is the second output of the device, while the composite search unit the sample in the analyzed sequence contains a delay element, n registers for storing the character codes of the composite sample in the analyzed sequence with bits of p bits each, m registers for storing character codes of text with bits of p bits each, k position triggers, and also a characteristic matrix consisting of search cells and having a parallelogram geometric shape, the matrix size is n × k search cells (k = m-n + 1 is the number of diagonals in the matrix) and (n-1) × k are two-input elements OR for line-by-line calculation of starts values, with each register for storing character codes of a composite sample in the analyzed sequence and each register for storing text character codes of text, respectively, have three inputs (first and second control inputs and a third information p-bit input) and one p-bit output, each a position trigger has three inputs (first and second control inputs and a third information input) and one p-bit output, respectively, each search cell has three information inputs (first and second inputs with a capacity of p b each, the third is a one-bit input) and one output, each search cell contains a two-input comparison scheme for the equality of p-bit codes of the symbols of the composite sample in the analyzed sequence and text and a two-input element And, the first and second p-bit inputs of the search cell are connected respectively with the first and second p-bit inputs of the two-input comparison circuit for equality, respectively, the output of which is the first input of the two-input element And, the output of which is the output of the search cell, the input of the two-input element And is connected to the third input of the search cell, and the first p-bit inputs of all the search cells of the i-th row of the matrix (i = 1-n) are connected to the p-bit output of the i-th register to store the symbol of the composite sample in the analyzed sequence, the p-bit output of the j-th register for storing the text character code (j = 1-m) is connected respectively to the second p-bit inputs of all the search cells included in the j-th column of the matrix, the output of the (i, j) -th the search cell, except for i = n (the last row of the matrix), is connected to the first input ohm of the (i, j) -th two-input OR element, the second input of which is connected to the output of the (i, j-1) -th two-input OR element, except for the first two-input OR element in the current row of the matrix, the output of the (i, j) -th two-input the OR element is connected to the second input (ij + 1) of the two-input OR element and to the third input (i + 1, j + 1) of the search cell, except i = n, the logical “ 0 ", the output of the search cell located in the last row of the matrix is connected to the third input of the j-th trigger Position, the logical “1” value is supplied to the third input of each search cell located in the first row of the matrix, the first input of the composite sample search unit in the analyzed sequence is connected respectively to the first inputs of n registers for storing the codes of the composite sample characters in the analyzed sequence, and with the first inputs of m registers for storing text character codes and the first inputs to position triggers, the second input is “Record strings” of the composite sample search block in the analyzed sequence and is connected to the input of the delay element and to the second inputs of n registers for storing codes of characters of the composite sample in the analyzed sequence and the second inputs of m registers for storing codes of text characters, respectively, the output of the delay element is connected to the second inputs of k position triggers, the outputs of which form information k bit output of the composite sample search block in the analyzed sequence, the third input of the matrix search block consists of n groups of p bits each group encoding the characters of an explicit sample in the analyzed sequence, the i-th group of bits (i = 1-n) being fed to the third p-bit input of the i-th register to store the code of the symbol of the composite sample in the analyzed sequence, the fourth input of the composite sample search block in the analyzed sequence consists of of m groups of digits of p digits each group encoding characters of the text, and the j-th group of digits (j = 1-m) is fed to the third p-bit input of the j-th register to store the code of the characters of the text, each two-input comparison circuit on equal your search cell consists of a p-input element And, as well as p two-input elements, the sums are modulo two with inversion, the first inputs of which are supplied with the corresponding bit from the ith p-bit group of the third input of the composite sample search block in the analyzed sequence , and the second inputs of two-input elements of the sum modulo two with inversion - the corresponding bit from the j-th p-bit group of the fourth input of the composite sample search unit in the analyzed sequence, the outputs of all two-input elements modulo two sum with inversion from p-coupled input elements and whose output is the output two-input one-bit comparison circuit for equality.

Images