使用自动机的高效多模式匹配算法资源-CSDN文库

共4个文件

pdf：4个

字符串匹配

多模式匹配

5星 · 超过95%的资源需积分: 9 132 浏览量 2009-01-09 14:55:15 上传评论收藏 971KB RAR 举报

资源详情

资源评论

资源推荐

收起资源包目录

FSM.rar （4个子文件）

FSM

基于网络处理器的高效中英文多模式匹配算法.pdf 140KB

A Fast Algorithm for Multi-pattern Searching.pdf 222KB

Efficient string matching.pdf 717KB

Sublinear Approximate.pdf 161KB

Programming Glenn Manacher

Techniques Editor

Efficient

String Matching:

An Aid to

Bibliographic Search

Alfred V. Aho and Margaret J. Corasick

Bell Laboratories

This paper describes a simple, efficient algorithm to

locate all occurrences of any of a finite number of key-

words in a string of text. The algorithm consists of con-

structing a finite state pattern matching machine from the

keywords and then using the pattern matching machine

to process the text string in a single pass. Construction

of the pattern matching machine takes time proportional

to the sum of the lengths of the keywords. The number

of state transitions made by the pattern matching

machine in processing the text string is independent of

the number of keywords. The algorithm has been used to

improve the speed of a library bibliographic search pro-

gram by a factor of 5 to 10.

Keywords and Phrases: keywords and phrases, string

pattern matching, bibliographic search, information re-

trieval, text-editing, finite state machines, computational

complexity.

CR Categories: 3.74, 3.71, 5.22, 5.25

General permission to republish, but not for profit, all or part of

this material is granted, provided that ACM's copyright notice is

given and that reference is made to this publication, to its date of

issue, and to the fact that reprinting privileges were granted by

permission of the Association for Computing Machinery.

Authors' present addresses: A. V. Aho, Bell Laboratories,

Murray Hill, N.J. 07974. M. J. Corasick, The MITRE Corporation,

Bedford, Mass. 01730.

333

1. Introduction

In many information retrieval and text-editing appli-

cations it is necessary to be able to locate quickly some or

all occurrences of user-specified patterns of words and

phrases in text. This paper describes a simple, efficient

algorithm to locate all occurrences of any of a finite

number of keywords and phrases in an arbitrary text

string.

The approach should be familiar to those acquainted

with finite automata. The algorithm consists of two parts.

In the first part we construct from the set of keywords a

finite state pattern matching machine; in the second part

we apply the text string as input to the pattern matching

machine. The machine signals whenever it has found a

match for a keyword.

Using finite state machines in pattern matching appli-

cations is not new [4, 8, 17], but their use seems to be

frequently shunned by programmers. Part of the reason

for this reluctance on the part of programmers may be

due to the complexity of programming the conventional

algorithms for constructing finite automata from regular

expressions [3, 10, 15], particularly if state minimization

techniques are needed [2, 14]. This paper shows that an

efficient finite state pattern matching machine can be

constructed quickly and simply from a restricted class of

regular expressions, namely those consisting of finite sets

of keywords. Our approach combines the ideas in the

Knuth-Morris-Pratt algorithm [13] with those of finite

state machines.

Perhaps the most interesting aspect of this paper is

the amount of improvement the finite state algorithm

gives over more conventional approaches. We used the

finite state pattern matching algorithm in a library biblio-

graphic search program. The purpose of the program is

to allow a bibliographer to find in a citation index all titles

satisfying some Boolean function of keywords and

phrases. The search program was first implemented with

a straightforward string matching algorithm. Replacing

this algorithm with the finite state approach resulted in a

program whose running time was a fifth to a tenth of the

original program on typical inputs.

2. A Pattern Matching Machine

This section describes a finite state string pattern

matching machine that locates keywords in a text string.

The next section describes the algorithms to construct

such a machine from a given finite set of keywords.

In this paper a

string

is simply a finite sequence of

symbols. Let K = {Yl,Y2 .....

Yk}

be a finite set of

strings which we shall call

keywords

and let x be an arbi-

trary string which we shall call the

text string.

Our prob-

lem is to locate and identify all substrings of x which are

keywords in K. Substrings may overlap with one another.

A pattern matching machine for K is a program which

takes as input the text string x and produces as output

the locations in x at which keywords of K appear as sub-

strings. The pattern matching machine consists of a set

states.

Each state is represented by a number. The

machine processes the text string x by successively read-

ing the symbols in x, making state transitions and occa-

Communications June 1975

of Volume 18

the ACM Number 6

sionally emitting output. The behavior of the pattern

