在一篇很长的文章或是一大串文字中找出自己想看到的段落是我们时常会需要做的事情,但是要如何有效率地让电脑寻找文字中的文字是一件需要思考的事情,甚至有许多针对这个议题所提出的研究论文。字符串搜索算法的好坏,在复杂的文档内容下,对搜索时间的影响是非常深远的。字符串搜索除了能够正确搜索一段文字内的特定字符串外,还可以用来搜索庞大的任意数据,因为任何的数据都可以借由数字编码转成只有数字的字符串,如一段原始的声音,一段原始的视频,甚至是一段生物基因。Boyer-Moore-MagicLen 是笔者结合 Boyer-Moore-Horspool 和 Quick Search Algorithm 得出的算法,这两种都是 Boyer-Moore (BM)算法的简化作法。这篇文章将会说明如何在 Rust 编程语言中使用 Boyer-Moore-MagicLen 算法。

如果您还不了解 Boyer-Moore-MagicLen 算法的话,可以先查看这篇文章。

Boyer-Moore-MagicLen

这个「Boyer-Moore-MagicLen」是笔者开发的套件,运用 Boyer-Moore-MagicLen 算法,支持字符、字符串以及字节数据的搜索。

Crates.io

Cargo.toml

boyer-moore-magiclen = "*"

使用方法

对于任意字节数据或是 UTF-8 的字符串数据,可以使用 BMByte 结构体。对于字符串行的数据,可以使用 BMCharacter 结构体,不过 BMCharacter 会比 BMByte 慢上不少。BMCharacter 需要标准函数库的支持,如果想要使用 BMCharacter 必须要激活 character 特色。

每个 BMXXX 类型,都可以利用 from 关联函数来传入要搜索的样本并产生出样本的结构实体。

use boyer_moore_magiclen::BMByte;

let bmb = BMByte::from("oocoo").unwrap();

如以上程序,bmb 这个 BMByte 结构实体可以用来在任意字节数据或是 UTF-8 的字符串数据中,搜索 oocoo 这段数据串行。

搜索的模式分为两种,第一种称为 全文搜索,这种搜索方式会去寻找要搜索的数据串行位于原始数据中的所在位置,包括重叠的部份。程序如下:

use boyer_moore_magiclen::BMByte;

let bmb = BMByte::from("oocoo").unwrap();

assert_eq!(vec![1, 4], bmb.find_full_in("coocoocoocoo", 2));

另一种搜索的模式称为 一般搜索,这种搜索方式会去寻找要搜索的数据串行位于原始数据中的所在位置,但不包括重叠的部份。程序如下:

use boyer_moore_magiclen::BMByte;

let bmb = BMByte::from("oocoo").unwrap();

assert_eq!(vec![1, 7], bmb.find_in("coocoocoocoo", 2));

另外除了由左往右搜索的 find_xxx 方法外,还有由右往左搜索的 rfind_xxx 方法。程序如下:

use boyer_moore_magiclen::BMByte;

let bmb = BMByte::from("oocoo").unwrap();

assert_eq!(vec![7, 1], bmb.rfind_in("coocoocoocoo", 2));
use boyer_moore_magiclen::BMByte;

let bmb = BMByte::from("oocoo").unwrap();

assert_eq!(vec![7, 4, 1], bmb.rfind_full_all_in("coocoocoocoo"));