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.

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.

Full Text Link

Share

 
COinS