Parameterized text indexing with one wildcard
Presented at the 2019 Data Compression Conference, DCC 2019 (March 2019), Snowbird, Utah, USA
Two equal-length strings X and Y over an alphabet Σ of size σ are a parameterized match iff X can be transformed to Y by renaming the character X[i] to the character Y[i] for 1 ≤ i ≤ |X| using a one-to-one function from the set of characters in X to the set of characters in Y. The parameterized text indexing problem is defined as: Index a text T of n characters over an alphabet set Σ of size σ, such that whenever a pattern P[1, p] comes as a query, we can report all occ parameterized occurrences of P in T. A position i [1, n] is a parameterized occurrence of P in T, iff P and T[i,(i+p-1)] are a parameterized match. We study an interesting generalization of this problem, where the pattern contains one wildcard character φ ∉ Σ that matches with any other character in Σ. Therefore, for a pattern P[1, p] = P1φP2, our task is to report all positions i in T, such that the string P_1 P_2 and the string obtained by concatenating T[i,(i+|P1|-1)] and T[(i+|P1|+1),(i+p-1)] are a parameterized match. We show that such queries can be answered in optimal O(p+occ) time per query using an O(n log n) space index. We then show how to compress our index into O(n log σ) space but with a higher query cost of O(p(log log n+logσ)+occ logσ).
|Keywords||Heavy Path, Parameterized Text Indexing, Succinct Data Structures, Suffix Tree, Wildcard|
|Conference||2019 Data Compression Conference, DCC 2019|
Ganguly, A, Hon, W.-K, Huang, Y.-A, Pissis, S, Shah, R, & Thankachan, S.V. (2019). Parameterized text indexing with one wildcard. In Data Compression Conference Proceedings (pp. 152–161). doi:10.1109/DCC.2019.00023