第二十二章 查询、检索与搜索
22.1 概述
查询（Query）是计算机科学中最基础也最广泛的应用之一。从最简单的数组查找，到复杂的搜索引擎，查询技术贯穿了软件开发的方方面面。本章将系统介绍查询领域的核心算法与数据结构，并结合 Rust 代码实现进行讲解。
查询在计算机中有十分广泛的应用：
- 字符串与文本查询：在字符串或文本文件中查询关键字、模式匹配、正则表达式
- 数据结构查询：在数组、树、哈希表等数据结构中查询指定数据
- 数据库查询：通过 SQL 等语言从数据库中检索数据
- 海量非结构化数据查询：在大量非结构化文件中进行全文检索
- 搜索引擎：在互联网海量网页中快速定位相关信息
下面是本章涉及的主要查询算法及其时间复杂度概览：
| 查询类别 | 算法/方法 | 时间复杂度 | 适用场景 |
|---|---|---|---|
| 字符串模式匹配 | 暴力匹配 | $O(m \times n)$ | 简单场景、短字符串 |
| 字符串模式匹配 | KMP 算法 | $O(m + n)$ | 需要多次匹配的文本 |
| 字符串模式匹配 | Boyer-Moore | $O(m + n)$ 平均 | 实际工程中常用 |
| 字符串模式匹配 | Rabin-Karp | $O(m + n)$ 平均 | 多模式匹配 |
| 敏感词检测 | DFA | $O(n)$ | 敏感词过滤 |
| 正则表达式 | NFA/DFA | 取决于模式 | 文本验证与提取 |
| 线性查找 | 顺序扫描 | $O(n)$ | 无序数据 |
| 二分查找 | 折半查找 | $O(\log n)$ | 有序数组 |
| 哈希查找 | 哈希表 | $O(1)$ 平均 | 键值对查找 |
| 树结构查找 | BST | $O(\log n)$ 平均 | 动态有序集合 |
| 树结构查找 | B+ 树 | $O(\log n)$ | 数据库索引 |
| 全文检索 | 倒排索引 | $O(1) \sim O(\log n)$ | 搜索引擎 |
其中 $m$ 为模式串长度，$n$ 为文本串长度。
22.2 字符串模式匹配
模式匹配是字符串处理中的一种基本运算：给定一个模式串（pattern），要求在某个文本串中找出与该模式串相同的所有子串的位置。
22.2.1 暴力匹配法
暴力匹配法是最直观的字符串匹配方法：从文本串的每个位置出发，逐个字符与模式串进行比较。若匹配成功则记录位置，否则回溯到文本串的下一个位置重新开始。
算法思路：
- 设文本串为 $T[0 \ldots n-1]$，模式串为 $P[0 \ldots m-1]$
- 从 $i = 0$ 开始，比较 $T[i \ldots i+m-1]$ 与 $P[0 \ldots m-1]$
- 若全部匹配，则找到一个匹配位置 $i$
- 否则 $i \leftarrow i + 1$，重复步骤 2
时间复杂度： 最坏情况下为 $O(m \times n)$，即文本串和模式串的长度乘积。当文本串中存在大量与模式串部分匹配的子串时，性能退化严重。
/// 暴力字符串匹配
/// 返回所有匹配位置的起始下标
pub fn brute_force_search(text: &str, pattern: &str) -> Vec<usize> {
let text_bytes = text.as_bytes();
let pattern_bytes = pattern.as_bytes();
let n = text_bytes.len();
let m = pattern_bytes.len();
let mut result = Vec::new();
if m == 0 || m > n {
return result;
}
for i in 0..=(n - m) {
let mut matched = true;
for j in 0..m {
if text_bytes[i + j] != pattern_bytes[j] {
matched = false;
break;
}
}
if matched {
result.push(i);
}
}
result
}
fn main() {
let text = "ababcabcababc";
let pattern = "abc";
let positions = brute_force_search(text, pattern);
println!("匹配位置: {:?}", positions); // [2, 5, 10]
}22.2.2 KMP 算法
KMP（Knuth-Morris-Pratt）算法是字符串模式匹配的经典算法，由 D.E.Knuth、J.H.Morris 和 V.R.Pratt 三人于 1977 年联合发表。其核心思想是：利用已匹配的信息，避免不必要的回溯，从而将时间复杂度降低到 $O(m + n)$。
原理
在暴力匹配中，当匹配失败时，文本串的指针 $i$ 会回溯到之前的位置。但 KMP 算法发现：在已经匹配的部分中，可能存在“前缀“与“后缀“相同的情况，利用这一信息可以让文本串指针 $i$ 不回溯，只移动模式串指针 $j$。
关键概念——next 数组（部分匹配表）：
next 数组 next[i] 表示模式串 $P[0 \ldots i]$ 中，最长相等真前缀和真后缀的长度。所谓“真前缀“和“真后缀“是指不包括整个串本身的前缀和后缀。
例如，模式串 "ABABC" 的 next 数组计算过程：
| 索引 $i$ | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 字符 | A | B | A | B | C |
| next[i] | 0 | 0 | 1 | 2 | 0 |
- $i=0$：
"A"无真前缀真后缀，next[0] = 0 - $i=1$：
"AB"真前缀"A"≠ 真后缀"B"，next[1] = 0 - $i=2$：
"ABA"真前缀"A"= 真后缀"A"，next[2] = 1 - $i=3$：
"ABAB"真前缀"AB"= 真后缀"AB"，next[3] = 2 - $i=4$：
"ABABC"真前缀与真后缀无相等，next[4] = 0
next 数组的构建
构建 next 数组的过程本身是一个递推过程：
$$ \text{next}[i] = \begin{cases} 0 & \text{若 } P[i] \neq P[j] \text{ 且 } j = 0 \ \text{next}[j-1] & \text{若 } P[i] \neq P[j] \text{ 且 } j > 0 \ j + 1 & \text{若 } P[i] = P[j] \end{cases} $$
其中 $j = \text{next}[i-1]$。
匹配过程
当 $T[i] \neq P[j]$ 时：
- 令 $j = \text{next}[j-1]$（模式串指针回退到前缀匹配位置）
- 文本串指针 $i$ 不动
当 $T[i] = P[j]$ 时：
- $i \leftarrow i + 1$，$j \leftarrow j + 1$
当 $j = m$ 时，说明找到了一个完整匹配。
时间复杂度
- 构建 next 数组：$O(m)$
- 匹配过程：$O(n)$
- 总计：$O(m + n)$
Rust 实现
/// https://github.com/TheAlgorithms/Rust/blob/master/src/string/knuth_morris_pratt.rs
pub fn knuth_morris_pratt(st: String, pat: String) -> Vec<usize> {
if st.is_empty() || pat.is_empty() {
return vec![];
}
let string = st.into_bytes();
let pattern = pat.into_bytes();
// build the partial match table
let mut partial = vec![0];
for i in 1..pattern.len() {
let mut j = partial[i - 1];
while j > 0 && pattern[j] != pattern[i] {
j = partial[j - 1];
}
partial.push(if pattern[j] == pattern[i] { j + 1 } else { j });
}
// and read 'string' to find 'pattern'
let mut ret = vec![];
let mut j = 0;
for (i, &c) in string.iter().enumerate() {
while j > 0 && c != pattern[j] {
j = partial[j - 1];
}
if c == pattern[j] {
j += 1;
}
if j == pattern.len() {
ret.push(i + 1 - j);
j = partial[j - 1];
}
}
ret
}
fn main() {
let result = knuth_morris_pratt(String::from("ababcabc"), String::from("abc"));
println!("{:?}", result);
}22.2.3 Boyer-Moore 算法
Boyer-Moore（BM）算法是实际应用中最快的字符串匹配算法之一，由 Robert S. Boyer 和 J Strother Moore 于 1977 年提出。与 KMP 从左向右匹配不同，BM 算法从右向左进行匹配。
核心思想：
-
坏字符规则（Bad Character Rule）：当模式串与文本串某个字符不匹配时，根据该字符在模式串中的位置，决定模式串向右滑动的距离。如果该字符不在模式串中，则可以跳过整个模式串的长度。
-
好后缀规则（Good Suffix Rule）：当模式串的某个后缀已经匹配但某个字符不匹配时，利用已匹配的后缀信息来决定滑动距离。
BM 算法取坏字符规则和好后缀规则中滑动距离较大者，因此平均时间复杂度可达 $O(n/m)$，最坏情况为 $O(m + n)$。在实际应用中（如文本编辑器的查找功能），BM 算法通常比 KMP 更快。
22.2.4 Rabin-Karp 算法
Rabin-Karp 算法由 Michael O. Rabin 和 Richard M. Karp 于 1987 年提出，采用**滚动哈希（Rolling Hash）**的思想进行字符串匹配。
核心思想：
- 计算模式串的哈希值 $h(P)$
- 计算文本串中每个长度为 $m$ 的子串的哈希值
- 若哈希值相等，再逐字符比较确认（避免哈希冲突）
滚动哈希的优势： 当窗口从位置 $i$ 滑动到位置 $i+1$ 时，不需要重新计算整个子串的哈希值，而是通过减去最左边字符的贡献、加上新字符的贡献，在 $O(1)$ 时间内完成更新：
$$ h(T[i+1 \ldots i+m]) = (h(T[i \ldots i+m-1]) - T[i] \times d^{m-1}) \times d + T[i+m] $$
其中 $d$ 为字符集大小（基数）。
Rabin-Karp 算法的平均时间复杂度为 $O(m + n)$，特别适合多模式匹配的场景——只需对文本串遍历一次，与多个模式串的哈希值进行比较即可。
22.2.5 各算法对比
| 算法 | 时间复杂度（最坏） | 时间复杂度（平均） | 空间复杂度 | 特点 |
|---|---|---|---|---|
| 暴力匹配 | $O(m \times n)$ | $O(m + n)$ | $O(1)$ | 实现简单，适合短串 |
| KMP | $O(m + n)$ | $O(m + n)$ | $O(m)$ | 不回溯，适合流式处理 |
| Boyer-Moore | $O(m \times n)$ | $O(n/m)$ | $O(\sigma)$ | 实际最快，从右向左 |
| Rabin-Karp | $O(m \times n)$ | $O(m + n)$ | $O(1)$ | 适合多模式匹配 |
$\sigma$ 为字符集大小。
22.3 DFA 敏感词检测
22.3.1 DFA 原理
DFA（Deterministic Finite Automaton，确定有限状态自动机）是一种计算模型，它具有以下特征：
- 有限个状态：自动机在任意时刻处于某个确定的状态
- 确定性的转移：对于每个状态和输入字符，最多有一个转移目标
- 初始状态和接受状态：从初始状态出发，根据输入字符序列进行状态转移，若最终到达接受状态，则表示匹配成功
DFA 可以用一个五元组 $M = (Q, \Sigma, \delta, q_0, F)$ 来形式化描述：
- $Q$：有限状态集合
- $\Sigma$：输入字母表（字符集）
- $\delta$：状态转移函数 $Q \times \Sigma \to Q$
- $q_0$：初始状态
- $F$：接受状态集合（$F \subseteq Q$）
22.3.2 Trie 树结构
在敏感词检测中，DFA 的状态转移图实际上是一棵 Trie 树（也称前缀树或字典树）。Trie 树的核心思想是：
- 每个节点代表一个字符
- 从根节点到某个节点的路径上的字符连接起来，构成一个前缀
- 标记为结束的节点表示一个完整的敏感词
例如，敏感词集合 {"信用卡套现", "信用卡代付", "信用卡代还"} 构成的 Trie 树结构如下：
信
└── 用
└── 卡
├── 套
│ └── 现 [END]
└── 代
├── 付 [END]
└── 还 [END]
22.3.3 最小匹配 vs 最大匹配
在敏感词检测中，有两种匹配策略：
- 最小匹配（MinMatchType）：一旦发现当前路径构成一个完整敏感词，立即停止并返回。适合对误判敏感的场景。
- 最大匹配（MaxMatchType）：继续沿 Trie 树向下查找，直到无法继续为止，返回最长的敏感词。适合需要检测所有嵌套敏感词的场景。
22.3.4 时间复杂度分析
DFA 敏感词检测的时间复杂度为 $O(n)$，其中 $n$ 为待检测文本的长度。这是因为：
- 每个字符最多被访问一次（不回溯）
- 状态转移的时间为 $O(1)$（HashMap 查找）
- 无论敏感词库中有多少词，检测时间仅与文本长度线性相关
这使得 DFA 算法非常适合大规模敏感词库的实时检测。
22.3.5 Rust 完整实现
#![allow(unused)]
fn main() {
use lazy_static::lazy_static;
use std::collections::BTreeSet;
use std::collections::HashMap;
use std::fs::File;
use std::io::prelude::*;
use std::io::BufReader;
use std::str::Chars;
/// 敏感词检测DFA算法（Rust实现，参考Java版实现 https://www.cnblogs.com/shihaiming/p/7048379.html）
/// 由于语言方面的限制，具体实现与Java有一定的差异。
///
lazy_static! {
static ref SENSITIVE_WORD_MAP: HashMap<char, SensitiveWordMap> = {
let set = read_sensitive_word_file();
build_sensitive_word_map(set)
};
}
pub enum MatchType {
MinMatchType, //最小匹配规则
MaxMatchType, //最大匹配规则
}
#[derive(Debug)]
struct SensitiveWordMap {
word: char,
is_end: char,
word_map: Option<HashMap<char, Box<SensitiveWordMap>>>,
}
/// 替换敏感字字符
/// # Examples
/// ```
/// let result = rust_by_example::dfa::replace_sensitive_word("信用卡之家", &MatchType::MinMatchType, '*')
/// assert_eq!(result,"**卡之家");
/// ```
pub fn replace_sensitive_word(txt: &str, match_type: &MatchType, replace_char: char) -> String {
let set: BTreeSet<String> = find_sensitive_word(txt, match_type);
let mut replace_str = String::from(txt);
for word in set {
let len = word.chars().count();
let replace_chars: String = vec![replace_char; len].iter().collect();
replace_str = replace_str.replace(word.as_str(), &replace_chars);
}
replace_str
}
/// 判断文字是否包含敏感字符
///
pub fn is_contains_sensitive_word(txt: &str, match_type: &MatchType) -> bool {
let mut is_contains = false;
let len = txt.chars().count();
let txt_vec: Vec<char> = txt.chars().collect();
let mut i = 0;
while i < len {
let length = check_sensitive_word(txt, i, match_type);
if length > 0 {
is_contains = true;
break;
}
i += 1;
}
is_contains
}
/// 获取文字中的敏感词
///
pub fn find_sensitive_word(txt: &str, match_type: &MatchType) -> BTreeSet<String> {
let mut sensitive_word_set = BTreeSet::<String>::new();
let len = txt.chars().count();
let txt_vec: Vec<char> = txt.chars().collect();
let mut i = 0;
while i < len {
let length = check_sensitive_word(txt, i, match_type);
if length > 0 {
//存在,加入list中
sensitive_word_set.insert(txt_vec[i..i + length].iter().collect());
i += length - 1; //减1的原因，是因为循环会自增
}
i += 1;
}
sensitive_word_set
}
/// 查文字中是否包含检敏感字符,如果存在，则返回敏感词字符的长度，不存在返回0
///
fn check_sensitive_word(txt: &str, begin_index: usize, match_type: &MatchType) -> usize {
let mut match_flag = 0;
let mut last_match_length = 0;
let mut word: char;
let txt_vec: Vec<char> = txt.chars().collect();
let len = txt.len();
if let Some(word) = &txt_vec.get(begin_index) {
if let Some(swm) = SENSITIVE_WORD_MAP.get(word) {
match_flag += 1;
if (*swm).is_end == '1' {
last_match_length = match_flag;
match match_type {
MatchType::MinMatchType => {
return last_match_length;
}
MatchType::MaxMatchType => (),
}
}
//递归查找
let mut j = begin_index + 1;
recursive_find_map(
swm,
&txt_vec,
&mut j,
&mut match_flag,
&mut last_match_length,
match_type,
);
}
}
last_match_length
}
/// 递归查找map
///
fn recursive_find_map(
swm: &SensitiveWordMap,
txt_vec: &[char],
i: &mut usize,
match_flag: &mut usize,
last_match_length: &mut usize,
match_type: &MatchType,
) {
if let Some(word) = txt_vec.get(*i) {
if let Some(wm) = &swm.word_map {
if let Some(next_swm) = wm.get(word) {
*match_flag += 1;
if swm.is_end == '1' {
*last_match_length = *match_flag;
match match_type {
MatchType::MinMatchType => {
return;
}
MatchType::MaxMatchType => (),
}
}
if next_swm.is_end == '1' {
*last_match_length = *match_flag;
match match_type {
MatchType::MinMatchType => {
return;
}
MatchType::MaxMatchType => (),
}
}
if let Some(nwm) = &next_swm.word_map {
if nwm.is_empty() {
*last_match_length = *match_flag;
match match_type {
MatchType::MinMatchType => {
return;
}
MatchType::MaxMatchType => (),
}
}
}
*i += 1;
recursive_find_map(
next_swm,
txt_vec,
i,
match_flag,
last_match_length,
match_type,
);
}
}
}
}
/// 递归地修改map
fn recursive_build_map(map: &mut SensitiveWordMap, chars: &mut Chars, count: &mut usize) {
if let Some(ch) = chars.next() {
*count -= 1;
if let Some(now_map) = map.word_map.as_mut() {
// let contains_key = now_map.contains_key(&ch);
if let std::collections::hash_map::Entry::Vacant(e) = now_map.entry(ch) {
let mut is_end = if *count == 0 { '1' } else { '0' };
let mut swm = SensitiveWordMap {
word: ch,
is_end,
word_map: Some(HashMap::<char, Box<SensitiveWordMap>>::new()),
};
now_map.insert(ch, Box::new(swm));
if let Some(m) = now_map.get_mut(&ch) {
recursive_build_map(&mut *m, &mut *chars, count);
}
} else if let Some(m) = now_map.get_mut(&ch) {
recursive_build_map(&mut *m, &mut *chars, count);
}
}
}
}
/// 读取敏感词库，将敏感词放入HashMap中，构建一个DFA算法模型
/// {
/// '信': SensitiveWordMap {
/// word: '信',
/// is_end: '0',
/// word_map: Some({
/// '用': SensitiveWordMap {
/// word: '用',
/// is_end: '0',
/// word_map: Some({
/// '卡': SensitiveWordMap {
/// word: '卡',
/// is_end: '0',
/// word_map: Some({
/// '套': SensitiveWordMap {
/// word: '套',
/// is_end: '0',
/// word_map: Some({
/// '现': SensitiveWordMap {
/// word: '现',
/// is_end: '1',
/// word_map: Som e({})
/// }
/// })
/// },
/// '代': SensitiveWordMap {
/// word: '代',
/// is_end: '0',
/// word_map: Some({
/// '付': SensitiveWordMap {
/// word: '付',
/// is_end: '1',
/// word_map: Some({})
/// },
/// '还': SensitiveWordMap {
/// word: '还',
/// is_end: '1',
/// word_map: Some({})
/// }
/// })
/// }
/// })
/// }
/// })
/// }
/// })
/// }
///
fn build_sensitive_word_map(set: BTreeSet<String>) -> HashMap<char, SensitiveWordMap> {
let mut sensitive_word_map = HashMap::<char, SensitiveWordMap>::new();
let mut iterator = set.iter();
for key in iterator {
let len = key.chars().count();
let mut count = len;
let mut key_chars = key.chars();
//读取每行的首个字符
if let Some(first_char) = key_chars.next() {
count -= 1;
if let Some(word_map) = sensitive_word_map.get_mut(&first_char) {
//读取下一个字符
recursive_build_map(&mut *word_map, &mut key_chars, &mut count);
} else {
let mut is_end = if len == 1 { '1' } else { '0' };
let mut now_map = SensitiveWordMap {
word: first_char,
is_end,
word_map: Some(HashMap::<char, Box<SensitiveWordMap>>::new()),
};
sensitive_word_map.insert(first_char, now_map);
if let Some(now_map) = sensitive_word_map.get_mut(&first_char) {
recursive_build_map(&mut *now_map, &mut key_chars, &mut count);
}
}
}
}
sensitive_word_map
}
/// 读取敏感词库中的内容，将内容添加到set集合中
fn read_sensitive_word_file() -> BTreeSet<String> {
let mut set = BTreeSet::<String>::new();
match File::open("sensitive-words.txt") {
Ok(f) => {
let reader = BufReader::new(f);
let lines = reader.lines();
for line in lines.map(|x| x.unwrap()) {
println!("{}", line);
set.insert(line);
}
}
Err(e) => panic!("can't open this file :{}", e),
}
set
}
pub fn read_file() {
let str_vec = vec![
"花呗信用卡代还OK套现",
"套花呗分期代付",
"马上套现信用卡",
"期货套利",
"空手套白狼",
"守信用卡脖子",
"坚定信心,同舟共济,科学防治,精准施策",
"D+1还是T+1秒到结算免结算费",
];
println!("find_sensitive_word MaxMatchType......");
for str in &str_vec {
let set = find_sensitive_word(str, &MatchType::MaxMatchType);
println!("{} --> {:?}", str, set);
}
println!("find_sensitive_word MinMatchType......");
for str in &str_vec {
let set = find_sensitive_word(str, &MatchType::MinMatchType);
println!("{} --> {:?}", str, set);
}
println!("is_contains_sensitive_word......");
for str in &str_vec {
let is_contains = is_contains_sensitive_word(str, &MatchType::MinMatchType);
println!("{} is contains sensitive words : {}", str, is_contains);
}
println!("replace_sensitive_word......");
for str in &str_vec {
let replace_str = replace_sensitive_word(str, &MatchType::MinMatchType, '*');
println!("{} --> {}", str, replace_str);
}
let result = replace_sensitive_word("信用卡之家", &MatchType::MinMatchType, '*');
assert_eq!(result, "**卡之家");
}
#[test]
fn sub_str() {
//实现类似Java String.substring()的功能，注意并不是适用于所有的字符。
let str = String::from("hello world");
let char_vec: Vec<char> = str.chars().collect();
let sub_str: String = char_vec[0..5].iter().collect();
println!("sub_str:{}", sub_str);
//不能使用上述代码进行截取子字符串的字符
for c in "नमस्ते".chars() {
println!("{}", c);
}
}
#[test]
fn set_iter() {
let mut b_tree_set = BTreeSet::<String>::new();
b_tree_set.insert(String::from("A"));
b_tree_set.insert(String::from("B"));
b_tree_set.insert(String::from("C"));
b_tree_set.insert(String::from("D"));
b_tree_set.insert(String::from("E"));
for val in &b_tree_set {
println!("{}", val);
}
let rm_key = String::from("C");
b_tree_set.remove(&rm_key);
println!("b_tree_set has {} items", b_tree_set.len());
println!("using VSCode coding rust program is greate");
}
}22.4 正则表达式
正则表达式（Regular Expression，简称 regex）是一种用于描述字符串模式的强大工具。它使用特定的语法规则来定义文本匹配的模式，广泛应用于文本搜索、验证、替换和提取等场景。
22.4.1 正则表达式基础语法
正则表达式由普通字符和特殊字符（元字符）组成。以下是常用的元字符：
| 符号 | 含义 | 示例 |
|---|---|---|
. | 匹配任意单个字符（除换行符） | a.c 匹配 abc、a1c |
* | 前一个字符出现 0 次或多次 | ab*c 匹配 ac、abbc |
+ | 前一个字符出现 1 次或多次 | ab+c 匹配 abc、abbc |
? | 前一个字符出现 0 次或 1 次 | ab?c 匹配 ac、abc |
^ | 匹配行首 | ^Hello 匹配行首的 Hello |
$ | 匹配行尾 | world$ 匹配行尾的 world |
\d | 匹配数字 [0-9] | \d+ 匹配 123 |
\w | 匹配字母、数字、下划线 | \w+ 匹配 hello_1 |
\s | 匹配空白字符 | \s+ 匹配空格、制表符 |
[abc] | 字符集合，匹配其中任一字符 | [aeiou] 匹配元音 |
{n,m} | 前一个字符出现 n 到 m 次 | a{2,4} 匹配 aa、aaa |
(...) | 分组捕获 | (ab)+ 匹配 abab |
| | 或（alternation） | cat|dog 匹配 cat 或 dog |
22.4.2 Rust regex 库
Rust 的正则表达式生态以 regex crate 为核心，它基于正则表达式的 NFA（非确定有限状态自动机）引擎实现，提供了高性能的模式匹配能力。
在 Cargo.toml 中添加依赖：
[dependencies]
regex = "1"
lazy_static = "1"
正则表达式的四大核心功能：
| 功能 | 方法 | 说明 |
|---|---|---|
| 查询（Search） | is_match() / find() | 检查是否存在匹配 / 查找匹配位置 |
| 验证（Validate） | is_match() + ^ $ | 验证整个字符串是否符合模式 |
| 替换（Replace） | replace() / replace_all() | 替换匹配的文本 |
| 提取（Extract） | captures() / captures_iter() | 提取分组匹配的内容 |
22.4.3 驼峰命名与蛇形命名转换
在实际开发中，不同编程语言有不同的命名规范。Rust 使用蛇形命名（snake_case），而 Java/C# 使用驼峰命名（camelCase），数据库字段也常用蛇形命名。下面通过正则表达式实现命名风格的转换。
echo "camelToSnakeName" | sed 's/\([a-z0-9]\)\([A-Z]\)/\1_\2/g' | tr '[:lower:]' '[:upper:]'
// Cargo.toml dependencies:
// lazy_static = "1"
// regex = "1"
use lazy_static::lazy_static;
use regex::Captures;
use regex::Regex;
lazy_static! {
// 驼峰命名转蛇形：第一遍处理 "任意字符 + 大写字母开头单词" 边界
// 如 "FalconHeavy" -> "Falcon_Heavy"
static ref CAMEL_TO_SNAKE1: Regex = Regex::new(r"(.)([A-Z][a-z]+)").unwrap();
// 第二遍处理 "小写/数字 + 大写" 边界，如 "HeavyRocket" -> "Heavy_Rocket"
static ref CAMEL_TO_SNAKE2: Regex = Regex::new(r"([a-z0-9])([A-Z])").unwrap();
}
/// 驼峰命名转为蛇形命名（全大写）
/// 例："FalconHeavyRocket" -> "FALCON_HEAVY_ROCKET"
pub fn camel_to_snake(origin: &str) -> String {
let result0 = CAMEL_TO_SNAKE1.replace_all(origin, |caps: &Captures| {
format!("{}_{}", &caps[1], &caps[2])
});
let result = CAMEL_TO_SNAKE2.replace_all(&result0, |caps: &Captures| {
format!("{}_{}", &caps[1], &caps[2])
});
result.to_uppercase()
}
/// 蛇形命名转为帕斯卡命名法（每个单词首字母大写，无分隔符）
/// 例："falcon_heavy_rocket" -> "FalconHeavyRocket"
pub fn snake_to_pascal(origin: &str) -> String {
origin
.split('_')
.map(|word| {
let mut chars = word.chars();
match chars.next() {
Some(ch) => {
let mut s = ch.to_uppercase().collect::<String>();
s.push_str(chars.as_str());
s
}
None => String::new(),
}
})
.collect::<String>()
}
/// 蛇形命名转驼峰命名（帕斯卡命名法首字母小写）
/// 例："falcon_heavy_rocket" -> "falconHeavyRocket"
pub fn snake_to_camel(s: &str) -> String {
let result = snake_to_pascal(s);
let mut chars = result.chars();
match chars.next() {
Some(ch) => {
let mut s = ch.to_lowercase().collect::<String>();
s.push_str(chars.as_str());
s
}
None => String::new(),
}
}
fn main() {
// 测试驼峰 -> 蛇形
let fields_vec = vec!["FalconHeavyRocket", "HTTPResponseCodeXYZ"];
for &field in &fields_vec {
let result = camel_to_snake(field);
println!("camel_to_snake({}) = {}", field, result);
}
println!("");
// 测试蛇形 -> 帕斯卡
let columns_vec = vec!["falcon_heavy_rocket", "http_response_code_xyz"];
for &col in &columns_vec {
let result = snake_to_pascal(col);
println!("snake_to_pascal({}) = {}", col, result);
}
println!("");
// 测试蛇形 -> 驼峰
for &col in &columns_vec {
let result = snake_to_camel(col);
println!("snake_to_camel({}) = {}", col, result);
}
}22.5 经典查询算法
查询算法是计算机科学中最基本的算法类别之一。根据数据是否有序、数据结构的不同，查询算法的选择和效率有很大差异。本节介绍几种经典的查找算法。
22.5.1 线性查找
线性查找（Linear Search）是最简单的查找算法：从数据结构的第一个元素开始，逐个与目标值进行比较，直到找到目标或遍历完所有元素。
时间复杂度： $O(n)$，其中 $n$ 为数据规模。
适用场景： 无序数据、小规模数据、链表等不支持随机访问的数据结构。
/// 线性查找：返回目标值的索引，未找到返回 None
pub fn linear_search<T: PartialEq>(arr: &[T], target: &T) -> Option<usize> {
for (i, item) in arr.iter().enumerate() {
if item == target {
return Some(i);
}
}
None
}
fn main() {
let arr = vec![5, 3, 8, 1, 9, 2];
if let Some(idx) = linear_search(&arr, &8) {
println!("找到 8，索引为 {}", idx);
}
}22.5.2 二分查找
二分查找（Binary Search）是一种高效的查找算法，前提是数据必须是有序的。其核心思想是：每次将查找区间缩小一半，通过比较中间元素与目标值的大小关系来决定查找方向。
算法步骤：
- 设有序数组为 $A[0 \ldots n-1]$，目标值为 $T$
- 初始化左边界 $left = 0$，右边界 $right = n - 1$
- 计算中间位置 $pivot = left + \lfloor(right - left) / 2\rfloor$
- 若 $A[pivot] = T$，找到目标，返回 $pivot$
- 若 $T < A[pivot]$，则 $right = pivot - 1$（目标在左半部分）
- 若 $T > A[pivot]$，则 $left = pivot + 1$（目标在右半部分）
- 重复步骤 3-6，直到 $left > right$
时间复杂度分析：
每次查找将区间缩小一半，因此最多需要比较的次数为：
$$ k = \lfloor \log_2 n \rfloor + 1 $$
即时间复杂度为 $O(\log n)$。对于 $n = 10^6$ 的有序数组，最多只需约 20 次比较即可找到目标。
/// 力扣（704. 二分查找) https://leetcode-cn.com/problems/binary-search/
pub fn search(nums: Vec<i32>, target: i32) -> i32 {
// target在[left,right]中查找
let len = nums.len();
let mut left = 0;
let mut right = len - 1;
let mut pivot;
while left <= right {
pivot = left + (right - left) / 2;
// 注意usize的范围和nums的下标范围
if nums[pivot] == target {
return pivot as i32;
}
if target < nums[pivot] {
if pivot == 0 {
break;
}
right = pivot - 1;
} else {
if pivot == len - 1 {
break;
}
left = pivot + 1;
}
}
-1
}
fn main() {
let nums = vec![-1, 0, 3, 5, 9, 12];
let target = 9;
let result = search(nums, target);
println!("result: {}", result);
}22.5.3 哈希查找
哈希查找通过哈希函数将键映射到数组中的位置，从而实现 $O(1)$ 平均时间复杂度的查找。
核心思想：
- 使用哈希函数 $h(key)$ 计算键的存储位置
- 直接通过索引访问，无需逐个比较
- 处理哈希冲突（链地址法、开放寻址法等）
Rust 标准库中的 HashMap 和 HashSet 就是基于哈希查找实现的。
use std::collections::HashMap;
fn main() {
let mut map = HashMap::new();
map.insert("apple", 3);
map.insert("banana", 5);
map.insert("cherry", 2);
// 哈希查找：O(1) 平均时间复杂度
if let Some(&count) = map.get("banana") {
println!("banana 的数量: {}", count);
}
}22.5.4 插值查找
插值查找（Interpolation Search）是二分查找的改进版本，适用于均匀分布的有序数据。与二分查找总是取中间位置不同，插值查找根据目标值在区间中的相对位置来估算其可能的位置：
$$ pivot = left + \frac{(target - A[left]) \times (right - left)}{A[right] - A[left]} $$
时间复杂度： 平均 $O(\log \log n)$（均匀分布时），最坏 $O(n)$。
插值查找在电话簿查号、字典查词等场景中非常高效，因为这些数据通常是近似均匀分布的。
22.5.5 各查找算法对比
| 算法 | 时间复杂度 | 空间复杂度 | 是否需要有序 | 适用场景 |
|---|---|---|---|---|
| 线性查找 | $O(n)$ | $O(1)$ | 否 | 无序数据、小数据量 |
| 二分查找 | $O(\log n)$ | $O(1)$ | 是 | 静态有序数据 |
| 哈希查找 | $O(1)$ 平均 | $O(n)$ | 否 | 键值对查找 |
| 插值查找 | $O(\log \log n)$ 平均 | $O(1)$ | 是 | 均匀分布的有序数据 |
22.6 树结构查找
树结构是一种重要的非线性数据结构，在查找场景中有着广泛的应用。本节介绍基于树的查找方法。
22.6.1 二叉搜索树（BST）
二叉搜索树（Binary Search Tree，BST）是一种特殊的二叉树，满足以下性质：
- 左子树中所有节点的值均小于根节点的值
- 右子树中所有节点的值均大于根节点的值
- 左右子树也分别是二叉搜索树
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13
查找过程：
- 从根节点开始
- 若目标值等于当前节点值，查找成功
- 若目标值小于当前节点值，递归查找左子树
- 若目标值大于当前节点值，递归查找右子树
- 若到达空节点，查找失败
时间复杂度：
- 平均情况（平衡树）：$O(\log n)$
- 最坏情况（退化为链表）：$O(n)$
插入与删除：
- 插入：按照查找路径走到空位置，将新节点插入
- 删除：分三种情况——叶子节点直接删除；只有一个子节点则用子节点替代；有两个子节点则用中序后继（或前驱）替代
// Cargo.toml dependencies（Playground 运行时需添加）:
// 无需第三方 crate，纯标准库
//! 二叉树
//! https://leetcode-cn.com/tag/binary-tree/problemset/
use std::cell::RefCell;
use std::cmp::max;
use std::rc::Rc;
#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
pub val: i32,
pub left: Option<Rc<RefCell<TreeNode>>>,
pub right: Option<Rc<RefCell<TreeNode>>>,
}
impl TreeNode {
#[inline]
pub fn new(val: i32) -> Self {
TreeNode {
val,
left: None,
right: None,
}
}
/// 树的深度：也称为树的高度，树中所有结点的层次最大值称为树的深度
pub fn get_height(root: &Option<Rc<RefCell<TreeNode>>>) -> i32 {
fn dfs(root: &Option<Rc<RefCell<TreeNode>>>) -> i32 {
match root {
None => 0,
Some(node) => {
let node = node.borrow();
1 + max(dfs(&node.left), dfs(&node.right))
}
}
}
dfs(root)
}
}
/// 从层序遍历数组构建二叉树（i32::MIN 表示空节点）
/// 标准层序: 对于下标 i，左子节点 = 2*i+1，右子节点 = 2*i+2
fn build_tree_from_level_order(arr: &[i32]) -> Option<Rc<RefCell<TreeNode>>> {
if arr.is_empty() || arr[0] == i32::MIN {
return None;
}
let root = Rc::new(RefCell::new(TreeNode::new(arr[0])));
let mut queue: Vec<Rc<RefCell<TreeNode>>> = vec![Rc::clone(&root)];
let mut i = 1;
while i < arr.len() {
let current = queue.remove(0);
// 左子节点
if i < arr.len() && arr[i] != i32::MIN {
let left_child = Rc::new(RefCell::new(TreeNode::new(arr[i])));
current.borrow_mut().left = Some(Rc::clone(&left_child));
queue.push(left_child);
}
i += 1;
// 右子节点
if i < arr.len() && arr[i] != i32::MIN {
let right_child = Rc::new(RefCell::new(TreeNode::new(arr[i])));
current.borrow_mut().right = Some(Rc::clone(&right_child));
queue.push(right_child);
}
i += 1;
}
Some(root)
}
/// 230. 二叉搜索树中第K小的元素 https://leetcode.cn/problems/kth-smallest-element-in-a-bst/
/// 中序遍历 BST，第 k 个元素即为第 k 小
pub fn kth_smallest(root: Option<Rc<RefCell<TreeNode>>>, k: i32) -> i32 {
fn inorder(node: &Option<Rc<RefCell<TreeNode>>>, result: &mut Vec<i32>) {
if let Some(n) = node {
let n = n.borrow();
inorder(&n.left, result);
result.push(n.val);
inorder(&n.right, result);
}
}
let mut result = vec![];
inorder(&root, &mut result);
// 中序遍历结果打印（辅助观察）
println!("中序遍历结果: {:?}", result);
result[(k - 1) as usize]
}
fn main() {
// 构建二叉搜索树:
// 3
// / \
// 1 4
// \
// 2
// 中序遍历: [1, 2, 3, 4]
// 第 1 小 = 1
let node2 = Rc::new(RefCell::new(TreeNode::new(2)));
let node1 = Rc::new(RefCell::new(TreeNode {
val: 1,
left: None,
right: Some(Rc::clone(&node2)),
}));
let node4 = Rc::new(RefCell::new(TreeNode::new(4)));
let node3 = Rc::new(RefCell::new(TreeNode {
val: 3,
left: Some(Rc::clone(&node1)),
right: Some(Rc::clone(&node4)),
}));
let root = Some(node3);
let k = 1;
let result = kth_smallest(root, k);
println!("第 {} 小的元素: {}", k, result);
// 也可以使用辅助函数从层序数组构建（i32::MIN = 空节点）
let arr = vec![3, 1, 4, i32::MIN, 2];
let root2 = build_tree_from_level_order(&arr);
println!("\n树的高度: {}", TreeNode::get_height(&root2));
}22.6.2 AVL 树
AVL 树（Adelson-Velsky and Landis Tree）是一种自平衡二叉搜索树。它通过引入平衡因子（Balance Factor）来维持树的平衡：
$$ \text{BalanceFactor}(node) = \text{height}(left_subtree) - \text{height}(right_subtree) $$
AVL 树要求任意节点的平衡因子绝对值不超过 1（即 $|\text{BF}| \leq 1$）。当插入或删除操作导致平衡因子超出范围时，通过旋转操作恢复平衡：
- LL 旋转（右旋）：左子树的左子树过深
- RR 旋转（左旋）：右子树的右子树过深
- LR 旋转（先左旋后右旋）：左子树的右子树过深
- RL 旋转（先右旋后左旋）：右子树的左子树过深
时间复杂度： 查找、插入、删除均为 $O(\log n)$。
22.6.3 红黑树
红黑树（Red-Black Tree）是另一种自平衡二叉搜索树，通过为节点着色（红色或黑色）并遵循特定规则来保持平衡。Rust 标准库中的 BTreeMap 和 BTreeSet 就是基于红黑树实现的。
红黑树的五条性质：
- 每个节点是红色或黑色
- 根节点是黑色
- 叶子节点（NIL 节点）是黑色
- 红色节点的两个子节点都是黑色（不能有连续的红色节点）
- 从任意节点到其所有叶子节点的路径上，黑色节点数量相同
时间复杂度： 查找、插入、删除均为 $O(\log n)$。与 AVL 树相比，红黑树在插入和删除时需要的旋转操作更少，适合频繁修改的场景。
22.6.4 B 树与 B+ 树
B 树（B-tree）和 B+ 树是多路平衡查找树，广泛应用于数据库索引和文件系统。
B 树的特点：
- 每个节点最多有 $m$ 个子节点（$m$ 阶 B 树）
- 除根节点和叶子节点外，每个节点至少有 $\lceil m/2 \rceil$ 个子节点
- 所有叶子节点在同一层
- 节点中的键值按序排列
B+ 树与 B 树的区别：
| 特性 | B 树 | B+ 树 |
|---|---|---|
| 数据存储 | 所有节点都存储数据 | 数据只存储在叶子节点 |
| 叶子节点链接 | 无 | 叶子节点通过链表连接 |
| 范围查询 | 效率较低 | 效率高（遍历链表即可） |
| 单次查询 | 可能提前终止 | 必须到达叶子节点 |
B+ 树是数据库索引的主流数据结构，MySQL 的 InnoDB 引擎就使用 B+ 树作为索引结构。
22.7 数据库查询
数据库查询是实际开发中最常见的查询场景之一。理解数据库查询的原理有助于编写高效的查询语句。
22.7.1 SQL 查询基础
SQL（Structured Query Language）是关系型数据库的标准查询语言。以下是常用的查询操作：
-- 基本查询
SELECT name, age FROM users WHERE age > 18;
-- 聚合查询
SELECT department, COUNT(*) as count, AVG(salary) as avg_salary
FROM employees
GROUP BY department
HAVING COUNT(*) > 5
ORDER BY avg_salary DESC;
-- 多表连接查询
SELECT u.name, o.product, o.amount
FROM users u
INNER JOIN orders o ON u.id = o.user_id
WHERE o.amount > 100;
-- 子查询
SELECT name FROM users
WHERE id IN (SELECT user_id FROM orders WHERE amount > 1000);
22.7.2 索引原理
数据库索引的本质是空间换时间。通过预先建立的数据结构（通常是 B+ 树），避免全表扫描，从而加速查询。
B+ 树索引的查找过程：
- 从根节点出发，根据比较结果选择合适的子节点
- 逐层向下查找，直到到达叶子节点
- 在叶子节点中找到目标记录或确认不存在
对于一棵 $m$ 阶 B+ 树，树的高度为 $h$，则查找的时间复杂度为 $O(h)$。一棵高度为 3 的 B+ 树，在 $m = 1000$ 时可以存储约 $10^9$ 条记录，即三次磁盘 I/O 即可定位到目标数据。
索引的设计原则：
- 选择性高的列（唯一值多的列）适合建索引
- 频繁作为 WHERE 条件的列适合建索引
- 联合索引遵循最左前缀匹配原则
- 避免在索引列上使用函数或隐式类型转换
22.7.3 Rust 数据库查询
在 Rust 生态中，常用的数据库 ORM/查询框架包括：
| 框架 | 类型 | 特点 |
|---|---|---|
| Diesel | 同步 ORM | 类型安全、编译时检查、性能优秀 |
| SeaORM | 异步 ORM | 基于 SeaQuery，支持异步、动态查询 |
| SQLx | 异步 SQL 工具包 | 编译时 SQL 检查、原生 SQL、轻量级 |
| rbatis | 动态 ORM | 类似 MyBatis，支持动态 SQL |
以下是使用 Diesel 的简单示例：
#![allow(unused)]
fn main() {
// Cargo.toml
// [dependencies]
// diesel = { version = "2.0", features = ["postgres"] }
use diesel::prelude::*;
// 查询所有年龄大于 18 的用户
fn find_adults(conn: &mut PgConnection) -> Vec<User> {
users::table
.filter(users::age.gt(18))
.load(conn)
.expect("Error loading users")
}
}22.8 搜索引擎简介
搜索引擎是查询技术的集大成者，需要在海量数据中快速、准确地找到用户需要的信息。
22.8.1 倒排索引
倒排索引（Inverted Index）是搜索引擎的核心数据结构。与传统的“文档 -> 单词“的正向索引不同，倒排索引建立的是“单词 -> 文档“的映射。
构建过程：
- 对每个文档进行分词（Tokenization）
- 对每个词项（Term）建立倒排列表（Posting List），记录包含该词项的文档 ID 及位置信息
文档1: "Rust 是一门系统编程语言"
文档2: "Rust 注重安全性和并发"
文档3: "Go 也是一门系统编程语言"
倒排索引:
"Rust" -> [文档1, 文档2]
"是" -> [文档1, 文档3]
"一门" -> [文档1, 文档3]
"系统" -> [文档1, 文档3]
"编程" -> [文档1, 文档3]
"语言" -> [文档1, 文档3]
"注重" -> [文档2]
"安全性" -> [文档2]
"和" -> [文档2]
"并发" -> [文档2]
"Go" -> [文档3]
"也" -> [文档3]
查询过程：
当用户搜索 “Rust 编程” 时：
- 对查询进行分词：[“Rust”, “编程”]
- 查找倒排列表：
"Rust" -> [文档1, 文档2]，"编程" -> [文档1, 文档3] - 求交集：[文档1]
- 返回结果：文档1
22.8.2 PageRank
PageRank 是 Google 创始人 Larry Page 提出的网页排名算法。它将互联网看作一个有向图，网页是节点，超链接是边。一个网页的 PageRank 值取决于指向它的其他网页的 PageRank 值和链接数量。
$$ PR(A) = (1 - d) + d \sum_{i=1}^{n} \frac{PR(T_i)}{C(T_i)} $$
其中：
- $PR(A)$ 是页面 A 的 PageRank 值
- $d$ 是阻尼系数（通常取 0.85），表示用户随机点击链接的概率
- $T_i$ 是指向页面 A 的页面
- $C(T_i)$ 是页面 $T_i$ 的出链数量
- $n$ 是指向页面 A 的页面总数
22.8.3 全文检索
全文检索（Full-Text Search）是指在大规模文本数据中，根据用户输入的关键词快速找到相关文档的技术。主流的全文检索引擎包括：
| 引擎 | 语言 | 特点 |
|---|---|---|
| Elasticsearch | Java | 分布式、实时搜索、生态丰富 |
| Apache Lucene | Java | 底层搜索引擎库 |
| Solr | Java | 基于 Lucene、企业级搜索平台 |
| Meilisearch | Rust | 轻量、快速、易部署 |
| Tantivy | Rust | 纯 Rust 实现、类 Lucene、高性能 |
22.8.4 Rust 的 Tantivy 全文搜索引擎
Tantivy 是一个用 Rust 编写的全文搜索引擎库，其设计灵感来自 Apache Lucene，但追求更高的性能和更低的资源消耗。
Tantivy 的核心特性：
- 纯 Rust 实现，无 unsafe 代码
- 支持全文检索、分词、BM25 相关性评分
- 支持增量索引和近实时搜索
- 压缩率高，内存占用低
- 支持多种分词器（中文分词需配合 jieba-rs 等）
// Cargo.toml
// [dependencies]
// tantivy = "0.22"
use tantivy::schema::*;
use tantivy::{Index, IndexWriter, doc};
fn main() -> tantivy::Result<()> {
// 1. 定义 schema
let mut schema_builder = Schema::builder();
let title = schema_builder.add_text_field("title", TEXT | STORED);
let body = schema_builder.add_text_field("body", TEXT);
let schema = schema_builder.build();
// 2. 创建索引
let index = Index::create_in_ram(schema.clone());
let mut writer = index.writer(50_000_000)?;
// 3. 添加文档
writer.add_document(doc!(
title => "Rust 编程语言",
body => "Rust 是一门注重安全性、并发性和性能的系统编程语言"
));
writer.add_document(doc!(
title => "Go 编程语言",
body => "Go 是一门注重简洁性和并发性的编程语言"
));
writer.commit()?;
// 4. 搜索
let reader = index.reader()?;
let searcher = reader.searcher();
let query_parser = QueryParser::for_index(&index, vec![title, body]);
let query = query_parser.parse_query("Rust 安全")?;
let top_docs = searcher.search(&query, &TopDocs::with_limit(10))?;
for (_score, doc_address) in top_docs {
let retrieved_doc = searcher.doc(doc_address)?;
println!("匹配文档: {}", schema.to_json(&retrieved_doc));
}
Ok(())
}22.9 总结
本章系统介绍了查询领域的核心算法与数据结构，从字符串模式匹配到搜索引擎，涵盖了查询技术的各个层面。下面是各查询算法的综合对比：
各查询算法综合对比
| 算法/数据结构 | 时间复杂度 | 空间复杂度 | 数据要求 | 主要应用场景 |
|---|---|---|---|---|
| 暴力匹配 | $O(m \times n)$ | $O(1)$ | 无 | 简单短串匹配 |
| KMP | $O(m + n)$ | $O(m)$ | 无 | 流式文本匹配 |
| Boyer-Moore | $O(n/m)$ 平均 | $O(\sigma)$ | 无 | 文本编辑器查找 |
| Rabin-Karp | $O(m + n)$ 平均 | $O(1)$ | 无 | 多模式匹配 |
| DFA 敏感词检测 | $O(n)$ | $O(k)$ | 敏感词库 | 内容安全过滤 |
| 正则表达式 | 取决于模式 | 取决于模式 | 无 | 文本验证与提取 |
| 线性查找 | $O(n)$ | $O(1)$ | 无 | 无序小数据 |
| 二分查找 | $O(\log n)$ | $O(1)$ | 有序数组 | 静态有序数据 |
| 哈希查找 | $O(1)$ 平均 | $O(n)$ | 无 | 键值对查找 |
| BST | $O(\log n)$ 平均 | $O(n)$ | 无 | 动态有序集合 |
| B+ 树 | $O(\log n)$ | $O(n)$ | 无 | 数据库索引 |
| 倒排索引 | $O(k)$ | $O(n)$ | 文档集合 | 搜索引擎 |
$m$ 为模式串长度，$n$ 为文本/数据规模，$k$ 为结果数量，$\sigma$ 为字符集大小。
场景选择建议
| 场景 | 推荐算法/工具 | 理由 |
|---|---|---|
| 简单子串查找 | 暴力匹配 / 标准库 str::find() | 实现简单，标准库已优化 |
| 大文本多次匹配 | KMP / Boyer-Moore | 避免回溯，性能稳定 |
| 敏感词过滤 | DFA（Trie 树） | $O(n)$ 线性扫描，支持大规模词库 |
| 文本格式验证 | 正则表达式 | 表达力强，覆盖面广 |
| 有序数组查找 | 二分查找 | $O(\log n)$，效率极高 |
| 键值对查找 | 哈希表（HashMap） | $O(1)$ 平均，最常用 |
| 动态有序数据 | BTreeMap / 红黑树 | 自动排序，$O(\log n)$ 操作 |
| 数据库查询 | B+ 树索引 + SQL | 成熟的索引技术 |
| 全文检索 | Tantivy / Elasticsearch | 倒排索引，相关性排序 |
22.10 练习题
练习 1： 实现暴力字符串匹配算法，找出文本串中所有模式串出现的位置，并分析其在最好和最坏情况下的时间复杂度。
练习 2： 手动计算模式串 "ABABABC" 的 KMP next 数组（部分匹配表），并画出匹配过程示意图。
练习 3： 使用 Rust 的 regex crate 实现一个简单的邮箱地址验证器，要求支持常见邮箱格式（如 user@example.com）。
练习 4： 给定一个有序整数数组和目标值，使用二分查找实现“查找第一个大于等于目标值的位置“（即 lower_bound）。
练习 5： 实现一个简单的 Trie 树（前缀树），支持插入、查找和前缀搜索（判断是否存在以某前缀开头的单词）。
练习 6： 使用 Tantivy 构建一个包含 100 篇文档的全文索引，实现关键词搜索并按相关性排序返回前 10 条结果。
练习 7： 对比分析 KMP 算法和 Boyer-Moore 算法在以下两种场景中的性能差异：（1）文本串和模式串都是英文小写字母；（2）模式串中包含大量重复子串。
练习 8： 设计一个基于 DFA 的 URL 敏感词检测系统，要求：（1）支持从文件加载敏感词库；（2）支持最小匹配和最大匹配两种模式；（3）支持敏感词替换功能。提示：可参考本章 22.3 节的 DFA 实现，将字符集从中文扩展到 URL 字符。