算法与计算机科学blog.notdot.net编辑精选
超酷算法：Levenshtein 自动机
Damn Cool Algorithms: Levenshtein Automata
2010 — 2022，它一次次回到首页
黑点是上首页（≥ 50 分）的那次投稿，空心点是没冲上去的投稿，点越大分数越高。
导读
本文介绍 Levenshtein 自动机：把“与查询词的编辑距离不超过 k”这一约束编码成自动机，用于在词典或索引中快速找出近似字符串。它属于作者的 Damn Cool Algorithms 系列，重点讲这种自动机的构造思路，以及它为何能避免对每个候选词都做一遍动态规划。
为什么经久不衰：它把模糊字符串匹配变成可用自动机/索引高效处理的问题，是拼写纠错、搜索 fuzzy 查询等场景的经典基础，因而多年后仍值得读。
HN 评论精选
指出漏掉了 Myers 位向量算法，它利用寄存器并行可更高效地计算编辑距离，并提到相关文献和带状优化。
不清楚为什么这些比较里没有包括 1999 年的 Myers 位向量算法。它一次能处理整个 32 位或 64 位寄存器，复杂度其实是 O(NM/w)，实际上接近 O(N)，而且能直接得到完整的编辑距离。Heikki Hyyrö 在 2001–2005 年前后的论文和博士论文里有伪代码，可移植到低级语言并推广编辑距离；多精度算术还能把它扩展到字母表很大的语言。生物信息学/DNA 分析似乎也注意到了它。另外还有“带状”算法，按 Ukkonen 1985 限制距离 < k 后，即使经典 DP 编辑距离也能提前退出（注意不是后缀树算法）。
cb321查看英文原文
Not sure why the Myers bit vector algorithm from 1999 is not included in these comparisons. Since it can operate on whole 32-bit or 64-bit registers at a time, it is really O(NM/w) which is in effect just O(N) and just gives you the whole edit distance. Heikki Hyyrö has a few papers and a PhD thesis from circa 2001..2005 that walk you through this in pseudo-code that you could port to any low level language and also generalize the edit distance. Multi-precision arithmetic also allows extending to languages with big words over the alphabet in question. It seems to at least not have escaped the attention of biologists/DNA analyzers in bioinformatics [1]. There are also "banded" algorithms that can exit early even with the classic dynamic programming edit distance if you just limit distances to < k after Ukkonen 1985 (No, NOT the suffix tree algorithm). https://www.ncbi.nlm.nih.gov/pmc/articles/PMC5408825/
提出该算法在“大语料、多查询串”场景下如何使用的疑问。
如何用它在大型固定语料库中查找一个小字符串（或与它相近的字符串）？通常的需求是在大语料库中查找许多小字符串。
amelius查看英文原文
How would you use this to find a small string (or string close to it) in a large fixed corpus? Usually you want to find many small strings in a large corpus.
说明 Elasticsearch 的 fuzzy 查询已采用该技术，值得在内存/关系型数据场景中了解。
很酷的技巧！补充一下：Elasticsearch 在使用 `fuzzy` 查询时就实现了这一技术；如果你要在内存或关系型数据里做类似的事，了解它很重要。
btown查看英文原文
A really cool trick! FYI Elasticsearch implements this technique when you use the `fuzzy` query: https://www.elastic.co/guide/en/elasticsearch/guide/master/fuzzy-query.html - but it's important to know about if you ever want to do this with in-memory or relational data!
实际在 RediSearch 的 Trie 中实现过，说明它适合内存搜索。
我前不久在 RediSearch 中实现过它，并把它集成进 Trie。这是一个非常强大的算法。
dvirsky查看英文原文
I've implemented this a while ago as part of RediSearch and integrated into a Trie. This is a super powerful algorithm. https://github.com/RedisLabsModules/RediSearch/tree/master/src/trie
历次讨论
同类还值得读
位运算技巧集
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编辑精选