AI 与机器学习norvig.com编辑精选
如何写一个拼写纠正器
How to Write a Spelling Corrector
2007 — 2022，它一次次回到首页
黑点是上首页（≥ 50 分）的那次投稿，空心点是没冲上去的投稿，点越大分数越高。
导读
Peter Norvig 用一个几十行的 Python 程序演示如何做拼写纠正：先用编辑距离（删除、插入、替换、换位）生成所有可能的候选词，再用从大量文本中统计出的词频概率，选出最可能的那个，并附上数据集与简单测试。全文把看似困难的现实问题拆成"生成候选 + 概率排序"两步，代码极短但完整可跑。
为什么经久不衰：它示范了真正的工程思维——用极少代码把直觉变成可验证的模型，二十多年来始终是学习贝叶斯式思路与问题拆解的经典入门读物。
HN 评论精选
编程教育应教如何思考与表达想法，而不是背语法、抄示例。
读到这篇文章，我忍不住想到我见过的那些 K-12 编程教育项目，只能摇头。Norvig 做的正是我们该教的：有条理地攻克一个看似极难的问题，把直觉翻译成代码，仔细构建论证，并思考如何扩展。这才是真正的工程师。而我见过的"编程"教育，大多是让孩子痛苦地记一堆语法细节，然后在他们成功复制老师演示的东西后，称他们为程序员、天才、计算机科学家。读 Norvig 的代码（我也很粉他的数独那篇）你会发现，代码本身其实是次要的，它真正做的是表达一个想法——一个细腻优雅的想法，但终究是硬思考和探索的产物。
ChicagoBoy11查看英文原文
I couldn't help but read this and think about all the "coding" initiatives I've seen in K-12 and shake my head. What Norvig is doing is what we should be teaching. He is tackling this seemingly REALLY hard problem by thinking about it methodically, translating some intuition into code, carefully constructing an argument about how to solve it, and ways that it could be extended. This is what actual engineers look like. Everything I've seen around "coding" though has become a masochistic exercise in teaching kids random syntax details and then calling them Coders and Geniuses and Computer Scientists when they successfully copy what the teacher showed them. When you read Norvig's code (big fan of his Sudoku one as well), you realize how the actual "code" is secondary in the sense that what it is really doing is expressing an idea. A very nunanced, elegant idea, but ultimately the product of doing some hard thinking and exploration on a problem domain. If we taught kids to just think about problems in this way, ohh what a world it would be!
只做删除并对称应用到查询侧，可大幅提速、缩小索引且不依赖字母表。
最近为一个项目研究这个方向时，我偶然发现了对 Norvig 思路的这个改进（faroo 博客）：它出奇地简单，简单到你会懊恼自己怎么没想到——如果对称地把同样的变换也应用到查询一侧，那么只生成删除操作（而不是插入和替换）也能达到"生成所有变体"的效果。比如词典里有 "cat"，你想匹配查询 "cast"，不必往语料里加 "cast"，而是在查询侧删掉 s（以及每个其他单字母），依然能匹配。结果快得多、索引小得多，还额外的好处是不再绑死在某个特定字母表上。
apendleton查看英文原文
While doing a bunch of research on exactly this problem space recently for a project, I stumbled onto this improvement on the Norvig corrector idea http://blog.faroo.com/2012/06/07/improved-edit-distance-based-spelling-correction/ that's one of those things that's so deceptively simple you kick yourself for not thinking of it: it turns out you can model the same "generate all the variations" effect but generating only the deletes, rather than also the insertions and substitutions, if you symmetrically apply the same transformation to the lookup side. So if your dictionary contains "cat" and you want to match queries for "cast," rather than adding "cast" to the corpus, you drop the s (and every other single letter) on the lookup side instead, and still match. Turns out it's much faster and, requires a much smaller index, and as a bonus, doesn't tie you to a specific alphabet like Norvig's approach does.
Trie+Levenshtein 比暴力枚举快，且同距离候选需靠用户行为统计来排序。
做 Typesense 时我正好深入过这个领域。只要你想实现拼写纠正，就绕不开 Norvig 这篇出色的文章（据说大部分是在一趟无聊的航班上写的！）。它巧妙简洁，但论原始速度，把词表建成 Trie 再用 Levenshtein 距离遍历要快得多，因为 Trie 能砍掉大量 Norvig 暴力法会做的无用查找。另一个有趣的点是统计角度：你常会遇到与目标词编辑距离相同的多个词，必须靠某种"热度指标"来排序——比如人们输入这个词后改成另一个词的次数，这正是 Google 拥有、并让它的搜索建议和拼写检查如此直觉的数据。
karterk查看英文原文
This has been an area of interest for me as part of working on Typesense[1]. If you are looking to implement spelling correction, you cannot but not stumble on this excellent post by Peter Norvig (most of it written on a bored flight journey!). While it's clever and concise, in terms of raw speed, indexing your vocabulary in a Trie, and then doing a traversal on it using a Levenshtein distance is way faster[2]. By using a trie, you eliminate lot of unwanted look-ups that Peter Norvig's brute-force approach takes. The other interesting thing for me personally about this problem is that there is a statistical angle as well. You will often find words that are of the same edit distance from a given target word -- you will need to rely on some form of "popularity metric" to rank those tied corrections. E.g. how many times did people type this word and then change it to another word - that's precisely the kind of data that Google has and which makes its search suggestions and spell checking so intuitive. [1]: https://typesense.org/ [2]: http://stevehanov.ca/blog/index.php?id=114
自动纠正在多语言与特殊搜索场景下常常是有害的，不该替用户改意图。
真正让我恼火的是"自动纠正"而非"检查/建议"。一旦你有国际用户（在互联网上你大概总有）或有非英文内容，自动纠正可能变成对用户有害的"功能"。尤其在搜索引擎上，我有时在搜其他语言的词、混合语言的结果，甚至故意搜拼错的词。在我的母语荷兰语里，他的第一个例子就会出问题："spelling" 与英文同义，但 "speling" 意为余量/裕度（名词），我不想其中一个被自动纠正成另一个。Facebook 上人名的模糊搜索让搜索几乎没用，尤其当你搜的是某个常见名字的少见变体时——真正要找的人肯定排在几十亿条垃圾结果之后。这种替用户二次猜测、"你想做 A，但我们猜你想做 B，所以就做 B"的风气，是我最讨厌的东西之一。
shdon查看英文原文
Spelling correction rather than spell checking and suggestions really bugs me. As soon as you have a somewhat international audience (and given that this is the internet - you probably do) or have any non-English content, automatic correction can be an actively user-hostile "feature". Especially on search engines, sometimes I am searching for words in another language, mixed-language results, or even doing an intentional search for misspelt words. In my native Dutch his first example would already cause problems: "spelling" means the same as in English, but "speling" means margin/give (the noun) and I wouldn't want one to be auto-corrected to the other. The fuzzy search for names on Facebook makes the search pretty much worthless especially in case you have an unusual variant of a common name in your search - you can be sure the actual person you're looking for is listed after half a billion bogus results. The whole trend of second-guessing the user and saying "you tried to do A, but we assume you meant B, so we're gonna do B instead" is one of my biggest pet peeves.
历次讨论
同类还值得读
面向黑客的概率编程与贝叶斯方法
Probabilistic Programming and Bayesian Methods for Hackers (2013)
《黑客的贝叶斯方法与概率编程》是一本开源的贝叶斯统计入门书，以 Python/PyMC 代码和交互式 Jupyter Notebook 为主线，强调“先实践、后数学”的学习路径，…
AI 与机器学习上首页 5 次 · 2013–2018camdavidsonpilon.github.io编辑精选神经网络黑客指南
Hacker's Guide to Neural Networks
Andrej Karpathy 写的神经网络入门教程，面向程序员，从最简单的表达式求导讲起，逐步推导出反向传播和梯度下降，最后引出神经网络。
AI 与机器学习上首页 4 次 · 2014–2019karpathy.github.io编辑精选神经网络能逼近任意函数的可视化证明
A visual proof that neural nets can approximate any function
这一章来自 Michael Nielsen 的在线书《Neural Networks and Deep Learning》，用 sigmoid 单元叠加成局部隆起/平滑阶跃的图示…
AI 与机器学习上首页 4 次 · 2014–2022neuralnetworksanddeeplearning.com编辑精选论乔姆斯基与统计学习的两种文化
On Chomsky and the Two Cultures of Statistical Learning
Norvig 回应 Chomsky 对统计语言模型批评的文章，围绕“统计学习能否解释语言”展开，比较生成与解释、少参数模型与 Shannon 式高参数统计模型。
AI 与机器学习上首页 4 次 · 2011–2025norvig.com编辑精选语音与语言处理（第三版草稿，2017）
Speech and Language Processing, 3rd ed. draft (2017)
Jurafsky 与 Martin 经典教材《Speech and Language Processing》第三版草稿的官方页面，按章提供 PDF，覆盖语音识别、自然语言处理与语…
AI 与机器学习上首页 4 次 · 2018–2025web.stanford.edu编辑精选