按年被提到
20162017 · 2 次2026
算法与数据结构›哈希、压缩与向量化·arXiv:1607.04346 · cs.DS

Space-Efficient Construction of Compressed Indexes in Deterministic Linear Time

J. Ian Munro, Gonzalo Navarro, Yakov Nekrich · 2016
开始阅读 ↗PDFalphaXiv 讨论
被提及 · 3 人首次 2017-05-14 · 最近 2020-01-08
3不同的人
2活跃月份
3讨论串
0被引(OpenAlex)
arXiv 摘要(候选层不写导读)

We show that the compressed suffix array and the compressed suffix tree of a string $T$ can be built in $O(n)$ deterministic time using $O(n\logσ)$ bits of space, where $n$ is the string length and $σ$ is the alphabet size. Previously described deterministic algorithms either run in time that depends on the alphabet size or need $ω(n\log σ)$ bits of working space. Our result has immediate applications to other problems, such as yielding the first linear-time LZ77 and LZ78 parsing algorithms that use $O(n \logσ)$ bits.

候选层:至少 2 个不同的人、在 2 个不同月份提到过,还没到主书架的 3 人 3 个月。没有做立场标注,所以只写“被提及”。

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
评论edward_rolf · 2017-05

“This is very interesting to me. What's the other one? Edit: no worries: found it [0]. So much to read today if you wanna stay ajour with indexing and compression. https://arxiv.org/abs/1607.04346”

Compressed Computation for Text Indexing (2016) [pdf]原评论 ↗
评论kragen · 2020-01

“They're pretty new! I think the first linear-time suffix-sorting algorithm was the "skew algorithm" introduced in "Linear work suffix array construction," J. Kärkkäinen, P. Sanders, and S. Burkhardt. Journal of the ACM, 53(6):918–936, 2006, although I think Kärkkäinen and Sanders published it in 2003 ("Simple linear work suffix array construction", J.C.M…”

Finding unique items: hash vs. sort原评论 ↗
被提交为 story · 1 次