Сборники трудов ИСП РАН


Спектрально-аналитический метод распознавания неточных повторов в символьных последовательностях

Панкратов А.Н. (ИМПБ РАН, Москва), Тетуев Р.К. (ИМПБ РАН, Москва), Пятков М.И. (ИМПБ РАН, Москва), Тойгильдин В.П. (МГУ, Москва), Попова Н.Н. (МГУ, Москва)

Аннотация

Предложены теоретическое обоснование и алгоритмическая реализация спектрально-аналитического метода распознавания повторов в символьных последовательностях. Теоретическое обоснование основывается на теореме об эквивалентном представлении символьной последовательности вектором непрерывных характеристических функций. Сравнение фрагментов характеристических функций производится в стандартной метрике в евклидовом пространстве коэффициентов разложения рядов Фурье по ортогональным многочленам. Существенным свойством данного подхода является способность оценивать повторы на разных масштабах. Другим важным свойством является возможность эффективного распараллеливания по данным. При разработке алгоритмов предпочиталась схема вычислений с минимальным количеством обращений к оперативной памяти, подразумевающая повторяющиеся и отложенные вычисления. В данной парадигме разработан алгоритм вычисления коэффициентов разложения по ортогональным многочленам за счет использования рекуррентных соотношений. Показано, что алгоритм вычисления коэффициентов разложения по ортогональным многочленам может быть эффективно векторизован за счет вычислений с фиксированной длиной вектора. Распараллеливание и векторизация реализованы с использованием стандарта OpenMP и расширения Cilk Plus языка C/C++. Разработанный метод эффективно масштабируется в зависимости от параметров задачи и числа ядер процессора на системах с общей памятью.

Ключевые слова

спектрально-аналитический метод; ряды Фурье; ортогональные многочлены; рекуррентные соотношения; OpenMP; Cilk Plus

Издание

Труды Института системного программирования РАН, том 27, вып. 6, 2015, стр. 335-344.

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

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

Полный текст статьи в формате pdf Вернуться к содержанию тома