Multidimensional String Matching
- PDF / 207,528 Bytes
- 4 Pages / 547.087 x 737.008 pts Page_size
- 1 Downloads / 234 Views
4. Amir, A., Benson, G., Farach, M.: The truth, the whole truth, and nothing but the truth: Alphabet independent two dimensional witness table construction.Technical Report GITCC-92/52, Georgia Institute of Technology (1992) 5. Amir, A., Benson, G., Farach, M.: An alphabet independent approach to two dimensional pattern matching. SIAM J. Comput. 23(2), 313–323 (1994) 6. Amir, A., Benson, G., Farach, M.: Optimal two-dimensional compressed matching. J. Algorithms 24(2), 354–379 (1997) 7. Amir, A., Benson, G., Farach, M.: Optimal parallel two dimensional text searching on a crew pram. Inf. Comput. 144(1), 1– 17 (1998) 8. Amir, A., Landau, G., Sokol, D.: Inplace 2d matching in compressed images. J. Algorithms 49(2), 240–261 (2003) 9. Amir, A., Landau, G., Sokol, D.: Inplace run-length 2d compressed search. Theor. Comput. Sci. 290(3), 1361–1383 (2003) 10. Berman, P., Karpinski, M., Larmore, L., Plandowski, W., Rytter, W.: On the complexity of pattern matching for highly compressed two dimensional texts. Proceeding of 8th Annual Symposium on Combinatorial Pattern Matching (CPM 97). LNCS, vol. 1264, pp. 40–51. Springer, Berlin (1997) 11. Crochemore, M., Galil, Z., Gasieniec, L., Hariharan, R., Muthukrishnan, S., Park, K., Ramesh, H., Rytter, W.: Parallel two-dimensional pattern matching. In: Proceeding of 34th Annual IEEE FOCS, 1993, pp. 248–258 12. Galil, Z., Park, K.: Alphabet-independent two-dimensional witness computation. SIAM. J. Comput. 25(5), 907–935 (1996) 13. Hennessy, J.L., Patterson, D.A.: Computer Architeture: A Quantitative Approach, 2nd edn. Morgan Kaufmann, San Francisco, CA (1996) 14. Klein, S.T., Shapira, D.: Compressed pattern matching in jpeg images. In: Proceeding Prague Stringology conference, 2005, pp. 125–134 15. Klein, S.T., Wiseman, Y.: Parallel huffman decoding with applications to jpeg files. Comput. J. 46(5), 487–497 (2003) 16. Park, K., Galil, Z.: Truly alphabet-independent two-dimensional pattern matching. In: Proceeding 33rd IEEE FOCS, 1992, pp. 247–256 17. Régnier, M., Rostami, L.: A unifying look at d-dimensional periodicities and space coverings. In: 4th Symp. on Combinatorial Pattern Matching, 15, 1993 18. Vishkin, U.: Optimal parallel pattern matching in strings. In: Proceeding 12th ICALP, 1985, pp. 91–113 19. Welch, T.A.: A technique for high-performance data compression. IEEE Comput. 17, 8–19 (1984) 20. Ziv, J.: Personal communication (1995)
Multidimensional String Matching 1999; Kärkkäinen, Ukkonen JUHA KÄRKKÄINEN, ESKO UKKONEN Department of Computer Science, University of Helsinki, Helsinki, Finland Keywords and Synonyms Multidimensional array matching; Image matching; Template registration
M
Problem Definition Given two two-dimensional arrays, the text T[1 : : : n; 1 : : : n] and the pattern P[1 : : : m; 1 : : : m], m n, both with element values from alphabet ˙ of size , the basic two-dimensional string matching (2DSM) problem is to find all occurrences of P in T, i. e., all m m subarrays of T that are identical to P. In addition to the basic problem, several types of gene
Data Loading...