matching machine is dictated by three functions: a goto

function g, a failure function f, and an output function

output.

Figure 1 shows the functions used by a pattern

matching machine for the set of keywords {he, she, his,

hers}.

Fig. 1. Pattern matching machine.

(a) Goto function.

f(i)

123456789

000120303

(b) FailureNnction.

i output (i)

2 {he}

5 {she, he}

7 {his}

9 {hers}

One state (usually 0) is designated as a

start

state. In

Figure 1 the states are 0, 1 .... ,9. The goto function g

maps a pair consisting of a state and an input symbol into

a state or the message

fail.

The directed graph in Figure

l(a) represents the goto function. For example, the edge

labeled h from 0 to 1 indicates that g(0, h) = 1. The

absence of an arrow indicates

fail

Thus, g(1, tr)

=fail

for all input symbols tr that are not e or i. All our pat-

tern matching machines have the property that

g (0, ~r) # fail

for all input symbols tr. We shall see that

this property of the goto function on state 0 ensures that

one input symbol will be processed by the machine in

every machine cycle.

The failure function f maps a state into a state. The

failure function is consulted whenever the goto function

reports

fail

Certain states are designated as output states

which indicate that a set of keywords has been found.

The output function formalizes this concept by associat-

ing a set of keywords (possibly empty) with every state.

operating cycle

of a pattern matching machine is

defined as follows. Let s be the current state of the

machine and a the current symbol of the input string x.

1. If

g(s, a) = s',

the machine makes a

goto transi-

tion.

It enters state s' and the next symbol of x becomes

the current input symbol. In addition, if

334

