Proceedings of ISP RAS


Spectral Analytical Method of Recognition of Inexact Repeats in Character Sequences

A.N. Pankratov (IMPB RAS, Moscow), R.K. Tetuev (IMPB RAS, Moscow), M.I. Pyatkov (IMPB RAS, Moscow), V.P. Toigildin (MSU, Moscow), N.N. Popova (MSU, Moscow)

Abstract

Proposed are theoretical basis and algorithmic implementation of spectral-analytical method of recognition of repeats in character sequences. The theoretical justification is based on the theorem on equivalent representation of the character sequence by the vector of continuous characteristic functions. Comparison of fragments of characteristic functions is performed in the standard metric in Euclidean space of expansion coefficients of the Fourier series of orthogonal polynomials. An essential feature of this approach is the ability to evaluate repeats at different scales. Another important feature is the possibility of efficient parallelization of data. In the development of algorithms we preferred scheme of computing with a minimal amount of references to memory, implying repetitive calculations and evaluations on demand. In this paradigm, proposed is an algorithm for calculating the coefficients of expansions in the orthogonal polynomials through the use of recurrence relations. It is shown that the algorithm for calculating the coefficients of expansions in the orthogonal polynomials can be effectively vectorized by computing with a fixed vector length. Parallelization and vectorization implemented using the OpenMP standard and extension Cilk Plus of language C/C++. The developed method effectively scales, depending on the parameters of the problem and the number of processor cores on systems with shared memory.

Keywords

spectral-analytical method; Fourier series; orthogonal polynomials; recurrence relations; OpenMP; Cilk Plus

Edition

Proceedings of the Institute for System Programming, vol. 27, issue 6, 2015, pp. 335-344.

ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).

DOI: 10.15514/ISPRAS-2015-27(6)-21

Full text of the paper in pdf (in Russian) Back to the contents of the volume