Monotonic run length text sampling and fake sampled positions
The Computer Journal · 23.07.2026
DOI: 10.1093/comjnl/bxag075 ↗Kurz gefasst
Fachartikel in der Zeitschrift The Computer Journal, online erschienen am 23.07.2026. Verfasst von Simone Faro und 4 weiteren Autor:innen. Die Arbeit nennt 43 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: National Centre for HPC, Big Data and Quantum Computing, ESFRI RI RESILIENCE.
Abstract (Originalsprache)
Text-sampling is an efficient approach for string matching problems introduced in order to overcome the prohibitive space requirements of indexed matching, on the one hand, and drastically reduce searching time for the online solutions, on the other hand. Known solutions to sampled string matching are very efficient in practical cases being able to improve standard online string matching algorithms up to $99.6$% using in the best cases $<1$% of the original text size when applied to natural languages combined with the condensed alphabet. In this paper we present our results obtained in an attempt to extend sampled-string matching to the general case of nonclassical string matching. Specifically, we introduce a new sampling approach that turns out to be suitable for both exact and nonclassical matching and evaluate it in the context of two specific cases of nonclassical matching, the order-preserving pattern matching problem and the Cartesian tree pattern matching problem. Our experimental results show that the new approach is extremely competitive both in terms of space and running time, and for both classical and nonclassical matching. We also discuss the applicability of the new approach to other different nonclassical string matching problems.
Förderung
- National Centre for HPC
- Big Data and Quantum Computing
- ESFRI RI RESILIENCE
Zitieren
APA
Faro, S., Lecroq, T., Marino, F. P., Pavone, A., & Scardace, A. (2026). Monotonic run length text sampling and fake sampled positions. The Computer Journal. https://doi.org/10.1093/comjnl/bxag075
Vancouver
Faro S, Lecroq T, Marino FP, Pavone A, Scardace A. Monotonic run length text sampling and fake sampled positions. The Computer Journal. 2026. doi:10.1093/comjnl/bxag075
BibTeX
@article{Faro2026,
author = {Faro, Simone and Lecroq, Thierry and Marino, Francesco Pio and Pavone, Arianna and Scardace, Antonio},
title = {Monotonic run length text sampling and fake sampled positions},
journal = {The Computer Journal},
year = {2026},
doi = {10.1093/comjnl/bxag075}
}
EUVIMED