Boyer-Moore算法详解：高效字符串搜索

需积分: 9 56 浏览量更新于2024-09-12 收藏 1.14MB PDF 举报

"这篇原始论文讨论了Boyer-Moore字符串搜索算法，这是一种在计算机科学中高效的字符串查找算法，常被用作实际字符串搜索性能的标准基准。由Robert S. Boyer和J Strother Moore在1977年开发，该算法对要搜索的模式进行预处理，但不对要搜索的文本进行预处理。当模式远短于文本或在多个搜索中保持不变时，它非常适用。Boyer-Moore算法利用预处理步骤收集的信息来跳过文本的某些部分，其运行速度通常比许多其他字符串算法更快，特别是随着模式长度的增加，效率更高。算法的关键特点是反向匹配模式的尾部，而不是头部，并以多字符跳跃的方式遍历文本，而非逐一检查文本中的每个字符。" 在详细说明Boyer-Moore算法的工作原理时，我们可以看到以下几个关键点： 1. **预处理阶段**：Boyer-Moore算法首先对模式字符串（要查找的字符串）进行预处理，生成一个“坏字符规则”表。这个表记录了模式字符串中每个字符最后一次出现的位置，以便在匹配过程中快速跳过不匹配的部分。 2. **坏字符规则**：当匹配过程中遇到不匹配的字符时，算法会使用坏字符规则来确定下一次应该从哪个位置开始比较。它会查找不匹配字符在模式字符串中的位置，并以模式长度减去这个位置的距离作为跳跃距离，跳过可能不匹配的部分。 3. **好后缀规则**：此外，Boyer-Moore算法还利用“好后缀规则”进一步优化。如果一部分模式字符串已经匹配，但最后一个字符不匹配，算法会查找与模式字符串剩余部分相同的后缀，并基于这个后缀的长度来决定跳跃的距离。这样可以避免重复匹配已知匹配的子串。 4. **效率优势**：由于这些规则的存在，Boyer-Moore算法在大多数情况下只需要检查输入文本的一小部分，平均检查的字符数量随模式长度的增加而减少。这使得算法在处理长模式字符串时尤其有效。 5. **实证分析**：论文中提到，对于随机的英语模式字符串，平均来说，Boyer-Moore算法执行的机器指令数量少于模式长度加上文本长度。这进一步证实了算法的高效性。 6. **应用**：由于其高效性和对模式长度的适应性，Boyer-Moore算法广泛应用于各种文本处理任务，如文件搜索、文本编辑器、数据挖掘等。 Boyer-Moore算法通过智能地跳过不匹配部分，显著减少了字符串搜索的时间复杂度，成为字符串匹配领域的一个重要工具。其预处理和动态调整的策略为字符串搜索算法的设计提供了新的思路。

展开

pat:

AT-THAT

string:

...

WHICH-FINALLY-HALTS.--AT-THAT-POINT ...

Since "F" is known not to occur in

pat,

we can appeal

to Observation 1 and move the pointer (and thus

pat)

down by 7:

pat:

AT-THAT

string:

... WHICH-FINALLY-HALTS.--AT-THAT-POINT ...

Appealing to Observation 2, we can move the pointer

down 4 to align the two hyphens:

pat:

AT-THAT

string:

... WHICH-FINALLY-HALTS.--AT-THAT-POINT ...

Now

char

matches its opposite in

pat.

Therefore we

step left by one:

pat:

AT-THAT

string:

... WHICH-FINALLY-HALTS.--AT T~IAT POINT ...

Appealing to Observation 3(a), we can move the

pointer to the right by 7 positions because "L" does

not occur in

pat. 2

Note that this only moves

pat

to the

right by 6.

pat:

AT-THAT

string:

... WHICH-FINALLY-HALTS.--AT-THAT-POINT ...

Again

char

matches the last character of

pat.

Stepping

to the left we see that the previous character in

string

also matches its opposite in

pat.

Stepping to the left a

second time produces:

pat:

AT-THAT

string:

... WHICH-FINALLY-HALTS.--AT-THAT-POINT ...

Noting that we have a mismatch, we appeal to Obser-

vation 3(b). The

delta2

move is best since it allows us

to push the pointer to the right by 7 so as to align the

discovered substring "AT" with the beginning of

pat. ~

pat:

AT-THAT

string:

... WHICH-FINALLY-HALTS.--AT-THAT-POINT ...

This time we discover that each character of

pat

matches the corresponding character in

string

so we

have found the pattern. Note that we made only 14

references to

string.

Seven of these were required to

confirm the final match. The other seven allowed us to

move past the first 22 characters of

string.

2 Note that

deltaz

would allow us to move the pointer to the

right only 4 positions in order to align the discovered substring "T"

string

with its second from last occurrence at the beginning of the

word "THAT" in

pat.

3 The

delta~

move only allows the pointer to be pushed to the

right by 4 to align the hyphens.

764

4. The Algorithm

We now specify the algorithm. The notation

pat(j)

refers to the jth character in

pat

(counting from 1 on

the left).

We assume the existence of two tables,

delta1

and

deltas.

The first has as many entries as there are

characters in the alphabet. The entry for some charac-

ter

char

will be denoted by

deltas(char).

The second

table has as many entries as there are character posi-

tions in the pattern. The jth entry will be denoted by

delta2(j).

Both tables contain non-negative integers.

The tables are initialized by preprocessing

pat,

and

their entries correspond to the values

deltaa

and

delta2

referred to earlier. We will specify their precise con-

tents after it is clear how they are to be used.

Our search algorithm may be specified as follows:

stringlen ,,--

length of

string.

i ~ patlen.

top:

if i >

stringlen

then return false.

j ,,-- patlen.

loop:

ifj = 0 then returnJ + 1.

string(i) = pat(j)

then

j~"-j-1.

i,~--i-1.

goto

loop.

close;

i ~-- i + max(delta1 (string(i)), delta2 (j)).

goto

top.

If the above algorithm returns false, then

pat

does not

occur in

string.

If the algorithm returns a number,

then it is the position of the left end of the first

occurrence

of pat

string.

The

deltal

table has an entry for each character

char

in the alphabet. The definition of

delta~

is:

deltas(char)

= If

char

does not occur in

pat,

then

pat-

len;

else

patlen - j,

where j is the

maximum integer such that

pat(j) =

char.

The

deltaz

table has one entry for each of the integers

from 1 to

patlen.

Roughly speaking,

delta2(j)

is (a) the

distance we can slide

pat

down so as to align the

discovered occurrence (in

string)

of the last

patlen-j

characters of

pat

with its rightmost plausible reoccurr-

ence, plus (b) the additional distance we must slide the

"pointer" down so as to restart the process at the right

end of

pat.

To define

delta2

precisely we must define

the rightmost plausible reoccurrence of a terminal

substring of

pat.

To this end let us make the following

conventions: Let $ be a character that does not occur

pat

and let us say that if i is less than 1 then

pat(i)

$. Let us also say that two sequences of characters [c~

• . . c,] and [d~ . . . d,] "unify" if for all i from 1 to n

either c~ =di or c~ = $ or d~ = $.

Finally, we define the position of the rightmost

plausible reoccurrence of the terminal substring which

starts at positionj + 1,

rpr(j),

forj from 1

topatlen,

be the greatest k less than or equal to

patlen

such that

Communications October 1977

of Volume 20

the ACM Number 10

下载后可阅读完整内容，剩余10页未读，立即下载

身份认证购VIP最低享 7 折!

30元优惠券

rock4you

粉丝: 140

Boyer-Moore算法详解：高效字符串搜索

论文研究-一种串匹配的快速Boyer-Moore算法.pdf

boyer-moore算法C实现

Boyer-Moore法实现字符串匹配（java）

Boyer-Moore 多数表决算法：Boyer-Moore 多数表决算法-matlab开发

Boyer-Moore算法

monkey-moore:基于Boyer-Moore字符串搜索算法的相对搜索器工具

newBM.rar_Boyer Moore_Boyer-Moore算法_boyer

boyer-moore-string-search:C语言中的Boyer Moore字符串搜索实现

cpp代码-boyer-Moore算法实现

Boyer-Moore-Horspool-Sunday.rar_Boyer Moore_horspo_horspool_sund

最新资源