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 Plus annual

Presents the access of premium content as premium feature

Premium Content

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 Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Grammar based compression, where one replaces a long string by a smallcontext-free grammar that generates the string, is a simple and powerfulparadigm that captures many popular compression schemes. In this paper, wepresent a novel grammar representation that allows efficient random access toany character or substring without decompressing the string.  Let $S$ be a string of length $N$ compressed into a context-free grammar$\mathcal{S}$ of size $n$. We present two representations of $\mathcal{S}$achieving $O(\log N)$ random access time, and either $O(n\cdot \alpha_k(n))$construction time and space on the pointer machine model, or $O(n)$construction time and space on the RAM. Here, $\alpha_k(n)$ is the inverse ofthe $k^{th}$ row of Ackermann's function. Our representations also efficientlysupport decompression of any substring in $S$: we can decompress any substringof length $m$ in the same complexity as a single random access query andadditional $O(m)$ time. Combining these results with fast algorithms foruncompressed approximate string matching leads to several efficient algorithmsfor approximate string matching on grammar-compressed strings withoutdecompression. For instance, we can find all approximate occurrences of apattern $P$ with at most $k$ errors in time $O(n(\min\{|P|k, k^4 + |P|\} + \logN) + occ)$, where $occ$ is the number of occurrences of $P$ in $S$. Finally, wegeneralize our results to navigation and other operations on grammar-compressedordered trees.  All of the above bounds significantly improve the currently best knownresults. To achieve these bounds, we introduce several new techniques and datastructures of independent interest, including a predecessor data structure, two"biased" weighted ancestor data structures, and a compact representation ofheavy paths in grammars.

Random Access to Grammar Compressed Strings