b4s

二分搜索单排序字符串：对排序但长度不等的子字符串的单个、分隔的字符串切片执行二分搜索。

最佳查看文档的方式是docs.rs。

使用方法

设置此crate通常有两种方式：编译时或运行时。感兴趣的主要（唯一...）方法是 [SortedString::binary_search()]。查看其文档以获取详细上下文。

运行时

use b4s::{AsciiChar, SortedString};

fn main() {
    match SortedString::new_checked("abc,def,ghi,jkl,mno,pqr,stu,vwx,yz", AsciiChar::Comma) {
        Ok(ss) => {
            match ss.binary_search("ghi") {
                Ok(r) => println!("Found at range: {:?}", r),
                Err(r) => println!("Not found, last looked at range: {:?}", r),
            }
        }
        Err(e) => println!("Error: {:?}", e),
    }
}

编译时

为了方便，还有一个可静态使用的const fn，但作为权衡，实例创建将不会执行正确性检查。未排序的字符串会导致二分搜索行为异常。虽然不会发生恐慌，但你会得到一个Error。有关详细信息，请参阅 [SortedString::new_unchecked()] 的文档。

use b4s::{AsciiChar, SortedString};

static SS: SortedString =
    SortedString::new_unchecked("abc,def,ghi,jkl,mno,pqr,stu,vwx,yz", AsciiChar::Comma);

fn main() {
    match SS.binary_search("ghi") {
        Ok(r) => println!("Found at range: {:?}", r),
        Err(r) => println!("Not found, last looked at range: {:?}", r),
    }
}

输入字符串的来源可以是任何东西，例如编译时准备好的文件

static SS: SortedString =
    SortedString::new_unchecked(include_str!("path/to/file"), AsciiChar::LineFeed);

如果已经有了分隔的（\n，...）文件，这会很方便。它只需要预先排序一次，然后就可以在良好的（尽管不是完美的）运行时性能下，基本上无启动成本地进行字符串包含检查。

动机

要挠的痒处如下

• 有一个字符串数组要查找，例如单词列表
• 查找是一个简单的包含检查，没有修改
• 单词列表在编译时（例如，在 build.rs）可用和准备（排序）
• 单词列表很大（可能比代码本身大得多）；想想5MB或更多
• 列表作为二进制文件的一部分进行分发

有几个可能的方法可以想到。总结表，其中 n 是字典中的单词数，k 是要查找的单词的字符数，如下所示（有关更多上下文，请参阅下面的各个部分）

本软件包试图提供一个具有

1. 良好，而非完美运行时性能的解决方案,
2. 极少的，一次性编译时预处理需要（仅排序），
3. 几乎没有额外的启动成本（与在运行时构建HashSet相比），[^4]
4. 尽可能小的二进制大小,
5. 尽可能快的编译时间.

发现使用切片和哈希集（通过phf）的方法会导致开发体验大打折扣，编译时间超过20分钟（！）对于30MB的单词列表（即使在快速硬件上），大型二进制文件，以及clippy崩溃，导致IDE崩溃。这个软件包就是为了解决这个问题而诞生的。它的主要缺点是运行时性能不佳。如果您的主要目标是这一点，请选择phf或类似的软件包。这个软件包不适合长时间运行的应用程序，其中初始的例如HashSet创建仅占整体运行时成本的一小部分。

替代方法

以下替代方法可以考虑，但出于一个或多个原因被发现不适合。有关更多讨论，请参阅此线程。

切片

简单的切片是一个明显的选择，可以在构建脚本中生成。

static WORDS: &[&str] = &["abc", "def", "ghi", "jkl"];

assert_eq!(WORDS.binary_search(&"ghi").unwrap(), 2);

这种方法有两个大问题

1. 编译时间变得非常慢（大约每100,000个单词需要1分钟，效果可能会有很大差异）

2. 二进制文件变得很大。

   单词比它们所包含的&str要短得多。在64位硬件上，&str是16字节，包含一个usize地址指针和一个usize长度。对于大型单词列表，这会导致生成的二进制文件产生令人难以置信的膨胀。

HashSet

常规的HashSet在编译时不可用。像phf这样的软件包改变了这一点

use phf::{phf_set, Set};

static WORDS: Set<&'static str> = phf_set! {
    "abc",
    "def",
    "ghi",
    "jkl"
};

assert!(WORDS.contains(&"ghi"))

与切片情况类似的问题也适用：非常长的编译时间和由于智能指针而产生的相当大的二进制膨胀。最终，哈希集是一个具有计算索引的切片，这是预期的。

有限状态转换器/接受器（自动机）

fst软件包是一个非常好的候选者，由其作者提出（与ripgrep和regex的著名作者相同）

use fst::Set; // Don't need FST, just FSA here

static WORDS: &[&str] = &["abc", "def", "ghi", "jkl"];

let set = Set::from_iter(WORDS.into_iter()).unwrap();
assert!(set.contains("ghi"));

它提供

