Efficient algorithm for two dimensional pattern matching problem (non-square pattern)

摘要

Since the recent advancements in computer storage capacities and processing speed have reached enhanced levels, researches are exerting more demand on higher storage capacity of multidimensional data and elevated computational strengths for research areas. Consequently, two-dimensional pattern matching is a primary topic of current research making good use of current technologies. In this paper, we will examine two-dimensional pattern solution. We are proposing an algorithm to convert the two-dimensional problem into a one-dimensional problem prior to the searching phase. Our proposed algorithm handles black and white images in general and text images in particular. Work in this phase will eliminate the need for soaring computational expense observed in preprocessing phase. Our experimental findings display results superior to both Brute-force algorithm, and RK-KMP algorithm. Suggested algorithm results show a clear reduction in comparisons'' numbers in multiple cases. Moreover, applied on one-dimensional text, our proposed algorithm is proportional to Θ (n) in time suggesting linear time.