Struct python_comm::prelude::TextSearcher

pub struct TextSearcher { /* fields omitted */ }

基于 Aho–Corasick 算法的全文匹配/替换

Aho–Corasick 算法

Aho–Corasick 算法通过预先定义的字典, 只扫描一遍文本, 可以完成多个关键字的查找、替换。

示例

关键字: {a, ab, bab, bc, bca, c, caa}.

构造

1. 每个关键字的每个前缀对应 trie 中的一个节点, 比如 bab 对应 (), b, ba, bab 四个节点;
2. 不同关键字可共享节点, 比如 bab, bca 共享 (), b 节点;
3. 对应关键字的节点为蓝色节点, 比如 bab 节点, 仅对应前缀的节点为灰色节点, 比如 ba 节点;
4. 同一关键字的相邻前缀间用黑色箭头连接, 比如 ba –> bab;
5. 除根节点外, 每个节点用蓝色箭头指向它的最长有效真后缀, 比如 caa 的真后缀包括 aa, a, (), 其中 a, () 在树中, a 是最长的, 所以蓝色箭头 caa –> a

节点 颜色 蓝箭头

() 灰 -

a 蓝 ()

ab 蓝 b

b 灰 ()

ba 灰 a

bab 蓝 ab

bc 蓝 c

bca 蓝 ca

c 蓝 ()

ca 灰 a

caa 蓝 a

查找

1. 从当前节点出发,

a) 沿黑色箭头匹配下一个字符, 切换到新节点;

b) 如果不存在有效的黑色箭头, 沿蓝箭头到下一个节点, 重复步骤 a) b);

2. 重复步骤 1. 直到没有字符需要匹配

搜索 abccab 过程

节点 剩余字符串 查找过程 输出

() abccab 黑箭 a 有效

a bccab 黑箭 ab 有效 蓝点 a

ab ccab 黑箭 abc 无效, 蓝箭 b 蓝点 ab

b ccab 黑箭 bc 有效

bc cab 黑箭 bcc 无效, 蓝箭 c 蓝点 bc

c cab 黑箭 cc 无效, 蓝箭 () 蓝点 c

() cab 黑箭 c 有效

c ab 黑箭 ca 有效 蓝点 c

ca b 黑箭 cab 无效, 蓝箭 a

a b 黑箭 ab 有效 蓝点 a

ab - - 蓝点 ab

用法

Step1. ts = TextSearcher::new();

Step2. ts.add_keyword(); // 可添加多个关键字

Step3. ts.create_blues();

Step4. ts.search() / ts.replace(); // ts 可复用

use python_comm::prelude::TextSearcher;

let mut ts0 = TextSearcher::new();
let mut ts1 = TextSearcher::new();
for (keyword, title) in &[("bcdef", "X"), ("defghi", "Y"), ("hijk", "Z")] {
    ts0.add_keyword(String::from(*keyword), None);
    ts1.add_keyword(String::from(*keyword), Some(String::from(*title)));
}
ts0.create_blues();
ts1.create_blues();

assert_eq!(
    ts0.search("abcdefghijklmn"),
    [
        (String::from("bcdef"), 1, 6),    // 返回匹配的每个关键字及起始位置
        (String::from("defghi"), 3, 9),
        (String::from("hijk"), 7, 11)
    ]
);
assert_eq!(
    ts1.search("abcdefghijklmn"),
    [
        (String::from("X"), 1, 6),    // 返回匹配的每个关键字别名及起始位置
        (String::from("Y"), 3, 9),
        (String::from("Z"), 7, 11)
    ]
);
assert_eq!(
    ts1.replace("abcdefghijklmn"),    // 替换匹配的每个关键字, 如果出现重叠则不替换
    "aXgZlmn"
);

Implementations

impl TextSearcher

pub fn add_keyword(&mut self, keyword: String, name: Option<String>)

添加关键字

pub fn create_blues(&mut self)

创建蓝色箭头

pub fn new() -> Self

构造

pub fn replace(&self, text: &str) -> String

替换

pub fn search(&self, text: &str) -> Vec<(String, usize, usize)>

查找