• 几乎免费（在时间和空间上）的反序列化：其序列化格式与其内存表示相同，与其他解决方案不同，从而简化了启动性能
• 压缩[^3]（对发布很重要），使其成为此比较中唯一能够原生地达到比原始单词列表更小大小的候选者
• 扩展点（模糊和大小写不敏感搜索、自行提供自动机等）
• 比此crate更快的查找，大约快2倍

从某种意义上说，为了达到目的，fst很可能是上述特定用例的最佳解决方案。

为了获得比fst更快的查找（缩小与哈希集的差距），但放弃压缩（TANSTAAFL!），请尝试来自regex-automata的自动机。请注意，如果您的用例涉及初始解压缩步骤，那么fst的较慢的运行时查找但内置的压缩可能仍然在组合中占上风。

单个、排序和填充的字符串

另一种方法可能是使用单个字符串（节省指针膨胀），但将所有单词填充到最常出现的长度，从而便于进行二分搜索（并在一定程度上增加膨胀）

static WORDS: &str = "abc␣␣def␣␣ghi␣␣jklmn";

// Perform binary search...

由于元素具有已知、固定的长度（在这种情况下，为5），二分搜索的实现因此很简单。这种方法被发现性能不佳。可以在基准测试中找到其（裸机）实现。

高阶数据结构

在某些情况下，人们可能会寻求更复杂的方法，例如字典树。这不是此crate设计的情况。这种结构必须是

• 在运行时构建，例如作为

  use trie_rs::TrieBuilder;
  
  let mut builder = TrieBuilder::new();
  builder.push("abc");
  builder.push("def");
  builder.push("ghi");
  builder.push("jkl");
  let trie = builder.build(); // Takes time
  
  assert!(trie.exact_match("def"));
  

  或者

• 从预构建的结构反序列化.

虽然工具如bincode非常出色，但与当前crate采取的方法相比，后一种方法在应用程序启动时仍然非常慢。

线性搜索

这仅包括在此处和基准测试中作为合理性检查和基线。线性搜索如下

static WORDS: &[&str] = &["abc", "def", "ghi", "jkl"];
assert!(WORDS.contains(&"ghi"));

是$O(n)$，对于大型列表，慢得多。如果你的当前实现依赖于线性搜索，这个crate可能提供了一个几乎可以即插即用的替换，并带来显著的性能提升。

基准测试

下面的基准测试显示了性能比较。基准测试在各种不同长度的输入单词列表上运行对代表性单词的搜索（起始、中间、结束、最短和最长的单词，这些单词在预先排序的输入列表中找到）。

集合出人意料地最快，但简单的二分搜索（内置的）似乎非常优化，速度相同。b4s慢5到10倍。填充字符串变体最慢。可以看到，随着输入列表的变长（“在X条条目内”），b4s会变慢。

在考虑这个crate（软件包）的用途时，这种缓慢可能不是问题：如果应用程序的启动时间是毫秒级别，查找操作是纳秒级别（！），那么在进行大约10万次查找之前，这个crate（快速启动）的权衡就变成了问题（这个crate对于Web服务器来说会很糟糕）。

线性搜索性能

包括线性搜索的基准测试图（#readme-linear-search）在很大程度上难以辨认，因为线性水平轴的缩放效果使得其他所有搜索方法相形见绌。因此，它被单独链接，但清楚地描绘了一幅图。

注意

基准测试是在以下规格的机器上运行的

• AMD Ryzen 7 5800X3D；DDR4 @ 3600MHz；NVMe SSD
• Windows 10 21H2上的WSL 2中的Debian 12
• 库的版本为commit 9e2f11c39342f1ea3460dda810a92b225ee9d4b8（参考其Cargo.toml）

这些基准测试并不非常科学（样本量低等），但可以作为粗略的指南和合理性检查。从存储库根目录运行它们，使用cargo install just && just bench。

关于名称的说明

这个3个字母的名字很酷。如果您有一个更具有意义、更大的项目，可以更好地利用它，请告诉我。我可能会将这个crate移动到另一个名称。

[^1]：请注意，预编译预处理通常只执行一次，除非单词列表本身发生变化。这个列可能没有意义，基本上是零成本。这种观点有利于这个crate。[^2]：构建自身是O(n)，但原始输入可能是未排序的（正如假设的所有其他方法一样）。排序是O(n log n)，因此构建自动机会降低到O(n + n log n) = O(n log n)。[^3]：作为一个自动机，有限状态转换器（在这种情况下，有限状态接受器）压缩了所有公共前缀，就像一个前缀树，但与后缀树不同，还压缩了所有后缀。如果压缩是一个问题，这将是一个巨大的优势。像德语这样的语言会受益匪浅。以übersehen为例：无数的变形在所有单词中共享，因此在整个自动机中只编码一次。前缀über也在许多单词中共享，也只编码一次。压缩是内置的。[^4]：这个crate最初设计的程序对启动时间敏感，因为程序的主要处理是快速的。即使是50毫秒的启动时间也会非常明显，将程序运行速度降低大约10倍。