2023-09-20
Frequency-constrained substring complexity
Publication
Publication
We introduce the notion of frequency-constrained substring complexity. For any finite string, it counts the distinct substrings of the string per length and frequency class. For a string x of length n and a partition of [n] in τ intervals, I = I1, . . . , Iτ , the frequency-constrained substring complexity of x is the function fx,I (i, j) that maps i, j to the number of distinct substrings of length i of x occurring at least αj and at most βj times in x, where Ij = [αj , βj ]. We extend this notion as follows. For a string x, a dictionary D of d strings (documents), and a partition of [d] in τ intervals I1, . . . , Iτ , we define a 2D array S = S[1 . . |x|, 1 . . τ ] as follows: S[i, j] is the number of distinct substrings of length i of x occurring in at least αj and at most βj documents, where Ij = [αj , βj ]. Array S can thus be seen as the distribution of the substring complexity of x into τ document frequency classes. We show that after a linear-time preprocessing of D, for any x and any partition of [d] in τ intervals given online, array S can be computed in near-optimal O(|x|τ log log d) time.
| Additional Metadata | |
|---|---|
| , , | |
| doi.org/10.1007/978-3-031-43980-3_28 | |
| Lecture Notes in Computer Science | |
| 30th International Symposium on String Processing and Information Retrieval, SPIRE 2023 | |
| Organisation | Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands |
|
Pissis, S., Shekelyan, M., Liu, C., & Loukides, G. (2023). Frequency-constrained substring complexity. In Proceedings of the International Symposium on String Processing and Information Retrieval (pp. 345–352). doi:10.1007/978-3-031-43980-3_28 |
|
