Article

Free access

Two-dimensional periodicity and its applications

Authors:

Gary BensonAuthors Info & Claims

SODA '92: Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms

Pages 440 - 452

Published: 10 October 2019 Publication History

Abstract

String matching is rich with a variety of algorithmic tools. In contrast, multidimensional matching has a rather sparse set of techniques. This paper presents a new algorithmic technique for two-dimensional matching, that of periodicity analysis.

Periodicity in strings has been used to solve string matching problems. The success of these algorithms suggests that periodicity can be as important a tool in multidimensional matching. However, multidimensional periodicity is not as simple as it is in strings and was not formally studied or used in pattern matching.

This paper's main contribution is defining and analysing two-dimensional periodicity in rectangular arrays. In addition, we introduce a new pattern matching paradigm - Compressed Matching. A text array T and a pattern array P are given in compressed forms c(T) and c(P). We seek all appearances of P in T, without decompressing T. By using periodicity analysis, we show that for the two-dimensional run-length compression there is a O(|c(T)|log|P|+|P|), or almost optimal algorithm that can achieve a search time that is sublinear in the size of the text |T|.

References

[1]

A.V. Aho and M.J. Corasick, "Efficient String Matching", C. ACM, Vol. 18, No. 6, 1975, pp. 333-340.

Digital Library

[2]

A. Amir, G.M. Landau and U. Vishkin, "Eff~cient Pattern Matching with Scaling", Proc. 1st ACM-SIAM Symposium on Discrete Algorithms, 1990, pp. 344-357.

Digital Library

[3]

A. Apostolico, C. Iliopoulos, G.M. Landau, B. Schieber, and U. Vishkin, "Parallel Construction of a Suffix Tree with Applications", Algorithmica, Vol. 3, 1988, pp. 347-365.

[4]

T.P. Baker, "A Technique For Extending Rapid Exact-Match String Matching to Arrays of More Than One Dimension", SIAM J. Comput., Vol. 7, No. 4, 1978, pp. 533-541.

[5]

G. Benson, Doctoral dissertation, University of Maryland, College Park, Md., 1992.

[6]

R.S. Bird, '~I'wo Dimensional Pattern Matching", information Processing Letters, Vol. 6, No. 5, 1977, pp. 168-170.

[7]

R.S. Boyer and J.S. Moore, "A Fast String Searching Algorithm", Comm. ACId, Vol. 20, 1977, pp. 762- 772.

Digital Library

[8]

Z. Galil, "Optimal Parallel Algorithms for String Matching", Information and Control, Vol. 67, 1985, pp 144-157.

Digital Library

[9]

D. Harel and R.E. Tarjan, "Fast Algorithms for Finding Nearest Common Ancestors", SIAM J. Computing, Vol. 13, No. 2, 1984, pp. 338-355.

Digital Library

[10]

D. A. Huffman, "A Method for the Construction of Minimum-Redundancy Code", Proceedings of the IRE 40, 1952, pp. 1098-1101.

[11]

R.M. Karp, and M.O. Rabin, "Efficient Randomized Pattern-Matching Algorithms", IBM JournM of Res. and Dev., 1987, pp. 249-260.

Digital Library

[12]

D.E. Knuth, J.H. Morris and V.R. Pratt, "Fast Pattern Matching in Strings", SIAM J. Comp., Vol. 6, 1977, pp. 323-350.

[13]

R.E. Ladner and M.J. Fischer, "Parallel Prefix Computation", JACM, Vol 27, 1980, pp. 831-838.

Digital Library

[14]

G. G. Langdon and J. Rissanen, "Compression of Black-White images with Arithmetic Coding", IEEE Trans. Communications, 1981, pp. 858-867.

[15]

A. Lempel and J. Ziv, "On the Complexity of Finite Sequences", IEEE Transactions on Information Theory, Vol. 22, pp. 75-81.

Digital Library

[16]

A. Lempel and J. Ziv, "Compression of Two- Dimensional Images", Combinatorial Algorithms on Words, (A. Apostolico and Z. Galil, editors), 1985, pp. 141-154.

[17]

M.G. Main and R.J. Lorentz, "An O(nlog,) Algorithm for Finding all Repetitions in a String", J. of Algorithms, 1984, pp. 422-432.

Digital Library

[18]

V. S. Miller and M. N. Wegman, "Variations on a Theme by Lempel and Ziv", Combinatorial Algorithms on Words, (A. Apostolico and Z. Galil, editors), 1985, pp. 131-140.

[19]

J. Rissanen, "Stochastic Complexity", J. of the Royal Statistical Society, Series B, Vol. 49, 1987, pp. 223-239.

[20]

J. Rissanen and G.G. Langdon, "Arithmetic Coding'', IBM JournM of Research and Development, Vol. 23, 1979, pp. 149-162.

[21]

H. Samet, The Design and Analysis of Spatial Data Structures, Addison-Wesley, 1990.

Digital Library

[22]

B. Schieber and U. Vishkin, "On Finding Lowest Common Ancestors: Simplification and Parallelization', SIAM J. Comput., Vol. 17, 1988, pp. 1253-1262.

Digital Library

[23]

J. A. Sto~er, :'Lossy On-Line dynamic Data Compression", Sequences: Combinatorics, Compression, Security, and Transmission, (R. M. Capocelli, editor), Springer-Verlag, 1990, pp. 348-357.

Digital Library

[24]

U. Vishkin, "Optimal Parallel Pattern Matching in Strings", Information and Control, Vol. 67, 1985, pp. 91-113.

Digital Library

[25]

