Top

Published in:

2020 | OriginalPaper | Chapter

Fast Multiple Pattern Cartesian Tree Matching

Authors : Geonmo Gu, Siwoo Song, Simone Faro, Thierry Lecroq, Kunsoo Park

Published in: WALCOM: Algorithms and Computation

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Cartesian tree matching is the problem of finding all substrings in a given text which have the same Cartesian trees as that of a given pattern. In this paper, we deal with Cartesian tree matching for the case of multiple patterns. We present two fingerprinting methods, i.e., the parent-distance encoding and the binary encoding. By combining an efficient fingerprinting method and a conventional multiple string matching algorithm, we can efficiently solve multiple pattern Cartesian tree matching. We propose three practical algorithms for multiple pattern Cartesian tree matching based on the Wu-Manber algorithm, the Rabin-Karp algorithm, and the Alpha Skip Search algorithm, respectively. In the experiments we compare our solutions against the previous algorithm [18]. Our solutions run faster than the previous algorithm as the pattern lengths increase. Especially, our algorithm based on Wu-Manber runs up to 33 times faster.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Angle Covers: Algorithms and Complexity

next chapter Generalized Dictionary Matching Under Substring Consistent Equivalence Relations

Aho, A.V., Corasick, M.J.: Efficient string matching: an aid to bibliographic search. Commun. ACM 18(6), 333–340 (1975)MathSciNetCrossRef

Berkman, O., Schieber, B., Vishkin, U.: Optimal doubly logarithmic parallel algorithms based on finding all nearest smaller values. J. Algorithms 14(3), 344–370 (1993)MathSciNetCrossRef

Boyer, R.S., Moore, J.S.: A fast string searching algorithm. Commun. ACM 20(10), 762–772 (1977)CrossRef

Charras, C., Lecroq, T., Pehoushek, J.D.: A very fast string matching algorithm for small alphabets and long patterns. In: Farach-Colton, M. (ed.) CPM 1998. LNCS, vol. 1448, pp. 55–64. Springer, Heidelberg (1998). https://doi.org/10.1007/BFb0030780CrossRef

Chhabra, T., Tarhio, J.: Order-preserving matching with filtration. In: Gudmundsson, J., Katajainen, J. (eds.) SEA 2014. LNCS, vol. 8504, pp. 307–314. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-07959-2_26CrossRef

Commentz-Walter, B.: A string matching algorithm fast on the average. In: Maurer, H.A. (ed.) ICALP 1979. LNCS, vol. 71, pp. 118–132. Springer, Heidelberg (1979). https://doi.org/10.1007/3-540-09510-1_10CrossRef

Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to algorithms second edition. The Knuth-Morris-Pratt Algorithm (2001)

Crochemore, M., Czumaj, A., Gasieniec, L., Lecroq, T., Plandowski, W., Rytter, W.: Fast practical multi-pattern matching. Inf. Process. Lett. 71(3–4), 107–113 (1999)MathSciNetCrossRef

Ganguly, A., Hon, W.K., Sadakane, K., Shah, R., Thankachan, S.V., Yang, Y.: Space-efficient dictionaries for parameterized and order-preserving pattern matching. In: 27th Annual Symposium on Combinatorial Pattern Matching (CPM), pp. 2:1–2:12. LIPIcs (2016)

10.

Han, M., Kang, M., Cho, S., Gu, G., Sim, J.S., Park, K.: Fast multiple order-preserving matching algorithms. In: Lipták, Z., Smyth, W.F. (eds.) IWOCA 2015. LNCS, vol. 9538, pp. 248–259. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-29516-9_21CrossRefMATH

11.

Hua, N., Song, H., Lakshman, T.: Variable-stride multi-pattern matching for scalable deep packet inspection. In: IEEE INFOCOM 2009, pp. 415–423. IEEE (2009)

12.

Karp, R.M., Rabin, M.O.: Efficient randomized pattern-matching algorithms. IBM J. Res. Dev. 31(2), 249–260 (1987)MathSciNetCrossRef

13.

Kim, J., et al.: Order-preserving matching. Theor. Comput. Sci. 525, 68–79 (2014)MathSciNetCrossRef

14.

Knuth, D.E.: The Art of Computer Programming, volume 2: Seminumerical algorithms. Addison-Wesley Professional, Boston (2014)

15.

Kubica, M., Kulczyński, T., Radoszewski, J., Rytter, W., Waleń, T.: A linear time algorithm for consecutive permutation pattern matching. Inf. Process. Let. 113(12), 430–433 (2013)MathSciNetCrossRef

16.

Liao, H.J., Lin, C.H.R., Lin, Y.C., Tung, K.Y.: Intrusion detection system: a comprehensive review. J. Netw. Comput. Appl. 36(1), 16–24 (2013)CrossRef

17.

Liu, J.N., Kwong, R.W.: Automatic extraction and identification of chart patterns towards financial forecast. Appl. Soft Comput. 7(4), 1197–1208 (2007)CrossRef

18.

Park, S., Amir, A., Landau, G.M., Park, K.: Cartesian tree matching and indexing. In: 30th Annual Symposium on Combinatorial Pattern Matching (CPM), pp. 16:1–16:14. LIPIcs (2019)

19.

Song, S., Ryu, C., Faro, S., Lecroq, T., Park, K.: Fast cartesian tree matching. In: Brisaboa, N.R., Puglisi, S.J. (eds.) SPIRE 2019. LNCS, vol. 11811, pp. 124–137. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-32686-9_9CrossRef

20.

Song, T., Zhang, W., Wang, D., Xue, Y.: A memory efficient multiple pattern matching architecture for network security. In: IEEE INFOCOM 2008-The 27th Conference on Computer Communications, pp. 166–170. IEEE (2008)

21.

Vuillemin, J.: A unifying look at data structures. Commun. ACM 23(4), 229–239 (1980)MathSciNetCrossRef

22.

Wu, S., Manber, U.: A fast algorithm for multi-pattern searching. Technical report. TR-94-17, Department of Computer Science, University of Arizona (1994)

Title: Fast Multiple Pattern Cartesian Tree Matching
Authors: Geonmo Gu
Siwoo Song
Simone Faro
Thierry Lecroq
Kunsoo Park
Publisher: Springer International Publishing
Book: WALCOM: Algorithms and Computation
Print ISBN: 978-3-030-39880-4

Electronic ISBN: 978-3-030-39881-1

Copyright Year: 2020
DOI: https://doi.org/10.1007/978-3-030-39881-1_10

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner