9 个版本 (5 个重大更改)
| 0.5.0 | 2024年4月2日 |
|---|---|
| 0.4.1 | 2024年3月11日 |
| 0.4.0 | 2024年2月20日 |
| 0.3.0 | 2023年12月22日 |
| 0.0.0 | 2023年8月6日 |
#50 在 算法 中
每月下载量 8,498
用于 11 个包（10 个直接使用）
310KB
6K SLoC
核子
nucleo 是一个用 Rust 编写的性能极高的模糊匹配器。它旨在填补与 fzf 和 skim 相同的使用场景。与 fzf 相比，nucleo 的匹配算法速度明显更快。这主要在匹配具有低选择性的多个项目时产生影响。下方的基准测试部分展示了（非科学的）比较。
注意：如果您正在寻找
fuzzy-matcher包的替代品，而不是一个完全管理的模糊选择器，您应该使用nucleo-matcher包。
nucleo 使用与 fzf 完全相同的评分系统。这意味着您应该获得与您在 fzf 中习惯的相同的排名质量（或更好）。然而，nucleo 对 Smith-Waterman 算法的实现更为忠实，该算法通常用于 DNA 序列比对（见 https://www.cs.cmu.edu/~ckingsf/bioinfo-lectures/gaps.pdf），使用两个独立的矩阵（而不是像 fzf 那样使用一个）。这意味着 nucleo 更频繁地找到最佳匹配。例如，如果您在 xf foo 中匹配 foo，nucleo 将匹配 x__foo，而 fzf 将匹配 xf_oo（您可以增加单词长度，结果将保持不变）。前者是更直观的匹配，根据 nucleo 和 fzf 使用的排名系统，得分更高。
与 skim（以及 fuzzy-matcher 库）相比，nucleo 具有更大的性能优势，通常比其快 六倍（见下文基准测试）。此外，nucleo 和 fzf 所使用的奖励系统（在我看来）更为一致/优越。nucleo 还能更好地处理非 ASCII 文本。（skim 的奖励系统甚至不区分大小写，仅适用于 ASCII）。
Nucleo 还能更正确地处理 Unicode 图形符号。 Fzf 和 skim 都在 Unicode 代码点上操作（字符）。这意味着多代码点图形符号可能会产生奇怪的效果（多次匹配，评分异常改变等）。nucleo 将始终使用图形符号的第一个代码点进行匹配（并报告图形符号索引，以便正确突出显示）。
状态
Nucleo 被用于 helix-editor，因此拥有大量真实世界测试的用户群体。核心匹配器实现被认为是完整的，不太可能看到重大变化。《code>nucleo-matcher 库已完工，准备广泛使用，破坏性更改应该非常罕见（1.0 版本发布不会太远）。
虽然高级 nucleo 库也表现良好（并且在 helix 中也被使用），但未来还将添加更多功能。高级库还需要更好的文档，并可能在未来看到一些 API 更改。
基准测试
目前更多是演示而不是全面的基准测试套件，特别是与
fzf的科学比较尚缺（因为不能作为库调用）
匹配器微基准测试
比较各种模式与 Linux 内核源代码中所有文件的运行时间。在您的系统上重复执行以下命令（您可以为空目录指定，内核将自动克隆）：BENCHMARK_DIR=<path_to_linux> cargo run -p benches --release
| 方法 | 平均值 | 样本 |
|---|---|---|
| nucleo "never_matches" | 2.30 毫秒 | 2,493/2,500 |
| skim "never_matches" | 17.44 毫秒 | 574/574 |
| nucleo "copying" | 2.12 毫秒 | 2,496/2,500 |
| skim "copying" | 16.85 毫秒 | 593/594 |
| nucleo "/doc/kernel" | 2.59 毫秒 | 2,499/2,500 |
| skim "/doc/kernel" | 18.32 毫秒 | 546/546 |
| nucleo "//.h" | 9.53 毫秒 | 1,049/1,049 |
| skim "//.h" | 35.46 毫秒 | 282/282 |
与 fzf 的比较
例如，在以下两个屏幕录制中，将模式 ///. 复制到 fzf 和 nucleo 中（都大约有 300 万个项目打开）。
fzf 需要一段时间来过滤文本（大约 1 秒），而 nucleo 几乎没有明显的延迟（屏幕录制中一帧，所以大约 1/30 秒）。这个比较是在一个非常强大的 CPU（Ryzen 5950x）上进行的，所以在较慢的系统上，差异可能更大
未来工作
- 将集成到 helix 中
- 构建一个独立的 CLI 应用程序
- 与
fzf达到功能一致性（主要是--no-sort和--tac） - 添加一种允许列匹配的方法
- 与
- 公开 C API，以便在高级 API 和匹配算法本身都可以在其他应用程序中使用（如各种 nvim 插件）
命名
名称 nucleo 是基于这样一个事实：它所依赖的 Smith-Waterman 算法最初是为匹配 DNA/RNA 序列而开发的。被匹配的 DNA/RNA 元素称为 核苷酸，在这里简称为 nucleo。
名称还表明它与 螺旋 编辑器有紧密的关系（继续DNA主题）。
实现细节
这仅针对感兴趣的人，对大多数人来说并不相关。我计划在有更多时间时将其变成一篇博客文章。
模糊匹配算法基于描述在 https://www.cs.cmu.edu/~ckingsf/bioinfo-lectures/gaps.pdf（待解释）的 Smith-Waterman 算法（具有平方型间隙）。Nucleo 忠实地实现了这个算法，因此有两个独立的矩阵。然而，通过预先计算下一个 m-matrix 行，我们可以完全避免存储 p-matrix，而只需在迭代行时将值存储在变量中。
Nucleo 也从未真正存储过 m-matrix，我们只存储当前行（同时作为下一行）。然而，在索引计算期间，需要一个完整的矩阵来回溯实际匹配的索引。这里我们只存储两个 bool 值（用于指示在矩阵中的位置）。
相比之下，skim 存储了完整的 p 和 m 矩阵。而 fzf 总是分配一个完整的 mn 矩阵（甚至在匹配期间！）。
nucleo 的矩阵宽度仅为 n-m+1，而不是宽度 n。这源于以下观察：字符 p 需要 p-1 个字符在其之前，以及 m-p 个字符在其之后，因此总共有 p-1 + m-p = m+1 个字符无法匹配当前字符。这对于仅使用单行特别有效，因为第一个相关字符总是处于同一位置，尽管它在技术上更靠右。这一点特别令人愉快，因为我们预先计算了 m-matrix 行。m-matrix 从对角线元素计算得出，因此预先计算值保持在相同的矩阵单元中。
与 skim 相比，nucleo 还采用了一些更简单（但可能更有影响）的优化。
- 预分段的 Unicode：Unicode 分段相对较慢，而匹配器会频繁过滤相同的元素，因此只进行一次是非常好的。它还防止了一个非常常见的错误来源（字符索引和 utf8 索引的混合），从而使得代码更加简单。Fzf 也这样做。
- 积极的预过滤：特别是对于 ASCII，这非常有效，但我们也以较小的程度对 Unicode 进行了这种操作。这确保我们尽可能快地拒绝不匹配的搜索空间。通常，在模糊匹配大型列表时，大部分搜索空间都不会匹配，因此为此情况提供快速路径是巨大的胜利。
- 特殊情况的 ASCII：90% 的实用文本是 ASCII。ASCII 可以存储为字节而不是
chars，这样大大提高了缓存局部性，并且我们可以使用memchar进行超级快速的预过滤（甚至可以通过这种方式进行不区分大小写的预过滤）。 - 非常长匹配的回退：为了避免大型匹配导致的
O(mn)爆炸，我们回退到贪婪匹配器，该匹配器运行在O(N)时间复杂度（以及O(1)空间复杂度）中。这是fzfs的旧算法，可以得到相当（但不是非常好）的结果。
依赖项
~2.1–7.5MB
~48K SLoC