Linguistic Semantic Algorithms

pproenca Linguistic and Semantic Algorithms Best Practices

Reference of 40 algorithms an agent should reach for when extracting structure, meaning, history, or risk signals from source code and commit data. Categories are ordered by insight-per-effort — how much non-obvious truth the technique exposes relative to how easy it is to apply. The first two categories target the highest-leverage questions: what business entities live in this code? and where else does this concept already exist? — questions that grep and intuition cannot answer.

When to Apply

Reach for these algorithms when:

• Orienting in an unfamiliar codebase: PageRank the import graph to find the core, run LDA over identifier tokens to discover business themes, mine change coupling to surface hidden architectural couplings.
• Hunting a bug from a description: BM25 + history prior + embedding re-rank produces a ranked file shortlist far better than grep.
• Scoping a feature: find prior PRs that did similar work via embedding similarity; map the feature's vocabulary against the codebase's domain via TF-IDF and noun-phrase mining.
• Reviewing a refactor: AST-level GumTree diff reveals semantic impact text diff hides; PDG isomorphism finds the "same logic, different code" twin you should also update.
• Auditing risk: hotspots (churn × complexity), bus factor, defect-magnet density, dead-code candidates — together they direct attention to the parts of the codebase that pay back attention.
• Identifying domain entities and bounded contexts: noun-phrase mining + TF-IDF rare-term extraction + Louvain communities + Jensen-Shannon divergence on per-cluster vocabulary.

Rule Categories by Priority

Quick Reference

1. Concept & Domain Extraction (CRITICAL)

• `concept-lda-topic-modeling` — LDA over identifier tokens surfaces latent business themes
• `concept-noun-phrase-mining` — POS-tag + chunk identifiers to extract entity candidates
• `concept-tfidf-rare-terms` — IDF against a generic corpus isolates domain vocabulary from framework noise
• `concept-identifier-cooccurrence-network` — PMI-weighted co-occurrence graph reveals conceptual neighborhoods
• `concept-entity-name-resolution` — Cluster name variants (user/usr/u/userAccount) via embedding + edit distance
• `concept-bounded-context-detection` — Louvain + Jensen-Shannon divergence detects DDD bounded contexts

2. Semantic Similarity & Feature Mapping (CRITICAL)

• `sim-codebert-embeddings` — CodeBERT + cosine for semantic code search across renames
• `sim-pdg-semantic-clones` — Program Dependence Graph isomorphism finds Type-4 clones
• `sim-cross-pr-feature-mapping` — Embed merged PRs once, retrieve precedent at feature-design time
• `sim-cosine-vsm-files` — TF-IDF VSM file similarity when no GPU is available
• `sim-call-pattern-similarity` — N-grams on call-sequence find behavioral twins
• `sim-doc-code-alignment` — Joint code-doc embedding flags drift between docs and code

3. Architectural Topology (HIGH)

• `graph-pagerank-core` — PageRank the import graph to find the codebase core
• `graph-betweenness-bottlenecks` — Betweenness centrality surfaces bottleneck modules
• `graph-louvain-modules` — Louvain community detection reveals natural module boundaries
• `graph-scc-cycle-tangles` — Tarjan's SCC algorithm exposes circular-dependency tangles
• `graph-feedback-arcs` — Eades-Lin-Smyth FAS chooses the smallest cycle-breaking cut

4. Co-Change & Temporal Mining (HIGH)

• `mine-change-coupling` — Conditional probability over commit history exposes hidden coupling
• `mine-hotspots-churn-complexity` — Churn × complexity = canonical hotspot score (Tornhill)
• `mine-bus-factor` — Per-file authorship Gini coefficient surfaces knowledge concentration
• `mine-commit-topic-modeling` — LDA on commit messages reveals quarterly themes
• `mine-bug-fix-density` — Classify commits, rank files by fix-density to find defect magnets
• `mine-codebase-aging` — Last-modified age + reachability splits stable code from dead code

5. Clone & Duplication Detection (MEDIUM-HIGH)

• `clone-minhash-lsh` — MinHash + LSH for sub-linear near-duplicate retrieval
• `clone-simhash` — SimHash 64-bit fingerprints for O(1) Hamming-distance lookups
• `clone-suffix-array-cpd` — Token-level suffix array (PMD CPD) for precise clone boundaries
• `clone-ast-gumtree` — GumTree algorithm for fine-grained AST differencing
• `clone-zhang-shasha-ted` — Zhang-Shasha tree edit distance for exact subtree similarity

6. Bug & Feature Localization (MEDIUM-HIGH)

• `local-tfidf-bug-reports` — TF-IDF rank source files against bug report tokens
• `local-bm25-saturation` — BM25 handles length normalization and TF saturation
• `local-history-prior-localization` — Bayesian fusion of IR score with bug-history prior
• `local-embedding-bug-text` — Two-stage BM25 + embedding re-rank for semantic localization

7. Identifier Linguistics (MEDIUM)

• `ling-camel-snake-split` — Split camelCase, snake_case, digit-boundaries before any analysis
• `ling-abbreviation-expansion` — Expand idx→index, mgr→manager via dictionary + mining
• `ling-porter-stemming` — Apply Porter stemmer to unify singular/plural forms
• `ling-pos-tagging-identifiers` — POS-tag identifier heads to flag misnamed functions/classes

8. Complexity & Risk Metrics (MEDIUM)

• `risk-cyclomatic-mccabe` — McCabe cyclomatic complexity for branch-test surface
• `risk-cognitive-complexity` — SonarSource Cognitive Complexity for readability gates
• `risk-halstead-volume` — Halstead volume for language-agnostic size and effort
• `risk-shannon-entropy-naming` — Per-token entropy flags overloaded names

How to Use

Pick the category that matches the user's question, then read one or two specific rules from that category. Most rules cite combinable partners ("Combine with mine-change-coupling...") that compound the signal — read the partner rule when you need higher precision.

For unfamiliar repos, the highest-ROI starting sequence is: 1. graph-pagerank-core → read the top-20 most central files 2. concept-lda-topic-modeling + concept-tfidf-rare-terms → identify the business themes 3. mine-hotspots-churn-complexity → find where the bugs concentrate 4. mine-change-coupling → uncover hidden architectural couplings

For a single-task bug or feature, the pipeline is: 1. local-bm25-saturation (broad candidates) → local-embedding-bug-text (semantic re-rank) → local-history-prior-localization (fix-history boost) 2. sim-cross-pr-feature-mapping for prior precedent on new features 3. mine-change-coupling to surface partner files that historically move together

Always preprocess identifier tokens via ling-camel-snake-split → ling-abbreviation-expansion → ling-porter-stemming before any vocabulary-based algorithm. Skipping this step silently degrades every downstream signal.

Cross-language parsing. Most rule code examples use Python's built-in ast module for brevity. For real cross-language work (Go, Rust, Java, TS, C++ in the same repo), use tree-sitter — it provides robust parsers for 40+ languages with a uniform API. Every AST-based rule in this skill (PDG clones, GumTree, Zhang-Shasha, POS-tag heads, identifier co-occurrence) maps cleanly onto tree-sitter ASTs.

Reference Files

Codebase Analysis Algorithms

Version 0.1.0 pproenca May 2026

Note:

This document is mainly for agents and LLMs applying Codebase Analysis Algorithms

when mapping, debugging, or refactoring codebases. Humans may also find it useful,

but guidance here is optimized for automation and consistency by AI-assisted workflows.

---

Abstract

Reference of 40 linguistic, semantic, statistical, and graph algorithms an AI agent should reach for when mapping an unfamiliar codebase, hunting bugs, scoping features, or analyzing commit history. Organized into 8 categories ordered by insight-per-effort — from concept and domain extraction (LDA, noun-phrase mining, TF-IDF rare-term extraction, entity resolution, bounded-context detection) and semantic similarity (CodeBERT embeddings, PDG isomorphism for Type-4 clones, call-pattern n-grams, doc-code alignment) through architectural topology (PageRank, betweenness, Louvain, SCC, feedback-arc-set), co-change mining (change coupling, hotspots, bus factor, commit-topic modeling), clone detection (MinHash, SimHash, suffix-array CPD, GumTree, Zhang-Shasha), bug-localization IR (TF-IDF, BM25, history priors, embedding re-rank), identifier-linguistic preprocessing (camel/snake split, abbreviation expansion, Porter stemming, POS tagging) to complexity metrics (cyclomatic, cognitive, Halstead, Shannon entropy on naming). Each rule contrasts the naive grep-or-eyeball approach with the algorithmic alternative, with production-realistic code in Python and references to canonical papers.

---

Table of Contents

1. Concept & Domain Extraction — CRITICAL

• 1.1 Build an Identifier Co-occurrence Graph to Reveal Conceptual Neighborhoods — HIGH (reduces noise from utility tokens via PMI-weighted edges)
• 1.2 Cluster Identifier Variants into Canonical Entities via Embedding plus Edit Distance — HIGH (deduplicates 30-50% of identifier vocabulary into canonical entity names)
• 1.3 Detect DDD Bounded Contexts via Louvain Communities Plus Vocabulary Divergence — HIGH (automatic detection of bounded-context candidates without manual partitioning)
• 1.4 Extract Noun Phrases from Identifiers to Find Candidate Domain Entities — CRITICAL (surfaces 80%+ of domain entities from naming alone)
• 1.5 Use LDA over Identifier Tokens to Surface Latent Domain Topics — CRITICAL (reduces a 100k-file codebase to 10-20 named topics in one pass)
• 1.6 Use TF-IDF Against a Generic Corpus to Separate Domain Vocabulary from Framework Noise — CRITICAL (eliminates 90%+ of framework terms from domain-vocabulary ranking)

2. Semantic Similarity & Feature Mapping — CRITICAL

• 2.1 Compare Functions by Call-Sequence N-grams to Find Behavioral Twins — MEDIUM-HIGH (reduces behavioral-clone search to set operations on call-trace n-grams)
• 2.2 Embed Documentation and Code in the Same Space to Detect Drift — MEDIUM-HIGH (automatic flagging of stale docs via joint code-doc embedding)
• 2.3 Find Type-4 Clones via Program Dependence Graph Isomorphism — HIGH (eliminates false negatives on Type-4 clones text and AST diff both miss)
• 2.4 Map New Feature Requests to Prior Pull Requests via Diff Embedding Similarity — HIGH (reduces a 1000-PR backlog to top-3 implementation precedents per feature)
• 2.5 Use CodeBERT Embeddings plus Cosine Similarity for Semantic Code Search — CRITICAL (enables semantic code search across renames, synonyms, and rewrites)
• 2.6 Use TF-IDF Vector Space Model for File Similarity When No GPU Is Available — MEDIUM-HIGH (enables semantic-ish file search at 100x lower cost than neural embeddings)

3. Architectural Topology — HIGH

