Efficient $(\delta ,\gamma )$-Pattern-Matching with Don’t Cares

Abstract

Here we consider string matching problems that arise naturally in applications to music retrieval. The $\delta$-Matching problem calculates, for a given text $T_{1..n}$ and a pattern $P_{1..m}$ on an alphabet of integers, the list of all indices ${\mathcal{I}}_{\delta }=\{1\le i\le n-m+1:\underset{j=1}{\overset{m}{max}}\{|P_j–T_{i+j-1}|\le \delta \}\}$. The $\gamma$-Matching problem computes, for given $T$ and $P$, the list of all indices ${\mathcal{I}}_{\gamma }=\{1\le i\le n-m+1:\sum _{j=1}^m|P_j–T_{i+j-1}|\le \gamma \}$. In this paper, we extend the current result on the different matching problems to handle the presence of “\emph{don’t care}” symbols. We present efficient algorithms that calculate ${\mathcal{I}}_{\delta }$, ${\mathcal{I}}_{\gamma }$, and ${\mathcal{I}}_{(\delta ,\gamma )}={\mathcal{I}}_{\delta }\cap {\mathcal{I}}_{\gamma }$ for pattern $P$ with occurrences of “don’t cares”.