The Practical Efficiency of Convolutions in Pattern Matching Algorithms

• Autorzy: Amir A. , Levy A. , Reuveni L.
• Języki publikacji: EN

Abstrakty

EN

Convolutions have proven to be an effective tool in asymptotically efficient pattern matching algorithms. This study attempts to find the type of problems where convolutions are inefficient in practice, and give possible solutions for the complex cases where the convolution method does not seem to aid realistic sized inputs.

Słowa kluczowe

EN

pattern matching; convolution algorithm

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2008
• Tom: Vol. 84, nr 1
• Strony: 1--15
• Opis fizyczny: bibliogr. 18 poz., wykr.

Twórcy

autor

Amir A.

autor

Levy A.

autor

Reuveni L.

• Department of Computer Science, Bar-Ilan University, 52900 Ramat-Gan, Israel,

Bibliografia

• [1] K. Abrahamson. Generalized string matching. SIAM J. Comp., 16(6):1039-1051, 1987.
• [2] A. Amir. Two glass balls and a tower. In S. N. Artemov, H. Barringer, A. S. d'Avilla Garcez, L.C. Lamb, and J. Woods, editors, We Will show Them!, volume 1, pages 57-76. College Publications, 2005.
• [3] A. Amir, R. Cole, R. Hariharan, M. Lewenstein, and E. Porat. Overlap matching. Information and Computation, 181(1):57-74, 2003.
• [4] A. Amir, E. Eisenberg, and E. Porat. Swap and mismatch edit distance. Algorithmica, 45(1):109-120, 2006.
• [5] A. Amir and M. Farach. Efficient 2-dimensional approximate matching of half-rectangular figures. Information and Computation, 118(1):1-11, April 1995.
• [6] A. Amir, C. Iliopoulos, O. Kapah, and E. Porat. Approximatematching in weighted sequences. In Proc. 17th Symposium on Combinatorial Pattern Matching (CPM), volume 4009 of LNCS, pages 365-376. Springer, 2006.
• [7] A. Amir, M. Lewenstein, and E. Porat. Faster algorithms for string matching with k mismatches. J. Algorithms, 2004.
• [8] R.S. Boyer and J.S. Moore. A fast string searching algorithm. Comm. ACM, 20:762-772, 1977.
• [9] C. Charras and T. Lecroq. Handbook of Exact String Matching Algorithms. King's College London Publications, 2004.
• [10] P. Clifford, R. Clifford, and C. S. Iliopoulos. Faster algorithms for _, matching and related problems. In Proc. 16th Annual Symposium on Combinatorial Pattern Matching (CPM '05), volume 3537 of LNCS, pages 68-78. Springer, 2005.
• [11] T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to Algorithms. MIT Press and McGraw-Hill, 1992.
• [12] M.J. Fischer and M.S. Paterson. String matching and other products. Complexity of Computation, R.M. Karp (editor), SIAM-AMS Proceedings, 7:113-125, 1974.
• [13] H. Kaplan, E. Porat, and N. Shafrir. Finding the position of the k-mismatch and approximate tandem repeats. In Scandinavian Workshop on Algorithm Theory (SWAT06), pages 90-101, 2006.
• [14] D.E. Knuth, J.H. Morris, and V.R. Pratt. Fast pattern matching in strings. SIAM J. Comp., 6:323-350, 1977.
• [15] S. Muthukrishnan. New results and open problems related to non-standard stringology. In Proc. 6th Combinatorial Pattern Matching Conference, pages 298-317. Lecture Notes in Computer Science 937, Springer- Verlag, 1995.
• [16] G. Navarro and M. Raffinot. Flexible Pattern Matching in Strings - Practical on-line search algorithms for texts and biological sequences. Cambridge University Press, 2002.
• [17] Tsung-Hsi Tsai. Average case analysis of the Boyer-Moore algorithm. Source Random Structures and Algorithms, 28(4):481-498, 2006.
• [18] W. T. Vettering, S. A. Teukolsky, W. H. Press, and B. P. Glannery. Numerical Recipes in C: The Art of Scientific Computing. Cambridge University Press, 2nd edition, 1992. ISBN 0521437202