• 3.1 Apply Louvain Community Detection to Reveal Natural Module Boundaries — HIGH (reduces O(N^2) modularity search to O(N log N) for module discovery)
• 3.2 Approximate Minimum Feedback Arc Set to Choose the Smallest Cycle-Breaking Cut — MEDIUM-HIGH (minimizes edits required to make the import graph acyclic)
• 3.3 Run PageRank on the Import Graph to Find the Codebase Core — HIGH (ranks the 1% of files that everything depends on)
• 3.4 Use Betweenness Centrality to Find Bottleneck Modules — HIGH (prevents brittle refactors by surfacing bottleneck modules)
• 3.5 Use Strongly Connected Components to Find Dependency Cycle Tangles — HIGH (reveals every cyclic import group in O(V+E) — Tarjan's algorithm)

4. Co-Change & Temporal Mining — HIGH

• 4.1 Compute Change Coupling from Git History to Find Hidden Architectural Couplings — HIGH (directly affects refactor scope by exposing cross-layer coupling static analysis misses)
• 4.2 Compute Per-File Bus Factor from Authorship Concentration — MEDIUM-HIGH (prevents key-person dependencies from surprising the team mid-incident)
• 4.3 Multiply Churn by Complexity to Find the Real Bug Hotspots — HIGH (ranks files where bugs concentrate — 80% of defects in 20% of files)
• 4.4 Plot Per-File Age Distribution to Separate Stable Code from Forgotten Code — MEDIUM (eliminates dead-code candidates that static analysis alone cannot confirm)
• 4.5 Rank Files by Bug-Fix Density to Find Defect Magnets — MEDIUM-HIGH (identifies files where 50%+ of commits are bug fixes)
• 4.6 Run LDA on Commit Messages to Discover the Real Themes of Recent Work — MEDIUM-HIGH (reduces 5000 quarterly commits to 5-10 named themes for retrospectives)

5. Clone & Duplication Detection — MEDIUM-HIGH

• 5.1 Compute Zhang-Shasha Tree Edit Distance for Subtree Similarity Scoring — MEDIUM (O(n^2 · m^2) tree distance — the exact baseline behind every approximate clone tool)
• 5.2 Use MinHash plus LSH to Find Near-Duplicate Code at Repository Scale — MEDIUM-HIGH (reduces O(n^2) pairwise Jaccard to sub-linear retrieval at 10k+ files)
• 5.3 Use SimHash 64-bit Fingerprints for Constant-Time Similarity Lookups — MEDIUM-HIGH (reduces a file to a 64-bit fingerprint with O(1) Hamming distance)
• 5.4 Use the GumTree Algorithm for Fine-Grained AST Differencing — MEDIUM-HIGH (reduces a 240-line text diff to 4 semantic AST actions on typical refactors)
• 5.5 Use Token-Level Suffix Arrays for Precise Clone Boundary Detection — MEDIUM-HIGH (finds clone boundaries in O(n log n) with exact location and length)

6. Bug & Feature Localization — MEDIUM-HIGH

• 6.1 Boost IR Scores with a Bug-History Prior for Better Localization Precision — MEDIUM (improves top-10 bug-localization precision by 15-30% over IR-only ranking)
• 6.2 Embed Bug Reports and Source Code in the Same Space for Semantic Localization — MEDIUM (enables semantic localization when bug and code share no vocabulary)
• 6.3 Rank Source Files by TF-IDF Against Bug Report Text for Localization — MEDIUM-HIGH (reduces a 10k-file repo to a 10-file candidate list from a bug report)
• 6.4 Use BM25 over TF-IDF when Source Files Vary Greatly in Length — MEDIUM (prevents long-file bias in IR ranking via TF saturation and length normalization)

7. Identifier Linguistics — MEDIUM

• 7.1 Apply Porter Stemming to Unify Singular and Plural Token Forms — MEDIUM (collapses 10-20% of vocabulary into shared roots without semantic loss)
• 7.2 Expand Identifier Abbreviations Against a Domain Dictionary — MEDIUM (reduces synonym fragmentation by 30-40% in identifier-vocabulary tasks)
• 7.3 Split camelCase and snake_case Identifiers Before Any Text Analysis — MEDIUM (prevents 50%+ vocabulary fragmentation that breaks every downstream algorithm)
• 7.4 Tag Identifier Tokens with POS to Find Misnamed Functions and Classes — MEDIUM (flags 5-10% of identifiers that violate noun/verb naming conventions)

8. Complexity & Risk Metrics — MEDIUM

• 8.1 Compute Shannon Entropy of Identifier Tokens to Flag Overloaded Names — LOW-MEDIUM (eliminates overloaded-name confusion via per-token directory entropy)
• 8.2 Measure McCabe Cyclomatic Complexity to Quantify Per-Function Branch Risk — MEDIUM (predicts independent test paths in O(edges - nodes + 2))
• 8.3 Use Cognitive Complexity When Readability Risk Matters More Than Test Surface — MEDIUM (prevents the false-positive complexity flags that cyclomatic complexity produces)
• 8.4 Use Halstead Volume for a Language-Agnostic Size and Effort Metric — LOW-MEDIUM (enables cross-language complexity comparison without LoC bias)

---

References

1. https://www.jmlr.org/papers/v3/blei03a.html 2. https://pragprog.com/titles/atcrime2/your-code-as-a-crime-scene-second-edition/ 3. https://arxiv.org/abs/2002.08155 4. https://arxiv.org/abs/2203.03850 5. https://hal.science/hal-01054552/document 6. https://epubs.siam.org/doi/10.1137/0218082 7. http://www.cs.princeton.edu/courses/archive/spring13/cos598C/broder97resemblance.pdf 8. https://www.cs.princeton.edu/courses/archive/spr04/cos598B/bib/CharikarEstim.pdf 9. https://arxiv.org/abs/0803.0476 10. https://epubs.siam.org/doi/10.1137/0201010 11. https://ieeexplore.ieee.org/document/1702388 12. https://www.sonarsource.com/resources/cognitive-complexity/ 13. https://nlp.stanford.edu/IR-book/pdf/06vect.pdf 14. https://miltos.allamanis.com/publications/2014idioms/ 15. https://aclanthology.org/J90-1003/ 16. https://github.com/adamtornhill/code-maat 17. https://pmd.github.io/pmd/pmd_userdocs_cpd.html 18. https://www.cs.toronto.edu/~frank/csc2501/Readings/R2_Porter/Porter-1980.pdf

---

Source Files

This document was compiled from individual reference files. For detailed editing or extension:

{Same title as frontmatter}

{1-3 sentences explaining WHY this algorithm matters for codebase analysis. Focus on what non-obvious information it extracts that grep/eyeball cannot. Include the rough complexity class if relevant. Cite the canonical paper or tool by name.}

Incorrect ({describe the naive approach}):

```{language}

Naive approach an agent would default to.

Show why it fails on a realistic codebase scenario —

a strawman is worse than no example.

**Correct ({describe the algorithmic approach}):**

Production-realistic code using the algorithm.

Use real Python/JS/etc. libraries (gensim, networkx, sklearn, etc.) —

not pseudocode unless absolutely necessary.

Include a small example of the OUTPUT in comments

so the reader sees what they get back.

{Optional sections — include any that help the reader apply the algorithm:}

**Tune the parameters:** {if there are dials (k, threshold, etc.), name them and the effect of moving them}

**Use [tool name] for production.** {Point at the canonical OSS tool that implements this rule, since reimplementing for serious use is rarely worth it}

**Combine with `{partner-rule-id}`:** {if two algorithms compound (e.g., minhash + suffix-array), explain the pipeline}

**When NOT to apply:**
- {Specific scenario 1 where the algorithm fails or is wasted}
- {Specific scenario 2}

Reference: [{Canonical paper or tool title}]({URL}), [{Second reference}]({URL})

---

## Authoring guidance for adding rules to this skill

- **Title pattern**: imperative-verb. The validator accepts `Use`, `Avoid`, `Cache`, `Run`, `Apply`, `Tag`, etc. and a generic `[A-Z][a-z]+ ...` fallback. If you write a non-imperative title, the validator will warn.
- **impactDescription must use quantified language**: numeric improvements (`2-10x improvement`, `200ms savings`, `O(n) to O(1)`) OR outcome verbs (`reduces`, `prevents`, `eliminates`, `enables`, `automatic`, `reveals` — *not* in that list — use the validator-accepted ones).
- **First tag MUST be the category prefix** (e.g., `concept`, `sim`, `graph`, `mine`, `clone`, `local`, `ling`, `risk`).
- **Code blocks need language specifiers** (```python, ```bash, ```sql).
- **Examples must be production-realistic** — no `foo`, `bar`, `MyClass`, `tmp`, `data1`. Use domain-appropriate names (e.g., for a housesitting domain: `Sitter`, `Listing`, `Host`, `Application`, `Booking`).
- **Length**: 80-200 lines per rule. Above 200, consider splitting into related rules.
- **References**: link to canonical papers or tool docs — never tutorial sites or blog posts without data.

Sections

This file defines all sections, their ordering, impact levels, and descriptions. The section ID (in parentheses) is the filename prefix used to group rules.

Categories are ordered by insight-per-effort — how much non-obvious truth the technique extracts from a codebase or its history relative to how easy it is to apply. The first two answer the highest-leverage questions: what business entities live in this code? and where else does this concept already exist?

Note: a category's impact level is the impact of its best rules. Individual rules within a CRITICAL category may carry HIGH or MEDIUM-HIGH impact themselves — they're still in the highest-leverage category because the top rules in that category are CRITICAL. Inspect each rule's frontmatter for its specific impact level.

---

1. Concept & Domain Extraction (concept)

Impact: CRITICAL Description: Discovers the latent business vocabulary and entities a codebase encodes implicitly — LDA topics, noun-phrase mining, identifier co-occurrence networks, TF-IDF rare-term extraction, name-variant resolution, and bounded-context detection turn an undocumented codebase into a domain model before a single file is opened by hand.

2. Semantic Similarity & Feature Mapping (sim)

Impact: CRITICAL Description: Finds equivalent or near-equivalent behaviour across renames, synonyms, and rewrites — embedding-based code search, PDG isomorphism for type-4 clones, call-pattern n-grams, and doc-code alignment — so an agent can answer "where else is this feature implemented?" instead of grep-and-pray.

3. Architectural Topology (graph)

Impact: HIGH Description: Treats imports, calls, and references as a graph so PageRank, betweenness centrality, Louvain communities, strongly-connected components, and minimum-feedback-arc-set surface the shape of the codebase — core modules, bottlenecks, natural module boundaries, and cycle tangles invisible at the file level.

4. Co-Change & Temporal Mining (mine)

Impact: HIGH Description: Uses commit history as a signal source — files that change together, churn × complexity hotspots, authorship concentration (bus factor), commit-message topic modelling, and bug-fix density — to reveal couplings and risks the current snapshot of the code cannot show.

5. Clone & Duplication Detection (clone)

Impact: MEDIUM-HIGH Description: Scales duplication detection beyond grep with MinHash + LSH, SimHash, token suffix arrays (CPD), GumTree AST diff, and Zhang-Shasha tree edit distance — catching type-1 copy-paste, type-2 rename-only, and type-3 near-miss clones across a whole repository in minutes.

6. Bug & Feature Localization (local)

Impact: MEDIUM-HIGH Description: Given a bug report or feature description in natural language, ranks source files by relevance using TF-IDF, BM25, history priors, and embedding-based retrieval — turning "where do I even start?" into a ranked short-list of files most likely to contain the change.

7. Identifier Linguistics (ling)

Impact: MEDIUM Description: The preprocessing layer every other algorithm depends on — camelCase / snake_case splitting, abbreviation expansion, Porter stemming, and POS tagging on identifiers — without which userId, user_id, and usrIdent look like three different things and every downstream signal degrades.

8. Complexity & Risk Metrics (risk)

Impact: MEDIUM Description: Quantifies risk per file — McCabe cyclomatic complexity, SonarSource cognitive complexity, Halstead volume, and Shannon entropy on identifier vocabularies — to direct attention toward the most error-prone parts of the codebase when combined with the temporal signals from mine-.

Use the GumTree Algorithm for Fine-Grained AST Differencing

git diff works on lines; it shows reformatting as a massive change and reorderings as deletions-plus-insertions. The GumTree algorithm (Falleri et al., 2014) works on AST nodes and produces a node-level edit script — "method processOrder was moved from class A to class B, then 3 statements were swapped". The same machinery detects fine-grained syntactic clones: two methods are clones if the edit script between their ASTs is small. This is the right tool for behavioural diff in code review, refactoring impact analysis, and Type-2/Type-3 clone detection.

Incorrect (line-based diff — confuses reformatting and movement with substantive change):

# A formatter run shows up as the entire file changed.
# A method-move shows up as a delete + an insert in a different place,
# losing the link that this is the SAME method.
git diff src/orders.py
# 240 lines changed — but the actual semantic change is one move + 2 statements.

Correct (GumTree — AST-level move/insert/delete/update operations):

# GumTree has implementations in Java (reference), Python, JS, and many wrappers.
# Below: gumtree-python invocation, then interpretation of the edit script.
import subprocess, json

# 1. Run gumtree between two versions of a file (or two clone candidates)
def gumtree_diff(left: str, right: str) -> list[dict]:
    out = subprocess.check_output([
        "gumtree", "textdiff", left, right, "--output", "json",
    ]).decode()
    return json.loads(out)["actions"]

actions = gumtree_diff("src/orders.py@v1", "src/orders.py@v2")
for a in actions:
    print(f"  {a['action']:>8}  node={a['tree']:>20}  at {a['at']}")
# Output (compressed):
# move      MethodDecl:processOrder    class A -> class B
# update    Identifier:gateway         old="stripe" new="paypal"
# insert    Statement:return           in method:abort
# delete    Statement:log              in method:abort
# A 240-line text diff reduces to 4 semantic actions.

As a clone detector, compare every pair of method ASTs and rank pairs by edit-script length normalized to subtree size:

# Clone score = 1 - (|edit_script| / |subtree_size|)
# 1.0 = identical; 0.9+ = near-Type-2; 0.7-0.9 = Type-3; <0.7 = behavioural divergence
def clone_score(left_method: str, right_method: str, tree_size: int) -> float:
    actions = gumtree_diff(left_method, right_method)
    return 1 - len(actions) / tree_size

Use [GumTree's standard library implementations](https://github.com/GumTreeDiff/gumtree) — Java is the reference, but Python (gumtree-python) and JS (gumtree-js) wrappers exist for whichever runtime fits your tooling.

Better than `tree-sitter`-based diff for many cases. Tree-sitter gives you the AST; GumTree gives you the mapping between two ASTs. The mapping is the hard part, and GumTree's top-down + bottom-up matching is the best general-purpose algorithm available.

Combine with `mine-change-coupling`: when two files change together (high coupling) AND their AST diffs are symmetric (the same logical change in both), they're cousin-clones that should share an abstraction. The combined signal directly proposes a refactor.

Use the edit script in PR review for cleaner reviewer experience. A change with 240 text-diff lines but only 4 GumTree actions is a low-risk refactor. A change with 30 text-diff lines but 50 GumTree actions is a deceptively-small commit with broad semantic impact. Both are misleading on text-diff alone.

When NOT to apply:

• Tiny snippets (<10 AST nodes) — every clone-score sits near 1.0 and discrimination fails
• Languages without a robust parser in the GumTree ecosystem — fall back to tree-sitter + Zhang-Shasha (see clone-zhang-shasha-ted)

Reference: Falleri et al., Fine-grained and Accurate Source Code Differencing (ASE 2014), GumTree GitHub

Use MinHash plus LSH to Find Near-Duplicate Code at Repository Scale

Pairwise Jaccard similarity on N files is O(N²) — quadratic and unrunnable on real repos. MinHash (Broder, 1997) replaces each file's k-shingle set with a fixed-size signature whose collisions estimate Jaccard. Locality-Sensitive Hashing on those signatures then makes the search sub-linear — given a query signature, you find all candidates above a similarity threshold in roughly O(log N). On a million-file mono-repo, finding all near-duplicate pairs above 0.7 Jaccard takes minutes, not days. This is the workhorse for Type-1 and most Type-2 clone detection across an enterprise codebase.

Incorrect (all-pairs Jaccard — quadratic, infeasible above ~10k files):

import pathlib, re, itertools

WORD = re.compile(r"\w+")

def shingles(text: str, k: int = 5) -> set[str]:
    toks = WORD.findall(text)
    return {" ".join(toks[i:i + k]) for i in range(len(toks) - k + 1)}

files = list(pathlib.Path("src").rglob("*.py"))
shing = {p: shingles(p.read_text(errors="ignore")) for p in files}

# O(n²) comparisons — for 10,000 files = 50 million pair comparisons
for a, b in itertools.combinations(files, 2):
    j = len(shing[a] & shing[b]) / max(1, len(shing[a] | shing[b]))
    if j > 0.7:
        print(f"  {j:.2f}  {a}  {b}")

Correct (MinHash signatures + LSH bands — sub-linear retrieval):

import pathlib, re
from datasketch import MinHash, MinHashLSH

WORD = re.compile(r"\w+")

def shingles(text: str, k: int = 5) -> set[str]:
    toks = WORD.findall(text)
    return {" ".join(toks[i:i + k]) for i in range(len(toks) - k + 1)}

def minhash(sh: set[str], num_perm: int = 128) -> MinHash:
    m = MinHash(num_perm=num_perm)
    for s in sh:
        m.update(s.encode("utf8"))
    return m

# 1. Build signatures
sigs: dict[str, MinHash] = {}
for p in pathlib.Path("src").rglob("*.py"):
    sigs[str(p)] = minhash(shingles(p.read_text(errors="ignore")))

# 2. Index in LSH with threshold = 0.7 (banding chosen to maximize recall at that threshold)
lsh = MinHashLSH(threshold=0.7, num_perm=128)
for path, sig in sigs.items():
    lsh.insert(path, sig)

# 3. Query each file's neighbours — only candidates above threshold are returned
seen = set()
for path, sig in sigs.items():
    for nbr in lsh.query(sig):
        if nbr == path: continue
        key = tuple(sorted([path, nbr]))
        if key in seen: continue
        seen.add(key)
        est = sigs[path].jaccard(sigs[nbr])
        if est > 0.7:
            print(f"  ~{est:.2f}  {path}  ~~  {nbr}")

Tune k (shingle size). Too small (k=2) → noise; too large (k=10) → misses small clones. k=5 for source code, k=3 for short identifiers, k=9 for natural-language text. Always shingle on tokens, not characters — character shingles match by syntax, token shingles match by meaning.

Use weighted MinHash for IDF-aware similarity. Plain MinHash treats every shingle equally. Real interesting clones share rare shingles, not common ones. datasketch.WeightedMinHashGenerator takes IDF weights and dramatically improves precision when paired with concept-tfidf-rare-terms.

LSH banding chooses the precision-recall tradeoff. MinHashLSH(threshold=0.7) solves for (b, r) such that recall is high at Jaccard ≥ 0.7. Lower threshold → more bands → more candidates → slower query but higher recall. Sweep 0.5/0.7/0.9 and pick by clone-purpose.

Combine with `clone-suffix-array-cpd` for precise clone boundaries. MinHash tells you which files are similar; suffix-array CPD tells you where in the file the duplicated tokens are.

When NOT to apply:

• Code translated between languages — token sets differ; use embeddings (sim-codebert-embeddings) instead
• Tiny repos (<500 files) — MinHash overhead exceeds savings; plain Jaccard is fine

Reference: Broder, On the resemblance and containment of documents (SEQUENCES 1997), datasketch — MinHash + LSH for Python

Use SimHash 64-bit Fingerprints for Constant-Time Similarity Lookups

SimHash (Charikar, 2002) compresses a document into a 64-bit fingerprint where similar documents have fingerprints differing in only a few bits — Hamming distance estimates dissimilarity. Compared to MinHash, SimHash uses less storage (one 64-bit integer per document vs. a 128-element array), and Hamming distance is faster to compute on modern CPUs (single XOR + popcount). It's the right choice when you have many documents and need a similarity index that fits in cache. Google originally used it for near-duplicate web page detection on the entire crawl.

Incorrect (MD5 / SHA hash → equality test — catches only identical files, misses near-duplicates):

import hashlib, pathlib

# Cryptographic hashes flip every bit on a one-character change.
# Useless for similarity — even reformatting whitespace destroys equality.
fingerprints = {}
for p in pathlib.Path("src").rglob("*.py"):
    h = hashlib.sha256(p.read_text(errors="ignore").encode()).hexdigest()
    fingerprints.setdefault(h, []).append(str(p))

# Returns only EXACT duplicates — useless for near-duplicate search.
dupes = {h: ps for h, ps in fingerprints.items() if len(ps) > 1}

Correct (SimHash — small Hamming distance ↔ small Jaccard, O(1) check per pair):

import re, pathlib
from simhash import Simhash, SimhashIndex   # pip install simhash

WORD = re.compile(r"\w+")

def features(text: str) -> list[str]:
    """Token features for SimHash. Stripping comments / strings first improves precision."""
    return WORD.findall(text)

# 1. Compute fingerprints for every file
records: list[tuple[str, Simhash]] = []
for p in pathlib.Path("src").rglob("*.py"):
    sig = Simhash(features(p.read_text(errors="ignore")), f=64)
    records.append((str(p), sig))

# 2. Build a fast index for near-neighbours (Hamming distance ≤ k bits)
index = SimhashIndex([(name, sig) for name, sig in records], k=8)   # 8/64 bit tolerance

# 3. Query each file's near-neighbours
seen = set()
for name, sig in records:
    for nbr in index.get_near_dups(sig):
        if nbr == name: continue
        key = tuple(sorted([name, nbr]))
        if key in seen: continue
        seen.add(key)
        dist = sig.distance(dict(records)[nbr])
        print(f"  hamming={dist:>2}/64  {name}  ~  {nbr}")
# hamming= 2/64  src/api/checkout_v1.py  ~  src/api/checkout_v2.py    <- near-identical
# hamming= 5/64  src/utils/email.py       ~  src/utils/sms.py          <- structural twin

The k parameter in SimhashIndex(records, k=N) is the Hamming-distance tolerance. Lower k → more strict matches but fewer false positives; higher k → looser matches. For Type-1 clones, k=3-5 (out of 64); for Type-2 (renamed identifiers, same structure), k=6-10.

Strip strings and comments before computing the fingerprint. Otherwise SimHash matches based on shared boilerplate text. Token-level features after dropping string-literal and comment tokens are far more discriminating.

SimHash vs MinHash decision rubric:

Combine with `mine-change-coupling`: two near-duplicate files that also change together are textbook copy-paste-and-edit clones — the worst kind, because the duplication is reinforced every commit. Refactor those first.

When NOT to apply:

• Need to identify duplicated regions within files — SimHash is whole-file; use suffix-array CPD or AST clone tools instead
• Documents shorter than ~50 tokens — fingerprint is unstable; fall back to direct token comparison

Reference: Charikar, Similarity Estimation Techniques from Rounding Algorithms (STOC 2002), Manku, Jain & Sarma, Detecting Near-Duplicates for Web Crawling (WWW 2007)

Use Token-Level Suffix Arrays for Precise Clone Boundary Detection

MinHash and SimHash tell you which files are similar; they don't tell you which lines. For that you need a suffix array over the entire codebase's token stream. Build the array once, find longest common substrings between every pair, and the algorithm hands you exact clone regions — start file, start line, length in tokens. This is the algorithm behind PMD CPD (Copy/Paste Detector), used at Google, Microsoft, and most large engineering orgs. It catches the exact "we wrote this same 40-line block in 7 places" situation that aggregate similarity scores blur.

Incorrect (diff every-pair to find common blocks — O(n²·m), days on a real repo):

import difflib, pathlib, itertools

def common_blocks(a: str, b: str, min_lines: int = 10) -> list[tuple]:
    matcher = difflib.SequenceMatcher(None, a.splitlines(), b.splitlines(), autojunk=False)
    return [(m.a, m.b, m.size) for m in matcher.get_matching_blocks() if m.size >= min_lines]

files = list(pathlib.Path("src").rglob("*.py"))
# For 10k files: 50M pair-diffs, each O(m·n)
for a, b in itertools.combinations(files, 2):
    blocks = common_blocks(a.read_text(errors="ignore"), b.read_text(errors="ignore"))
    if blocks:
        print(f"{a} ~ {b}: {blocks}")

Correct (token-stream suffix array — one pass over the concatenated corpus):

# Build the corpus token stream once; suffix array gives all
# longest-common-token-runs ≥ K in O(N log N).
import re, pathlib
import pydivsufsort                              # pip install pydivsufsort

WORD = re.compile(r"[A-Za-z_][A-Za-z0-9_]*|\S")
K = 80                                            # minimum clone length in tokens

# 1. Tokenize every file and remember which tokens came from where
tokens: list[str] = []
origin: list[tuple[str, int]] = []                # (file, token-index-within-file)
SENTINEL = "\x01"                                 # forbidden in source — separates files
for p in pathlib.Path("src").rglob("*.py"):
    src = p.read_text(errors="ignore")
    file_toks = WORD.findall(src)
    for i, t in enumerate(file_toks):
        tokens.append(t)
        origin.append((str(p), i))
    tokens.append(SENTINEL)
    origin.append(("__sep__", 0))

# 2. Map tokens to small integers, build the suffix array
vocab = {t: i for i, t in enumerate(sorted(set(tokens)))}
arr = bytes(vocab[t] % 255 + 1 for t in tokens)   # crude byte-encode for the demo
sa = pydivsufsort.divsufsort(arr)

# 3. Compute LCP (longest common prefix) array
lcp = pydivsufsort.kasai_lcp(arr, sa)

# 4. Adjacent suffixes with lcp >= K and from different files are clones
clones = []
for i in range(1, len(sa)):
    if lcp[i] >= K:
        a_file, a_idx = origin[sa[i - 1]]
        b_file, b_idx = origin[sa[i]]
        if a_file != "__sep__" and b_file != "__sep__" and a_file != b_file:
            clones.append((lcp[i], a_file, a_idx, b_file, b_idx))

clones.sort(reverse=True)
for ln, af, ai, bf, bi in clones[:10]:
    print(f"  {ln} toks  {af}:tok{ai}  ~  {bf}:tok{bi}")
# 312 toks  src/integrations/stripe/refund.py:tok40  ~  src/integrations/braintree/refund.py:tok42
# 218 toks  src/api/v1/orders.py:tok110  ~  src/api/v2/orders.py:tok98

Use a real tool for production. PMD CPD (Java, but supports 25+ languages including Python, Go, JS, C/C++), Simian, and jscpd for JS implement this algorithm with all the gotchas handled (tokenization, identifier normalization, ignore-blocks). The DIY version above is fine for one-off analyses; for CI, use the tools.

Token normalization controls clone type detected. Replace every identifier with IDENT before suffix-array construction → detects Type-2 clones (renamed identifiers). Replace literals with LIT too → Type-3 (constant changes). Most CPD tools toggle this per-mode.

Combine with `clone-minhash-lsh` for a two-stage pipeline: MinHash to find candidate file pairs (fast), suffix array within each pair (precise). Together they handle whole-repo Type-1/2 clone detection on >10M LoC in under an hour.

When NOT to apply:

• Cross-language clone detection — token streams are incompatible; use AST or embedding methods
• Generated code (protobuf, GraphQL schemas) — they all clone-match each other meaninglessly; exclude or ignore by file pattern

Reference: Kamiya, Kusumoto & Inoue, CCFinder (TSE 2002), PMD CPD docs, Manber & Myers, Suffix arrays: A new method for on-line string searches (1990)

Compute Zhang-Shasha Tree Edit Distance for Subtree Similarity Scoring

Zhang-Shasha (1989) computes the minimum number of node insertions, deletions, and label changes to turn one ordered tree into another. Unlike GumTree, which is an approximation tuned for speed and human-readable edit scripts, Zhang-Shasha gives the exact optimal cost. Use it when you need ground-truth distance for benchmarking, for ranking small clone candidates precisely, or as a similarity primitive in a larger clustering pipeline. Modern implementations (e.g. APTED, an O(n²) descendant) run in seconds on AST pairs up to a few thousand nodes.

Incorrect (compare AST node count or histogram of node types — coarse, position-blind):

import ast, collections

def kind_hist(src: str) -> collections.Counter:
    return collections.Counter(type(n).__name__ for n in ast.walk(ast.parse(src)))

# Two methods can have identical kind-histograms but completely
# different control flow — the histogram throws away structure.
a = "def f(x):\n    if x: return x\n    return -x"
b = "def f(x):\n    if x: pass\n    if not x: return -x"
print(kind_hist(a) == kind_hist(b))  # True — but the trees are different!

Correct (Zhang-Shasha / APTED — exact minimum edit distance, normalized to tree size):

# Using apted (O(n^2), the modern implementation of choice)
# pip install apted
import ast
from apted import APTED, Config

class ASTNode:
    """APTED expects nodes with .name and .children"""
    def __init__(self, name: str, children: list):
        self.name = name
        self.children = children

def ast_to_apted(node) -> ASTNode:
    children = [ast_to_apted(c) for c in ast.iter_child_nodes(node)]
    return ASTNode(type(node).__name__, children)

class LabelConfig(Config):
    def rename(self, n1, n2):
        return 0 if n1.name == n2.name else 1

def tree_distance(src_a: str, src_b: str) -> tuple[int, int]:
    t1 = ast_to_apted(ast.parse(src_a))
    t2 = ast_to_apted(ast.parse(src_b))
    size = max(_size(t1), _size(t2))
    dist = APTED(t1, t2, LabelConfig()).compute_edit_distance()
    return dist, size

def _size(n) -> int:
    return 1 + sum(_size(c) for c in n.children)

# Score: 1 - (distance / max_size). Higher = more similar.
methods = {
    "checkout_stripe": "def f(c):\n    validate(c)\n    stripe.charge(c.total)\n    record(c)\n    notify(c.user)",
    "checkout_paypal": "def f(c):\n    validate(c)\n    paypal.execute(c.total)\n    record(c)\n    notify(c.user)",
    "process_refund":  "def f(r):\n    log(r)\n    if r.processed:\n        return\n    stripe.refund(r.id)",
}

names = list(methods)
for i, a in enumerate(names):
    for b in names[i + 1:]:
        d, n = tree_distance(methods[a], methods[b])
        sim = 1 - d / n
        print(f"  sim={sim:.2f}  d={d}/n={n}  {a} ~ {b}")
# sim=0.92  d=2/n=24  checkout_stripe ~ checkout_paypal      <- near-Type-2 clone
# sim=0.41  d=14/n=24  checkout_stripe ~ process_refund      <- not a clone

Use APTED, not the original Zhang-Shasha implementation. APTED (Pawlik & Augsten, 2015) is mathematically equivalent for cost but ~30× faster on real AST sizes. The reference implementation is the eth-sri/apted Java repo with Python bindings on PyPI.

TED is the right primitive when you need exact distances but the wrong tool when you need to scale beyond ~5000-node trees. Above that, GumTree's approximation is faster and good enough; or hash sub-tree shingles and use MinHash on the shingle sets.

Apply to identifier-stripped ASTs for Type-2 clone detection. Replace every Identifier(name="...") with Identifier(name="_") before measuring distance; the rename-induced changes drop to zero and structurally-equivalent code scores near 1.0.

Combine with `clone-minhash-lsh`: use MinHash on sub-tree shingles to find candidate clone pairs (fast), then run APTED only on candidates (precise). The pipeline scales to whole-codebase clone detection with exact final scoring on the candidates.

When NOT to apply:

• Large AST trees (>5k nodes) — quadratic time is the practical limit; use approximate methods
• Languages with extremely flat ASTs (raw lists of statements) — TED becomes pure label-edit and doesn't reflect structural similarity well; use semantic embeddings instead

Reference: Zhang & Shasha, Simple Fast Algorithms for the Editing Distance Between Trees (SIAM 1989), Pawlik & Augsten, Tree Edit Distance — Robust and Memory-Efficient (Information Systems 2016)

Detect DDD Bounded Contexts via Louvain Communities Plus Vocabulary Divergence

A bounded context (Evans, Domain-Driven Design) is a region of the codebase where a shared term has a single, internally consistent meaning. Real codebases don't declare their bounded contexts — they emerge from naming and call-graph topology. Two signals identify them with high precision: (1) Louvain community detection on the file-level import graph identifies densely-connected clusters; (2) Jensen-Shannon divergence on the per-cluster identifier-vocabulary distribution confirms the clusters use different vocabularies. When both signals agree, you have a bounded context. The output is a partition of the codebase that maps to real domain boundaries — for refactoring, micro-service extraction, or just for orientation.

Incorrect (use the directory structure as bounded contexts — assumes folders match domains):

# Treat every top-level directory under src/ as a bounded context.
# Wrong: legacy codebases often have a single "models" directory
# containing entities from 4 different contexts.
import pathlib

contexts = {p.name: list(p.rglob("*.py")) for p in pathlib.Path("src").iterdir() if p.is_dir()}
# {"models": [user.py, invoice.py, sitter.py, listing.py, ...],
#  "services": [user_service.py, billing_service.py, ...],
#  "controllers": [...]}
# Every "context" is actually a layer, not a bounded context.

Correct (Louvain on import graph + Jensen-Shannon divergence on vocabularies):

import ast, re, pathlib, collections, math
import networkx as nx

WORD = re.compile(r"[A-Z]?[a-z]+|[A-Z]+(?=[A-Z]|$)")

# 1. Build the file-level import graph
G = nx.Graph()
files = list(pathlib.Path("src").rglob("*.py"))
mod_map = {".".join(p.relative_to("src").with_suffix("").parts): p for p in files}

for p in files:
    G.add_node(str(p))
    for node in ast.walk(ast.parse(p.read_text(errors="ignore"))):
        if isinstance(node, ast.ImportFrom) and node.module in mod_map:
            G.add_edge(str(p), str(mod_map[node.module]))

# 2. Louvain communities = dense clusters in the import graph
communities = nx.community.louvain_communities(G, seed=42)

# 3. For each community, build its identifier-token distribution
def vocab(files: list[str]) -> collections.Counter:
    c = collections.Counter()
    for f in files:
        c.update(w.lower() for w in WORD.findall(pathlib.Path(f).read_text(errors="ignore")))
    return c

dists = [vocab(c) for c in communities]

# 4. Jensen-Shannon divergence between every pair of communities
def js_divergence(p: dict, q: dict) -> float:
    keys = set(p) | set(q)
    sp, sq = sum(p.values()), sum(q.values())
    div = 0.0
    for k in keys:
        pi, qi = p.get(k, 0) / sp, q.get(k, 0) / sq
        m = 0.5 * (pi + qi)
        if pi > 0: div += 0.5 * pi * math.log(pi / m)
        if qi > 0: div += 0.5 * qi * math.log(qi / m)
    return div

# A community is a true bounded context if mean JS-divergence to others > 0.25
for i, comm in enumerate(communities):
    other = collections.Counter()
    for j, d in enumerate(dists):
        if j != i: other.update(d)
    div = js_divergence(dists[i], other)
    if div > 0.25:
        top_terms = [w for w, _ in dists[i].most_common(8)]
        print(f"Context {i}: |files|={len(comm)} JS={div:.2f} top_terms={top_terms}")
# Context 0: |files|=42 JS=0.41 top_terms=['sitter', 'listing', 'host', 'application', 'stay', ...]
# Context 2: |files|=18 JS=0.38 top_terms=['invoice', 'subscription', 'plan', 'charge', ...]
# Context 5: |files|=27 JS=0.31 top_terms=['user', 'session', 'auth', 'token', 'login', ...]

Validate against the team's mental model. The output is a candidate partition — show it to a domain expert and ask "does this match how you think about the system?". Real bounded contexts that the algorithm misses signal places where the code's structure has drifted from the domain.

Combined with `mine-change-coupling`: files that change together across contexts are leaky abstractions. Co-change between bounded contexts is a refactoring signal — those files belong in a shared kernel.

When NOT to apply:

• Monolithic codebases with no internal module boundaries — Louvain returns one giant community
• Codebases following strict layered architecture — the layers will be detected as "contexts" but they aren't; weight by concept-tfidf-rare-terms to confirm domain divergence

Reference: Evans, Domain-Driven Design, Blondel et al., Fast unfolding of communities (Louvain, 2008), Lin, Divergence Measures Based on Shannon Entropy

Cluster Identifier Variants into Canonical Entities via Embedding plus Edit Distance

A 5-year-old codebase will refer to the same business entity as user, usr, u, userAccount, accountHolder, customer, and member — all in the same repo, often in the same module. Treating them as separate concepts breaks every downstream analysis: topic modelling fragments topics, co-occurrence graphs split clusters, and bug-localization ranks all variants near the bottom. Entity resolution clusters these variants into a single canonical entity using a two-pass approach: edit-distance for typos/abbreviations and embedding similarity for semantic synonyms. The output is a variant → canonical map you apply as a preprocessing step to every other algorithm in this skill.

Incorrect (treat every identifier token as a distinct entity — vocabulary fragments):

import re, pathlib, collections

# Counts every distinct token. "user", "usr", "u", "userAccount" all
# scored separately — user-related signal is split across 7 buckets.
WORD = re.compile(r"\b[a-zA-Z_][a-zA-Z0-9_]{1,}\b")
counts = collections.Counter()
for p in pathlib.Path("src").rglob("*.py"):
    counts.update(WORD.findall(p.read_text(errors="ignore")))

# "user": 1820, "usr": 412, "userAccount": 300, "accountHolder": 270,
# "customer": 240, "member": 180 — six entries for one entity.

Correct (cluster variants via edit-distance + embedding similarity, output canonical map):

import re, pathlib, collections
import numpy as np
from rapidfuzz.distance import Levenshtein
from sentence_transformers import SentenceTransformer
from sklearn.cluster import AgglomerativeClustering

WORD = re.compile(r"[A-Z]?[a-z]+|[A-Z]+(?=[A-Z]|$)")
encoder = SentenceTransformer("all-MiniLM-L6-v2")   # 22MB, fast on CPU

# 1. Collect all identifier tokens with their frequency
tokens: collections.Counter = collections.Counter()
for p in pathlib.Path("src").rglob("*.py"):
    for ident in re.findall(r"\b[A-Za-z_][A-Za-z0-9_]{2,}\b", p.read_text(errors="ignore")):
        for w in WORD.findall(ident):
            tokens[w.lower()] += 1

vocab = [t for t, c in tokens.items() if c >= 5 and len(t) >= 2]

# 2. Build a combined-distance matrix: 0.6 × embedding + 0.4 × edit-distance
embs = encoder.encode(vocab, normalize_embeddings=True)
emb_dist = 1 - embs @ embs.T

n = len(vocab)
edit_dist = np.zeros((n, n), dtype=np.float32)
for i in range(n):
    for j in range(i + 1, n):
        d = Levenshtein.normalized_distance(vocab[i], vocab[j])
        edit_dist[i, j] = edit_dist[j, i] = d

combined = 0.6 * emb_dist + 0.4 * edit_dist

# 3. Agglomerative clustering with a distance threshold
clusters = AgglomerativeClustering(
    n_clusters=None, distance_threshold=0.35, metric="precomputed", linkage="average",
).fit(combined)

# 4. Canonical name = most frequent variant per cluster
canon: dict[str, str] = {}
for cid in set(clusters.labels_):
    members = [vocab[i] for i, c in enumerate(clusters.labels_) if c == cid]
    canon_name = max(members, key=tokens.get)
    for m in members:
        canon[m] = canon_name

# Sample output
for variant in ("user", "usr", "u", "useraccount", "accountholder", "customer"):
    print(f"  {variant:>16} → {canon.get(variant, variant)}")
# user → user
# usr → user        (edit-distance: abbreviation)
# u → user          (edit-distance: short alias)
# useraccount → user  (embedding: compound noun)
# accountholder → user (embedding: synonym)
# customer → customer (no merge — semantically distinct in this domain)

Tune the threshold per domain. Too low (< 0.2) misses synonyms; too high (> 0.5) merges distinct entities (subscriber with subscription). Inspect a sample of the merges before applying — entity resolution is the algorithm in this skill with the highest risk of confidently-wrong output.

Use the canonical map as a preprocessing step for concept-lda-topic-modeling, concept-identifier-cooccurrence-network, and ir-tfidf-bug-localization. All three improve substantially when their input vocabulary is consolidated.

When NOT to apply:

• Codebases under ~500 distinct tokens — manual inspection is faster
• When the variants represent legitimately different concepts (asyncUser vs syncUser in a perf-sensitive API)

Reference: Christen, Data Matching: Concepts and Techniques, Sentence-BERT (Reimers & Gurevych)

Build an Identifier Co-occurrence Graph to Reveal Conceptual Neighborhoods

Two identifiers that frequently appear in the same function or file are conceptually adjacent in the domain — far more so than two identifiers that merely live in the same module directory. A weighted co-occurrence graph (nodes = identifier tokens, edge weight = number of functions in which both appear) lets you ask: "which concepts cluster around subscription?" and get back {plan, invoice, charge, billingCycle, renewal} — even when those terms live in completely different files. This is the trick that turns "I read the code" into "I read the relationships between concepts in the code".

Incorrect (file-level co-occurrence — too coarse, dominated by `utils.py`):

import pathlib, itertools, collections

WORD = __import__("re").compile(r"\b[a-zA-Z_][a-zA-Z0-9_]{3,}\b")
edges = collections.Counter()
for p in pathlib.Path("src").rglob("*.py"):
    tokens = set(WORD.findall(p.read_text(errors="ignore")))
    for a, b in itertools.combinations(sorted(tokens), 2):
        edges[(a, b)] += 1

# Top edges are ("logging", "request"), ("logging", "response"),
# ("self", "value") — utility tokens that appear in every file.
# Real domain relationships drown.

Correct (function-scoped co-occurrence with PMI weighting — domain neighborhoods emerge):

import ast, math, pathlib, itertools, collections
import networkx as nx

WORD = __import__("re").compile(r"[A-Z]?[a-z]+|[A-Z]+(?=[A-Z]|$)")

def function_tokens(src: str) -> list[set[str]]:
    bags = []
    for node in ast.walk(ast.parse(src)):
        if isinstance(node, (ast.FunctionDef, ast.AsyncFunctionDef)):
            text = ast.unparse(node)
            bags.append({w.lower() for w in WORD.findall(text) if len(w) > 3})
    return bags

pair_counts: collections.Counter = collections.Counter()
unigram_counts: collections.Counter = collections.Counter()
total_funcs = 0
for p in pathlib.Path("src").rglob("*.py"):
    for bag in function_tokens(p.read_text(errors="ignore")):
        total_funcs += 1
        unigram_counts.update(bag)
        for a, b in itertools.combinations(sorted(bag), 2):
            pair_counts[(a, b)] += 1

# PMI = log( P(a,b) / (P(a)·P(b)) ) — promotes pairs that co-occur
# more than chance, demotes pairs that are individually frequent.
def pmi(a: str, b: str, n_ab: int) -> float:
    p_ab = n_ab / total_funcs
    p_a = unigram_counts[a] / total_funcs
    p_b = unigram_counts[b] / total_funcs
    return math.log(p_ab / (p_a * p_b))

G = nx.Graph()
for (a, b), n_ab in pair_counts.items():
    if n_ab >= 5 and unigram_counts[a] >= 10 and unigram_counts[b] >= 10:
        w = pmi(a, b, n_ab)
        if w > 0:
            G.add_edge(a, b, weight=w)

# Neighborhood of "subscription": its strongest PMI partners
nbrs = sorted(G[("subscription")].items(), key=lambda kv: -kv[1]["weight"])[:10]
for term, attrs in nbrs:
    print(f"  {term:<20} pmi={attrs['weight']:.2f}")
# plan          pmi=4.81
# invoice       pmi=4.32
# renewal       pmi=4.10
# charge        pmi=3.88
# billingCycle  pmi=3.71

Run Louvain on the resulting graph (nx.community.louvain_communities(G)) — the communities are conceptual clusters that map almost directly to bounded contexts. This is the algorithmic backbone of concept-bounded-context-detection.

Tune the function-bag size: too-large functions (>200 lines) generate noisy edges; consider per-statement or per-class scoping for monolithic files.

When NOT to apply:

• Files where every function imports the same wide set of utilities — PMI alone won't filter
• Languages without per-function parsing support — use file-scoped co-occurrence with TF-IDF re-weighting instead

Reference: Church & Hanks, Word Association Norms (1990), Allamanis & Sutton, Mining Idioms from Source Code

Use LDA over Identifier Tokens to Surface Latent Domain Topics

Latent Dirichlet Allocation (Blei/Ng/Jordan, 2003) treats each source file as a "document" of identifier tokens and infers a fixed number of topics — distributions of words that co-occur. On real codebases the topics line up almost exactly with business sub-domains: {user, account, email, session, login} (auth), {invoice, charge, subscription, plan, billing} (billing), {sitter, listing, host, application, stay} (housesitting). LDA finds these clusters before you open a single file, even when no module names them. The cost of skipping it: weeks of grep-driven exploration that systematically misses themes spread across the tree.

Incorrect (naïve domain inference — biased toward framework noise):

# Walk top-level READMEs and the 20 most-imported files,
# then guess at the domain. Misses business themes spread
# across many small files, and overweights framework code.
from collections import Counter
import ast, pathlib

import_counts = Counter()
for p in pathlib.Path("src").rglob("*.py"):
    tree = ast.parse(p.read_text())
    for node in ast.walk(tree):
        if isinstance(node, ast.ImportFrom) and node.module:
            import_counts[node.module] += 1

# Top-20 imports are `django.db.models`, `rest_framework`,
# `typing`, `logging` — zero signal about the business domain.
print(import_counts.most_common(20))

Correct (LDA over identifier tokens — topics map to sub-domains):

import re, pathlib
from gensim import corpora, models

SPLIT = re.compile(r"[A-Z]?[a-z]+|[A-Z]+(?=[A-Z]|$)|\d+")

def file_tokens(path: pathlib.Path) -> list[str]:
    src = path.read_text(errors="ignore")
    return [w.lower() for w in SPLIT.findall(src) if len(w) > 2]

docs = [file_tokens(p) for p in pathlib.Path("src").rglob("*.py")]
dictionary = corpora.Dictionary(docs)
dictionary.filter_extremes(no_below=5, no_above=0.5)   # drop rares & stopwords
corpus = [dictionary.doc2bow(d) for d in docs]

lda = models.LdaMulticore(
    corpus, id2word=dictionary, num_topics=15, passes=10, random_state=42,
)

for tid, words in lda.print_topics(num_words=8):
    print(f"Topic {tid}: {words}")
# Topic 3: 0.07*"sitter" + 0.05*"listing" + 0.04*"host" + 0.03*"application"
# Topic 7: 0.08*"invoice" + 0.06*"subscription" + 0.05*"plan" + 0.04*"charge"
# Topic 12: 0.09*"booking" + 0.06*"stay" + 0.05*"pet" + 0.04*"review"

Choosing topic count: use coherence score (CoherenceModel(model=lda, texts=docs, coherence="c_v")), sweep k ∈ {5, 10, 15, 20, 30}, pick the local max. For repos under 5k files, k = 10 is a reasonable starting point.

Preprocessing matters more than the algorithm: apply ling-camel-snake-split and ling-abbreviation-expansion to tokens first. Skipping these steps means userId and user_id look like two unrelated words and topics fragment.

When NOT to apply:

• Repos under ~200 files — eyeballing is faster and LDA's topics are unstable on small corpora
• Monolithic single-file libraries — there's nothing to cluster

Reference: Latent Dirichlet Allocation (Blei et al., 2003), gensim LDA tutorial

Extract Noun Phrases from Identifiers to Find Candidate Domain Entities

Domain entities almost always show up in code as noun phrases inside identifier names: customerSubscription, pet_sit_application, HouseListingReview. Tokenize identifiers, tag each token with a part-of-speech tag, then run a noun-phrase chunker — the result is a frequency-ranked list of multi-word entity candidates with very little noise. This is how engineers manually "see" the domain in a codebase, automated. Done well, the top 50 noun phrases capture ~80% of the actual domain ubiquitous language; you'd recover the same list by interviewing the team for half a day.

Incorrect (counting bare tokens — misses multi-word entities, swamped by verbs):

# Counts every lowercase word in identifiers and ranks by frequency.
# Result is dominated by verbs ("get", "set", "is") and framework
# words ("request", "response"). Multi-word entities like
# "house listing review" never surface as a unit.
import re, pathlib, collections

SPLIT = re.compile(r"[A-Z]?[a-z]+|[A-Z]+(?=[A-Z]|$)")
counter = collections.Counter()
for p in pathlib.Path("src").rglob("*.py"):
    counter.update(w.lower() for w in SPLIT.findall(p.read_text()))

# Top 20: get, set, is, request, return, self, value, data, response, ...
print(counter.most_common(20))

Correct (POS-tag identifier tokens, chunk into noun phrases, rank):

import re, pathlib, collections
import spacy
nlp = spacy.load("en_core_web_sm")

SPLIT = re.compile(r"[A-Z]?[a-z]+|[A-Z]+(?=[A-Z]|$)")
DOMAIN_STOPS = {"get", "set", "is", "do", "make", "self", "value", "data"}

def identifiers(path: pathlib.Path) -> list[str]:
    return re.findall(r"\b[A-Za-z_][A-Za-z0-9_]{2,}\b", path.read_text(errors="ignore"))

phrase_counts = collections.Counter()
for p in pathlib.Path("src").rglob("*.py"):
    for ident in identifiers(p):
        tokens = [t.lower() for t in SPLIT.findall(ident) if t.lower() not in DOMAIN_STOPS]
        if len(tokens) < 2:
            continue
        # POS-tag the reconstructed phrase and keep noun-headed chunks
        doc = nlp(" ".join(tokens))
        for chunk in doc.noun_chunks:
            phrase_counts[chunk.text] += 1

for phrase, n in phrase_counts.most_common(50):
    print(f"{n:>5}  {phrase}")
# 3122  user account
# 2410  house listing
# 1880  pet sit application
# 1655  customer subscription
# 1402  payment method

Filter the top-N against a generic-code corpus (see concept-tfidf-rare-terms) so framework noun phrases like "http response" don't dominate. The combination of POS + IDF leaves a high-purity domain entity list.

Combine with `ling-abbreviation-expansion` before chunking — without expansion, pet_sit_appl reads as three short noun tokens and the chunker drops it.

When NOT to apply:

• Languages where identifiers are short cryptic codes (legacy Fortran, COBOL) — POS tagging on EMPMAST is useless
• Codebases written in a language other than English — load a non-English spaCy model or skip

Reference: Allamanis et al., Mining Source Code Repositories at Massive Scale, spaCy noun chunks

Use TF-IDF Against a Generic Corpus to Separate Domain Vocabulary from Framework Noise

The most-frequent words in a codebase are always framework words — request, controller, response, model — not domain words. To isolate domain vocabulary, compute Term Frequency in this codebase but use Inverse Document Frequency from a generic code corpus (a sample of unrelated open-source projects in the same language). Terms with high TF in this repo and high IDF against the generic corpus are domain-specific. controller has high TF here but low IDF (every repo uses it) → demoted. sitterApplication has high TF here and high IDF (no other repo uses it) → promoted to the top. The result is a ranked list of words that genuinely define what this codebase is about.

Incorrect (raw frequency — top results are always framework noise):

import re, pathlib, collections

WORD = re.compile(r"\b[a-zA-Z_][a-zA-Z0-9_]{3,}\b")
counts = collections.Counter()
for p in pathlib.Path("src").rglob("*.py"):
    counts.update(w.lower() for w in WORD.findall(p.read_text(errors="ignore")))

# Top results: request, response, return, model, view, self, value, data.
# Domain words like "sitter", "listing" are buried at position 200+.
for w, n in counts.most_common(20):
    print(f"{n}\t{w}")

Correct (TF here ÷ DF in generic corpus — domain words rise to the top):

import re, math, pathlib, collections, json

WORD = re.compile(r"\b[a-zA-Z_][a-zA-Z0-9_]{3,}\b")

def tokens(path):
    return [w.lower() for w in WORD.findall(path.read_text(errors="ignore"))]

# Term frequency in THIS repo
tf = collections.Counter()
for p in pathlib.Path("src").rglob("*.py"):
    tf.update(tokens(p))

# Document frequency from a pre-built generic corpus
# (e.g. top-1000 Python repos on GitHub — ship as JSON with the skill)
generic_df: dict[str, int] = json.loads(pathlib.Path("generic_python_df.json").read_text())
N_DOCS_GENERIC = 1000

def domain_score(term: str, count: int) -> float:
    df = generic_df.get(term, 1)                       # smooth missing terms
    idf = math.log((N_DOCS_GENERIC + 1) / (df + 1)) + 1
    return count * idf

scored = sorted(
    ((domain_score(w, c), w, c) for w, c in tf.items() if c >= 5),
    reverse=True,
)
for score, w, c in scored[:25]:
    print(f"{score:>8.1f}  tf={c:>5}  {w}")
# 4821.3  tf=2210  sitter
# 3990.7  tf=1640  housesit
# 3502.9  tf=1310  pet
# 3120.4  tf=1180  listing
#  201.8  tf=8211  request    <- framework noise demoted

Build the generic corpus once, ship it. A generic_python_df.json of ~50k terms × 1000 repos compresses to a few MB. The same file serves every domain-extraction run.

For multi-token entities: compute TF-IDF on the noun-phrase output of concept-noun-phrase-mining, not on bare tokens. Single tokens are too coarse; the phrase sitter_application is more informative than sitter and application separately.

When NOT to apply:

• Repos that are the framework (e.g., Django itself) — generic corpus excludes the very repo you're scoring
• Highly multilingual codebases — IDF only works against a same-language reference corpus

Reference: Salton & Buckley, Term-Weighting Approaches in Automatic Text Retrieval, Sparck Jones, A statistical interpretation of term specificity (1972)

Use Betweenness Centrality to Find Bottleneck Modules

Betweenness centrality measures how often a node sits on the shortest path between other pairs of nodes. In a code graph, a high-betweenness file is a bottleneck: changes to it ripple across the graph, and removing it would shatter the dependency structure. These files are rarely the most-imported (PageRank already finds those) — they're typically modest-import-count files sitting on critical paths between sub-systems. They are exactly the files where one careless refactor breaks five seemingly-unrelated features.

Incorrect (look at imports / lines-of-code — both miss path-criticality):

# Files ranked by LoC and import count. A file with 30 imports
# and 2000 LoC looks "big" but might be a leaf service.
# Meanwhile a 200-LoC adapter that bridges two large sub-systems
# scores low here — yet it is the actual bottleneck.
import pathlib

stats = []
for p in pathlib.Path("src").rglob("*.py"):
    src = p.read_text(errors="ignore")
    loc = len([l for l in src.splitlines() if l.strip()])
    imports = src.count("import ")
    stats.append((loc + 10 * imports, p))
for score, p in sorted(stats, reverse=True)[:10]:
    print(f"  {score:>5}  {p}")

Correct (betweenness centrality on the file graph — bottlenecks surface):

import ast, pathlib
import networkx as nx

G = nx.Graph()                                       # undirected for shortest paths
files = list(pathlib.Path("src").rglob("*.py"))
mod_map = {".".join(p.relative_to("src").with_suffix("").parts): str(p) for p in files}

for p in files:
    G.add_node(str(p))
    try: tree = ast.parse(p.read_text(errors="ignore"))
    except SyntaxError: continue
    for node in ast.walk(tree):
        if isinstance(node, ast.ImportFrom) and node.module in mod_map:
            G.add_edge(str(p), mod_map[node.module])

# Exact betweenness is O(V·E); use the approximation for large graphs
if len(G) > 5000:
    bc = nx.betweenness_centrality(G, k=500, seed=42)   # k=500 sample
else:
    bc = nx.betweenness_centrality(G)

top = sorted(bc.items(), key=lambda kv: -kv[1])[:15]
for path, score in top:
    print(f"  {score:.4f}  {path}")
# 0.142  src/adapters/payments/gateway.py     <- bridges billing & ledger
# 0.118  src/core/events/bus.py               <- the bus everything goes over
# 0.097  src/integrations/stripe/client.py
# 0.084  src/adapters/messaging/dispatch.py

Compare with PageRank. A file high on PageRank but low on betweenness is a popular dependency (e.g., a logging helper). A file high on betweenness but low on PageRank is a bridge — far more dangerous to refactor without care, because its callers are diverse.

Use edge-betweenness for cycle-breaking decisions. nx.edge_betweenness_centrality(G) ranks edges the same way; the highest-scoring edges are the import statements you should delete first when breaking a tangle (see graph-feedback-arcs).

Combine with `mine-change-coupling`: a high-betweenness file that also has high temporal coupling with many others is a refactoring target — it carries architectural load and changes constantly.

When NOT to apply:

• Densely-connected graphs (everything imports everything) — betweenness scores all converge and the ranking is uninformative
• Real-time use — betweenness on a 50k-node graph takes minutes even with sampling; precompute and store

Reference: Freeman, A set of measures of centrality based on betweenness (Sociometry 1977), Brandes, A faster algorithm for betweenness centrality (2001)

Approximate Minimum Feedback Arc Set to Choose the Smallest Cycle-Breaking Cut

Once graph-scc-cycle-tangles has found a tangle, the next question is: what is the smallest set of import statements I can delete (or invert) to make the tangle acyclic? That set is called a Feedback Arc Set, and finding the minimum is NP-hard. But the Eades–Lin–Smyth greedy approximation runs in O(V+E) and produces a feedback arc set within a small constant factor of optimum on real codebases. The output is a ranked list of edges to break — far more actionable than "this tangle has 12 files, good luck."

Incorrect (delete an arbitrary edge in each cycle — often picks the wrong one):

# Find a cycle, delete any edge in it. Repeat until acyclic.
# Often breaks an edge that was the cheap one to keep and leaves
# the expensive ones. Result: more edits than necessary.
import networkx as nx

def break_cycles_naive(G: nx.DiGraph) -> list[tuple]:
    deleted = []
    try:
        while True:
            cycle = nx.find_cycle(G)
            G.remove_edge(*cycle[0])               # always the first edge
            deleted.append(cycle[0])
    except nx.NetworkXNoCycle:
        return deleted

Correct (Eades–Lin–Smyth greedy — minimum-ish FAS in linear time):

import networkx as nx
from collections import deque

def eades_feedback_arc_set(G: nx.DiGraph) -> list[tuple]:
    """
    Eades, Lin, Smyth (1993): A fast and effective heuristic for the FAS problem.
    Repeatedly pull sinks, then sources, then highest delta(v) = outdeg - indeg.
    Edges to delete = edges going "backward" in the resulting ordering.
    """
    H = G.copy()
    s1: deque[str] = deque()
    s2: deque[str] = deque()
    while H.number_of_nodes() > 0:
        # Sinks: out-degree 0 -> append to s2 from the right
        while True:
            sinks = [v for v in H if H.out_degree(v) == 0]
            if not sinks: break
            for v in sinks: s2.appendleft(v); H.remove_node(v)
        # Sources: in-degree 0 -> append to s1
        while True:
            sources = [v for v in H if H.in_degree(v) == 0]
            if not sources: break
            for v in sources: s1.append(v); H.remove_node(v)
        if H.number_of_nodes() == 0: break
        # Otherwise: pick max delta(v)
        v = max(H, key=lambda x: H.out_degree(x) - H.in_degree(x))
        s1.append(v); H.remove_node(v)

    ordering = list(s1) + list(s2)
    pos = {v: i for i, v in enumerate(ordering)}
    return [(u, v) for u, v in G.edges() if pos[u] > pos[v]]    # backward edges

# Usage on a tangle
import ast, pathlib
G = nx.DiGraph()
# ... build import graph as before ...
sccs = [c for c in nx.strongly_connected_components(G) if len(c) > 1]
worst = max(sccs, key=len)
sub = G.subgraph(worst).copy()

cut = eades_feedback_arc_set(sub)
print(f"Tangle has {sub.number_of_edges()} edges; breaking {len(cut)} makes it acyclic.")
for u, v in cut:
    print(f"  break: {u}  -- imports -->  {v}")

Weight edges by cost-of-breaking to bias the cut toward cheap edges to remove. A useful weight: number of identifiers actually imported from the module. Edges that import many symbols are harder to break (you'd have to provide alternatives for each); edges importing one symbol are cheap. Apply the weight by duplicating cheap edges or by replacing the greedy delta with a weighted variant.

Use the inverse of the FAS as a refactor plan. The ordering produced by Eades-Lin-Smyth is the dependency order you should aim for after the refactor. Files near the start of the ordering should depend on nothing in the tangle; files near the end depend on everything. Make the ordering match physical module layout.

Combine with `graph-betweenness-bottlenecks`: edges in the FAS that are also high in edge-betweenness are doubly motivated to delete — they break cycles AND reduce graph fragility.

When NOT to apply:

• Tangles under 4-5 files — eyeballing the cycle and picking by hand is faster
• Cycles you can't break by edge removal (legitimate mutual recursion) — use dependency inversion (interfaces) instead; FAS gives the answer but you implement it differently

Reference: Eades, Lin, Smyth, A fast and effective heuristic for the feedback arc set problem (1993), Berger & Shor, Approximation algorithms for the maximum acyclic subgraph problem (1990)

Apply Louvain Community Detection to Reveal Natural Module Boundaries

The folder structure of a 5-year-old codebase rarely matches its actual modular structure. Files that used to belong together have drifted across directories; files that share no real coupling sit next to each other. Louvain community detection (Blondel et al., 2008) maximizes graph modularity in O(N log N) — fast enough for million-node graphs — and partitions the import/call graph into communities that actually coheres. Differences between this partition and the directory tree are a directly-actionable list of files to move.

Incorrect (use directory structure as the modular partition — assumes folders match reality):

# Treat each top-level directory as a module.
# Wrong on any codebase older than ~2 years.
import pathlib

modules = {p.name: list(p.rglob("*.py")) for p in pathlib.Path("src").iterdir() if p.is_dir()}
# Files have been moved, renamed, split, merged for years —
# directories no longer reflect the actual coupling structure.

Correct (Louvain on the file-import graph — communities = real modules):

import ast, pathlib
import networkx as nx

G = nx.Graph()
files = list(pathlib.Path("src").rglob("*.py"))
mod_map = {".".join(p.relative_to("src").with_suffix("").parts): str(p) for p in files}

for p in files:
    G.add_node(str(p))
    try: tree = ast.parse(p.read_text(errors="ignore"))
    except SyntaxError: continue
    for node in ast.walk(tree):
        if isinstance(node, ast.ImportFrom) and node.module in mod_map:
            G.add_edge(str(p), mod_map[node.module])

communities = nx.community.louvain_communities(G, resolution=1.0, seed=42)
modularity = nx.community.modularity(G, communities)
print(f"Communities: {len(communities)}  Modularity Q: {modularity:.3f}")

# Compare against directory partition: files in same community but different directory
# are misplaced; files in same directory but different communities are leaky.
from collections import Counter
for i, comm in enumerate(sorted(communities, key=len, reverse=True)[:6]):
    dir_dist = Counter(str(pathlib.Path(f).parent) for f in comm)
    top_dirs = dir_dist.most_common(3)
    print(f"Community {i}: |{len(comm)}|  directories: {top_dirs}")
# Community 0: |42|  directories: [('src/billing', 18), ('src/admin', 14), ('src/api', 10)]
#   -> billing + admin + api all share a community — billing logic leaked into admin & api

Tune `resolution`. Higher (≥1.5) produces more, smaller communities; lower (≤0.7) produces fewer, larger ones. Sweep and pick the level that maximizes intuitive understanding — modularity Q is a useful signal but not the goal.

A modularity Q above ~0.4 means the codebase has real modular structure; below 0.2 means it is a "ball of mud" — the algorithm finds little to partition. Knowing this upfront sets expectations for any refactoring effort.

Pair with `concept-tfidf-rare-terms` per community to name the communities. A community's top TF-IDF domain terms are usually a coherent label.

Combine with `mine-change-coupling`: Louvain on the temporal coupling graph (files that change together) often differs sharply from Louvain on the static import graph. The difference points to architectural drift: places where structure says one thing and history says another.

When NOT to apply:

• Codebases where one giant file imports everything — Louvain collapses into one community
• When you need stable community membership across runs — Louvain is non-deterministic without seed=; use Leiden (leidenalg) for guaranteed convergence

Reference: Blondel et al., Fast unfolding of communities in large networks (2008), Traag et al., From Louvain to Leiden (2019)

Run PageRank on the Import Graph to Find the Codebase Core

When you join a new codebase, the highest-leverage move is to read the ~20 files that everything else depends on — the "core" — before reading any features. PageRank on the directed import graph identifies these files automatically. A file imported by many other important files gets a high score. The eigenvector behind the algorithm bakes in the recursive property: importance is conferred by other important things. The output is a ranked file list; reading the top 20 gives you the codebase's mental model in an afternoon, not three weeks.

Incorrect (sort by in-degree — confuses popular with central):

# Naive: count how many files import each file.
import ast, pathlib, collections

in_degree: collections.Counter = collections.Counter()
for p in pathlib.Path("src").rglob("*.py"):
    try: tree = ast.parse(p.read_text(errors="ignore"))
    except SyntaxError: continue
    for node in ast.walk(tree):
        if isinstance(node, ast.ImportFrom) and node.module:
            in_degree[node.module] += 1

# Top results: "logging" (imported 800x), "typing", "os".
# These are popular but not *central* — they are leaves of the
# import DAG, not hubs. Importing them tells you nothing.
for mod, n in in_degree.most_common(10):
    print(f"  {n:>5}  {mod}")

Correct (PageRank — importance propagates through the graph):

import ast, pathlib
import networkx as nx

# Build directed graph: edge A -> B means A imports B
G = nx.DiGraph()
files = list(pathlib.Path("src").rglob("*.py"))
mod_map = {".".join(p.relative_to("src").with_suffix("").parts): str(p) for p in files}

for p in files:
    src_node = str(p)
    G.add_node(src_node)
    try: tree = ast.parse(p.read_text(errors="ignore"))
    except SyntaxError: continue
    for node in ast.walk(tree):
        if isinstance(node, ast.ImportFrom) and node.module in mod_map:
            G.add_edge(src_node, mod_map[node.module])

# PageRank — damping 0.85 is the standard from Brin & Page
pr = nx.pagerank(G, alpha=0.85)
top = sorted(pr.items(), key=lambda kv: -kv[1])[:20]
for path, score in top:
    print(f"  {score:.4f}  {path}")
# 0.0421  src/core/db/session.py        <- everything goes through this
# 0.0398  src/core/auth/context.py
# 0.0367  src/domain/listing/repository.py
# 0.0341  src/api/response.py
# 0.0289  src/domain/sitter/repository.py

Reverse the edge direction to find files that use the most rather than files that are used the most — useful for finding the top-level entry points of the system. nx.pagerank(G.reverse()).

Weight by import frequency if your language allows multiple imports from the same module (Python's from x import a, b, c). Counting each import statement as edge weight slightly improves precision on heavily-fanned-in modules.

Read the top-20 in order on day one. This is the single highest-ROI orientation activity in a new codebase — far more than reading READMEs or top-level directories.

Combine with `mine-hotspots-churn-complexity`: files high on PageRank and high on churn × complexity are the architectural debt magnets. Reading them tells you where the codebase's pain lives.

When NOT to apply:

• Monorepos with many independent packages — run PageRank per package, not globally; otherwise low-coupling packages dilute the score
• Dynamic-import-heavy codebases (factory patterns) — static import graph misses runtime dependencies; use a runtime call profile instead

Reference: Brin & Page, The Anatomy of a Large-Scale Hypertextual Web Search Engine, NetworkX pagerank

Use Strongly Connected Components to Find Dependency Cycle Tangles

A clean codebase has a directed acyclic dependency graph. A real codebase has cycles — A.py imports B.py, which imports C.py, which imports A.py. These cycles often hide behind multi-step paths and are invisible to "did you add a circular import?" linters. Tarjan's SCC algorithm finds every strongly-connected component (every maximal set of files where everyone can reach everyone) in O(V+E). Any SCC with size > 1 is a tangle — a cluster of files that must move together because they cannot be separated. Refactoring starts with knowing where the tangles are.

Incorrect (catch cycles only when Python raises ImportError — most cycles hide):

# Python silently allows many "almost-circular" import patterns
# via deferred imports inside functions. The runtime never raises
# but the static graph has cycles. Waiting for ImportError misses
# 90%+ of real tangles.
try:
    import src.app                              # if it runs, "no cycles"
except ImportError as e:
    print("Cycle detected:", e)

Correct (Tarjan's SCC on the static import graph — every tangle surfaces):

import ast, pathlib
import networkx as nx

G = nx.DiGraph()
files = list(pathlib.Path("src").rglob("*.py"))
mod_map = {".".join(p.relative_to("src").with_suffix("").parts): str(p) for p in files}

for p in files:
    G.add_node(str(p))
    try: tree = ast.parse(p.read_text(errors="ignore"))
    except SyntaxError: continue
    for node in ast.walk(tree):
        if isinstance(node, ast.ImportFrom) and node.module in mod_map:
            G.add_edge(str(p), mod_map[node.module])

# Tarjan finds SCCs in O(V + E)
sccs = [c for c in nx.strongly_connected_components(G) if len(c) > 1]
sccs.sort(key=len, reverse=True)

print(f"Found {len(sccs)} cycle tangles, largest has {len(sccs[0])} files")
for i, scc in enumerate(sccs[:5]):
    print(f"\nTangle {i} ({len(scc)} files):")
    for f in scc:
        # In-degree within the SCC = how many cycle-mates need this file
        in_within = sum(1 for u in G.predecessors(f) if u in scc)
        print(f"  in_within={in_within:>2}  {f}")

Order tangles by size of SCC × external impact. The biggest tangle is the most painful to break, but a small tangle right at the architectural core can cause more damage than a large peripheral one. Multiply tangle size by the sum of PageRank of its members for a "tangle priority" score.

Pick the right cut. Inside a tangle, run nx.algorithms.minimum_edge_cut(scc_subgraph) or compute edge betweenness within the SCC — the high-betweenness edges are the import statements to break first. This is the bridge to graph-feedback-arcs.

Identify "false cycles" caused by re-exports. Common pattern: pkg/__init__.py re-exports symbols from sub-modules, then sub-modules import from pkg. The cycle is a packaging accident, not a logical loop. Filter SCCs whose only edges go through __init__.py files before alerting.

Combine with `mine-change-coupling`: SCCs whose members ALSO change together are real coupling. SCCs whose members never change together are accidents of the static graph — usually safe to leave.

When NOT to apply:

• Languages where circular imports are intentional (Haskell modules) — SCCs aren't a defect signal there
• Codebases with heavy lazy imports — static analysis under-reports the graph; combine with runtime import tracing

Reference: Tarjan, Depth-first search and linear graph algorithms (SIAM 1972), NetworkX strongly_connected_components

Expand Identifier Abbreviations Against a Domain Dictionary

After camel/snake splitting, the resulting tokens are still polluted by abbreviations: idx, mgr, cfg, usr, addr. To downstream algorithms these are distinct from index, manager, config, user, address — yet semantically they're the same words. Abbreviation expansion maps each short form to its canonical long form. A combined approach — community dictionary for common abbreviations + corpus-mined expansions for project-specific ones — recovers most of the lost signal. The output is a vocabulary 30-40% smaller and substantially less fragmented.

Incorrect (treat abbreviations and their expansions as different tokens — synonym dilution):

# After camel/snake split, "userManager" and "usrMgr" produce
# {user, manager} and {usr, mgr}. Topic models split this concept,
# similarity scores miss the match. Two buckets per real word.

Correct (expand with a dictionary + project-mined map, then index):

import re, collections, pathlib

# 1. Community dictionary for common abbreviations.
#    Curate this once and reuse across projects.
COMMON_ABBREV = {
    "idx": "index", "mgr": "manager", "cfg": "config", "usr": "user",
    "addr": "address", "auth": "authentication", "msg": "message",
    "req": "request", "resp": "response", "err": "error", "val": "value",
    "num": "number", "obj": "object", "ctx": "context", "txn": "transaction",
    "qty": "quantity", "amt": "amount", "ts": "timestamp", "dt": "datetime",
    "btn": "button", "ack": "acknowledgement", "len": "length", "max": "maximum",
    "min": "minimum", "alloc": "allocate", "init": "initialize", "img": "image",
    "evt": "event", "perm": "permission", "pkg": "package", "lib": "library",
}

# 2. Mine project-specific abbreviations: if "sitter" and "sttr" co-occur
#    in the same files frequently, treat "sttr" -> "sitter".
def mine_project_abbrev(token_counts: collections.Counter,
                        co_occur: collections.Counter,
                        min_overlap: float = 0.7) -> dict[str, str]:
    """For each candidate short token, find the long token it commonly co-occurs with
    and whose Levenshtein-normalized prefix overlap exceeds threshold."""
    from rapidfuzz.distance import Levenshtein
    long_terms = [t for t, c in token_counts.items() if len(t) >= 5 and c >= 20]
    short_terms = [t for t, c in token_counts.items() if 2 <= len(t) <= 4 and c >= 10]
    project_map = {}
    for short in short_terms:
        best_score = 0
        best_long = None
        for long in long_terms:
            if not long.startswith(short[0]): continue
            # Co-occurrence count + edit-distance proximity
            co = co_occur.get(tuple(sorted([short, long])), 0)
            if co < 5: continue
            ed_norm = 1 - Levenshtein.normalized_distance(short, long[:len(short) + 2])
            score = co * ed_norm
            if score > best_score:
                best_score = score
                best_long = long
        if best_long and best_score > min_overlap * token_counts[short]:
            project_map[short] = best_long
    return project_map

# 3. Combine and apply uniformly
def expand(token: str, expansion_map: dict) -> str:
    return expansion_map.get(token, token)

# Project-specific abbreviations might include {"sttr": "sitter", "lstng": "listing"}
# Combined map is applied to every identifier token before any downstream algorithm.
full_map = {**COMMON_ABBREV}                         # then merge mined map

Validate the project-mined map by hand. Auto-mining produces ~80% correct expansions but the wrong ones can be very wrong (io → iota, id → idle). Have a human approve the top-100 mined expansions before applying — it takes 15 minutes.

Order matters: split → expand → stem. Apply this rule between ling-camel-snake-split and ling-porter-stemming. Stemming an unexpanded usr gives you usr; stemming user gives you user. The combined pipeline produces a clean vocabulary that's stable across spelling variants.

For identifier-heavy languages (Java, C#) the impact is largest. Languages with looser conventions (Python, JS, Ruby) tend toward written-out names already; the dictionary helps but mining yields less. Measure your specific gain on a held-out set.

Combine with `concept-entity-name-resolution` for the most aggressive normalization. Abbreviation expansion handles spelling variants of the same word; entity resolution handles synonyms (user ↔ customer ↔ member). The two complement.

When NOT to apply:

• Codebases with intentionally-cryptic identifiers (heavily golfed code, generated symbols) — expansion adds noise
• Single-letter loop variables (i, j, k) — exclude from expansion entirely; they carry no semantic content

Reference: Lawrie et al., Effective Identifier Names for Comprehension and Memory (ISSE 2007), Corazza et al., Identifier Expansion via TF-IDF (CASCON 2012)

Split camelCase and snake_case Identifiers Before Any Text Analysis

Every algorithm in this skill — TF-IDF, LDA, embeddings, clone detection, bug localization — fails silently if you forget to split identifiers. Treating userId, user_id, and usrIdent as three distinct tokens shatters vocabulary across spelling variants and produces nonsense topics, weak similarity, and useless clones. The correct preprocessing applies a single regex that handles camelCase, snake_case, screaming-snake, dotted (pkg.Class.method), and digits at boundaries. Do this once at the start of every pipeline, validate the output on a sample, and forget it.

Incorrect (use the raw identifier as a token — every spelling variant is its own bucket):

import collections, pathlib, re

# Raw identifier tokenization. "userId" and "user_id" and "USER_ID"
# all count separately — vocabulary fragments, topics break.
RAW = re.compile(r"[A-Za-z_][A-Za-z0-9_]{2,}")
counts = collections.Counter()
for p in pathlib.Path("src").rglob("*.py"):
    counts.update(RAW.findall(p.read_text(errors="ignore")))
# Top entries: userId, user_id, USER_ID, usrId — same concept, four buckets.

Correct (split on case/underscore/digit boundaries, lowercase, output sub-tokens):

import re, collections, pathlib

# Combined camelCase + snake_case + digit-boundary splitter.
# Tested against the Allamanis identifier-splitting corpus.
SPLIT = re.compile(
    r"""
    [A-Z]+(?=[A-Z][a-z])    |    # APIKey -> "API" "Key"
    [A-Z]?[a-z]+            |    # PascalCase or camelCase "case" parts
    [A-Z]+                  |    # all-caps acronym (URL, HTML)
    \d+                          # numeric parts
    """,
    re.VERBOSE,
)

def split_identifier(name: str) -> list[str]:
    return [t.lower() for t in SPLIT.findall(name)]

# Sanity checks
assert split_identifier("getUserById") == ["get", "user", "by", "id"]
assert split_identifier("user_id_2") == ["user", "id", "2"]
assert split_identifier("HTMLParser") == ["html", "parser"]
assert split_identifier("getHTTP2URL") == ["get", "http", "2", "url"]
assert split_identifier("USER_ROLE_ADMIN") == ["user", "role", "admin"]

# Apply everywhere
IDENT = re.compile(r"[A-Za-z_][A-Za-z0-9_]{1,}")
counts = collections.Counter()
for p in pathlib.Path("src").rglob("*.py"):
    for ident in IDENT.findall(p.read_text(errors="ignore")):
        counts.update(split_identifier(ident))
# Now "user" is a single token, "id" is a single token — vocabulary is clean.

Validate against a labeled sample. Identifier splitting is the kind of preprocessing that looks right until it isn't. Build a 200-identifier ground-truth list (mix of acronyms, abbreviations, compound nouns, numeric suffixes) and confirm the splitter agrees on >95% before trusting it.

Use [spiral](https://github.com/casics/spiral) for production-quality splitting. The regex above handles common cases; spiral handles long sequences of acronyms (XMLHttpRequest), domain-specific abbreviations (URLEncoder), and concatenated lowercase (numfound → num, found) that regex cannot. It's slower (a small ML model) but worth it for serious analysis.

This rule is upstream of every other rule in this skill. If you forget it, every downstream signal degrades — topics fragment, clone detection misses, bug localization scores noisier matches. Validate it FIRST.

When NOT to apply:

• Code where identifiers are intentional opaque codes (compiler-generated names, obfuscated builds) — splitting produces garbage
• Single-language repos where the convention is strictly enforced (e.g., only snake_case) — a simpler split-on-underscore is sufficient

Reference: Hill & Pollock, Automatically Mining Identifier-name Conventions (ICSE 2009), Spiral identifier-splitter

Apply Porter Stemming to Unify Singular and Plural Token Forms

After splitting and expanding, you still have user/users/userService/Userize as distinct tokens, even though all four share the root user. The Porter stemmer (1980, still the standard) reduces every word to a deterministic root via a small set of rewrite rules. It's not a lemmatizer (no dictionary) — users → user, running → run, policies → polici. The "polici" stems are ugly but they're consistent: every form of "policy" maps to the same root token, which is all downstream algorithms need. Use it in any pipeline that compares vocabularies, ranks documents, or clusters by content.

Incorrect (every grammatical variant as a separate token — recall drops):

# Bug report says: "policies are being deleted incorrectly"
# Source uses: "policy", "policyService", "Policies"
# TF-IDF matches nothing — different tokens entirely.

import collections, re

WORD = re.compile(r"[A-Za-z_][A-Za-z0-9_]{2,}")
def tokens(text):
    return WORD.findall(text.lower())

counts = collections.Counter(tokens("policy policies policy_service Policies"))
# {'policy': 1, 'policies': 1, 'policy_service': 1, 'Policies': 1} — wait, normalize case at least.
# Even after lowercasing: {'policy': 1, 'policies': 2, 'policy_service': 1}
# Should be one bucket; it's three.

Correct (lowercase + stem — singular/plural/derivational forms collapse):

import re, collections
from nltk.stem.porter import PorterStemmer       # pip install nltk

stemmer = PorterStemmer()
WORD = re.compile(r"[A-Za-z_][A-Za-z0-9_]{2,}")

def normalize(text: str) -> list[str]:
    return [stemmer.stem(w) for w in WORD.findall(text.lower())]

# Apply uniformly to source and query
source_tokens = normalize("policy policies policy_service Policies")
query_tokens = normalize("policies are being deleted incorrectly")

print(collections.Counter(source_tokens))
# {'polici': 3, 'polici_servic': 1}
print(query_tokens)
# ['polici', 'are', 'be', 'delet', 'incorrectli']
# Now 'polici' matches between source and query — recall is restored.

Use Snowball / Porter2 in production. The original 1980 Porter has minor bugs; Snowball (Porter's own 2001 successor, in NLTK as SnowballStemmer("english")) fixes them and supports 16+ languages. For multilingual corpora, Snowball is the right choice.

Stemming destroys human-readability of the index — you can't show users "polici" as a search hint. Keep the original→stem map and display the most-frequent original form for any stem.

Don't double-stem. Stemming is idempotent on its own output, but applying two different stemmers (Porter then Snowball) produces noise. Pick one and stick with it across all stages of a pipeline.

Lemmatization is better when accuracy matters, but slower. spaCy lemmatization produces real words (policies → policy, running → run) using a dictionary. For information retrieval over millions of files, Porter's speed wins; for human-facing analysis (top-terms reports), use spaCy's lemmatizer.

Combine with `ling-abbreviation-expansion` first, then stem. Order matters: stem before expansion produces mgr → mgr (no rule fires); expand-then-stem produces mgr → manager → manag which matches all variants of management. Pipeline order: split → expand → stem.

This rule alone is the smallest improvement in this category but compounds with the others. The full preprocessing chain (split + expand + stem) typically collapses 30-50% of vocabulary into shared roots — which is the difference between TF-IDF working and TF-IDF being noise on identifier-heavy code.

When NOT to apply:

• Languages with rich morphology (Finnish, Turkish) — Porter is English-only; use a language-appropriate stemmer or lemmatizer
• Single-token identifier search (find every place that defines User class) — stemming over-matches; use exact match instead

Reference: Porter, An algorithm for suffix stripping (Program 1980), Snowball — multilingual stemmer

Tag Identifier Tokens with POS to Find Misnamed Functions and Classes

A small style convention with disproportionate consequence: functions should start with verbs, classes/types should be nouns. Codebases that follow this convention are easier to read, search, and statically analyze. Violators (function userData(), class Validate) hide intent and break naming-based heuristics. POS-tag the leading token of every identifier and check it against the expected category. The mismatches are a cheap renaming backlog with high readability ROI; the rate of mismatches is also a useful proxy for "how disciplined was this team's naming?".

Incorrect (eyeball + grep for "bad names" — ad-hoc and inconsistent):

# A code reviewer comments "this should be a verb" when they notice.
# 90% of mismatches slip through review because no one notices.
grep -r "def " src/ | head -10
# Returns every function definition; reviewer scans visually.
# Inconsistent and obviously not run on legacy code.

Correct (POS-tag the leading split-token, flag category mismatches):

import ast, re, pathlib
import spacy

nlp = spacy.load("en_core_web_sm")
SPLIT = re.compile(r"[A-Z]?[a-z]+|[A-Z]+(?=[A-Z]|$)")

def first_word(identifier: str) -> str | None:
    parts = SPLIT.findall(identifier)
    return parts[0].lower() if parts else None

def pos_of(word: str) -> str:
    # Single-word POS tagging — supply a verb-form sentence frame for accuracy
    doc = nlp(f"I want to {word} it.")
    return doc[3].pos_                              # POS of the verb-slot word

def is_verb(word: str) -> bool:
    return pos_of(word) in {"VERB", "AUX"} or word in CUSTOM_VERBS

CUSTOM_VERBS = {                                    # whitelist code-specific verbs
    "init", "destroy", "render", "serialize", "lookup", "fetch", "parse",
    "marshal", "diff", "ack", "dispatch", "yield", "fork", "spawn",
}
CUSTOM_NOUN_ROOTS = {                               # tokens that "look like" verbs but aren't
    "data", "info", "service", "user", "process",   # 'process' as a noun in code
}

flags = []
for p in pathlib.Path("src").rglob("*.py"):
    try: tree = ast.parse(p.read_text(errors="ignore"))
    except SyntaxError: continue
    for node in ast.walk(tree):
        if isinstance(node, ast.FunctionDef):
            head = first_word(node.name)
            if head and not is_verb(head) and head not in CUSTOM_VERBS:
                flags.append((str(p), node.lineno, "function-not-verb", node.name))
        elif isinstance(node, ast.ClassDef):
            head = first_word(node.name)
            if head and is_verb(head) and head not in CUSTOM_NOUN_ROOTS:
                flags.append((str(p), node.lineno, "class-not-noun", node.name))

for path, line, kind, name in flags[:25]:
    print(f"  {path}:{line}  {kind:>18}  {name}")
# src/api/handlers.py:142  function-not-verb  userData      -> rename to getUserData / fetchUser
# src/billing/validate.py:88 class-not-noun    Validate      -> rename to Validator

Tune CUSTOM_VERBS for your domain. Code uses many specialized verbs that spaCy doesn't tag as verbs out of the box (render, marshal, dispatch, ack). Curate a per-language whitelist; without it, false-positive rate is too high to be useful.

This is the simplest rule in this skill, and one of the most overlooked. Most codebases have a 5-10% rate of convention violations; surfacing them gives clear, agreed-upon renaming tasks that improve readability with zero design risk.

*Use the rate as a code-health metric.* A codebase with <2% violation rate has disciplined naming; >15% means naming convention isn't being enforced and other naming-based heuristics (clone detection, similarity ranking) will degrade.

Combine with `concept-noun-phrase-mining`: the noun phrases in your codebase represent domain entities. POS-mismatched functions or classes block extraction — fix them first, then re-run mining for better coverage.

Pre-tag with a frame ("I want to ${word} it."). Tagging a bare word out of context produces unreliable POS labels for ambiguous words like "log" or "match". A grammatical frame disambiguates without adding much code.

When NOT to apply:

• Languages where the convention is opposite or absent (Lisp, Haskell idioms differ) — adapt the rule or skip
• Domain-specific languages where identifiers are physical units (meters, volts) — POS tagging produces noise; whitelist heavily

Reference: Caprile & Tonella, Restructuring Program Identifier Names (ICSM 2000), spaCy POS tagging docs

Use BM25 over TF-IDF when Source Files Vary Greatly in Length

TF-IDF treats a 100-LoC file and a 5000-LoC file with the same vocabulary as equally relevant — long files have inflated TF and dominate the ranking. BM25 (Robertson & Spärck Jones, 1994) fixes both problems: a length-normalization factor adjusts for file size, and a TF-saturation function (k1 parameter) prevents repeated occurrences from gaining more than logarithmic weight. The result: BM25 reliably picks the most relevant file rather than the longest file. It's the ranking function in Elasticsearch / Lucene, in Sourcegraph, and in every serious code-search system built in the last decade. Default it for any bug-localization or feature-localization task in a repo with diverse file sizes.

Incorrect (raw TF-IDF — long files dominate, repeated terms inflate scores linearly):

import math, collections

# Toy TF-IDF without saturation or length normalization
class NaiveTFIDF:
    def __init__(self, docs):
        self.n = len(docs)
        self.df = collections.Counter()
        self.docs = []
        for d in docs:
            toks = d.split()
            self.docs.append(toks)
            for t in set(toks): self.df[t] += 1

    def score(self, query: list[str], doc_id: int) -> float:
        d = self.docs[doc_id]
        tf = collections.Counter(d)
        return sum(tf[q] * math.log(self.n / (1 + self.df[q])) for q in query)

# A long file with "checkout" repeated 50 times beats a focused
# 100-LoC file where "checkout" is the entire topic with TF=8.

Correct (BM25 — TF saturates, document length is normalized):

# pip install rank-bm25
import re, pathlib
from rank_bm25 import BM25Okapi

WORD = re.compile(r"[A-Za-z_][A-Za-z0-9_]{2,}")
files = list(pathlib.Path("src").rglob("*.py"))

def tokens(text: str) -> list[str]:
    return [w.lower() for w in WORD.findall(text)]

corpus = [tokens(p.read_text(errors="ignore")) for p in files]
bm25 = BM25Okapi(corpus, k1=1.5, b=0.75)        # default Lucene params

# Query the index
query = tokens("checkout fails after retry with card declined")
scores = bm25.get_scores(query)

ranked = sorted(zip(scores, files), reverse=True)[:10]
for s, p in ranked:
    print(f"  {s:.2f}  {p}")
# 24.31  src/api/v2/checkout_retry.py    <- focused 80 LoC, all relevant
# 19.78  src/billing/decline_handler.py
# 14.22  src/payments/stripe/retry.py
#  8.61  src/integrations/legacy_sync.py  <- long file, lower despite many "checkout" mentions

Tune k1 and b per corpus.

• k1 (default 1.5): how quickly TF saturates. Lower (1.0) for code with extreme repetition (logs); higher (2.0) for prose-like documents.
• b (default 0.75): how aggressive length normalization is. b=1 fully normalizes; b=0 disables it.

For source code with mixed file sizes, the defaults are good. For markdown-heavy mono-repos, try k1=1.2, b=0.85.

Compare against alternative scoring functions: BM25F handles fielded documents (when you want to weight filename more than body); BM25+ corrects an edge-case where long highly-relevant documents still under-score. Both available in rank_bm25.BM25Plus and via dedicated libraries.

Combine with `local-tfidf-bug-reports` as the underlying ranker — same query/document model, better scoring function. Most "TF-IDF" pipelines published since 2010 are actually BM25 under the hood.

Combine with `local-embedding-bug-text` in a re-ranking pipeline: BM25 retrieves the top-100 candidates fast; an embedding model re-ranks the top-100 with semantic similarity. Final precision exceeds either alone.

When NOT to apply:

• Tiny indexes (<200 files) — overhead exceeds value; raw cosine TF-IDF is enough
• Code in a single language with extremely uniform file sizes — length normalization gains are marginal

Reference: Robertson & Spärck Jones, Relevance weighting of search terms (JASIS 1976), Robertson, The probabilistic relevance framework: BM25 and beyond

Embed Bug Reports and Source Code in the Same Space for Semantic Localization

The hardest bug-localization case is when the bug report describes user-visible symptoms in natural language and the source code uses entirely different technical vocabulary. "Users see a duplicated invoice line" matches src/billing/line_item_dedup.py — a file where neither "invoice" nor "duplicated" appears in the way the user thinks of them. TF-IDF and BM25 fail this case. CodeBERT / UniXcoder were trained on paired natural language and code, so they embed both into the same vector space. Cosine similarity in that space finds semantic matches no IR scheme can. Use it as the re-ranker on top of BM25 candidates.

Incorrect (BM25 alone — fails when vocabulary doesn't overlap):

# Bug: "Users see a duplicated invoice line on monthly statements"
# Source: src/billing/line_item_dedup.py uses "dedup", "lineItem", "monthly_bill"
# No token overlap. BM25 returns irrelevant files.

from rank_bm25 import BM25Okapi
# ... vocabulary mismatch — top-10 misses the actual buggy file ...

Correct (BM25 candidates → embedding re-rank → hybrid score):

import re, pathlib
import numpy as np
from rank_bm25 import BM25Okapi
from sentence_transformers import SentenceTransformer

# 1. Stage one — BM25 retrieves top-K candidates (fast, lexical)
WORD = re.compile(r"[A-Za-z_][A-Za-z0-9_]{2,}")
files = list(pathlib.Path("src").rglob("*.py"))
texts = [p.read_text(errors="ignore") for p in files]
corpus = [[w.lower() for w in WORD.findall(t)] for t in texts]
bm25 = BM25Okapi(corpus)

bug = "Users see a duplicated invoice line on monthly statements"
bm25_scores = bm25.get_scores([w.lower() for w in WORD.findall(bug)])
top_k_idx = np.argsort(-bm25_scores)[:100]                # K=100 candidates

# 2. Stage two — embedding model re-ranks the K candidates (precise, semantic)
encoder = SentenceTransformer("microsoft/unixcoder-base")
candidate_texts = [texts[i][:4000] for i in top_k_idx]    # truncate to model limit
cand_emb = encoder.encode(candidate_texts, normalize_embeddings=True)
bug_emb = encoder.encode(bug, normalize_embeddings=True)
sem_scores = cand_emb @ bug_emb

# 3. Fuse — normalized BM25 + semantic, weighted
def normalize(arr: np.ndarray) -> np.ndarray:
    rng = arr.max() - arr.min()
    return (arr - arr.min()) / max(rng, 1e-9)

bm25_n = normalize(bm25_scores[top_k_idx])
sem_n = normalize(sem_scores)
final = 0.4 * bm25_n + 0.6 * sem_n

ranked = sorted(zip(final, top_k_idx), reverse=True)[:10]
for s, i in ranked:
    print(f"  {s:.3f}  bm25={bm25_n[list(top_k_idx).index(i)]:.2f}  sem={sem_n[list(top_k_idx).index(i)]:.2f}  {files[i]}")
# 0.812  bm25=0.21  sem=1.00  src/billing/line_item_dedup.py    <- semantic win
# 0.640  bm25=0.62  sem=0.65  src/billing/monthly_statement.py
# 0.587  bm25=0.45  sem=0.68  src/billing/invoice_lines.py

Two-stage retrieval is non-negotiable above ~10k files. Encoding every file at every query is slow. BM25 (fast, broad recall) narrows the candidate set; the embedding model (slow, precise) re-ranks. Final precision exceeds either alone.

Use a small fast model for re-ranking. microsoft/unixcoder-base (110M params) is the sweet spot for code: cross-lingual, paired NL+code, and runs in <500ms per query on CPU. CodeBERT (125M) is similar. Larger models help marginally but pay 10× the latency.

Combine with the history prior from local-history-prior-localization. Three signals (BM25 + embedding + bug-history) fused with weights [0.3, 0.5, 0.2] outperforms any pair on published benchmarks.

Cache file embeddings. Re-encode only files that changed since last index build (use git for the diff). For monorepos, batch encode on a schedule and store in a vector store (faiss / Qdrant / PostgreSQL pgvector).

Combine with `sim-doc-code-alignment`: the same encoder used here can pre-compute doc-section embeddings; bug reports may match documented contracts that the code no longer honours, surfacing both the code location and the doc to update.

When NOT to apply:

• Bug reports that are pure stack traces — embedding a stack trace gives noisy results; jump straight to the top frame's file
• Languages outside the encoder's training set — multilingual coverage matters; use UniXcoder or CodeT5+ which support more languages than CodeBERT

Reference: UniXcoder (Guo et al., 2022), Wang et al., CodeT5+ (2023), Zhou et al., Where Should the Bugs Be Fixed? (ICSE 2012)