压缩Aho-Corasick自动机：资源受限的多模式匹配

155 浏览量更新于2024-08-29 收藏 273KB PDF 举报

"Space-efficient multiple string matching automata" 在信息技术领域，多字符串匹配是搜索文本中多个模式串出现的关键技术，广泛应用于数据挖掘、文本检索、病毒检测等场景。Aho-Corasick（AC）自动机是一种高效的数据结构，用于解决这个问题。本文详细介绍了如何在资源有限的系统，如移动设备上，实现空间效率更高的AC自动机。 AC自动机是由Aho和Corasick在1975年提出的一种算法，它扩展了KMP算法的概念，允许一次性查找多个模式串。AC自动机构建了一个包含失败指针的有向图，这个图能够快速地跳过不匹配的部分，一旦在一个路径上找不到匹配的字符，它会沿着失败指针回溯，而无需重新检查已遍历过的文本。在资源有限的环境中，存储和计算效率至关重要。文章提出了两种压缩方法来优化AC自动机： 1. 第一种方法关注于减少空间占用。对于一个大小为σ的字母表，AC自动机针对模式集P需要(σ + 1)I + (1 + log|P| + logM)M + o(M)位来存储，其中M是自动机的状态数量，I是非叶节点状态的数量。这种方法的优势在于状态转移的时间复杂度仅为O(1)，即常数时间，能够在保持较快搜索速度的同时减小内存需求。 2. 第二种方法则更注重空间效率，但牺牲了一些时间性能。这种情况下，空间需求变为I + (1 + log|P| + logM + logσ)M + o(Mlogσ)位，但状态转移的时间复杂度提高到O(loglogσ)。这意味着虽然需要更多的时间来处理状态转移，但总体空间使用量进一步降低。这两种方法的结合使得开发者可以在时间和空间复杂度之间进行权衡，根据实际应用场景选择合适的策略。关键词包括：多字符串匹配、Aho-Corasick自动机、空间效率和时间复杂度。这篇研究论文对AC自动机进行了深入的优化，尤其适用于资源受限的环境，如移动设备。通过压缩技术和不同时间复杂度的方案，实现了在有限内存下进行高效的多模式字符串匹配，为实际应用提供了理论支持和实用技巧。

308 Int. J. Wireless and Mobile Computing, Vol. 5, No. 3, 2012

Space-efficient multiple string matching automata

Meng Zhang*, Tianyu Yang and Rui Wu

College of Computer Science and Technology,

Jilin University,

Changchun, China

Email: zhangmeng@jlu.edu.cn

Email: tricky1997@qq.com

Email: 1245023548@qq.com

*Corresponding author

Abstract: Aho–Corasick (AC) automaton is a data structure for multiple string matching. We

present two compressing methods that enable the AC automaton to work on systems with limited

resource such as mobile devices. By the first method, the AC automaton for a pattern set P over

an alphabet of size

needs (

+ 1)I + (1 + log|P| + logM)M + o(M) bits where M and I are the

number of states and the number of non-leaf states of the AC automaton respectively, and a state

transition takes O(1) time. By the second method, the space is I + (1 + log|P| + logM + log

)M +

o(M log

) bits, and a state transition takes O(log log

) time. We then combine the two methods

together and archive trade-offs between the space and time complexity.

Keywords: multiple string matching; Aho–Corasick automaton; succinct data structure.

Reference to this paper should be made as follows: Zhang, M., Yang, T. and Wu, R. (2012)

‘Space-efficient multiple string matching automata’, Int. J. Wireless and Mobile Computing,

Vol. 5, No. 3, pp.308–313.

Biographical notes: Meng Zhang is currently an Associate Professor in College of Computer Science

and Technology, Jilin University. He received his PhD in Computer Science from Jilin University in

2003. His main research interests include stringology, network security and computational biology.

Tianyu Yang is currently a third year undergraduate student in College of Computer Science and

Technology at Jilin University. His research interests include algorithm design and network security.

Rui Wu is currently a third year undergraduate student in College of Computer Science and

Technology at Jilin University. His research interests include algorithm design and network security.

1 Introduction

The

problem of multiple string matching is to find a set of strings

P = {p

, …, p

} in a text t. Throughout the paper, k denotes the

number of patterns, n denotes the length of t, Σ = {a

, a

, …,

} denotes the alphabet of

symbols from which the symbols

in P and t are chosen. Much research focus on multiple string

matching problem. The first algorithm to solve this problem in

O(n log

) time is presented by Aho and Corasick (1975) and

Cormen et al. (2001) which generalises the Knuth–Morris–Pratt

algorithm (Knuth et al., 1977). The Commentz-Walter (1979)

algorithm is a direct extension of the Boyer–Moore algorithm

(Boyer and Moore, 1977) which also combines the idea of AC

algorithm. There are also several factors recognition approach-

based algorithms (Raffinot, 1997; Allauzen and Raffinot, 1999;

Crochemore et al., 1999) that use either suffix automata or

factor oracles for precise or weak factor recognition. For short

patterns, bit parallelism leads to algorithms that are efficient in

practice (see Navarro and Raffinot, 2002). Though presented

30 years ago, AC algorithm is still extensively used in practice.

The AC-automaton is also the core data structure in deep

packet inspection systems (Song et al., 2008; Snort Intrusion

Detection System, 2012, see http://www.snort.org) and anti-

virus systems (ClamAV, 2012; http://www.clamav.net).

Succinct data structures (Jacobson, 1989; Munro, 1996;

Munro and Raman, 1997; Ferragina and Manzini, 2000; Grossi

and Vitter, 2000; He et al., 2005) recently have received much

attention. A succinct data structure stores objects using

space close to the information-theoretic lower bound, while

simultaneously supporting a number of primitive operations on

the objects in constant time. The compressed suffix array

structure proposed by Grossi and Vitter (2000) is the first

method that reduces the size of the suffix array from O(n log n)

bits to O(n) bits and supports access to any entry of the original

suffix array in

(

)

logOn

∈

time, for any fixed constant 0 < ∈

< 1 (without computing the entire original suffix array).

FM-index proposed by Ferragina and Manzini (2000) is a self-

index data structure with good compression ratio and fast

decompressing speed. The FM-index occupies at most 5nH

(T)

+ o(n) bits of storage, where H

is the k-th order entropy of T

and allows the search for the occ occurrences of a pattern

p[1…m] within T in O(m + occ log

1+∈

n) time.

In this paper, we focus on compacting AC automata to

make it possible to work on systems with limited resource. The

major drawback that limits the applicability of AC automata is

their space complexity. We present space compacting methods

for AC automata based on succinct data structure technologies

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

weixin_38680308

粉丝: 13
资源: 888

压缩Aho-Corasick自动机：资源受限的多模式匹配

Efficient String Matching : An Aid to Bibliographic Search

FACE-RECOGNITION-USING-ENSEMBLE-STRING-MATCHING.r_ensemble_face

Fast Multiple String Matching Using Streaming SIMD Extensions Technology - 2013 (psc13p08_presentation)-计算机科学

String Matching with Finite Automata

Two-Way String Matching (1991)-计算机科学

computer-vision---template-matching-:基于matlab的计算机视觉项目，用于大学课程项目

Approximate-String-Matching

approximate-string-matching

Efficient string matching with wildcards and length constraints

Approximate-String-Matching:KAUST AMCS 260 算法

最新资源