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

We present a simple adaptation of the Lempel Ziv 78' (LZ78) compressionscheme ({\em IEEE Transactions on Information Theory, 1978}) that supportsefficient random access to the input string. Namely, given query access to thecompressed string, it is possible to efficiently recover any symbol of theinput string. The compression algorithm is given as input a parameter $\eps>0$, and with very high probability increases the length of the compressedstring by at most a factor of $(1+\eps)$. The access time is $O(\log n +1/\eps^2)$ in expectation, and $O(\log n/\eps^2)$ with high probability. Thescheme relies on sparse transitive-closure spanners. Any (consecutive)substring of the input string can be retrieved at an additional additive costin the running time of the length of the substring. We also formally establishthe necessity of modifying LZ78 so as to allow efficient random access.Specifically, we construct a family of strings for which $\Omega(n/\log n)$queries to the LZ78-compressed string are required in order to recover a singlesymbol in the input string. The main benefit of the proposed scheme is that itpreserves the online nature and simplicity of LZ78, and that for {\em every}input string, the length of the compressed string is only a small factor largerthan that obtained by running LZ78.

A simple online competitive adaptation of Lempel-Ziv compression with efficient random access support