Exploiting word-level parallelism for fast convolutions and their applications in approximate string matching
作者： Kimmo Fredriksson , Szymon Grabowski
DOI: 10.1016/J.EJC.2012.07.013
关键词: Mathematics 、 Combinatorics 、 Word ram 、 Binary logarithm 、 Approximate string matching 、 Word (computer architecture) 、 Parallelism (rhetoric) 、 Algorithm 、 Model of computation 、 Hamming distance
摘要: We develop a method for performing convolutions efficiently in word RAM model of computation, having size w = ? ( log n ) bits, where is the input size. The basic?idea?is to pack several elements vector into single computer word, effectively enabling parallel computation convolutions. technique applied approximate string matching under Hamming distance. obtained algorithms are fastest known. In particular, we reduce complexity Amir et?al.?(2000) algorithm k -mismatches from O + / . Those impose some (not severe) limitation on pattern length, m present another, less efficient however, based word-level parallelism, which works without length limitation.
core.ac.uk
sci-hub.se 参考文章(28)
Donald E. Knuth, The Art of Computer Programming: Combinatorial Algorithms, Part 1 Addison-Wesley Professional. ,(2011)
Smith, O Julius, Mathematics of the Discrete Fourier Transform (DFT) with Audio Applications ,(2007)
Amihood Amir, Liron Reuveni, Avivit Levy, The Practical Efficiency of Convolutions in Pattern Matching Algorithms Fundamenta Informaticae. ,vol. 84, pp. 1- 15 ,(2008)
Amihood Amir, Ohad Lipsky, Ely Porat, Julia Umanski, Approximate Matching in the L 1 Metric Combinatorial Pattern Matching. pp. 91- 103 ,(2005) , 10.1007/11496656_9
M. S. Paterson, M. J. Fischer, STRING-MATCHING AND OTHER PRODUCTS Massachusetts Institute of Technology. ,(1974)
Kimmo Fredriksson, Szymon Grabowski, Fast Convolutions and Their Applications in Approximate String Matching Lecture Notes in Computer Science. ,vol. 5874, pp. 254- 265 ,(2009) , 10.1007/978-3-642-10217-2_26
U Vishkin, G M Landau, Efficient String Matching With K Mismatches ,(2018)
Z Galil, R Giancarlo, Data structures and algorithms for approximate string matching Journal of Complexity. ,vol. 4, pp. 33- 72 ,(1988) , 10.1016/0885-064X(88)90008-8
Ricardo Baeza-Yates, Gaston H. Gonnet, A new approach to text searching Communications of The ACM. ,vol. 35, pp. 74- 82 ,(1992) , 10.1145/135239.135243
Karl Abrahamson, Generalized string matching SIAM Journal on Computing. ,vol. 16, pp. 1039- 1051 ,(1987) , 10.1137/0216067