MiniSearch 是一款专为浏览器与 Node.js 环境打造的轻量级全文检索引擎，其核心亮点在于内置的容错搜索能力——即便用户输入存在笔误，依然能够返回相关结果。这一能力的底层支撑，正是经典的字符串相似度度量方法：Levenshtein 距离。

容错检索的核心概念

容错检索（Fuzzy Search）的本质是容忍查询串与目标串之间的差异。在 MiniSearch 的实现中，这种"差异"被量化为最小编辑代价：将字符串 A 变换为字符串 B 所需的最少单字符操作次数。合法操作仅包含三种原子动作：

• 插入：在任意位置添加一个字符
• 移除：删除任意位置的单个字符
• 置换：将某位置的字符替换为另一个

以 "kitten" → "sitting" 为例，最优变换路径为：k→s（置换）、e→i（置换）、末尾插入 g，总计 3 步。

算法架构与索引设计

MiniSearch 采用压缩前缀树（Radix Tree）作为倒排索引的存储载体。相比普通 Trie，该结构通过合并单分支节点显著降低空间开销，同时为前缀匹配与容错匹配提供 O(m) 级别的遍历效率，其中 m 为模式串长度。

动态规划矩阵的构建

在 src/SearchableMap/fuzzySearch.ts 中，算法初始化二维状态表：

// 状态表列数由查询串长度决定
const cols = pattern.length + 1;

// 目标串长度上限受编辑阈值约束
const rows = cols + tolerance;

状态转移遵循 Bellman 最优性原理：

• 若当前字符匹配，代价继承左上角单元格
• 若失配，代价为"左上（置换）、正上（删除）、左方（插入）"三者最小值加 1

工程实践与接口设计

开发者可通过配置对象灵活控制容错程度：

// 允许编辑距离不超过查询串长度的 20%
engine.query('ismael', { fuzzy: 0.2 });

// 或指定绝对阈值
engine.query('ismael', { fuzzy: 2 });

性能优化手段

为应对大规模语料，实现层引入三项关键优化：

1. 带状剪枝：仅计算以主对角线为中心、宽度为 2×threshold + 1 的带状区域，将时空复杂度从 O(n²) 降至 O(n×k)
2. 分支限界：DFS 遍历 Radix Tree 时，若某节点对应状态行所有值均超出阈值，立即回溯跳过该子树
3. 内存池复用：单次查询复用同一矩阵对象，通过滚动数组技术避免频繁内存分配

技术选型对比

实现细节补充

源码中针对 Unicode 组合字符与大小写折叠做了特殊处理，确保多语言场景下的编辑距离计算符合用户直觉。此外，通过 WebAssembly 版本的矩阵计算模块（可选加载），可将密集型运算性能提升 3-5 倍。

对于需要客户端实时检索的场景——如文档站搜索、离线应用、大型表单筛选——MiniSearch 在功能完整性与资源占用之间取得了难得的平衡，值得作为首选方案评估。