×

Simpler FM-index for parameterized string matching. (English) Zbl 1506.68017

Summary: In parameterized string matching, a string comprises static and parameterized symbols. Two strings are said to be matched if there exists a one-to-one mapping of parameterized symbols onto itself such that it transforms one string into the other. Traditionally, to construct a full-text index for this problem, suffixes are transformed in a manner referred to as previous occurrence encoding. Although a space-efficient backward searching based data structure has been proposed recently, the data structure is specialized and complex owing to the nature of the encoding scheme. In this study, we demonstrate that a slight modification of the encoding scheme, by using \(\infty\) instead of 0 to denote the first occurrences of each parameterized symbol, enables us to develop a much simpler FM-index for this problem, which only comprises two wavelet trees and one range maximum query index.

MSC:

68P05 Data structures
68W32 Algorithms on strings
Full Text: DOI

References:

[1] Baker, B. S., Parameterized pattern matching: algorithm and applications, J. Comput. Syst. Sci., 52, 28-42 (1996) · Zbl 0849.68019
[2] Ganguly, A.; Shah, R.; Thankachan, S., pbwt: achieving succinct data structures for parameterized pattern matching and related problems, (Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (2017)), 397-407 · Zbl 1410.68098
[3] Ferragina, P.; Manzini, G., Opportunistic data structures with applications, (Proceedings of the 41st Annual Symposium on Foundation of Computer Science (2000)), 390-398
[4] Grossi, R.; Gupta, A.; Vitter, J. S., High-order entropy-compressed text indexes, (Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (2003)), 841-850 · Zbl 1092.68584
[5] Fischer, J.; Heun, V., Space-efficient preprocessing schemes for range minimum queries on static arrays, SIAM J. Comput., 40, 2, 465-492 (2011) · Zbl 1222.05024
[6] Burrows, M.; Wheeler, D. J., A block-sorting lossless data compression algorithm (1994), Digital Equipment Corporation, Tech. rep.
[7] Navarro, G., Wavelet trees for all, J. Discret. Algorithms, 25, 2-20 (2014) · Zbl 1284.68217
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.