如何使用Rust程式語言進行快速的字串或是任意資料的搜尋？

在一篇很長的文章或是一大串文字中找出自己想看到的段落是我們時常會需要做的事情，但是要如何有效率地讓電腦尋找文字中的文字是一件需要思考的事情，甚至有許多針對這個議題所提出的研究論文。字串搜尋演算法的好壞，在複雜的文件內容下，對搜尋時間的影響是非常深遠的。字串搜尋除了能夠正確搜尋一段文字內的特定字串外，還可以用來搜尋龐大的任意資料，因為任何的資料都可以藉由數位編碼轉成只有數字的字串，如一段原始的聲音，一段原始的影片，甚至是一段生物基因。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

使用方法

對於任意位元組資料或是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"));