数学

01窗口取指纹

判两个文件共享哪些归一化 token 串，指纹取每个窗口的最小值。

t = window + kgram - 1 = 26 + 25 - 1 = 50 个记号

no-miss 下界（Schleimer 等人 SIGMOD'03，作为正确性契约）：长度至少 t 的公共串含 t - k + 1 = w 个连续 k-gram，即一整个窗口，两份拷贝必选出它的同一个最小值。

• kgram 25
• window 26
• 保证阈 t 50
• BASE 1_000_003

推导 · 方法学册 01

02树编辑距离

判近似克隆：TSED ≥ 0.85 的两棵树是克隆。

TSED(a, b) = (max(n1, n2) - ted(a, b)) / max(n1, n2)
clone      ⇔ TSED >= 0.85
cloneDecidesWith (num, den) t n1 n2 = (mx - t) * den >= num * mx  where mx = max n1 n2

单位代价的 Zhang-Shasha（删 = 插 = 1，kind 码相同时 relabel 0，否则 1）恒为整数，边界是精确的交叉相乘：max = 100 时 ted 15 是克隆、ted 16 不是。

• tsedNum 85
• tsedDen 100
• minUnitNodes 24

推导 · 方法学册 02

03shingle 上的 Jaccard

两段文档在 5 词 shingle 上 Jaccard ≥ 0.80、或有 50 词逐字连续段即判重复。

dupDecidesWith num den inter union  =  inter * den >= num * union

dupVerdictWith (num, den, vfloor) inter union run
  =  dupDecidesWith num den inter union  ||  run >= vfloor

MinHash/LSH 只提名候选对，且无 RNG（置换下标即盐）；判决是精确的整数比较。

• jaccardNum 80
• jaccardDen 100
• shingleK 5
• verbatimFloor 50

推导 · 方法学册 03

18克隆合并

克隆组成员的差异处成为洞，每个不同的取值向量一个参数：至多 6 个，且确有省行才可行。

align  : T1/T2 同构，洞 = 不同的叶；T3 取自顶向下收窄的树编辑映射，重标与不等长间隙是洞
params : 每个不同的取值向量一个；可行当且仅当每个洞都是表达式或名字、params ≤ 6 且 savings > 0

反统一：取每个成员都是其实例的最小一般骨架，用各成员自己的值填洞即还原该成员。

• groupCap 4096
• treeNodeCap 131072
• paramCap 6

推导 · 方法学册 18

04Tsallis-2 与 χ²

目录多样性与布局散度，全程精确有理数。

tsallis2 cs     = 1 - Σ (c/N)^2            -- N == 0 时也 = 0
tsallis2Norm cs = tsallis2 cs / (1 - 1/n)  -- n = 非零桶数，n > 1
chi2 pairs      = Σ_{r > 0} (p - q)^2 / q  -- p = o/Σo, q = r/Σr
perMille r      = floor (r * 1000)

Shannon 熵与 KL 需要对数（无理数，不可精确判定），故改用同族中不取对数的成员 Tsallis-2 与 χ² f-散度，跑在 Data.Ratio 上；参考质量为 0 的 bin 上有观测质量时 χ² 返回 Nothing——点名那些目录的拒绝，而不是零。

• scale 1000

推导 · 方法学册 04

04Newman 模块度

每个目录的模块度占其最大值的份额：从不外引为 1000‰，恰在零模型期望处为 0。

rho = q / qMax = (e*m − o*i) / (mu*(m − mu))

设内部边数 e、出质量 o、入质量 i、关联质量 mu = e + crossOut + crossIn、全树边数 m，Newman 贡献为 q = e/m − o*i/m^2，最大值（关联边全在内部）为 qMax = mu(m−mu)/m^2。

• modFloor 1
• modMassFloor 4

推导 · 方法学册 04

19分层与切割

把最便宜的弧从环里切掉后给目录分层，不稳定度以整数千分数给出。

cuts   : 逐个 SCC，≤ 14 个目录时走子集规划（exact 1），否则 Eades–Lin–Smyth + 冗余清理（exact 0）
layers : d 无出边时 level(d) = 0，否则 1 + d 所指者的最大 level，切掉的弧不算
metrics: fanIn, fanOut, instability = ⌊1000 · out ÷ (in + out)⌋，没有边碰到该目录时为 −1

切边逐个强连通分量求：分量之间的弧不在任何环上，所以全图的最小值是各分量最小值的并。

• exactVertexCap 14
• instabilityScale 1000

推导 · 方法学册 19

05分数

各判轴在凸的尺寸罚分下折成一个 0–1000 分；文件上限只缩不涨，增长超过 max(+2 %, +10) 即判负。

raw     = sum_i (w_i * p_i * violCost)
wTotal  = sum_i w_i                            -- 推导而来，从不写死
score   = max 0 (scoreScale - raw `div` (violCostNeutral * wTotal))

p(x) = 0                              if x <= S          -- S 读作 min S H
     = pMax                           if H <= S          -- 退化时的兜底
     = pMax * ((x - S) / (H - S))^2   if S < x <= H
     = pMax * (1 + 2*(x - H)/(H - S)) if x > H           -- C¹ 线性臂

判轴 0 是唯一不是计数的轴：对文件尺寸的凸罚，精确 Rational，越过硬线仍单调。

