Towards an Efficient Text Sampling Approach for Exact and Approximate Matching

Abstract

Text-sampling is an efficient approach for the string matching problem re- cently introduced in order to overcome the prohibitive space requirements of indexed matching, on the one hand, and drastically reduce searching time for the online solu- tions, on the other hand. Known solutions to sampled string matching are very efficient in practical cases being able to improve standard online string matching algorithms up to 99.6% using less than 1% of the original text size. However at present text sampling is designed to work only in the case of exact string matching. In this paper we present some preliminary results obtained in the attempt to extend sampled-string matching to the general case of approximate string matching. Specifi- cally we introduce a new sampling approach which turns out to be suitable for both exact and approximate matching and evaluate it in the context of a specific case of approximate matching, the order preserving pattern matching problem. Our preliminary experimental results show that the new approach is extremely com- petitive both in terms of space and running time, and for both approximate and exact matching. We also discuss the applicability of the new approach to different approxim- ate string matching problems.