U. Vishkin, "Deterministic Sampling-a new technique for fast pattern matching", SIAM J. Comput., Vol. 20, 1991, pp. 303-314.

Digital Library

[26]

P. Weiner, "Linear Pattern Matching Algorithms", Proc. 14tb IEEE Symposium on Switching and Automata Theory, 1973, pp. 1-11.

[27]

T. A. Welch, "A Technique for High-Performance Data Compression", IEEE Computer, Vol. 17, 1984, pp. 8-19.

Cited By

Gamard GRichomme GShallit JSmith T(2017)Periodicity in rectangular arraysInformation Processing Letters10.1016/j.ipl.2016.09.011118:C(58-63)Online publication date: 1-Feb-2017
https://dl.acm.org/doi/10.1016/j.ipl.2016.09.011
Marcus SSokol D(2017)2D Lyndon Words and ApplicationsAlgorithmica10.1007/s00453-015-0065-z77:1(116-133)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.1007/s00453-015-0065-z
Brimkov V(2014)Parallel Algorithms for Combinatorial Pattern MatchingProceedings of the 16th International Workshop on Combinatorial Image Analysis - Volume 846610.1007/978-3-319-07148-0_2(8-16)Online publication date: 28-May-2014
https://dl.acm.org/doi/10.1007/978-3-319-07148-0_2
Show More Cited By

Index Terms

Two-dimensional periodicity and its applications
1. Information systems
  1. Data management systems
    1. Data structures
      1. Data layout
        Data compression
2. Theory of computation
  1. Design and analysis of algorithms
    1. Data structures design and analysis
      1. Pattern matching

Recommendations

Two-Dimensional Periodicity in Rectangular Arrays

String matching is rich with a variety of algorithmic tools. In contrast, multidimensional matching has had a rather sparse set of techniques. This paper presents a new algorithmic technique for two-dimensional matching: periodicity analysis . Its ...
Two-dimensional periodicity and matching algorithms
Periodicity and Permanence of Two Prey-One Predator Model with Infinite Delay
ICIC '12: Proceedings of the 2012 Fifth International Conference on Information and Computing Science

This paper studies a nonautonomous predator-prey system with two compete prey predated by one predator and infinite delay. By using differential equation Comparability Theorem and Continuation theorem based on Coincidence degree theory, we obtain the ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

SODA '92: Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms

September 1992

472 pages

ISBN:089791466X

Chairman:
Greg Frederickson

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIAM: Society for Industrial and Applied Mathematics

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 10 October 2019

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

23
Total Citations
View Citations
142
Total Downloads

Downloads (Last 12 months)72
Downloads (Last 6 weeks)10

Reflects downloads up to 15 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Gamard GRichomme GShallit JSmith T(2017)Periodicity in rectangular arraysInformation Processing Letters10.1016/j.ipl.2016.09.011118:C(58-63)Online publication date: 1-Feb-2017
https://dl.acm.org/doi/10.1016/j.ipl.2016.09.011
Marcus SSokol D(2017)2D Lyndon Words and ApplicationsAlgorithmica10.1007/s00453-015-0065-z77:1(116-133)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.1007/s00453-015-0065-z
Brimkov V(2014)Parallel Algorithms for Combinatorial Pattern MatchingProceedings of the 16th International Workshop on Combinatorial Image Analysis - Volume 846610.1007/978-3-319-07148-0_2(8-16)Online publication date: 28-May-2014
https://dl.acm.org/doi/10.1007/978-3-319-07148-0_2
Marcus SSokol D(2013)On Two-Dimensional Lyndon WordsProceedings of the 20th International Symposium on String Processing and Information Retrieval - Volume 821410.1007/978-3-319-02432-5_24(206-217)Online publication date: 7-Oct-2013
https://dl.acm.org/doi/10.1007/978-3-319-02432-5_24
Bille P(2009)Fast Searching in Packed StringsProceedings of the 20th Annual Symposium on Combinatorial Pattern Matching - Volume 557710.5555/3127091.3127102(116-126)Online publication date: 22-Jun-2009
https://dl.acm.org/doi/10.5555/3127091.3127102
Bille PFagerberg RGørtz I(2009)Improved approximate string matching and regular expression matching on Ziv-Lempel compressed textsACM Transactions on Algorithms10.1145/1644015.16440186:1(1-14)Online publication date: 28-Dec-2009
https://dl.acm.org/doi/10.1145/1644015.1644018
Apostolico AParida LRombo S(2008)Motif patterns in 2DTheoretical Computer Science10.1016/j.tcs.2007.10.019390:1(40-55)Online publication date: 1-Jan-2008
https://dl.acm.org/doi/10.1016/j.tcs.2007.10.019
Bille PFagerberg RGørtz I(2007)Improved approximate string matching and regular expression matching on Ziv-Lempel compressed textsProceedings of the 18th annual conference on Combinatorial Pattern Matching10.5555/2394373.2394384(52-62)Online publication date: 9-Jul-2007
https://dl.acm.org/doi/10.5555/2394373.2394384
Fredriksson KNikitin F(2007)Simple compression code supporting random access and fast string matchingProceedings of the 6th international conference on Experimental algorithms10.5555/1768570.1768592(203-216)Online publication date: 6-Jun-2007
https://dl.acm.org/doi/10.5555/1768570.1768592
Fredriksson KGrabowski S(2006)A general compression algorithm that supports fast searchingInformation Processing Letters10.1016/j.ipl.2006.04.020100:6(226-232)Online publication date: 31-Dec-2006
https://dl.acm.org/doi/10.1016/j.ipl.2006.04.020
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents