codebase-comprehension-algorithms

社区代码库理解与领域映射算法最佳实践

一份面向实践者的参考指南，介绍如何将代码库映射到易于理解的功能／业务领域的有效算法。这些技术大多出自软件架构恢复与软件仓库挖掘领域的文献，日常开发者很少接触，却正是编码 Agent 每天需要完成的任务所适用的工具：“这个代码库做什么，分别在哪里实现？”

这 47 条规则按执行生命周期影响分类：流水线早期的错误决策（例如构建哪种图、保留哪些标识符）会影响所有后续环节。三个 CRITICAL 类别（graph-、clust-、valid-）中的错误无法在后续阶段补救。请先阅读这些内容。

范围：采用经过验证的算法，并提供同行评审文献或权威著作作为依据，包括 Newman 的 Networks、Leskovec-Rajaraman-Ullman 的 Mining of Massive Datasets、Ganter-Wille 的 Formal Concept Analysis，以及 40 多篇 ICSE / FSE / TSE / PNAS / JMLR 论文。不包括教程网站、Stack Overflow 和营销文章。有意留待未来版本介绍：GNN/CodeBERT/code2vec（尚未经过“数十年验证”）以及重构配方相关内容（由 react-refactor 和 typescript-refactor 等相关技能涵盖）。

适用场景

在以下情况下使用这些规则：

• 帮助 Agent 熟悉陌生代码库：“按领域说明这个代码库的功能”
• 生成架构图：“主要子系统有哪些？它们如何连接？”
• 定位功能：“哪些文件实现了支付／身份验证／搜索？”
• 审查重构：“此更改是否遵循了架构边界？”
• 检测架构债务：“哪些文件存在意料之外的耦合？”
• 验证现有分解是否合理：“README 中的架构是否与代码相符？”
• 为上述任一任务选择算法——用户需要的是经过验证的方案，而不是凭感觉

按优先级排列的规则类别

#	类别	前缀	影响	功能
1	图构建与边权重	graph-	CRITICAL	构建哪种图；无处不在的过滤器；环处理；多层图
2	社区检测与聚类	clust-	CRITICAL	Leiden、Infomap、SBM、MCL、Walktrap、谱聚类、HDBSCAN
3	验证与质量指标	valid-	CRITICAL	MoJoFM、ARI/NMI、分辨率限制、共识、协同变更预测、消融研究
4	标识符与词法预处理	lex-	HIGH	Samurai 拆分、缩写扩展、TF-IDF/BM25、词干提取、动宾结构解析
5	软件专用架构恢复	arch-	HIGH	Bunch + MQ、ACDC、Limbo、Reflexion、DSM
6	源代码主题建模	topic-	HIGH	LDA、LSI/SVD、NMF、HDP、基于一致性的 K 值选择
7	演化耦合与协同变更挖掘	evol-	HIGH	提升度／置信度／支持度、大型提交过滤、时间衰减、逻辑耦合
8	信息论方法	info-	MEDIUM-HIGH	归一化压缩距离、互信息、MDL、代码自然度
9	中心性、层次结构与标注	rank-	MEDIUM	PageRank、HITS、介数中心性、TextRank/YAKE 标签

快速参考

1. 图构建与边权重（关键）

• graph-filter-omnipresent-utilities-before-clustering — 在聚类前移除日志记录器和基类（可提升 20–40 个 MoJoFM 点）
• graph-pick-edge-type-by-question-asked — 调用、导入、共同变更、二部图——问题决定图的类型
• graph-collapse-sccs-before-clustering — Tarjan 强连通分量凝聚可明确表示循环，并让每种算法都更稳定
• graph-weight-edges-by-information-content — 在边上使用 IDF / PMI / Jaccard 可抑制噪声（MoJoFM 提升 2–5 倍）
• graph-bipartite-file-term-for-joint-structure — 适用于依赖注入 / 动态分派导致调用图被隐藏的情况
• graph-combine-signals-in-multilayer-graphs — 在归一化的 α 加权层上使用 Mucha 2010 多层模块度

2. 社区检测与聚类（关键）

• clust-leiden-not-louvain — Louvain 会在 5–25% 的节点上产生不连通的社区（Traag 2019）
• clust-infomap-mdl-on-random-walks — 对随机游走应用 MDL；适用于强调流量含义的图
• clust-stochastic-block-model — 贝叶斯、分层，可从数据中学习 K；能处理非同配结构
• clust-mcl-markov-clustering — 流量模拟；在生物信息学中占主导地位；抗噪能力强
• clust-walktrap-short-random-walks — 随机游走距离 + 层次凝聚聚类
• clust-spectral-laplacian-fiedler — 通过拉普拉斯矩阵特征向量求最优 k 路归一化割
• clust-hdbscan-density-based — 在文件嵌入上而非图上进行聚类时使用

3. 验证与质量指标（关键）

• valid-mojofm-as-software-clustering-distance — SAR 的黄金标准距离指标（Wen-Tzerpos 2004）
• valid-adjusted-rand-index-and-nmi — 经随机机会校正的跨算法比较
• valid-be-aware-of-resolution-limit — 模块度无法识别小于 √(2m) 的簇（Fortunato-Barthélemy PNAS 2007）
• valid-consensus-clustering-for-stability — 单次运行的结果并不可靠；多次运行的共识结果才是正确答案
• valid-cochange-prediction-as-ground-truth-proxy — 使用时间上留出的共同变更替代缺失的真实标签
• valid-ablate-each-input-signal — 逐一剔除输入信号；揭示实际驱动结果的因素

4. 标识符与词法预处理（高）

• lex-split-identifiers-with-samurai — 精确率达 87%，而朴素的驼峰命名拆分为 60%（Enslen MSR 2009）
• lex-build-programming-language-stop-words — 三层结构：关键字 + 通用词 + 基于 IDF 的词
• lex-expand-abbreviations-with-context — usr → user，ctx → context（Lawrie GenTest 2011）
• lex-tf-idf-and-bm25-on-identifiers — 常见词会主导原始计数；TF-IDF / BM25 可以解决这一问题
• lex-stem-versus-subword-tokenization — 聚类使用 Porter 词干提取器，嵌入使用 BPE
• lex-extract-verb-object-pattern-from-method-names — getUserById →（动词=get，对象=user）；复合概念信号

5. 软件专用架构恢复（高）

• arch-bunch-with-mq-fitness — MQ 适应度函数 + 搜索；在代码上优于 Q 最大化
• arch-acdc-subgraph-patterns — 子系统与骨架模式；符合架构师的直觉
• arch-limbo-information-bottleneck — 将 Tishby 的 IB 应用于软件（Andritsos-Tzerpos 2005）
• arch-reflexion-model — 对比假设与实际情况；Murphy-Notkin 1995 提出却鲜少使用的瑰宝
• arch-dsm-partitioning — 设计结构矩阵；已有 60 年历史的工程技术

6. 源代码主题建模（高）

• topic-lda-on-source-code — 基于标识符和注释文本生成逐文件的概率主题分布
• topic-lsi-svd-on-term-document — 基于 SVD 的确定性语义嵌入（Maletic-Marcus 2001）
• topic-nmf-non-negative-factorization — 基于部分的加性主题，完全可复现
• topic-hdp-for-nonparametric-topic-count — 层次狄利克雷过程——从数据中学习 K
• topic-pick-topic-count-by-coherence-not-perplexity — 困惑度与人类评估的主题质量呈负相关

7. 演化耦合与协同变更挖掘（高）

• evol-mine-cochange-with-lift-and-confidence — Lift > 2 是分界值；原始协同变更计数只是噪声
• evol-filter-large-commits — 一次涉及 200 个文件的提交会产生 20K 个虚假的配对计数；应严格筛选
• evol-temporal-decay-on-edge-weights — 按 6 个月半衰期进行指数衰减
• evol-logical-coupling-as-architectural-signal — 最强耦合中有 30-50% 无法通过静态分析发现（Gall 1998）

8. 信息论方法（中高）

• info-normalized-compression-distance — 无需特征工程即可聚类；基于 gzip 的通用相似度
• info-mutual-information-as-coupling — 能捕捉 Lift 无法发现的非线性 / 条件耦合
• info-mdl-for-model-selection — 有原则地选择 K；将奥卡姆剃刀作为代码长度
• info-naturalness-of-code-as-quality-signal — Hindle 2012——代码的可预测性比英语高 30-50%；出现错误时熵会激增

9. 中心性、层级与标注（中等）

• rank-pagerank-for-module-importance — 在反向依赖图上使用 PageRank，找出架构主干
• rank-hits-hubs-and-authorities — 区分编排器与实现（Kleinberg 1999）
• rank-betweenness-centrality-for-bottlenecks — 找出领域间的桥接点；检测上帝类
• rank-textrank-for-cluster-labels — 使用多词关键短语作为聚类标签（Mihalcea-Tarau 2004，YAKE 2020）

如何使用

从 Agent 要回答的问题入手：

• “这个代码库有哪些主要领域？” → graph-（选择一种图）→ clust-（Leiden / Infomap / SBM）→ topic-（为它们添加标签）→ valid-（检查稳定性并进行消融）
• “哪些文件实现了功能 X？” → 使用 topic-lda-on-source-code 定位主题；将 X 的文件作为种子，使用 rank-pagerank-for-module-importance 进行个性化 PageRank
• “架构主干在哪里？” → 在依赖图上使用 rank-pagerank-for-module-importance + rank-hits-hubs-and-authorities
• “README 中描述的架构与代码是否一致？” → arch-reflexion-model 专为此用途打造
• “这里真正的耦合是什么（超出静态依赖之外）？” → evol-logical-coupling-as-architectural-signal 和 evol-mine-cochange-with-lift-and-confidence
• “如何在不设计特征的情况下进行聚类？” → info-normalized-compression-distance
• “聚类规模应该有多大？” → valid-be-aware-of-resolution-limit 和 topic-hdp-for-nonparametric-topic-count
• “如何判断我的分解是否正确？” → 整个 valid- 类别；必须使用多代理评估

本技能的理念：首先构建正确的图（并过滤无处不在的文件），选择与图和问题相匹配的算法，在词汇信号重要时使用针对代码的预处理流程（Samurai + 停用词 + 词干提取 + TF-IDF），并且始终进行验证——如果有专家提供的真实基准数据，就使用 MoJoFM；如果没有，就使用共识 + 共变更预测 + 消融。

代码示例使用 Python 编写，因为参考实现（networkx、igraph、leidenalg、scikit-learn、gensim、graph-tool、hdbscan）都基于 Python。相关思路也适用于任何语言。

参考文件

文件	描述
references/_sections.md	类别定义与排序
assets/templates/_template.md	新规则模板
metadata.json	版本和参考信息
AGENTS.md	自动生成的目录导航

相关技能

• computer-science-algorithms — 算法与数据结构参考（本技能会在 MinHash/LSH、Aho-Corasick 等方面交叉引用它）
• complexity-optimizer — 对本规则识别出的热点路径进行静态分析
• design-to-react-algorithms — 用于设计到代码结构恢复的配套技能