EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Monotonic run length text sampling and fake sampled positions

Simone Faro, Thierry Lecroq, Francesco Pio Marino, Arianna Pavone, Antonio Scardace

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →