Efficient computations of \(\ell _1\) and \(\ell _{\infty }\) rearrangement distances. (English) Zbl 1186.68142
Summary: 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 was defined-the class of rearrangement errors. In this type of error the pattern is transformed through a sequence of rearrangement operations, each with an associated cost. The natural \(\ell _{1}\) and \(\ell _{2}\) rearrangement systems were considered. The best algorithm presented for general patterns, that may have repeating symbols, is \(O(nm)\). In this paper, we show that the problem can be approximated in linear time for general patterns! Another natural rearrangement system is considered in this paper-the \(\ell _{\infty }\) rearrangement distance. For this new rearrangement system efficient exact solutions for different variants of the problem are provided, as well as a faster approximation.
MSC:
| 68P10 | Searching and sorting |
References:
| [1] | Amir, A.; Lewenstein, M.; Porat, E., Faster algorithms for string matching with \(k\) mismatches, J. Algorithms, 50, 2, 257-275 (2004) · Zbl 1103.68129 |
| [2] | Galil, Z.; Giancarlo, R., Improved string matching with \(k\) mismatches, SIGACT News, 17, 4, 52-54 (1986) · Zbl 0608.68058 |
| [3] | Landau, G. M.; Vishkin, U., Efficient string matching with \(k\) mismatches, Theoret. Comput. Sci., 43, 239-249 (1986) · Zbl 0597.68055 |
| [4] | Abrahamson, K., Generalized string matching, SIAM J. Comput., 16, 6, 1039-1051 (1987) · Zbl 0646.68079 |
| [5] | Karloff, H., Fast algorithms for approximately counting mismatches, Inform. Process. Lett., 48, 2, 53-60 (1993) · Zbl 0788.68062 |
| [6] | R. Cole, R. Hariharan, Approximate string matching: A faster simpler algorithm. in: Proc. 9th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, 1998, pp. 463-472; R. Cole, R. Hariharan, Approximate string matching: A faster simpler algorithm. in: Proc. 9th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, 1998, pp. 463-472 · Zbl 0942.68033 |
| [7] | Levenshtein, V. I., Binary codes capable of correcting, deletions, insertions and reversals, Soviet Phys. Dokl., 10, 707-710 (1966) · Zbl 0149.15905 |
| [8] | R. Cole, L. Gottlieb, M. Lewenstein, Dictionary matching and indexing with errors and don’t cares, in: Proc. 36 Annual ACM Symposium on Theory of Computing, STOC, 2004, pp. 91-100; R. Cole, L. Gottlieb, M. Lewenstein, Dictionary matching and indexing with errors and don’t cares, in: Proc. 36 Annual ACM Symposium on Theory of Computing, STOC, 2004, pp. 91-100 · Zbl 1192.68818 |
| [9] | P. Ferragina, R. Grossi, Fast incremental text editing, in: Proc. 7th ACM-SIAM Annual Symposium on Discrete Algorithms, SODA, 1995, pp. 531-540; P. Ferragina, R. Grossi, Fast incremental text editing, in: Proc. 7th ACM-SIAM Annual Symposium on Discrete Algorithms, SODA, 1995, pp. 531-540 · Zbl 0851.68123 |
| [10] | M. Gu, M. Farach, R. Beigel, An efficient algorithm for dynamic text indexing, in: Proc. 5th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, 1994, pp. 697-704; M. Gu, M. Farach, R. Beigel, An efficient algorithm for dynamic text indexing, in: Proc. 5th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, 1994, pp. 697-704 · Zbl 0871.68072 |
| [11] | S.C. Sahinalp, U. Vishkin, Efficient approximate and dynamic matching of patterns using a labeling paradigm, in: Proc. 37th IEEE Annual Symposium on Foundations of Computer Science, FOCS, 1996, pp. 320-328; S.C. Sahinalp, U. Vishkin, Efficient approximate and dynamic matching of patterns using a labeling paradigm, in: Proc. 37th IEEE Annual Symposium on Foundations of Computer Science, FOCS, 1996, pp. 320-328 |
| [12] | Lowrance, R.; Wagner, R. A., An extension of the string-to-string correction problem, J. ACM, 177-183 (1975) · Zbl 0301.68028 |
| [13] | Berman, P.; Hannenhalli, S., Fast sorting by reversal, (Hirschberg, D.; Myers, E., Proc. 8th Annual Symposium on Combinatorial Pattern Matching. Proc. 8th Annual Symposium on Combinatorial Pattern Matching, CPM. Proc. 8th Annual Symposium on Combinatorial Pattern Matching. Proc. 8th Annual Symposium on Combinatorial Pattern Matching, CPM, LNCS, vol. 1075 (1996), Springer), 168-185 |
| [14] | Carpara, A., Sorting by reversals is difficult, (Proc. 1st Annual Intl. Conf. on Research in Computational Biology. Proc. 1st Annual Intl. Conf. on Research in Computational Biology, RECOMB (1997), ACM Press), 75-83 |
| [15] | Bafna, V.; Pevzner, P., Sorting by transpositions, SIAM J. Discrete Math., 11, 221-240 (1998) · Zbl 0973.92014 |
| [16] | Christie, D. A., Sorting by block-interchanges, Inform. Process. Lett., 60, 165-169 (1996) · Zbl 0900.68232 |
| [17] | A. Amir, Y. Aumann, G. Benson, A. Levy, O. Lipsky, E. Porat, S. Skiena, U. Vishne, Pattern matching with address errors: Rearrangement distances, in: Proc. 17th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, 2006, pp. 1221-1229; A. Amir, Y. Aumann, G. Benson, A. Levy, O. Lipsky, E. Porat, S. Skiena, U. Vishne, Pattern matching with address errors: Rearrangement distances, in: Proc. 17th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, 2006, pp. 1221-1229 · Zbl 1192.68813 |
| [18] | A. Amir, Y. Aumann, O. Kapah, A. Levy, E. Porat, Approximate string matching with address bit errors, in: P. Ferragina, G.M. Landau (Eds.), Proc. 19th Annual Symposium on Combinatorial Pattern Matching, CPM, 2008, pp. 118-129; A. Amir, Y. Aumann, O. Kapah, A. Levy, E. Porat, Approximate string matching with address bit errors, in: P. Ferragina, G.M. Landau (Eds.), Proc. 19th Annual Symposium on Combinatorial Pattern Matching, CPM, 2008, pp. 118-129 · Zbl 1143.68624 |
| [19] | Amir, A.; Hartman, T.; Kapah, O.; Levy, A.; Porat, E., On the cost of interchange rearrangement in strings, (Arge, L.; Welzl, E., Proc. 15th Annual European Symposium on Algorithms. Proc. 15th Annual European Symposium on Algorithms, ESA. Proc. 15th Annual European Symposium on Algorithms. Proc. 15th Annual European Symposium on Algorithms, ESA, LNCS, vol. 4698 (2007)), 99-110 · Zbl 1151.68387 |
| [20] | O. Lipsky, E. Porat, Approximated pattern matching with the \(l_1, l_2 l_\infty \); O. Lipsky, E. Porat, Approximated pattern matching with the \(l_1, l_2 l_\infty \) · Zbl 1215.68282 |
| [21] | Zolotarev, V., One-dimensional stable distributions, Transl. Math. Monogr., 65 (1986) · Zbl 0589.60015 |
| [22] | P. Indyk, Stable distributions, pseudorandom generators, embeddings and data stream computation, in: Proc. 39th IEEE Annual Symposium on Foundations of Computer Science, FOCS, 2000, pp. 189-197; P. Indyk, Stable distributions, pseudorandom generators, embeddings and data stream computation, in: Proc. 39th IEEE Annual Symposium on Foundations of Computer Science, FOCS, 2000, pp. 189-197 |
| [23] | P. Indyk, M. Lewenstein, O. Lipsky, E. Porat, Closest pair problems in very high dimensions, in: Proc. 31 International Colloquium on Automata, Languages and Programming, ICALP, 2004, pp. 782-792; P. Indyk, M. Lewenstein, O. Lipsky, E. Porat, Closest pair problems in very high dimensions, in: Proc. 31 International Colloquium on Automata, Languages and Programming, ICALP, 2004, pp. 782-792 · Zbl 1099.68123 |
| [24] | Fischer, M.; Paterson, M., String matching and other products, (Karp, R. M., Complexity of Computation. Complexity of Computation, SIAM-AMS Proceedings, vol. 7 (1974)), 113-125 · Zbl 0301.68027 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
