Golang实现基于最长公共子序列（LCS）的文本文档字符串相似度计算-Golang-PHP中文网

直接用lcs长度算相似度会出错，因其仅匹配字符顺序而忽略长度差异、空白符、大小写等干扰，且未归一化预处理；需统一转小写、折叠空白、去首尾空格，并避免内存爆炸，建议用滚动数组或改用n-gram方法。

golang实现基于最长公共子序列（lcs）的文本文档字符串相似度计算

为什么直接用 `lcs` 长度算相似度会出错

很多人一上来就写 similarity = float64(len(lcs)) / float64(max(len(a), len(b)))，结果发现两个完全无关的长字符串（比如“abc”和“xyz123456789”）也能给出 0.3+ 的假阳性分。问题出在：LCS 只考虑字符顺序匹配，不惩罚长度差异，也不处理空格、换行、大小写等实际文档中必然存在的干扰。真实文本文档比对时，lcs 必须先归一化再参与计算。

实操建议：

预处理必须做：统一转小写、折叠连续空白符（regexp.MustCompile(`\s+`).ReplaceAllString(s, " ")）、去掉首尾空格
不要直接拿原始字节或 rune 切片算 LCS —— 中文、emoji、组合字符会导致 len([]rune(s)) 和视觉长度严重不符；对纯文本相似度，按「词」或「语义单元」切分更稳（但若坚持字符级，至少用 strings.TrimSpace + strings.ToLower）
如果文档含大量重复标点或停用词（如“的”“了”“。”），LCS 会被这些高频字符拉高，需提前过滤或加权降权

Go 标准库没有 `lcs`，手写二维 DP 要注意内存爆炸

常见错误是直接开 dp[len(a)][len(b)] int，当两个文档都超 10KB（即约 10k 字符），内存就奔 100MB 去了，且 GC 压力大。实际文档比对往往只需相似度值，不需要重构 LCS 字符串本身。

实操建议：

用滚动数组优化：只保留 dp[2][n]，空间从 O(m×n) 降到 O(min(m,n))；注意索引取模：dp[i%2][j]
如果只需要相似度分数（非 LCS 内容），连滚动数组都可省——只维护上一行和当前行两个 slice，每次迭代后 swap(prev, curr)
对超长文本（>50KB），直接放弃字符级 LCS；改用基于 n-gram 的 Jaccard 或 MinHash，或者先抽关键句再比对

简短示例（滚动数组核心逻辑）：

Golang Naming

Go（Golang）命名规范 — 包括包、构造函数、结构体、接口、常量、枚举、错误、布尔值、接收器、getter/setter、函数等。

下载

func lcsScore(a, b string) float64 {
    m, n := len(a), len(b)
    if m == 0 || n == 0 { return 0 }
    prev, curr := make([]int, n+1), make([]int, n+1)
    for i := 1; i <h3>
<code>lcsScore</code> 在中文文档里跑出来总是偏低？检查 rune vs byte</h3><p>Go 的 <code>len("你好")</code> 是 6（byte 数），但语义长度是 2（rune 数）。如果你把字符串直接当 byte 序列喂给 LCS，一个中文字符被拆成 3 个字节参与匹配，根本无法形成有效子序列 —— 导致 <code>lcs</code> 长度趋近于 0，相似度永远低于 0.1。</p><p>实操建议：</p>

中文/多语言文本必须转 rune 切片：ra, rb := []rune(a), []rune(b)，然后基于 len(ra) 做 DP
但注意：rune 切片分配开销大，别在热循环里反复转换；预处理阶段一次性转好并缓存
如果文档混排（中英数标），且你发现 “Hello世界” 和 “Hello世” 匹配异常，大概率是没统一 normalize —— 用 norm.NFC.String(s)（需 "golang.org/x/text/unicode/norm"）先标准化 Unicode 组合形式

相似度分母选 `max(len(a), len(b))` 还是 `len(a)+len(b)`？

选错分母会让结果失去可比性。用 max 时，短文本改动一个字，相似度波动剧烈（如 “ab”→“ac”，LCS=1，相似度从 1.0 → 0.5）；用 len(a)+len(b) 则对长度敏感度低，但无法反映“主体是否一致”。文档比对场景下，更合理的其实是 Sørensen–Dice 系数：2 * len(lcs) / (len(a) + len(b))，它天然抑制长度偏差影响。

实操建议：