算法与计算机科学swtch.com编辑精选
Google Code Search 如何工作：用三元组索引进行正则匹配（2012）
How Google Code Search Worked: Regex Matching with a Trigram Index (2012)
2012 — 2024，它一次次回到首页
黑点是上首页（≥ 50 分）的那次投稿，空心点是没冲上去的投稿，点越大分数越高。
导读
这篇由 Russ Cox 撰写的文章解释 Google Code Search 如何用 trigram（三字符）索引来加速正则表达式搜索：从正则中提取可能出现的 trigram，用索引快速筛出候选文档，再对候选执行精确的正则匹配。它展示了在超大代码库上做正则搜索时，如何用简单的索引结构把全量扫描变成可行的候选过滤。
为什么经久不衰：它把看似昂贵的正则搜索拆成可理解的索引过滤问题，方案简单优雅，对今天的代码搜索和全文检索设计仍有启发。
HN 评论精选
想了解 trigram 索引的实现细节，以及是否有现成库或数据库可用。
有没有关于如何实现 trigram 索引这一侧的好文章？例如代码里暗示可以把每个 trigram 存成覆盖文档的位图，这样布尔组合就变成位运算。我想可以用压缩（甚至概率草图）形式保存位图，只在查询需要时解压，但这是不是正确的直觉？有没有底层库或数据库擅长做这种事，而不是自己在 KV 存储上造轮子或用 ElasticSearch 这种庞然大物？
btown查看英文原文
Are there any good writeups on how to implement the trigram index side of this? For instance, the code alludes to the idea that you could store each trigram as a bitmap over documents, then the Boolean combinations become bitwise operations. I suppose you could keep the bitmaps in compressed (or even probabilistic sketch) form, then decompress only those required for a query, but is this the right intuition? Are there lower-level libraries or databases that do this kind of thing well, rather than rolling your own on a KV store or using something monstrous like ElasticSearch?
提供了基于该思路的实际开源实现和论文参考。
自荐一下：Debian Code Search 就是基于这个做的：https://codesearch.debian.net/ 。如果感兴趣，细节见 https://codesearch.debian.net/research/bsc-thesis.pdf 。
secure查看英文原文
Shameless plug: This is what I based Debian Code Search on: https://codesearch.debian.net/ See also https://codesearch.debian.net/research/bsc-thesis.pdf if you’re interested in details.
提出另一种做法：先把正则展开成候选词做全文检索，再过滤精确匹配。
有趣的方案。我在 searchco.de 实现正则搜索时做法略有不同：比如正则 [cb]at，我把它展开成所有候选词 cat 和 bat，再基于这些词做标准全文搜索得到尽量接近的结果，然后遍历结果取精确匹配。实际更复杂，但加上中缀和前缀索引等技巧后效果不错，虽然还有些小问题要修。
boyter查看英文原文
Interesting solution. I did something a little different for searchco.de when I was implementing regex search. Essentially I took the regex such as [cb]at and then expand it out to get all of the terms, in this case cat and bat and then do a standard fulltex search based on those terms to get as close a match as possible. I then loop over the results to get back those which are exact matches. Its actually more complex then that but with some other trickery (infix and prefix indexing) but it works reasonably well although I am still ironing out some kinks.
惋惜 Google Code Search 被关闭，认为它作为学习工具价值巨大且无人替代。
Google 关掉 Code Search 是个错误。索引全世界的源代码并让它可搜索，显然是其核心使命的一部分，我很好奇这个决定是怎么做出的。代码搜索在人数上或许是小众市场，但在智力和经济上（考虑到软件的经济影响）很重要。Google 做得比所有人都好，完全占据了这个领域，运行它的成本怎么可能不值得？现在我们失去了好东西。我以前这样用 Google Code Search：遇到陌生的语言或 API 构造，就去代码搜索，一页页看真实用法；或者想知道怎么做 X，就想象实现 X 的代码会怎么写，搜索片段直到找到可工作的例子。它是一个强大的学习工具，失去它让我难过。希望有创业公司能把全世界的源代码搜索做好。GitHub 应该做，但它的搜索很糟。总之，祝贺 Russ Cox 等人做出了一项出色的工作。
gruseom查看英文原文
Google made a mistake in killing code search. Indexing the world's source code and making it searchable is so obviously part of their core mission that I wonder how this decision even got made. Yeah, code search is a niche market numerically speaking, but intellectually and economically (considering the economic impact of software) it is vital. Google was doing so much better a job of it than anybody else that they completely owned the space. How could that not be worth what it cost them to run it? And now we are bereft of anything good. I used to use Google Code Search like this: encounter an unfamiliar language or API construct, go to code search, get page after page of real-world usages. Or like this: wonder how to do X, imagine what code that does X might say, search for snippets of that until hitting a working example of X. It was a powerful learning device that I am sad to lose. I sure hope a startup comes along to get search right for the world's source code. Github ought to, but their search sucks. In any case, congratulations Russ Cox et. al. on a brilliant piece of work.
历次讨论
同类还值得读
位运算技巧集
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编辑精选