Abstract
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.
Recommended Citation
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 https://doi.org/10.1109/ISPAN.1997.645099
Meeting Name
3rd International Symposium on Parallel Architectures, Algorithms, and Networks, 1997
Department(s)
Computer Science
Keywords and Phrases
RMESH; RMESH Algorithms; Approximate String Matching; Parallel Algorithms; Parallel Architectures; Parallel String Matching; Reconfigurable Architectures; Reconfigurable Mesh Architectures; String Matching
Document Type
Article - Conference proceedings
Document Version
Final Version
File Type
text
Language(s)
English
Rights
© 1997 Institute of Electrical and Electronics Engineers (IEEE), All rights reserved.
Publication Date
01 Jan 1997
