Method and apparatus for searching for composite sample in sequence

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

 

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, data transmission systems, specialized devices and systems for processing character information, etc.

The task is to find a composite sample in the analyzing sequence (text, data flow). 13 the General case, a composite sample and analyzed sequence represent one-dimensional data structures (strings) composed of letters of the working alphabet. Sheetwise composite sample x of length m-symbols containing z substrings of x1, x2...xzwith lengths t1, t2, ...tzsuch that (t1+t2,+...+tz≤m, and a text of length n symbols, where n>0, m>0 and m≤n. You want to find the positions of the occurrences of substrings of x in y, i.e., determine the lowest addresses (i1, i2...izin which is true

,.

In the particular case, for samples that include only one substring, the search task is formulated as a search entry. When the scrap of wura the part of the condition (1) is written as

i1+1=i2; i2+1=1i3;.

By default, the expression (2) means, they determine the physical�Cesky adjacent the location of individual occurrences of substrings of x in the structure of the text y.

The most important practical case for systems of symbolic information processing is the search for a composite sample of x containing z substrings of x1, x2...xzwith lengths equal to one character each, i.e., t1=t2=...tz=1. In fact, in the analyzed sequence y is performed character-by-character search from x, for each element which is not necessarily the condition (2), but necessarily performed the condition (1).

The known method of conveyor searching for occurrences of [Kulik, B. A. search in arbitrary text / B. A. Kulik // Programming. 1987. No. 1 Pp. 6-10.], based on the parallel comparison between the current character of the sample with the analyte sequence and the computation, storage, and processing of two binary (characteristic) vectors with the number of bits equal to the number of characters in the text. Algorithmization of this method lies in the cyclic processing of the previous and current feature vectors based on 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 to check the positions of "1" in binary vectors in the corresponding�AI with the distribution of composite characters of a sample text.

The known method of matrix occurrences of the search string reference [Titenko, E. A. parallel search Method on the sample matrix and the device for its realization / K. A. Titenko // Information systems and technology. No. 4. - 2011 Pp. 24-30.], based on a two-dimensional representation of words-operands to account for positional and time-based relationships between characters of two strings and consisting in the organization of computations for diagonal binary (characteristic) matrix. Parallel processing of matrix is bitwise processing elements of rows and columns composed of k (k=m-n-1) diagonals of the matrix. Sequence of adjacent "1" in the diagonal of the matrix describe the structural relationship of the occurrence. If you search a composite sample, the disadvantage of this method is the impossibility of accounting position Nude irregular distribution of the symbols of the composite sample on the text and, as a consequence, the delays for the sequential processing of each composite symbol sample and further verification of current and previous addresses single occurrences of PA condition ij-1<ijwhere j=1...z.

It is known device [A. S. 1485254 the USSR, MKI G06F 12/00. A device for addressing the content of the memory block /.And.Kulik, E. V. Rahim, N. N. The Vostrov, Etc. Copies - No. 4313200/24-24, Appl. 05.10.87; publ. 07.06.89, bull. No. 21. 10 p., ill.] for addressing ODS�the neighing of the memory block, consisting of two blocks of associative signs, memory block logical vectors and operating unit that performs, including the operation identification based on the processing of binary vectors of stolons (search by column). However, the limited operations of identification associated with the set-theoretic interpretation of the original data. Because of this structural relationship of following in the characteristic vectors are not taken into account that cannot directly use the operating unit to search for occurrences of the composite sample in the text.

Known parallel system of information retrieval [Patent 2195015 of the Russian Federation, IPC G06K 17/30. Parallel information retrieval system / V. M. Dovgal, S. S. Shevelev; applicant and patentee of the Kursk state technical. Univ - No. 2001 120172/09: Appl. 18.07.2001; publ. 20.12.2002, bull. No. 12], containing a block of memory occurrences, a block of memory words, the control unit, the array of blocks defining occurrences running simultaneously and having in its composition, the shift register for storing text and associative memory for graphene substrings of the sample. The system is in the parallel comparison in associative memory substrings of pattern and text. In the absence of the occurrence is a shift in the text of one police and the new iteration of the search. The disadvantage of this system is nevozmojnost� account the structural relationship of the ordering of occurrences of substrings of the composite sample in the analyzed text.

The device-the prototype is a device for parallel searching and processing data [Patent 72771 Russian Federation, IPC G06F 12/00. The device for parallel searching and processing data E. A. Titenko, L. A. Lisitsyn, V. M. Dovgal; applicant and patentee of the Kursk state technical. Univ - No. 2007149075/22: Appl. 25.12.2007; publ. 27.04.2008, bull. No. 12.], consisting of two blocks of the storage and comparison of associative signs, memory block logical vectors, operating unit and the block matrix search that performs parallel processing of the set of characteristic vectors are combined in a two-dimensional matrix search. The disadvantage of this device is the limited functionality of the device allows to only search for occurrences of the sample, consisting of only one substring. The characteristic matrix of the search has a geometric form of a parallelogram, and the connection between adjacent components of the diagonals are local in nature that do not allow this unit to solve the problem of finding a composite sample analyzed in the sequence.

An object of the invention is the extension of functionality by upgrading relations characteristic of cells of the matrix and enter additional items in the characteristic matrix, which will allow to solve the problem. Nature of the state.�industry modernization of the characteristic matrix is combination of parallel bitwise processing elements in the diagonals of the matrix, the length of which is equal to the length of the sample, with line-by-line calculation of the starting values of cells characteristic of the matrix.

The solution of a technical problem is achieved in that the device search composite sample in the sequence containing the first and second blocks of the storage and comparison of associative signs, the logical memory block vectors and the operating unit, and the information inputs of the first and second blocks of the storage and comparison of associative signs are respectively the first and second information inputs, and outputs blocks of the storage and comparison of associative signs are connected respectively with the first and second address inputs of the memory block logical vectors inputs assignment of the modes of the first and second blocks of storage and associative comparison of signs and sign-write-read memory block logical vectors are respectively first, second and third inputs assignment of the modes of the device, and the fourth, fifth, and sixth inputs assignment of the modes of the device respectively connected to three inputs of an operation code operating unit, the first output of which is the first output, the first input of the initial installation of the device connected to the input of the initial installation of the operating unit, the second input of the initial installation to the inputs of the initial installation pyo�first and second blocks of the storage and comparison of associative signs, the first and second outputs of the memory block logical vectors are connected respectively to the first and second information inputs of the operational block, the additional single-bit output of the operational unit, which is the second output of the operational block and the search block of a composite sample having four inputs and one output, the first input of the initial installation of the device connected to the first input of the search block of the composite sample, a second input connected to the second output of the operational block, the third and fourth inputs of the block search composite sample are respectively the third and fourth information inputs of the device, and the output of the search block of the composite pattern is the second output device, in this case, the search block of the composite sample contains a delay element, n registers for graphene character codes of a composite sample, the bit width of p bits each, m registers for storing character codes of the text by the width of p bits each, k triggers the position and the characteristic matrix consisting of a search of the cells and having the geometrical form of a parallelogram, the matrix size is n×k search cells (k-m-n+1 is the number of diagonals in the matrix) and (n-1)×k two-input element OR line-by-line calculation of the starting values, in this case, each register for storing character codes composition�th sample and each register for storing character codes of the text are respectively three inputs (first and second control inputs and the third information p-bit input) and one p-bit output, each trigger position has three inputs respectively (the first and second control inputs and the third information input) and one p-bit output, each search cell has three data inputs (first and second inputs of the bit width of p bits each, and the third one-bit input) and one output, each search cell contains two-input schema compare for equality p-bit character codes composite sample text, and two-input element And, moreover, the first and second p-bit inputs a search of the cell are connected respectively with the first and second p-bit inputs of two-input scheme equality comparisons, respectively, the output of which is the first input of two-input element And whose output is the output of the search of the cell, the second input of two-input element And is connected to the third input of the search of the cell, the first p-bit inputs of all search cells of the i-th row of the matrix (i=1 to n) is connected to the p-bit output of the i-th register storage character composite sample, p-bit output of the j-th register for storing the character code of the text (j=1 to m) is connected respectively with the second p-bit inputs of all search cells included in the j-th column of the matrix, output (i, j)-th search of the cell, except for i=n (the last row of the matrix), connected to the first input (i, j)-th two-input element OR the second input to�of which is connected to the output (i,j-1)-th two-input element OR, except for the first two-input OR element in the current row of the matrix, output (i, j)-th two-input element OR is connected to the second input (ij+1) two-input OR gate and the third input (i+1, j+1) a search of the cell, except for i=n, to the second input of the first of a two-input OR element in each row of the matrix is given logical value "0", the output of the search cell in the last row of the matrix is connected to the third input of the j-th trigger position to the third input of each of the search cells located in the first row of the matrix, the logical value "1", the first input of the search block composite sample respectively connected with the first inputs of n registers for storing character codes of a composite sample, as well as with the first m inputs of registers for storing character codes of the text and the first k inputs of the triggers of positions, a second input "Entry lines" block search composite sample is connected to the input of the delay element and with the second inputs of n registers for storing character codes of a composite sample and second inputs of the m registers for storing character codes of the text accordingly the output of the delay element is connected with the second inputs of the k trigger positions, the outputs of which form the information k-bit output of the search block of the composite sample, the third input of the block matrix search consists of n groups of p bits each �Rupp, encoding symbols of a composite sample, where the i-th group of bits (i=1 to n) is supplied to the third p-bit input of the i-th register for storing the character code of the composite pattern, the fourth input of the search block of a composite sample consists of m groups of bits in p bits, each group encoding text characters, and the j-th group of bits (j=1-m) is supplied to the third p-bit input of the j-th register for storing the code symbols of the text, each two-input comparison circuit for equality on the search of the cell consists of a p-argument of the element And, as well as from p two-input elements of the sum modulo two with inversion, to the first inputs of which are served the appropriate category from the i-th p-bit group, the third input of the search block of the composite sample, and PA second inputs of two-input elements of the sum modulo two inversion - related discharge from the jth p-bit group of the fourth input of the search block of the composite sample, all the outputs of two-input elements of the sum modulo two with inversion connected with p-shadowy element And, the output of which is a one-bit output of two-input schema compare for equality.

The invention is illustrated by drawings, where Fig.1 presents a functional diagram of the device of searching a composite sample in the sequence of Fig.2 is a functional block diagram of the search composite sample�, Fig.3 - functional diagram of the search of the cell characteristic matrix of Fig.4 - search example of a composite sample, Fig.5 - time diagram of the operation "SEARCH COMPOSITE SAMPLE" ("DCA").

The essence of the proposed method lies in the combination of a parallel bitwise processing diagonally arranged elements of the characteristic matrix, the length of which is equal to the length of the composite sample, with line-by-line calculation of the starting values for the search of cells characteristic of the matrix. The organization's by-line calculation of the initial value of the search cells characteristic of the matrix allows to take into account the irregular nature of the individual constituent substrings of the pattern in the structure of the analyzed sequence. The initial value within a separate row of the matrix are formed as an iterative function OR results character by character comparison within the analyzed sequence. The calculated initial values of "1" in the positions of the current row of the characteristic matrix causes the process of parallel search along the diagonals of the matrix that allows to combine in one search object positional irregular arrangement of characters of a composite sample.

Device search composite sample in the sequence (Fig.1) contains blocks 11and 1 the storage and comparison of associative features, the memory unit 2 Boolean vectors, an operating unit 3, unit 4 search composite sample, information inputs 41, 42, 43and 44information outputs 51-52inputs 61-66specify the mode of operation, inputs 71and 72the initial installation.

Structure block 11, 12, 2, 3 strictly correspond to the device-the prototype in circuit and functional relation, consists of matching elements and the connections between them.

The search unit 4 composite sample contains two inputs: "setup" 71(first entry) and the entry "Entry lines" (the second entrance), third and fourth inputs for submission of composite characters is a sample of text in parallel code using information inputs 43and 44device and one data output, the second output 52device. The second control input unit 4 connected to the second output of the operational unit 3.

The search unit 4 composite sample contains the element 31 of the delay, consisting of n pairs of inverters, n registers 321-32nfor storing character codes of a composite sample, m registers 331-33mfor storing character codes of the text, the characteristic matrix of the search cells 3411-34nm.and (n-1)×k two-input� elements 40 OR line-by-line calculation of the starting values, it triggers 37 positions, and the register 32i(i=1 to n) and the register 33j(j=1-m) contain the first and second control inputs, the third p-bit information input and one output, respectively. First and second n inputs 32 registers for storing character codes of a composite sample and the first and second inputs of the m registers 33 for storing character codes of the text are connected respectively with the first and second control inputs of the block 4 search composite sample, the third input of which the bit width p×n bit is used to record the composite sample in the registers 321-32nand consists of n groups of bits of the p bits of each group of encoding symbols of a composite sample, where the i-th group of bits (i=1 to n) is supplied to the third p-bit input to the register 32i(i=1 to n), the fourth input of the unit 4 search composite sample bit depth p×m bit is used for parallel recording of the text in the registers 331-33mand consists of m groups of bits in p bits, each group encoding text characters, and the j-th group of bits (j=1-m) is supplied to the third p-razrady input to the register 33j(j=1-m). The second control input unit 4, search composite sample is also connected to the input of the element 31 of the delay.

The characteristic matrix of the search cells 3411-34nmhas size n×k cells (k=m-n+1 is the number of diagonals in the matrix, moreover, each search cell 34ijhas three inputs and one output and contains a two-input circuit 35ijequality comparisons p-bit character codes composite shaped, and two-input element 36 And, each two-input circuit 35ijequality comparisons on the search of the cell 34ijconsists of p-argument element 39 and p two-input elements 381-38pthe sum modulo two with inversion, to the first inputs of which serves a corresponding discharge of the i-th p-bit group, the third input unit 4 search composite sample, and the second inputs of two-input elements 381-38pthe sum modulo two inversion - related discharge from the jth p-bit group of the fourth input of the unit 4 search composite sample, all outputs of two-input elements 381-38pthe sum modulo two with inversion in the structure of the two-input circuit 35ijequality comparisons connected with p-shadowy element 39, the output of which is the output of two-input circuits 35ijequality comparisons. First and second p-bit inputs a search of the cell 34ijrespectively connected with the first and second p-bit inputs of two-input circuits 35ijequality comparisons, the output of which is the first input of two-input element 36 And a second input which is the third�m entrance search cell 34 ij, the output of which is the output of two-input element 36. Also in each row of the characteristic matrix except for the last line, to include a two-input elements 40 OR.

The characteristic matrix of the search cells 3411-34nmhave the geometric shape of a parallelogram in which each line is k search cells shifted relative to the next row of cells to the right by 1 position, since the cells of the first row 3411-341k. This form of the matrix provides the search direction along the diagonals passing through the cell from the first line to the last line, inclusive. Also in each row of the characteristic matrix except for the last line, composed of k two-input elements 40 OR. The first p-bit inputs k of the search cells of the i-th row of the matrix (i=1 to n) is connected to the p-bit output register 32i. P-bit output of the register 33j(j=1 to m) is connected with the second p-bit inputs of all search cells included in the j-th column of the matrix. The output of each search cell 34ijexcept i=n (the last row of the matrix), connected to the first input (i, j)-th two-input element 40 OR, a second input coupled to an output (i, j-1)-th two-input element 40 OR except for the first two-input element 40 OR in each row of the matrix, output (i, j)-th two-input element 40 OR compounds� to the second input (i,j+1) two-input element and 40 OR with a third input (i+1, j+1) a search of the cell, except for i=n, PA the second input of the first of a two-input element 40 OR in each row of the matrix is given logical value "0", the output of the search cell in the last row of the matrix is connected to the third input of the j-th trigger position. To the third input of each cell in the first row of the matrix is given logical value "1", thereby setting the search direction corresponding to the diagonal from the first row of the matrix to the last line, inclusive.

Trigger 371-37kpositions store a search result in the form of a k-bit code in which the logical value "1" marked the starting position of the occurrences of the composite sample in the text. The trigger 37ipositions (i=1 to k) contains three inputs (first and second control, the third one-bit information input) and one output. The first input unit 4 search composite sample is connected respectively with the first k inputs of the triggers 37 positions, the second inputs of k triggers 37 positions connected with the output element 31 of the delay. The outputs of the triggers 371-37kpositions form a k-bit information block output 4 search composite sample.

This device, like the prototype device works in modes "Record" and "Operation". Mode "Record" strictly corresponds to the algorithm described in the device prototype.

In the algorithm Regis�and "Operation" in addition to performed in the device-prototype operation is entered, referred to as "DCA" and having their own operation code, which is fed to the appropriate input mode. Taking into account the appearance of the block 4 compared with the device-the prototype of the algorithm of mode "Operation" makes the following additions.

Let the device performs a mode "Operation with the operation code "DCA". On entry 71"Setup" operating unit 3 and unit 4 search composite sample is fed a pulse signal initial setup, which resets to zero the condition register 22 commands on its input 1, the register 30 at its input 1, and k triggers 37 items on their entrance 1, n 32 registers for their input 1 and m registers 33 for their input 1. After the expiration of the initial signal installation at the entrance 66mode the operating unit 3 is fed operation code "DCA", which is detected by the decoder 23 teams and from the second output of the operational unit 3 to the second input "Entry lines" of the search unit 4 composite sample is fed a pulse signal. This pulse signal input "Entry lines" of the search unit 4 composite sample is fed respectively to the second inputs of the write n registers 32 for storing character codes of a composite sample and the second inputs of the write m registers 33 for storing character codes of the text, thus providing a record of n symbols spanned about�of ASCA and m characters of the text in parallel code with inputs 4 3and 44device. Also, the pulse signal input "Entry lines" of the search unit 4 composite sample through the element 31 of the delay are respectively the second inputs recording resolution k triggers 37 positions. The element 31 of the delay, made in the form of n pairs of inverters required for the completion of the search processes of the composite sample along the diagonals of the characteristic matrix of a search of the cells 3411-34nm. The search starts from the cells of the first row of the characteristic matrix. 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 parallel search on all the diagonals of the characteristic matrix of the search cells of the first row to search the cells of the last line, inclusive. Search time composite sample is determined by T=mτAndwhere τAndthe time delay element 36 I. Upon completion of the search processes the pulse signal from the output of element 31 after a time delay T=m2τinv(2τinvthe delay chain of inverters) outputs k-bit search result of the composite sample in the trigger 371-37kpositions. The outputs of the triggers 371-37kpositions are k-bit output of the search unit 4 composite sample and form the second output mouth�STS 5 2.

The algorithm in the "Operation" on the rest of the operations are strictly corresponds to the device-the prototype.

Thus, the behavior of the device search composite sample in the sequence by upgrading relations characteristic of cells of the matrix and enter additional items in the characteristic matrix of the search.

1. A search method of a composite sample in the analyzed sequence, wherein the parallel combination of bitwise processing 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 characteristic of the matrix, to account for the positional irregular arrangement of characters composite sample analyzed in sequence and connect in one search object positional irregular arrangement of characters of the composite sample in the analyzed sequence.

2. Device search composite sample analyzed in the sequence containing the first and second blocks of the storage and comparison of associative signs, the logical memory block vectors and the operating unit, and the information inputs of the first and second storage units of comparison and Association�tive signs are respectively the first and second information inputs of the device and outputs blocks of the storage and comparison of associative signs are connected respectively with the first and second address inputs of the memory block logical vectors, inputs assignment of the modes of the first and second blocks of storage and associative comparison of signs and sign-write-read memory block logical vectors are respectively first, second and third inputs assignment of the modes of the device, and the fourth, fifth, and sixth inputs assignment of the modes of the device respectively connected to three inputs of an operation code operating unit, the first output of which is the first output, the first input of the initial installation of the device connected to the input of the initial 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 of the storage and comparison of associative signs, first and second outputs of the memory block logical vectors are connected respectively to the first and second information inputs of the operational block, characterized in that, firstly, the additional single-bit output of the operational unit, which is the second output of the operational unit, and secondly, a search of a compound in the analyzed sample of a sequence having four inputs and one output, moreover, the first input of the initial installation of the device Conn�Chen to the first input of the search block of the composite sample in the analyzed sequence, a second input connected to the second output of the operational block, the third and fourth inputs of the block search composite sample in the analyzed sequence are respectively the third and fourth information inputs of the device, and the output of the search block of the composite sample in the analyzed sequence is the second output device, wherein the search block of the composite sample in the analyzed sequence contains a delay element, n registers for storing character codes of a composite sample analyzed in sequence by the bit width of p bits each, m registers for storing character codes of the text by the width of p bits each, k triggers positions, as well as the characteristic matrix consisting of a search of the cells and having the geometrical form of a parallelogram, the matrix size is n×k search cell (k=m-n+1 is the number of diagonals in the matrix) and (n-1)×k two-input element OR line-by-line calculation of the starting values, each register for storing character codes of a composite sample analyzed in sequence and each register for storing character codes of the text are respectively three inputs (first and second control inputs and the third information p-bit input) and one p-bit output, each trigger position has three inputs respectively (the first and second control inputs and the third information input) and one p-bit output, each search cell has three data inputs (first and second inputs of the bit width of p bits each, and the third one-bit input) and one output, each search cell contains two-input schema compare for equality p-bit character codes composite sample analyzed in sequence, and the two-input element and the first and second p-bit inputs a search of the cell are connected respectively with the first and second p-bit inputs of two-input scheme equality comparisons, respectively, the output of which is the first input of two-input element And whose output is the output of the search of the cell the second input of two-input element And is connected to the third input of the search of the cell, the first p-bit inputs of all search cells of the i-th row of the matrix (i=1 to n) is connected to the p-bit output of the i-th register of the storage composite symbol sample in the analyzed sequence, p-bit output of the j-th register for storing the character code of the text (j=1 to m) is connected respectively with the second p-bit inputs of all search cells included in the j-th column of the matrix, output (i,j)-Oh search the cells except i=n (the last row of the matrix), connected to the first input (i,j)-th two-input OR element, a second input coupled to an output (i,j-1)-th two-input OR element, except the first�th two-input OR element in the current row of the matrix, output (i,j)-th two-input element OR is connected to the second input (ij+1) two-input OR gate and the third input (i+1, j+1) a search of the cell, except for i=n, to the second input of the first of a two-input OR element in each row of the matrix is logical value "0", the output of the search cell in the last row of the matrix is connected to the third input of the j-th trigger position to the third input of each search cell in the first row of the matrix, filed logical value "1", the first input of the search block of the composite sample in the analyzed sequences respectively connected with the first inputs of n registers for storing character codes of a composite sample analyzed in sequence, and with the first m inputs of registers for storing character codes of the text and inputs to the first trigger position, the second input "Entry lines" block search composite sample analyzed in the sequence is connected to the input of the delay element and with the second inputs of n registers for storing character codes of a composite sample in the analyzed sequence and the second m inputs of registers for storing character codes of the text accordingly the output of the delay element is connected with the second inputs of the k trigger positions, the outputs of which form the information k-bit output of the search block of the composite image�and analyzed in sequence, the third input of the block matrix search consists of n groups of p bits of each group of encoding symbols of a composite sample in the analyzed sequence, where the i-th group of bits (i=1 to n) is supplied to the third p-bit input of the i-th register for storing the character code of the composite sample in the analyzed sequence, the fourth input of the search block of the composite sample in the analyzed sequence consists of m groups of bits in p bits, each group encoding text characters, and the j-th group of bits (j=1-m) served on the third p-bit input of the j-th register for storing the code symbols of the text, each two-input comparison circuit for equality on the search of the cell consists of a p-argument of the element And, as well as from p two-input elements of the sum modulo two with inversion, to the first inputs of which serves a corresponding discharge of the i-th p-bit group, the third input of the search block of the composite sample in the analyzed sequence, and the second inputs of two-input elements of the sum modulo two inversion - related discharge from the jth p-bit group of the fourth input of the search block of the composite sample analyzed in sequence, all the outputs of two-input elements of the sum modulo two with inversion connected with p-shadowy element And, the output of which is a one-bit input�Ohm two-input schema compare for equality.



 

Same patents:

FIELD: information technology.

SUBSTANCE: personal data identification is achieved through linguistic techniques, realised by a data collection server, a linguistic processing server and an application server. The disclosed method includes creating a task based on open source bypass parameters coming in through an administrator's automated workstation. Further, the method includes loading text, bypassing open sources and loading texts or transmitting texts from an external system; selecting links from the loaded texts for addition thereof to addresses for further bypass; extracting text and converting binary files to a text format; text prepared for analysis is broken down and the substance is determined; the substance of personal data in the text is selected; personal data are identified; facts (substance determined at the previous step associated with persons) of personal data in the text are identified.

EFFECT: providing high relevance of results when identifying personal data in open information sources and in text files of the most common formats.

7 cl, 3 dwg

FIELD: physics, computer engineering.

SUBSTANCE: invention relates to means of communication over the Internet for applications and content. The system comprises network infrastructure configured to create a pattern and implement an application supermarket which supports a plurality of users, wherein the application supermarket provides customers with access to online stores which provide digital products, wherein relationships between the plurality of users are flexibly and dynamically specified for at least some of the plurality of users.

EFFECT: high efficiency and reliability when selling and buying applications owing to customisation thereof.

31 cl, 11 dwg

FIELD: physics.

SUBSTANCE: method includes receiving geodetic data for a plurality of locations on a surface, wherein the geodetic data contain information on surface gradient for at least a subset of locations on the surface; generating a set of constraining relations based on the geodetic data, wherein the set of constraining relations correlates undefined values for temporary changes in surface height in the subset of locations on the surface with information on surface gradient included in the geodetic data; the set of constraining relations includes undefined values for temporary changes in surface height at multiple locations on the surface; identifying specific values for temporary changes in surface height at each location on the surface in the subset based on determining the solution of the set of constraining relations.

EFFECT: high accuracy of the model of a geophysical area.

33 cl, 7 dwg

FIELD: physics, computer engineering.

SUBSTANCE: invention relates to information retrieval means. method comprises receiving a request at the input; outputting said request at the output in a plurality of different sources, at least one of which is a public domain search engine and at least one of which is a private domain search engine; receiving, at the input, a list of results from each of said plurality of different sources; determining whether to merge said list of results based on determining relevancy using a merging model; creating, by a processor, a full list of results from the received list of results using a merging model; providing presentation of the full list of results through a user interface; monitoring user behaviour in response to the presented full list of results; using the user behaviour to update the merging model.

EFFECT: improved relevancy of results.

21 cl, 12 dwg

FIELD: physics, video.

SUBSTANCE: invention relates to detection of audio and/or video streams broadcast in real time. The method includes receiving, from a media server, information about a media stream, which includes searching for features indicating that an analysed stream is a source of multimedia broadcast in real time. The features used can be, for example, a parameter which characterises stream Duration and/or a parameter which characterises the Start Time of the stream and/or a Seekable parameter within the transmitted stream.

EFFECT: high reliability of determining streams in real time in a multiple stream environment.

8 cl, 3 dwg, 7 tbl

FIELD: medicine.

SUBSTANCE: invention refers to medical equipment. A method for managing the execution of clinical guidelines involving the stages, whereat: accepting an input comprising a patient's condition; retrieving a set of recommendations corresponding to the above condition; displaying at least a portion of the set of recommendations to the user; accepting the user's selection of recommendations from the set of recommendations, issuing warnings, if the user's selection is rejected from the recommended sequence from the set of recommendation; accepting the input that one of the recommendations has been executed; and changing the display of recommendations on the basis of the above input that one of recommendations has been executed.

EFFECT: automatic management of executing the medical guidelines.

15 cl, 3 dwg

FIELD: physics, computer engineering.

SUBSTANCE: invention relates to database search means. The method includes receiving a request to initiate a search for data for a specific individual; determining, based on the request, a strategy to search a reference database; searching the reference database, in accordance with the strategy, for a match to the request and outputting the match; extracting, from said request, an attribute that is relevant to the search; assigning a weight to the attribute, thus yielding a weighted attribute, wherein said weight is indicative of the usefulness of the attribute in finding a match to the request; establishing a function, based on said weighted attribute; retrieving from the reference database, candidates having attribute values that indicate likely matches to the request, based on said function; determining a best candidate from said candidates and returning said best candidate as the match, wherein the request includes a request value for the attribute; modifying the weight depending on the number of records in the reference database that have the request value for the attribute.

EFFECT: improved match of the result with the request data.

9 cl, 2 dwg, 8 tbl

FIELD: physics, computer engineering.

SUBSTANCE: invention relates to computer engineering and specifically to intelligent automated assistant systems. Disclosed is method of operating an intelligent automated assistant. The method is carried out in an electronic device having a processor and memory which stores instructions for execution by the processor. The processor executes instructions on which a user request is received, wherein the user request includes a speech input received from the user. A prompt is provided to the user, the prompt presenting two or more properties relevant to items of an object selection domain. The user is requested to specify relative importance between the two or more properties.

EFFECT: high accuracy of providing a user with relevant information owing to consideration of relative importance between properties which correspond to items of an object domain.

12 cl, 50 dwg, 5 tbl

FIELD: physics, computer engineering.

SUBSTANCE: invention relates to computer engineering and specifically to intelligent automated assistant systems. Disclosed is method of operating an intelligent automated assistant. The method is carried out in an electronic device having a processor and memory which stores instructions for execution by the processor. The processor executes instructions on which a user request is received, wherein the user request includes a speech input received from the user. Two or more alternative interpretations of user intent are obtained based on the received user request and one or more similarities and one or more differences between said alternatives are identified. Further, the user is presented with a response, said response being at least one of the identified differences.

EFFECT: high accuracy of presenting relevant interpretations of user intent in the correct context.

13 cl, 50 dwg, 5 tbl

FIELD: physics, computer engineering.

SUBSTANCE: invention relates to computer engineering. Proposed method converts all info-important cells of standard down-loads from data bases from data base with indication of their position in every down-load. Definite conditions are set to indicate interrelations between cells in one line of down-load. Converted standard down-loads and named conditions are memorised in definite memory. Revealed are cell of standard down-loads in electronic file of analysed document. Found cells matrix is compiled to apply preset named conditions to matrix of found cells. Compiled the list of conditions whereto corresponds the matrix of found cells. Decision is made on if the portion of standard down-load exists in analysed document which satisfied the preset named conditions.

EFFECT: protection of data stored in protected data base from leaks.

2 cl, 2 dwg

FIELD: radio engineering, communication.

SUBSTANCE: present invention relates to telecommunications, particularly to a system and a method of processing multimedia messages (MMS). The technical result is increase in overall throughput of the MMS system during peak pulsed loads. The technical result is achieved through a system which comprises: first and second data storage units designed to store MMS data; a first control unit designed to control storage of MMS data obtained from outside the system in the first data storage unit and obtaining data from the first data storage unit; and a second control unit designed to control the recording of MMS data stored in the first data storage unit in the second data storage unit according to the current throughput of the second data storage unit.

EFFECT: invention increases throughput of the system for processing MMS, reduces costs on creating an MMS system server and ensures stable operation of MMS systems.

9 cl, 9 dwg

FIELD: physics, computer engineering.

SUBSTANCE: present group of inventions relates to computer engineering and can be used in building high-capacity and energy-efficient parallel computing systems. The result is achieved due to that, when using more flexible conditions of suspending sampling and decoding of commands it becomes possible in several cases to continue sampling and decoding commands of the next paragraph despite the presence of incomplete processes of the previous paragraph. Therefore, if after recording a command with an "end of paragraph" attribute in the buffer, previously selected commands which form new values of registers in a general-purpose register unit are not executed, sampling and decoding of commands of the next paragraph can continue, for example, read commands whose read address is specified directly in the command. The possibility of even partially executing a command of a new paragraph simultaneously with execution of a command of the previous paragraph increases the capacity of the computing system.

EFFECT: high capacity and low power consumption of the computing system.

5 cl, 4 dwg, 3 tbl

FIELD: physics, computer engineering.

SUBSTANCE: invention relates to the technology of playing back 3D and 2D video. A recording medium facilitates seamless connection between preceding play items which are streaming data located before a long transition and subsequent play items which are streaming data located after the long transition. An interleaved stream includes a general view stream for playing back 2D video and a sub-view stream for playing back 3D video in a combination with the general view stream. An Ln2D unit, designed for 2D playback, is arranged such that it follows a 3D extension unit in which a depth map data unit, a right view point data unit and a left view point data unit are interleaved. The 3D extension unit, which includes an L3ss unit designed for 3D playback, is located between the Ln2D unit and the LB point of the long transition. The Ln2D unit an the L3ss unit are identical on content.

EFFECT: smaller buffer size required during stereo playback.

7 cl, 104 dwg

FIELD: physics, computer engineering.

SUBSTANCE: invention relates to microprocessor systems with shared memory. The processing system includes transactional memory, first and second resource managers, and a transaction manager for a concurrent program having a thread including an atomic transaction having an action with a side effect. The first resource manager is configured to enlist in the atomic transaction and manage a resource related to the action with a side effect. The second resource manager is configured to enlist in the atomic transaction and manage the transaction memory. The transaction manager is connected to the first and second resource managers and manager is configured to receive a vote from the first and second resource managers as to whether to commit the transaction. The action with a side effect is postponed until after the transaction commits or applied along with a compensating action to the action with a side effect.

EFFECT: high efficiency of managing an atomic transaction having an action with a side effect.

20 cl, 3 dwg

FIELD: physics, computer engineering.

SUBSTANCE: invention relates to information technology, particularly methods and means of facilitating information exchange between nodes of a distributed computer system. Disclosed is a method of replicating information in distributed databases with competitive flow distribution where, during exchange of data to be replicated between nodes of a distributed database, exchange files are created and transmitted between nodes of the distributed database, the method being characterised by that, based on parameters of the exchange files and information on available network resources, a version of flow distribution of exchange files at communication devices is calculated, information on the version of flow distribution of exchange files is transmitted in form of a control signal to inputs of the communication devices, transmission routes of the exchange files are calculated by the communication devices based on a distributed algorithm and the exchange files are transmitted over the calculated routes.

EFFECT: high rate of replication in distributed databases by influencing distribution of flow of data on nodes of distributed databases.

3 dwg

FIELD: physics, computer engineering.

SUBSTANCE: invention relates to an information processing device on which a plurality of applications can be installed and which can collectivise user mandate among applications, and a method of driving the information processing device. The device comprises: an obtaining unit which obtains, from each of the plurality of applications running on the information processing device, a condition for sharing user mandate with another application; a generation unit which generates, based on the obtained sharing condition, sharing settings which assign said user mandate sharing condition among applications; and a providing unit which provides, upon receiving a user mandate request from an application, different from said first application from said plurality, said user mandate to the requesting application in accordance with sharing settings stored in memory.

EFFECT: high security of user mandate owing to use of conditions for sharing with another application when transferring user mandate with applications.

10 cl, 13 dwg

FIELD: radio engineering, communication.

SUBSTANCE: IPv4 to IPv6 translation component provides IPv4 to IPv6 translation for data traffic that is incoming to the network interface card. An IPsec component is configured to terminate an IPsec connection. An enterprise security assessment sharing component is configured to implement a security assessment publish and subscribe model in hardware for sharing security assessments among network endpoints, a security assessment being arranged to provide contextual meaning to a security incident that occurs within an enterprise network environment.

EFFECT: high security of an enterprise network.

15 cl, 11 dwg

FIELD: information technology.

SUBSTANCE: co-authoring application provides an authoring environment wherein two or more uses can edit a document simultaneously. Each user edits a copy of the document, sends updates to the master copy of the document and receives updates from the master copy of the document. Normally, the authoring environment prohibits users from providing conflicting edit instructions to the master copy of the document. For example, each user can lock content of one or more data units in the document. The authoring environment can synchronise content locking automatically and content only at the request of a user.

EFFECT: reducing delays and edit conflicts when authoring a document by multiple users.

20 cl, 31 dwg

FIELD: information technology.

SUBSTANCE: method of replacing a failed node storing distributed data, comprising steps of: receiving, through a first storage node, a first set of shares generated from a data file, each share in the first set including a linear combination of pieces of a data file along with a set of coefficients used to generate the linear combination; receiving, through the first storage node, an indication of a new storage node replacing the failed node, wherein the failed node includes a second set of shares generated from a data file; through the first storage node, generating a first replacement share as a response to said indication, the first replacement share generated by: multiplying each share in the first set and set of coefficients by a random scaling value and combining the multiplied first set of shares and the multiplied set of coefficients; and through the first storage node, transferring the generated first replacement share to the new storage node. The first replacement share and at least another replacement share form a second set of shares in the new storage node, said other replacement share being generated by a second storage node.

EFFECT: improved reliability of storing data.

23 cl, 5 dwg

FIELD: information technology.

SUBSTANCE: late-lock acquire apparatus, having a logic decoding unit configured to identify lock instructions at the beginning of a critical section to acquire a lock for the critical section; a logic execution unit configured for elision of at least part of the lock instruction to acquire a lock for the critical section, store an address and lock value referred to by the lock instruction in the lock entry, and executing the critical section without a lock for the critical section; and a logic late-lock acquire unit connected to the logic execution unit. The logic late-lock acquire unit is configured to instruct the logic execution unit to attempt to execute at last part of the lock instructions to acquire a lock for the critical section after the beginning of the critical section and without re-launching the critical section in response to detection of a late-lock acquire event when expecting critical section processing.

EFFECT: providing reliable data.

24 cl, 5 dwg

FIELD: computers.

SUBSTANCE: system has nine registers, four address selectors, triggers, AND elements, OR elements and delay elements.

EFFECT: higher speed.

8 dwg

Up!