String matching problem received much attention over the years due to its importance in various applications such as text/file comparison, DNA sequencing, search engines, and spelling correction. Especially with the introduction of search engines dealing with tremendous amount of textual information presented on the world wide web and the research on DNA sequencing, this problem deserves special attention and any algorithmic or hardware improvements to speed up the process will benefit these important applications. In this paper, we present three algorithms for string matching on reconfigurable mesh architectures. Given a text T of length n and a pattern P of length m, the first algorithm finds the exact matching between T and P in O(1) time on a 2-dimensional RMESH of size (n-m+1) * m. The second algorithm finds the approximate matching between T and P in O(k) time on a 2D RMESH, where k is the maximum edit distance between T and P. The third algorithm allows only the replacement operation in the calculation of the edit distance and finds an approximate matching between T and P in constant-time on a 3D RMESH.
H. Lee and F. Erçal, "RMESH Algorithms for Parallel String Matching," Proceedings of the 3rd International Symposium on Parallel Architectures, Algorithms, and Networks, 1997, Institute of Electrical and Electronics Engineers (IEEE), Jan 1997.
The definitive version is available at http://dx.doi.org/10.1109/ISPAN.1997.645099
3rd International Symposium on Parallel Architectures, Algorithms, and Networks, 1997
Keywords and Phrases
RMESH; RMESH Algorithms; Approximate String Matching; Parallel Algorithms; Parallel Architectures; Parallel String Matching; Reconfigurable Architectures; Reconfigurable Mesh Architectures; String Matching
Article - Conference proceedings
© 1997 Institute of Electrical and Electronics Engineers (IEEE), All rights reserved.