METHOD AND ASSOCIATIVE MATRIX APPARATUS FOR PARALLEL SEARCH OF A SAMPLE BASED ON THE PREFIXES THEREOF

摘要

FIELD: computing technology.;SUBSTANCE: technical result is achieved by means of parallel search, implemented in no more than m-1 search steps. The even step of the operation therein consists of the stage of parallel comparisons of the sample and m-1 prefixes thereof with the text in a matrix representation thereof and a stage of combining and processing the comparison matrix to calculate the position of the next possible occurrence of the sample at the next search step. The odd step of the operation consists of a left shift of the text in a one-dimensional (linear) representation thereof by a calculated amount of characters. At the stage of parallel comparisons, the relative shift of the prefixes by 1 character allows for m parallel comparisons, and if the occurrence of the tth prefix with a length of m-t characters (t=1-m) in the text is detected, at the next step, a shift thereof to the left (shift towards the initial position) by the calculated amount of characters.;EFFECT: reduction in the time for the operation of searching for occurrences of a sample in the text based on associative memory.;2 cl, 9 dwg