算法与计算机科学blog.burntsushi.net
用有限状态机作为表示有序集合与映射的数据结构
Finite state machines as data structure for representing ordered sets and maps
2015 — 2021，它一次次回到首页
黑点是上首页（≥ 50 分）的那次投稿，空心点是没冲上去的投稿，点越大分数越高。
导读
BurntSushi 的经典长文，讲解如何用有限状态机（FSA/FST）作为数据结构来表示有序集合和映射：通过把 trie 压缩成 DAG 并最小化，可以共享前后缀状态，从而紧凑地存储字符串集合或键值映射。文章还介绍了 FST 中边携带输出值、沿路径累加得到查询结果的机制。
为什么经久不衰：它把编译原理中的自动机理论变成了实用的数据结构教程，是 Lucene 等系统背后的核心思想，多年后仍是理解紧凑有序映射的最佳入门材料。
HN 评论精选
提供全文的 Cliff Notes 式精要总结
文章内容很有意思但相当啰嗦，这里给个精简版：trie 是存储字符串集合或字符串键映射的著名数据结构。可以把 trie 压缩成 DAG/FSM 而不是树，这样后缀也能共享状态（树只能共享前缀）。但对大规模集合，对整个 trie 做最小化代价太高；如果按键有序插入，就可以廉价地边构建边最小化。如果是映射而非集合，这个 DAG 就叫 FST（有限状态转换器），每条边携带一个值并累加进最终结果，例如值为整数时每条边就是加到结果上的整数。在保持转换器不变式的同时共享前后缀状态，算法上需要更多技巧。
haberman查看英文原文
Interesting stuff. The article is quite verbose -- here is the Cliff Notes versions: The trie is a well-known data structure for storing string sets or string-keyed maps (https://en.wikipedia.org/wiki/Trie). You can compress a trie by using a DAG/FSM instead of a tree -- this lets you share states for suffixes, whereas trees only let you share states for prefixes. But for large sets minimizing a DAG is too expensive to perform on the whole trie. If you insert the keys in-order, you can minimize the DAG on-the-fly much more cheaply. If you have a map instead of a set, the DAG is called a FST (finite state tranducer) instead of a finite state acceptor. In this case every edge has some value that you accumulate into the final result. For example, if the map values are integers, each edge can be an integer that is added to the final result. It takes a bit more cleverness in the algorithm to share prefix/suffix states while maintaining the tranducer invariants.
指出同义名称 DAWG 并附 JS 实现参考
这种结构也叫 DAWG（有向无环词图）。John Resig 五年前写过一篇讨论类似问题的博客，我为它写了一个 JavaScript 实现。
mckoss查看英文原文
Also called DAWGs (Directed Acyclic Word Graphs [1]). John Resig blogged about a similar problem 5 years ago, for which I wrote a JavaScript solution [2]. [1] https://en.m.wikipedia.org/wiki/Directed_acyclic_word_graph [2] https://github.com/mckoss/lookups
推荐 OpenFst 库
好文章。Google 有一个这方面非常出色的库，值得一读：OpenFst。
blackkettle查看英文原文
Nice article. Google has an incredible library for this stuff which is also worth checking out: http://www.openfst.org
类比 GADDAG，并指出 FST 不可变的弱点
用无环图存储信息的 FST 机制很像拼字游戏词典用的 GADDAG 结构。我在研究压缩领域时发现很多基因组学研究建议把压缩算法与查找方法结合，因为识别样本间的公共项既减少存储又加快查找。文中提到 FST 一旦生成就无法修改，这确实是这类简洁数据结构的普遍弱点：删除数据很困难（维护一个“已删除集合”容易些，但删除后重新添加会有问题）。
gopalv查看英文原文
The FST mechanism for using an acyclic graph to store information is very reminiscent of GADDAG[1] structure for Scrabble dictionaries. In my search for interesting problems in the compression space, I ran into quite a lot of genomics research which suggests combining a compression algorithm with a lookup method, because identifying common items between samples reduces both storage and speeds up lookup. > An FST based data structure as presented in this article does not have this capability. Namely, once it is produced, it cannot be changed. That is somewhat of a weakness in general for succinct data structures of this sort, which makes it harder to remove data (much easier to maintain a "deleted set" to go with it, but that has problems with a delete + re-add). [1] - https://en.wikipedia.org/wiki/GADDAG
历次讨论
同类还值得读
位运算技巧集
Bit Twiddling Hacks
斯坦福页面上的经典位运算技巧合集，收录了 popcount、前导/尾随零、位反转、交换、舍入等大量技巧，并附有解释和性能讨论。
算法与计算机科学上首页 8 次 · 2011–2024graphics.stanford.edu编辑精选如何不按平均评分排序
How Not To Sort By Average Rating
经典文章解释了为什么按平均评分排序不可靠：只有少量评价的条目（比如仅一条五星）会轻易排到最前，而评价数量的差异被忽略。
算法与计算机科学上首页 7 次 · 2009–2024evanmiller.org编辑精选数据结构可视化
Data Structure Visualizations
旧金山大学 David Galles 教授制作的数据结构与算法交互式可视化网站，涵盖 B 树、红黑树、排序、图算法等，可逐步操作观察其运行过程。
算法与计算机科学上首页 6 次 · 2011–2021cs.usfca.edu编辑精选1996 年以来的计算机科学最佳论文奖
Best Paper Awards in Computer Science since 1996
Jeff Huang 维护的一个汇总页面，收录了自 1996 年以来计算机科学各主要会议的“最佳论文奖”获奖名单，并按年份和会议整理，方便读者一站式浏览历届获奖论文。
算法与计算机科学上首页 6 次 · 2010–2018jeffhuang.com编辑精选算法（Jeff Erickson）
Algorithms, by Jeff Erickson
伊利诺伊大学 Jeff Erickson 教授的算法课教材，免费在线开放。
算法与计算机科学上首页 5 次 · 2018–2022jeffe.cs.illinois.edu编辑精选