Efficient Computations of e_1 and e_∞ Rearrangement Distances

摘要

Recently, a new pattern matching paradigm was proposed, pattern matching with address errors. In this paradigm approximate string matching problems are studied, where the content is unaltered and only the locations of the different entries may change. Specifically, a broad class of problems in this new paradigm was defined - the class of rearrangement errors. In this type of errors the pattern is transformed through a sequence of rearrangement operations, each with an associated cost. The natural e_1 and e_2 rearrangement systems were considered. A variant of the e_1-rearrangement distance problem seems more difficult - where the pattern is a general string that may have repeating symbols. The best algorithm presented for the general case is O(nm). In this paper, we show that even for general strings the problem can be approximated in linear time! This paper also considers another natural rearrangement system - the e_∞ rearrangement distance. For this new rearrangement system we provide efficient exact solutions for different variants of the problem, as well as a faster approximation.