用滚动数组优化空间、early termination提前终止、词库按长度预筛；查询时改用BK-tree替代线性扫描，平均时间复杂度降至O(log N)。
Levenshtein距离计算函数怎么写才不超时？
直接手写三层嵌套循环的 levenshtein 函数在长字符串（比如 >20 字符）或词库 >1000 个词时，很容易卡住——因为标准 DP 实现是 O(m×n) 时间，对每个查询词都要扫一遍词库，整体变成 O(N×m×n)，N 是词库大小。
实操建议：
- 用滚动数组优化空间，只保留两行
dp数组，避免分配完整二维表 - 加 early termination：当当前行最小值已超过设定阈值（如 3），立刻 break，不用算完
- 对词库预筛：先按长度过滤，只比对
abs(len(query) - len(candidate)) 的候选词 - 不要在运行时反复 new/delete，把
dp数组做成线程局部静态变量复用
示例关键片段：
int levenshtein(const std::string& a, const std::string& b, int max_dist = 3) {
if (std::abs((int)a.size() - (int)b.size()) > max_dist) return max_dist + 1;
std::vector<int> prev(b.size()+1), curr(b.size()+1);
for (int j = 0; j <= (int)b.size(); ++j) prev[j] = j;
for (int i = 1; i <= (int)a.size(); ++i) {
curr[0] = i;
int min_in_row = curr[0];
for (int j = 1; j <= (int)b.size(); ++j) {
int cost = (a[i-1] == b[j-1]) ? 0 : 1;
curr[j] = std::min({prev[j]+1, curr[j-1]+1, prev[j-1]+cost});
min_in_row = std::min(min_in_row, curr[j]);
}
if (min_in_row > max_dist) return max_dist + 1;
prev.swap(curr);
}
return prev[b.size()];
}词库加载和查询怎么避免每次遍历全量？
把词库存在 std::vector<:string></:string> 里然后线性 scan，10k 词查一次就要算上万次距离——实际项目里基本不可用。
立即学习“C++免费学习笔记（深入）”；
实操建议：
- 构建前缀 Trie，但不是存拼写，而是存「编辑距离 ≤1 的所有变形」——不现实，爆炸式增长
- 更可行的是用 BK-tree（Burkhard-Keller tree）：基于 Levenshtein 距离满足三角不等式的特性组织树结构，单次查询平均 O(log N)
- 若词库固定且不大（std::unordered_map<:string std::vector std::string>>> 缓存每个词的 top-k 纠错结果
- 加载时把词按长度分桶，查询时只查同长±1 桶，再用 BK-tree 或排序后二分剪枝
BK-tree 插入示意：
struct BKNode {
std::string word;
std::map<int, std::unique_ptr<BKNode>> children;
};
void insert(BKNode*& root, const std::string& word) {
if (!root) { root = new BKNode{word}; return; }
int dist = levenshtein(root->word, word);
auto& child = root->children[dist];
if (!child) child = std::make_unique<BKNode>(BKNode{word});
else insert(child.get(), word);
}自动提示（autocomplete）和纠错（correction）能共用一套逻辑吗？
不能硬套。Levenshtein 适合纠错（找相似拼写），但自动提示本质是前缀匹配——比如输 “app”，要返回 “apple”“application”，而不是 “apply”（编辑距离小但无共同前缀）。
实操建议：
- 纠错走 BK-tree 或阈值距离扫描；提示走 Trie 或
std::set<:string></:string>+lower_bound前缀查找 - 混合策略：先做前缀匹配取 top 5，再对这 5 个做 Levenshtein 补充（比如用户输 “aple”，前缀没命中，再 fallback 到纠错）
- 注意大小写：词库统一转小写存储，但返回时还原原始 casing；
levenshtein计算前做 tolower，别直接比 char - 中文拼音场景要额外处理：先转拼音再比，否则 “苹果” 和 “平果” 完全无法匹配
为什么用 std::string 而不是 std::string_view 会拖慢性能？
在高频查询中，每次传 std::string 参数会触发隐式拷贝，尤其词库词平均长度 8~12 字节时，拷贝开销叠加起来很可观；而 std::string_view 零拷贝，但要注意生命周期。
实操建议：
- 所有内部计算函数参数用
std::string_view，比如int levenshtein(std::string_view a, std::string_view b, ...) - 词库存储用
std::vector<:string></:string>（保证数据持久），但构建 BK-tree 或 Trie 时，节点存std::string_view指向原 vector 内存 - 千万别把临时
std::string的sv存进容器——比如auto sv = std::string("tmp").substr(0,2).substr(0);，悬垂指针 - VS2019+ / GCC9+ 支持
std::string_view::data()直接喂给 C 风格函数，避免 .c_str() 多一次检查
容易被忽略的是：Levenshtein 本身不关心编码，但 UTF-8 下一个汉字占 3 字节，直接按 byte 算距离会错——如果业务含中文，必须先转 Unicode code point 序列再算，或者改用 ICU 库的 UnicodeString。
