编辑距离计算需用动态规划二维数组，初始化行列为len+1，首行/列填0,1,2…，字符比较用str1[i-1]==str2[j-1]，支持转置需额外判断相邻交换，筛选候选词须预处理分桶+剪枝，排序应融合距离、词频、首字母、长度等加权。
编辑距离计算函数怎么写才不踩坑
编辑距离（Levenshtein Distance）是单词纠错的核心，但直接手写容易忽略边界和性能问题。标准实现必须处理空字符串、避免重复分配内存、用二维数组而非递归（否则指数级耗时）。
-
std::vector<:vector>></:vector>初始化时行列大小要包含空串位置（即len1 + 1×len2 + 1） - 第一行/列初始化为
0, 1, 2, ...，不是全 0 —— 否则插入/删除代价算错 - 字符比较用
str1[i-1] == str2[j-1]，下标偏移容易漏减 1，导致越界或匹配失效 - 若只关心是否 ≤ 某阈值（如 2），可在内层循环加
if (dp[i][j] > threshold) continue;提前剪枝
如何快速筛选候选词而不是遍历整个词典
全词典逐个算编辑距离在实际场景中不可行——万级词表下每次查询上百毫秒。必须预处理索引，不能只靠暴力匹配。
- 按长度分桶：先用
abs(len_input - len_candidate) 过滤，跳过长度差超限的桶 - 使用 BK-tree（Burkhard-Keller Tree）：基于编辑距离的度量树，插入/查询复杂度约
O(log n)，比线性快一个数量级 - 简单替代方案：对每个词提取 2-gram 或 3-gram，建立倒排索引；输入词也切 n-gram，取交集后再算编辑距离
- 注意：BK-tree 的
distance()必须与纠错用的编辑距离定义完全一致，否则树结构失效
为什么 edit_distance("ab", "ba") == 2 而不是 1
这是常见误解点：编辑距离只允许插入、删除、替换三种操作，不支持相邻字符交换（transposition）。"ab"→"ba" 需删 a、插 a 到末尾（或删 b、插 b 到开头），共两步。
- 若需支持交换（如拼写纠错更实用），应改用 Damerau-Levenshtein 距离，额外增加判断
i > 1 && j > 1 && s[i-1] == t[j-2] && s[i-2] == t[j-1] - 但要注意：Damerau 版本不能直接套用 BK-tree，因不满足三角不等式，需换用其他索引结构（如 Tries + 动态规划剪枝）
- 多数开源词典纠错库（如 SymSpell）默认启用 transposition，但 C++ 标准实现（如
edit_distance）通常不包含，务必确认算法变体
纠错结果排序时权重怎么加才合理
单纯按编辑距离升序排序会把 "cat" → "car"（距离 1）排在 "cat" → "act"（距离 2）前面，但后者可能是更合理的语法候选。需要多维度打分。
- 基础分 =
1.0 / (1 + edit_distance)，避免除零且保持单调 - 加权项：词频（从语料统计的
word_freq_map中查）、首字母是否相同（s[0] == t[0]加权 0.3）、长度是否接近（abs(len_s - len_t) 加权 0.2） - 慎用大模型打分：本地 C++ 实现里嵌入 LLM 显著拖慢响应，更适合后端服务分离，而非单次
correct()调用 - 返回前做去重：不同路径可能算出相同候选词，用
std::set<:string></:string>或哈希过滤
编辑距离本身很稳定，真正难的是候选生成和排序策略——词典质量、领域适配、用户习惯反馈都得介入，纯算法跑出来的 top1 往往不是用户想要的那一个。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