output(s') # empty,

then the machine emits the set

output(s')

along with the position of the current input

symbol. The operating cycle is now complete.

2. If

g(s, a) = fail,

the machine consults the failure

function f and is said to make a

failure transition.

f(s) = s"

the machine repeats the cycle with s' as the

current state and a as the current input symbol.

Initially, the current state of the machine is the start

state and the first symbol of the text string is the current

input symbol. The machine then processes the text

string by making one operating cycle on each symbol of

the text string.

For example, consider the behavior of the machine M

that uses the functions in Figure 1 to process the text

string "ushers." Figure 2 indicates the state transitions

made by M in processing the text string.

Fig. 2. Sequence of state transitions.

u s h e r s

00345 89

Consider the operating cycle when M is in state 4 and

the current input symbol is e. Since g(4, e) = 5, the

machine enters state 5, advances to the next input sym-

bol and emits

output(5),

indicating that it has found the

keywords "she" and "he" at the end of position four in the

text string.

In state 5 on input symbol r, the machine makes two

state transitions in its operating cycle. Since

g(5, r)

=fail M

enters state 2 =f(5). Then since

g(2, r) -- 8, M enters state 8 and advances to the next

input symbol. No output is generated in this operating

cycle.

The following algorithm summarizes the behavior of a

pattern matching machine.

Algorithm I. Pattern matching machine.

Input. A text string x = a I a 2 - - •

a n

where each

a i

is an input

symbol and a pattern matching machine M with goto func-

tion g, failure function f, and output function

output,

described above.

Output. Locations at which keywords occur in x.

Method.

begin

state ~ 0

for i~ 1 until n do

begin

while

g (state, a i ) = fail

state ~ f(state)

state ~ g (state, a i )

output (state) ;~ empty then

begin

print i

output (state)

end

Each pass through the for-loop represents one operating cy-

cle of the machine.

Communications June 1975

of Volume 18

the ACM Number 6

Algorithm 1 is patterned after the Knuth-Morris-Pratt

algorithm for finding one keyword in a text string [13]

and can be viewed as an extension of the "trie" search

discussed in [11]. Hopcroft and Karp (unpublished) have

suggested a scheme similar to Algorithm 1 for finding the

first occurrence of any of a finite set of keywords in a

text string [13]. Section 6 of this paper discusses a deter-

ministic finite automaton version of Algorithm 1 that

avoids all failure transitions.

3. Construction of Goto, Failure, and Output Functions

We say that the three functions g, f, and

output

are

valid

for a set of keywords if with these functions Algo-

rithm 1 indicates that keyword y ends at position i of text

string x if and only if x =

uyv

and the length of

is i.

We shall now show how to construct valid goto,

failure and output functions from a set of keywords.

There are two parts to the construction. In the first part

we determine the states and the goto function. In the

second part we compute the failure function. The com-

putation of the output function is begun in the first part

of the construction and completed in the second part.

To construct the goto function, we shall construct a

goto graph.

We begin with a graph consisting of one ver-

tex which represents the state 0. We then enter each

keyword y into the graph, by adding a directed path to

the graph that begins at the start state. New vertices and

edges are added to the graph so that there will be, starting

at the start state, a path in the graph that spells out the

keyword y. The keyword y is added to the output func-

tion of the state at which the path terminates. We add

new edges to the graph only when necessary.

For example, suppose {he, she, his, hers} is the set of

keywords. Adding the first keyword to the graph, we ob-

tain:

The path from state 0 to state 2 spells out the keyword

"he"; we associate the output "he" with state 2. Adding

the second keyword "she," we obtain the graph:

The output "she" is associated with state 5. Adding the

keyword "his," we obtain the following graph. Notice

that when we add the keyword "his" there is already an

edge labeled h from state 0 to state 1, so we do not need

to add another edge labeled h from state 0 to state 1. The

output "his" is associated with state 7.

(

Adding the last keyword "hers," we obtain:

The output "hers" is associated with state 9. Here we

have been able to use the existing edge labeled h from

state 0 to 1 and the existing edge labeled e from state 1 to

Up to this point the graph is a rooted directed tree.

To complete the construction of the goto function we add

a loop from state 0 to state 0 on all input symbols other

than h or s. We obtain the directed graph shown in Fig-

ure l(a). This graph represents the goto function.

The failure function is constructed from the goto

function. Let us define the

depth

of a state s in the goto

graph as the length of the shortest path from the start

state to s. Thus in Figure 1 (a), the start state is of depth

0, states 1 and 3 are of depth 1, states 2, 4, and 6 are of

depth 2, and so on.

We shall compute the failure function for all states of

depth 1, then for all states of depth 2, and so on, until the

failure function has been computed for all states (except

state 0 for which the failure function is not defined). The

algorithm to compute the failure function f at a state is

conceptually quite simple. We make

f(s)

--0 for all

states s of depth 1. Now suppose f has been computed

for all states of depth less than d. The failure function

for the states of depth d is computed from the failure

function for the states of depth less than d. The states of

depth d can be determined from the nonfail values of the

goto function of the states of depth d- 1.

Specifically, to compute the failure function for the

states of depth d, we consider each state r of depth d--1

and perform the following actions.

1. lfg(r,

a) =failfor

all a, do nothing.

2. Otherwise, for each symbol a such that

g(r, a) -- s,

do the following:

335

Communications June 1975

of Volume 18

the ACM Number 6

tonyfu4001

2012-11-10

目前正在研究这方面的东西,非常感谢楼主的贡献

评论收藏

内容反馈

Sword_liao

粉丝: 0
资源: 1

使用自动机的高效多模式匹配算法

评论2

最新资源

使用自动机的高效多模式匹配算法

评论2

FACA：一种基于交流自动机的多模式匹配算法

AC自动机算法（Aho-Corasick 多模式匹配算法）

Aho-Corasick 多模式匹配算法、AC自动机详解1

有限自动机的多模式匹配算法

一种多模式匹配高效算法的设计与实现 (2009年)

多模式匹配 ac自动机 dawg自动机

论文研究-基于树型有限自动机的DES规则匹配算法研究 .pdf

ACAuto自动机 多模式匹配 多字符串匹配

PHP版的AC多模式匹配算法

论文研究-THT-MSMA：基于双哈希表的高效多模式匹配算法.pdf

基于网络处理器的高效中英文多模式匹配算法.pdf

一种面向PDF文本内容审查的高效多模式匹配算法

一种改进的KMP高效模式匹配算法

论文研究-一种快速高效的模式匹配算法的应用研究.pdf

论文研究-一种基于双重状态编码的多模式匹配算法.pdf

36丨AC自动机：如何用多模式串匹配实现敏感词过滤功能？1

论文研究-基于模板有限自动机的正则表达式匹配算法.pdf

使用有限自动机做字符串匹配

一种存储优化的多模式匹配算法

论文研究-基于Aho-Corasick算法的多模式匹配算法研究.pdf

AC自动机实现多模式串匹配，支持中文

java版的AC多模式匹配算法

多模式串匹配之AC自动机算法

论文研究-改进的AAC多模式实时匹配算法.pdf

自动机理论，KMP算法等

Qt 5实现串口调试助手 （源工程文件、0积分下载）

【SystemVerilog】路科验证V2学习笔记（全600页）.pdf

AutoSAR标准协议4.2.2

光伏-储能并网系统仿真.rar

最新资源

ACAuto自动机多模式匹配多字符串匹配

Qt 5实现串口调试助手（源工程文件、0积分下载）