An acceleration of FFT-based algorithms for the match-count problem
| Autor: | Kensuke Baba |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Computation
Fast Fourier transform Prime-factor FFT algorithm Acceleration (differential geometry) 0102 computer and information sciences 02 engineering and technology 01 natural sciences Computer Science Applications Theoretical Computer Science Convolution Split-radix FFT algorithm 010201 computation theory & mathematics Rader's FFT algorithm Signal Processing 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Convolution theorem Algorithm Information Systems Mathematics |
| Zdroj: | Information Processing Letters. 125:1-4 |
| ISSN: | 0020-0190 |
| DOI: | 10.1016/j.ipl.2017.04.013 |
| Popis: | The match-count problem on strings is a problem of counting the matches of characters for every possible gap of the starting positions between two strings. This problem for strings of lengths m and n ( m ≤ n ) over an alphabet of size σ is classically solved in O ( σ n log m ) time using the algorithm based on the convolution theorem and a fast Fourier transform (FFT). This paper provides a method to reduce the number of computations of the FFT required in the FFT-based algorithm. The algorithm obtained by the proposed method still needs O ( σ n log m ) time, but the number of required FFT computations is reduced from 3 σ to 2 σ + 1 . This practical improvement of the processing time is also applicable to other algorithms based on the convolution theorem, including algorithms for the weighted version of the match-count problem. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect