Text-sampling is an efficient approach for the string matching problem re- cently introduced in order to overcome the prohibitive space requirements of indexed matching, on the one hand, and drastically reduce searching time for the online solu- tions, 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 less than 1% of the original text size. However at present text sampling is designed to work only in the case of exact string matching. In this paper we present some preliminary results obtained in the attempt to extend sampled-string matching to the general case of approximate string matching. Specifi- cally we introduce a new sampling approach which turns out to be suitable for both exact and approximate matching and evaluate it in the context of a specific case of approximate matching, the order preserving pattern matching problem. Our preliminary experimental results show that the new approach is extremely com- petitive both in terms of space and running time, and for both approximate and exact matching. We also discuss the applicability of the new approach to different approxim- ate string matching problems.

Faro S., Marino F.P., Pavone A., Scardace A. (2021). Towards an Efficient Text Sampling Approach for Exact and Approximate Matching. In Proceedings of the Prague Stringology Conference 2021 (pp. 75-89). Prague Stringology Club.

Towards an Efficient Text Sampling Approach for Exact and Approximate Matching

Pavone A.;
2021-01-01

Abstract

Text-sampling is an efficient approach for the string matching problem re- cently introduced in order to overcome the prohibitive space requirements of indexed matching, on the one hand, and drastically reduce searching time for the online solu- tions, 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 less than 1% of the original text size. However at present text sampling is designed to work only in the case of exact string matching. In this paper we present some preliminary results obtained in the attempt to extend sampled-string matching to the general case of approximate string matching. Specifi- cally we introduce a new sampling approach which turns out to be suitable for both exact and approximate matching and evaluate it in the context of a specific case of approximate matching, the order preserving pattern matching problem. Our preliminary experimental results show that the new approach is extremely com- petitive both in terms of space and running time, and for both approximate and exact matching. We also discuss the applicability of the new approach to different approxim- ate string matching problems.
2021
Settore INF/01 - Informatica
978-80-01-06869-4
Faro S., Marino F.P., Pavone A., Scardace A. (2021). Towards an Efficient Text Sampling Approach for Exact and Approximate Matching. In Proceedings of the Prague Stringology Conference 2021 (pp. 75-89). Prague Stringology Club.
File in questo prodotto:
File Dimensione Formato  
Pubblicazione 2021-PSC.pdf

Solo gestori archvio

Tipologia: Versione Editoriale
Dimensione 218.37 kB
Formato Adobe PDF
218.37 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10447/640680
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? ND
social impact