A Practical Semi-External Memory Method for Approximate Pattern Matching

AbstractThe approximate pattern matching problem (APM) consists in locating all occurrences of a given pattern P in a text T allowing a specific amount of errors. Due to the character of real applications and the fact that solutions do not have error-free nature in Computer Science, solving APM is crucial for developing meaningful applications. Recently, Ilie, Navarro and Tinta presented a fast algorithm to solve APM based on the well-known Landau-Vishkin algorithm. However, the amount of available memory limits the usage of their algorithm, since it requires all the answer array be in memory. In this article, a practical semi-external memory method to solve APM is presented. The method is based on the direct-comparison variation from Ilie et al.'s algorithm. Performance tests with real data of length up to 1.2 GB showed that the presented method is about 5 times more space-efficient than Ilie et al.'s algorithm and yet, has a competitive trade-off regarding time