@isdk/approx-text-match

English | 中文

近似子串定位：在长文本里找出最相似的连续区间 + 相似度

它解决什么

和模糊搜索库的区别：

| | 模糊搜索（Fuse / fuzzysort / SymSpell） | 本包 | |---|---|---| | 回答 | 哪些字符匹配上了 | 命中哪一段 | | 输出 | 分散的匹配下标 | { start, end, score } |

前者推不出后者：模糊搜索跳过的不匹配字符（如标点） 在区间语义里必须被包含，否则高亮会缺字。

不重复发明轮子：比对算法用现成库。本包只做库不管的两件事：

1. seed-and-extend —— Bitap 用位运算，pattern 长度有 32 位上限，长摘录 直接扔进去会抛 Pattern too long。所以先从摘录里挑一段短种子去定位， 再开窗精修。
2. 区间边界确定 —— match_main 只返回起始位置、不给长度，靠 diff 精修。

jsdiff 被排除不是因为它不好，而是它只有全量比对，做不了模糊定位。

它是怎么工作的

① 挑种子    从摘录里截一段（默认 ≤ 24 字）当"探子"
                ↓
② 粗定位    Bitap 在全文里模糊定位这颗种子 → 一个大致落点
                ↓
③ 开窗口    以落点为原点，左右各留 slack（默认 64 字）
                ↓
④ 精修      跑 diff，取「首个共同段 → 末个共同段」的跨度 → { start, end, score }

种子必须"稀有但存在"（这一步最容易踩坑）

种子是锚点，价值在唯一性，所以直觉规则是「挑出现次数最少的」。 但0 次不是最稀有，是不存在 —— 摘录常混进原文根本没有的字符 （md 标记 **、被压坏的列表序号、OCR 噪声……），含它们的窗口在原文里 必然出现 0 次。就像在词典里查一个词返回 0 条，那不是定位精准，是打错字了； Bitap 拿着原文里不存在的串去找，只会空手而归。

所以真正的规则是：先问存不存在，再问稀不稀有 —— 挑「非零最少出现次数」 的窗口。只有所有窗口都找不到时，0 次的才沦作备胎，且备胎之间改比 「中毒程度」（窗口里有几个字符在原文里出现过）。

不设这条防线：**甲方**应当按照合同约定支付货款 会选中 **甲方**应当 → Bitap 返回 -1 → 整条摘录定位失败，而它明明能命中。

分数为什么用「跨度」而不是累加差异

分母取 last - first（首个共同段 → 末个共同段的窗口跨度）， 而不是所有差异段长度之和。区别在于：窗口尾部那些跟摘录无关的原文 会被累加进分母，长窗口下分数被压到 0（中文漏字用例实测：0.63，用跨度则 0.875）。

window = 本院认为，被告的行为已经构成根本违约，应当赔偿。
needle = 本院认为被告的行为构成根本违约

共同段   本院认为(4) 被告的行为(5) 构成(2) 根本违约(4)  → common = 15
跨度     first = 0, last = 18     （夹进来的「，」「已经」共 3 字）
分数     2×15 / (18 + 15) = 0.909

用法

npm i @isdk/approx-text-match

import * as dmp from 'diff-match-patch-es';
import { createDmpEsFallback } from '@isdk/approx-text-match';

const fuzzy = createDmpEsFallback(dmp);
fuzzy.find('本院认为被告的行为构成根本违约', '本院认为，被告的行为已经构成根本违约，应当赔偿。');
// → [{ start: 0, end: 18, score: 0.909 }]

拿到区间后直接 text.slice(start, end) 即可高亮，中间未匹配的字也在区间内，不会缺字。

拿到区间后直接 text.slice(start, end) 即可高亮，中间未匹配的字也在区间内，不会缺字。

找多处命中

默认只返回最像的那一处。要找同一摘录在长文里的多处近似出现，传 maxMatches：

const fuzzy = createDmpEsFallback(dmp, { maxMatches: 3, minScore: 0.8 });
fuzzy.find('甲方应当按照合同约定支付货款', doc);
// → [{ start, end, score }, …]  最多 3 个，按分数降序

maxMatches > 1 时务必同时设 minScore：Bitap 是模糊的，第 2、第 3 个命中的 分数会明显低于第 1 个（实测：正确命中 0.9 量级，错误位置只有 0.135）。 不设门槛的话，列表尾部基本是噪声。

实现上，Bitap 一次只返回一个位置，所以找第 N 个靠遮蔽已命中区间后重新定位： 把已命中区间替换成等长哨兵串，遮蔽区因含哨兵而匹配不上，Bitap 自然去别处找。 代价是每轮重建一次字符串，开销 O(maxMatches × 文档长度)。

边界与取舍

• 默认不要传 threshold —— threshold 就是 Bitap 的准确度门槛 （accuracy = 错误字符数 / pattern 长度）。两个后端的 Bitap 实现逐行一致， 差异只在默认值：createDmpEsFallback 不传就用库自己的 0.5， createDmpFallback 是 0.4。在 accuracy ≈ 0.44–0.50 的用例上， 0.4 会返回 -1 而 0.5 仍能命中。这是历史遗留，不要顺手对齐 —— 那会改变既有调用方的命中结果
• Bitap 返回 -1 时会放宽重试，但先判断 loc 可不可靠：毒化种子找不到 精确落点时 loc 退化为 0，于是 |loc - 真实位置| / matchDistance 这条 proximity 惩罚爆表（真实位置 1127、distance 1000 时惩罚就是 1.127）。 这条惩罚是坏位置估计的产物，不代表匹配质量差 —— 此时保持阈值严格、只摘掉 proximity。若 loc 可靠，则先放宽阈值（保留位置先验）、再摘 proximity 兜底。 （踩过的坑：曾经无条件放宽阈值到 1.0，等于接受 loc 周围 1000 字内几乎任何 东西，实测把真实位置 1127 的用例定位到了 8）
• 一次调用默认只返回一处：结果按分数降序，out[0] 恒为最佳命中； 要多处请传 maxMatches（配合 minScore）
• 命中与否最终由 diff 分数把关，所以放宽 Bitap 不会造成假阳性 —— 但分数低于 minScore 时会被直接丢弃
• diff-match-patch-es 是纯 ESM，构建链有 CJS 环节要先确认
• 旧后端 createDmpFallback 通过实例属性设置 Match_*；适配器用 try/finally 保证调用结束后还原，共享同一个 dmp 实例是安全的 （注意：在实例上预设 Match_* 无效，会被适配器覆盖，请走 options）
• 输入输出都是纯字符串下标：本包不关心坐标映射，只回答"哪一段最像"

相关

• 总览：../../PACKAGES.md
• 英文：README.en.md