An efficient algorithm for 2-dimensional pattern matching problem

• Autorzy: Dimri Sushil Chandra , Tiwari Umesh Kumar , Ram Mangey

Identyfikatory

DOI

10.2478/jok-2020-0041

• Języki publikacji: EN

Abstrakty

EN

Pattern matching is the area of computer science which deals with security and analysis of data. This work proposes two 2D pattern matching algorithms based on two different input domains. The first algorithm is for the case when the given pattern contains only two symbols, that is, binary symbols 0 and 1. The second algorithm is in the case when the given pattern contains decimal numbers, that is, the collection of symbols between 0 and 9. The algorithms proposed in this manuscript convert the given pattern into an equivalent binary or decimal number, correspondingly find the cofactors of the same dimension and convert these cofactors into numbers if a particular cofactor numer matches indicate the matching of the pattern. Furthermore, the algorithm is enhanced for decimal numbers. In the case of decimal numbers, each row of the pattern is changed to its decimal equivalent, and then, modulo with a suitable prime number changes the decimal equivalent into a number less than the prime number. If the number mismatched pattern does not exist, the complexity of the proposed algorithm is very low as compared to other traditional algorithms.

Słowa kluczowe

EN

two-dimensional; algorithm; cofactor; complexity

• Wydawca: Wydawnictwo Instytutu Technicznego Wojsk Lotniczych
• Czasopismo: Journal of KONBiN
• Rocznik: 2020
• Tom: Vol. 50, iss. 2
• Strony: 295--313
• Opis fizyczny: Bibliogr. 15 poz., rys.

Twórcy

autor

Dimri Sushil Chandra

• Graphic Era Deemed to be University, Dehradun, Uttarakhand, India

autor

Tiwari Umesh Kumar

• Graphic Era Deemed to be University, Dehradun, Uttarakhand, India

autor

Ram Mangey

• Graphic Era Deemed to be University, Dehradun, Uttarakhand, India

Bibliografia

• 1. Amir A., Landau G.M., Marcus S., Sokol D.: Two-dimensional maximal repetitions. Theoretical Computer Science, 2019, DOI 10.1016/j.tcs.2019.07.006.
• 2. Amir A., Butman A., Crochemore M., Landau G.M., Schaps M.: Two-dimensional pattern matching with rotations. Theoretical Computer Science, Elsevier, 314, 2004.
• 3. Apostolico A., Giancarlo R.: The Boyer-Moore-Galil String Searching Strategies Revisited. SIAM J. COMPUT., 15, 1, 1986.
• 4. Baker T.: A technique for extending rapid exact string matching to arrays of more than one dimension. SIAM Journal on Computing, 7, 3, 1978.
• 5. Bayer R., Moore J.: A fast matching algorithm. ACM, 20, 10, 1977.
• 6. Bird R.: Two dimensional pattern matching. Information Processing Letters, 6, 5, 1977.
• 7. Cáceres M., Puglisi S.J., Zhukova B.: Fast Indexes for Gapped Pattern Matching. In: Chatzigeorgiou A. et al. (eds.) SOFSEM 2020: Theory and Practice of Computer Science. SOFSEM 2020. Lecture Notes in Computer Science, Vol. 12011. Springer, Cham, 2020, DOI 10.1007/978-3-030-38919-2_40.
• 8. Charalampopoulos P., Kociumaka T., Pissis S.P., Radoszewski J., Rytter W., Straszyński J., Waleń T., Zuba W.: Circular Pattern Matching with k Mismatches. In: Gąsieniec L., Jansson J., Levcopoulos C. (eds.) Fundamentals of Computation Theory. FCT 2019. Lecture Notes in Computer Science, Vol. 11651. Springer, Cham, 2019, DOI 10.1007/978-3-030-25027-0_15.
• 9. Clifford R., Fontaine A., Starikovskaya T., Vildhøj H.W.: Dynamic and Approximate Pattern Matching in 2D. In: Proceedings of 23 International Symposium SPIRE 2016: String Processing and Information Retrieval. Lecture Notes in Computer Science, Vol. 9954. Beppu, Japan, October 18–20, 2016.
• 10. Dunn W.N.: Pattern matching: Methodology. International Encyclopedia of the Social & Behavioral Sciences, 2001.
• 11. Karp R.M., Rabin M.: Efficient randomized pattern-matching algorithms. IBM, 31, 2, 1987.
• 12. Karp R.M., Miller R.E., Rosenberg A.L.: Rapid identification of repeated patterns in strings, trees and arrays. Proceedings of the 4th Annual ACM Symposium on Theory of Computing, Assoc. for Comput. Mach., New York 1972.
• 13. Knuth D., Morris J., Pratt V.: Fast pattern matching in strings. SIAM Journal of Computing, 6, 2, 1977.
• 14. Knuth D.E., Morris J.H. Jr., Pratt V.R.: Fast pattern matching in strings. Research report, STANCS-74-440, Computer Science Department, Stanford, California 1974.
• 15. Manea F., Schmid M.L.: Matching Patterns with Variables. In: Mercaş R., Reidenbach D. (eds.) Combinatorics on Words. WORDS 2019. Lecture Notes in Computer Science, Vol. 11682. Springer, Cham, DOI 10.1007/978-3-030-28796-2_1.