算法与理论计算机2017arxiv.org
确定性线性时间内空间高效地构建压缩索引
Space-Efficient Construction of Compressed Indexes in Deterministic Linear Time
专业 · 约 120 分钟读完前置知识：字符串算法、后缀数组/树、LZ77 压缩
导读
这篇论文研究如何在确定性线性时间内、以较低空间构造压缩索引，核心涉及 LZ77 解析以及搜索所需的数据结构，目标是严格证明 O(n) 时间与空间界。它属于理论算法结果，能否实用还要看常数因子和后续算法工程；共同作者认为该算法易于并行化，有落地潜力。
HN 关注点：焦点是：这个理论上的线性时间压缩索引结果到底实不实用、常数因子多大，以及工程化和并行化前景如何。
HN 评论精选
这几条评论里：支持 1 质疑 1 亲历 2
支持称赞论文经同行评审，并指出其同时改进了线性时间 LZ77 和搜索索引构造。
这看起来非常棒。根据 Google Scholar，它经过了同行评审。能改进压缩（线性时间 LZ77）已经很酷，但它不仅做到这一点，还能计算搜索索引数据结构。
zitterbewegung查看英文原文
This looks really awesome. According to google scholar it went through peer review. Seeing that it would improve compression (linear time LZ77) would be cool but not only does it do that but also compute search index data structures. https://scholar.google.com/scholar?hl=en&q=Space-Efficient+Construction+of+Compressed+Indexes+in+Deterministic+Linear+Time&btnG=&as_sdt=1%2C14&as_sdtp=
亲历共同作者回应：这是理论结果，实用化需算法工程，但算法易并行、已有实现尝试。
我是论文共同作者之一。是的，这是一篇理论论文，因此展示重点在于证明可以达到相应的大 O 复杂度。有些理论论文永远不会实用，但我们相信这篇可以；不过这需要大量算法工程，把重要的理论思想用常识实现，用实践中更好、即使达不到最坏情况复杂度的模块替换理论上漂亮但无用的模块。一个有希望的点是算法容易并行化（批量查询）。我的一位有多线程和紧凑数据结构经验的博士后已经在做实现。至于最终 LZ 解析算法竞争力如何，我不敢断言。我们也有过理论结果看似难以实现、但经过算法工程后表现很好的经验，比如 top-k 文档检索工作，以及 FM-index 从早期常数很大到 BWA 等实现。
gnavarro69查看英文原文
Hi, a note from one of the coauthors of the paper ;-) Yes, it is a theoretical paper and then the presentation focuses on what is needed in such a paper: to establish that the big-Oh complexity can be reached. Some theoretical papers will never become practical, but we believe this one can. However, this will require a fair amount of algorithm engineering, to take the important theoretical ideas and implement them with common sense, changing theoretically appealing but practically useless modules by others that work better, even if they do not reach the desired worst-case complexity. A promising aspect of this algorithm is that it is easily parallelizable (the batched queries). A postdoc of mine that has experience in multithreading and compact data structures is already working on this. I won't dare to say how competitive will be the resulting LZ-parsing algorithm, though. We have had some experiences with good theoretical results whose implementation looks unsurmountable but that turned out to work very well after some algorithm engineering. An example is our work on top-k document retrieval: http://epubs.siam.org/doi/abs/10.1137/140998949 http://dl.acm.org/citation.cfm?id=3043958 Another well-known case is the first paper on the FM-index, with constants like sigma^sigma multiplying the space, and its current realizations, e.g. Burrows-Wheeler Aligner. In this case, I think it will not be that hard, but still it will not be a matter of just translating the algorithm into code. Best, Gonzalo
质疑质疑理论复杂度之外的实际常数因子，询问是否实用。
有没有深入读过论文的人能评论一下这个结果是否实用？因为这是理论计算机科学论文，很难判断常数因子是否可接受；很多理论 CS 论文给出渐近最优或显著改进的算法，但常数因子大得离谱（比如矩阵乘法）。
pzh查看英文原文
Can somebody who read the paper in depth comment on whether the result is practical or not? Since it's a TCS paper, it's hard to gauge whether the constant factors are palatable or not, and there are many theoretical CS papers that give asymptotically optimal or significantly improved algorithms that have astronomical constant factors (e.g. matrix multiplication, etc.)
亲历分享后缀数组工具 sary 的实际使用经验，说明此类索引的实用价值。
我很久以前玩过后缀数组。我想加速对 GB 级文本文件的 grep。那个工具叫 sary（suffix array 的缩写），至今还在一个被遗忘的 SourceForge 页面上。它很好用，能在超大文件里瞬间找到任意子串。
visarga查看英文原文
I used to play with suffix arrays a long time ago. I wanted to accelerate grep on a gigabyte text file. The tool was called "sary" (short for suffix array) and still exists on a forgotten SourceForce page. Good tool, it was able to find any substring in a huge file instantly.
相关资源
从这篇论文所有 HN 讨论帖的全部评论里整理出来的链接。
历次讨论
- 2017Hacker News 讨论帖197 分 · 40 评
同领域还值得读
哲学家为何应关注计算复杂性
Why Philosophers Should Care About Computational Complexity (2011)
Scott Aaronson 的这篇长文论证计算复杂性理论（如 P vs NP、停机问题的复杂度视角）对哲学问题（如知识的本质、中文房间、水槽论证等）具有实质意义，而不仅是技术细…
算法与理论计算机2015 · 552 分 · 120 评进阶 · 约 90 分钟编辑精选通信的数学理论
A Mathematical Theory of Communication
是香农1948年的《通信的数学理论》，为通信建立数学框架：把信息量定义为不确定性或自由度（信息熵），并讨论信源编码、信道容量与可靠传输。
算法与理论计算机2020 · 495 分 · 91 评进阶 · 约 120 分钟编辑精选物理、拓扑、逻辑与计算：罗塞塔石碑
Physics, Topology, Logic and Computation: A Rosetta Stone (2009)
用范畴论充当“罗塞塔石碑”，试图在量子物理、拓扑、逻辑与计算四个领域之间建立统一的结构性类比：物理中的量子过程、拓扑中的配边、逻辑中的证明和计算中的程序，都可被视为某类范畴中的态…
算法与理论计算机2009 · 390 分 · 55 评 · 引用 13专业 · 约 180 分钟编辑精选一种快速、极小内存的一致性哈希算法
A Fast, Minimal Memory, Consistent Hash Algorithm
论文给出一种快速、省内存的一致哈希方案，目标是在桶数量变化时保持较小的键迁移成本，同时降低计算和内存开销。
算法与理论计算机2014 · 327 分 · 57 评 · 引用 4进阶 · 约 25 分钟编辑精选第五个 Busy Beaver 值的确定
Determination of the fifth Busy Beaver value
宣布确定了第五个 Busy Beaver 值 BB(5)：即 5 状态图灵机中停机前运行步数最多的机器（Champion）在 47,176,870 步后停机。
算法与理论计算机2025 · 288 分 · 116 评 · 引用 1专业 · 约 75 分钟编辑精选