English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

Indexing highly repetitive texts --- such as genomic databases, softwarerepositories and versioned text collections --- has become an important problemsince the turn of the millennium. A relevant compressibility measure forrepetitive texts is $r$, the number of runs in their Burrows-Wheeler Transform(BWT). One of the earliest indexes for repetitive collections, the Run-LengthFM-index, used $O(r)$ space and was able to efficiently count the number ofoccurrences of a pattern of length $m$ in the text (in loglogarithmic time perpattern symbol, with current techniques). However, it was unable to locate thepositions of those occurrences efficiently within a space bounded in terms of$r$. Since then, a number of other indexes with space bounded by other measuresof repetitiveness --- the number of phrases in the Lempel-Ziv parse, the sizeof the smallest grammar generating the text, the size of the smallest automatonrecognizing the text factors --- have been proposed for efficiently locating,but not directly counting, the occurrences of a pattern. In this paper we closethis long-standing problem, showing how to extend the Run-Length FM-index sothat it can locate the $occ$ occurrences efficiently within $O(r)$ space (inloglogarithmic time each), and reaching optimal time $O(m+occ)$ within$O(r\log(n/r))$ space, on a RAM machine of $w=\Omega(\log n)$ bits. Within$O(r\log (n/r))$ space, our index can also count in optimal time $O(m)$.Raising the space to $O(r w\log_\sigma(n/r))$, we support count and locate in$O(m\log(\sigma)/w)$ and $O(m\log(\sigma)/w+occ)$ time, which is optimal in thepacked setting and had not been obtained before in compressed space. We alsodescribe a structure using $O(r\log(n/r))$ space that replaces the text andextracts any text substring of length $\ell$ in almost-optimal time$O(\log(n/r)+\ell\log(\sigma)/w)$. (...continues...)

Optimal-Time Text Indexing in BWT-runs Bounded Space