Efficient Computation of Periods and Covers Using Sampling
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910848940769280 |
|---|---|
| author | Lecroq, Thierry Marino, Francesco Pio |
| author_facet | Lecroq, Thierry Marino, Francesco Pio |
| contents | Identifying regularities in strings, such as \emph{periods} and \emph{covers}, is crucial for applications in text compression, computational biology, and pattern recognition. \emph{Characters-Distance-Sampling} (\texttt{CDS}) is an efficient technique that encodes a string by storing distances between selected pivot characters, accelerating string-processing tasks.
We apply \texttt{CDS} to compute periods and shortest covers, selecting only the first character as the pivot. This strategy yields optimized computations, achieving speedups of $38\%$--$43\%$ for period computation and $63\%$--$72\%$ for cover detection. These results demonstrate the potential of \texttt{CDS}-based representations for efficient string analysis and broader applications. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_18216 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Efficient Computation of Periods and Covers Using Sampling Lecroq, Thierry Marino, Francesco Pio Data Structures and Algorithms Identifying regularities in strings, such as \emph{periods} and \emph{covers}, is crucial for applications in text compression, computational biology, and pattern recognition. \emph{Characters-Distance-Sampling} (\texttt{CDS}) is an efficient technique that encodes a string by storing distances between selected pivot characters, accelerating string-processing tasks. We apply \texttt{CDS} to compute periods and shortest covers, selecting only the first character as the pivot. This strategy yields optimized computations, achieving speedups of $38\%$--$43\%$ for period computation and $63\%$--$72\%$ for cover detection. These results demonstrate the potential of \texttt{CDS}-based representations for efficient string analysis and broader applications. |
| title | Efficient Computation of Periods and Covers Using Sampling |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2407.18216 |