• scoreScale 1000
• violCost 10
• sizeHard H 750
• sizePMax 10
• softLineK 2
• [softMin, softMax] [200, 500]

推导 · 方法学册 05

05棘轮

把七条判轴的分数对着一份只准收紧的基线把门。

tolerated(c) = max (c * tolNum `div` tolDen) (c + tolAbs)   -- 复杂度行用 tolAbsCoc

added   = current \ baseline        -- 非空 => fail
removed = baseline \ current        -- 只作告知；驱动收缩

fail 位是六个具名条件的析取：ratchet_over、discrete_added、floor、dedup_budget、knobs_digest、rows_dropped。

• tolNum/tolDen 102/100
• tolAbs 10
• tolAbsCoc 1

推导 · 方法学册 05

05认知复杂度

认知复杂度连同 SonarSource 自家分析器没实现的 S3776 附录 B1 递归增量：调用环由核找出，每个成员各加一次。

+1：递归环里的每个方法各加一，直接与间接同价

• cocCeil 15

推导 · 方法学册 05

08拆分 ROI

给拆分缝定价：它退回的尺寸罚分对切割的代价。

benefitMilli(u) = max 0 (floor (1000 * (p(total) - p(end_u) - p(total - end_u))))

costMilli(u)    = crossRefs(u)      * roiRefMilli
                + cutClones(end_u)  * roiCloneMilli
                + crossChurn(u)     * roiChurnMilli
                + roiPhiMilli

viable          ⇔ b >= c            -- ROI >= 1，不做除法即判

p 凸且 p(0) = 0，故超可加，所以收益——算在与判决家族同一条曲线上（直接 import，不重推）——从不为负。

• seamSoft S 300
• seamHard H 750
• seamPMax 10
• roiRefMilli 250
• roiCloneMilli 500
• roiChurnMilli 150
• roiPhiMilli 500

推导 · 方法学册 08

10Theil-Sen 斜率

趋势取成对斜率的中位数（trend/2）。

x_i   = ts_i % 86400                 -- 秒折成天，精确比值
y_i   = (score_i * 1000000) % scale_i

slope = median{ (y_j - y_i) / (x_j - x_i) : x_i ≠ x_j }   -- Theil-Sen

slope < -band  → 2  （变差）
slope >  band  → 0  （变好）
否则           → 1  （持平）      其中 band = floorMicro

一个野点（测出来的坏提交）能把最小二乘均值拽到任何地方，却拽不动中位数半步。

• minPoints 3（knob 0）
• tsWindow 512
• 满量程网格 10⁶

推导 · 方法学册 10

06可达性

活的入口都到不了的文件即死；环由 Kosaraju 强连通分量只找一次。

arcs  = { (s,d) | [s,d,kind,rung] ∈ edges,  rung <= minRung,  kind ∉ inert }
reach = ⋃ { reachable(G, s) | s ∈ entries(entryMask, flags) }

public     = testBit flags 0
referenced = indeg >= 1 over kept arcs
judged     = i ∉ reach
code       = 1 + public + 2*referenced    -- 以查找表为准

环只报不判；没有入口种子的环岛仅凭可达性即判死。

• minRung 5
• entryMask 126（bits 1–6）
• sccFloor 2

推导 · 方法学册 06

17可达性与活跃性

在每个函数的控制流图上求可达，在它的变量上做逆向活跃性分析。

kind 0 : unreachable  = 入口无路径可达，每段极大连续 seq 一条发现
kind 1 : dead_store   = 下次写或出口之前没有路径读到的写（反向活性）
kind 2 : unused_local = 无读 · kind 3 : unused_param = 无读（顾问，从不判决）

活跃入集在整张图上解到 in = transfer(∪ in of successors) 的不动点。

推导 · 方法学册 17

16分层 Datalog

在索引自身的事实上逐层半朴素求值的 Datalog；每个答案带着它的推导树。

dead(F) :- file(F), not reach(F).
strata : 头位于体内每个被否定或被聚合的谓词之上；SCC 内的负边是程序错误
eval   : 逐层半朴素求值，建在惰性位掩码索引上；元组的第一条推导即其出处

集合语义，最小模型。

• derivedCap 2097152
• proofCap 16384

推导 · 方法学册 16

15整数 BM25 与 PPMI

整数 BM25（k1 = 6/5、b = 3/4）为一个单元排出最像它的单元；仓内 PPMI 可拓宽查询，只作建议。

score  = Σ w · idf · 22·tf·avg / (10·tf·avg + 3·avg + 9·len)   （k1 = 6/5，b = 3/4；整数定点）
widen  = 前 m 个 PPMI 邻居，权重 ≤ ½      （选开的视图；从不作证据）
role   ⇔ (N ≥ 1 ∧ C ≥ 1) ∨ (N ≥ 2 ∧ shapeEqual)  （在 Haskell 里经 similar/1 判；只当顾问）
PPMI(a, b) = max(0, log2(n_ab · N / (n_a · n_b)))

Haskell 把每个候选的九整数行按精确有理数排序并施加角色合取；在 similar/1 与 rank/1 上只过哈希与计数——词袋所据的单元原文经本机管道在 bags/1 里送核一次。

• topM 3
• minCooc 2
• roleMinName 1
• roleMinCallee 1
• roleMinNameShape 2

推导 · 方法学册 15