Position-restricted approximate string matching with metric Hamming distance
Sunghwan Kim, Hwan-Gue Cho · 2017
Approximate string matching is an important problem in many applications such as computer security, bioinformatics, and time series analysis. This paper presents a simple data structure for the position-restricted approximate string matching problem under a metric distance measure. In the problem discussed in this paper, a query is given as a triplet of a pattern string of a fixed length, a threshold, and a searching interval, so all occurrences of the pattern in the interval on a preprocessed text allowing errors within the threshold should be reported. Our proposed method is a framework which combines metric data structures and succinct rank/select data structure, and allows to execute such position-restricted approximate string matching queries efficiently. We show the experimental results to demonstrate when and how our method outperforms other alternatives.