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

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

In this paper, we present a new data structure called the packed compact trie(packed c-trie) which stores a set $S$ of $k$ strings of total length $n$ in $n\log\sigma + O(k \log n)$ bits of space and supports fast pattern matchingqueries and updates, where $\sigma$ is the size of an alphabet. Assume that$\alpha = \log_\sigma n$ letters are packed in a single machine word on thestandard word RAM model, and let $f(k,n)$ denote the query and update times ofthe dynamic predecessor/successor data structure of our choice which stores $k$integers from universe $[1,n]$ in $O(k \log n)$ bits of space. Then, given astring of length $m$, our packed c-tries support pattern matching queries andinsert/delete operations in $O(\frac{m}{\alpha} f(k,n))$ worst-case time and in$O(\frac{m}{\alpha} + f(k,n))$ expected time. Our experiments show that ourpacked c-tries are faster than the standard compact tries (a.k.a. Patriciatrees) on real data sets. As an application of our packed c-trie, we show thatthe sparse suffix tree for a string of length $n$ over prefix codes with $k$sampled positions, such as evenly-spaced and word delimited sparse suffixtrees, can be constructed online in $O((\frac{n}{\alpha} + k) f(k,n))$worst-case time and $O(\frac{n}{\alpha} + k f(k,n))$ expected time with $n \log\sigma + O(k \log n)$ bits of space. When $k = O(\frac{n}{\alpha})$, by usingthe state-of-the-art dynamic predecessor/successor data structures, we obtainsub-linear time construction algorithms using only $O(\frac{n}{\alpha})$ bitsof space in both cases. We also discuss an application of our packed c-tries toonline LZD factorization.

ieice transactions on fundamentals of electronics, communications and computer sciences/ieice transactions on fundamentals of electronics, communications and computer science

Packed Compact Tries: A Fast and Efficient Data Structure for Online String Processing