A Practical Algorithm for Two-Dimensional Dictionary Matching


The Transactions of the Korea Information Processing Society (1994 ~ 2000), Vol. 6, No. 3, pp. 812-820, Mar. 1999
10.3745/KIPSTE.1999.6.3.812,   PDF Download:

Abstract

In two-dimensional dictionary matching problem, we are given a two-dimensional text T and a dictionary D = {P1, ..., Pk} as a set of two-dimensional patterns. We seek the locations of all the dictionary patterns that appear in T. We present a new two-dimensional pattern matching algorithm that can handle just a single pattern, and then show how to extend it into two-dimensional dictionary matching algorithm. The suggested algorithm is practical in the sense that it can deal with patterns of various sizes and shapes, that it runs fast in practice examining only a small fraction of the text characters, that it uses a small extra space propartional to the size of the dictionary, and that it is quite simple to be implemented without depending on complicated data structures.


Statistics
Show / Hide Statistics

Statistics (Cumulative Counts from September 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article
[IEEE Style]
L. G. Soo, "A Practical Algorithm for Two-Dimensional Dictionary Matching," The Transactions of the Korea Information Processing Society (1994 ~ 2000), vol. 6, no. 3, pp. 812-820, 1999. DOI: 10.3745/KIPSTE.1999.6.3.812.

[ACM Style]
Lee Gwang Soo. 1999. A Practical Algorithm for Two-Dimensional Dictionary Matching. The Transactions of the Korea Information Processing Society (1994 ~ 2000), 6, 3, (1999), 812-820. DOI: 10.3745/KIPSTE.1999.6.3.812.