首页>
外国专利>
String matching in hardware using the FM-index
String matching in hardware using the FM-index
展开▼
机译:使用FM-index在硬件中进行字符串匹配
展开▼
页面导航
摘要
著录项
相似文献
摘要
String matching is a ubiquitous problem that arises in a wide range of applications in computer science, e.g., packet routing, intrusion detection, web querying, and genome analysis. Due to its importance, dozens of algorithms and several data structures have been developed over the years. A recent breakthrough in this field is the FM-index, a data structure that synergistically combines the Burrows-Wheeler transform and the suffix array. In software, the FM-index allows searching (exact and approximate) in times comparable to the fastest known indices for large texts (suffix trees and suffix arrays), but has the additional advantage to be much more space-efficient than those indices. This disclosure discusses an FPGA-based hardware implementation of the FM-index for exact and approximate pattern matching.
展开▼