An Aho-Corasick based assessment of algorithms generating failure deterministic finite automata

Madoda Nxumalo; Derrick G. Kourie; Loek Cleophas; Bruce W. Watson

An Aho-Corasick based assessment of algorithms generating failure deterministic finite automata

Madoda Nxumalo, Derrick G. Kourie, Loek Cleophas, Bruce W. Watson

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

Abstract

The Aho-Corasick algorithm derives a failure deterministic finite automaton for finding matches of a finite set of keywords in a text. It has the minimum number of transitions needed for this task. The DFA-Homomorphic Algorithm (DHA) algorithm is more general, deriving from an arbitrary complete deterministic finite automaton a language-equivalent failure deterministic finite automaton. DHA takes formal concepts of a lattice as input. This lattice is built from a state/outtransition formal context that is derived from the complete deterministic finite automaton. In this paper, three general variants of the abstract DHA are benchmarked against the specialised Aho-Corasick algorithm. It is shown that when heuristics for these variants are suitably chosen, the minimality attained by the Aho-Corasick algorithm can be closely approximated. A published non-lattice-based algorithm is also shown to perform well in experiments.

Original language	English
Title of host publication	Proceedings of the Twelfth International Conference on Concept Lattices and Their Applications, October 13-16, 2015, Clermont-Ferrand, France
Editors	S. Ben Yahia, J. Konecny
Publisher	CEUR-WS.org
Pages	87-98
Number of pages	12
ISBN (Print)	9782954494807
Publication status	Published - 2015
Event	12th International Conference on Concept Lattices and their Applications (CLA 2015), October 13-16, 2015, Clermont-Ferrand, France - Campus des Cézeaux, Clermont-Ferrand, France Duration: 13 Oct 2015 → 16 Oct 2015 http://cla2015.isima.fr/

Publication series

Name	CEUR Workshop Proceedings
Volume	1466

Conference

Conference	12th International Conference on Concept Lattices and their Applications (CLA 2015), October 13-16, 2015, Clermont-Ferrand, France
Abbreviated title	CLA 2015
Country/Territory	France
City	Clermont-Ferrand
Period	13/10/15 → 16/10/15
Internet address	http://cla2015.isima.fr/

Keywords

Aho-Corasick algorithm
Failure deterministic finite automaton

Cite this

Nxumalo, M., Kourie, D. G., Cleophas, L., & Watson, B. W. (2015). An Aho-Corasick based assessment of algorithms generating failure deterministic finite automata. In S. Ben Yahia, & J. Konecny (Eds.), Proceedings of the Twelfth International Conference on Concept Lattices and Their Applications, October 13-16, 2015, Clermont-Ferrand, France (pp. 87-98). (CEUR Workshop Proceedings; Vol. 1466). CEUR-WS.org.

Nxumalo, Madoda ; Kourie, Derrick G. ; Cleophas, Loek et al. / An Aho-Corasick based assessment of algorithms generating failure deterministic finite automata. Proceedings of the Twelfth International Conference on Concept Lattices and Their Applications, October 13-16, 2015, Clermont-Ferrand, France . editor / S. Ben Yahia ; J. Konecny. CEUR-WS.org, 2015. pp. 87-98 (CEUR Workshop Proceedings).

@inproceedings{a61fefe6d9eb49439bc9cf64bd6b77c7,

title = "An Aho-Corasick based assessment of algorithms generating failure deterministic finite automata",

abstract = "The Aho-Corasick algorithm derives a failure deterministic finite automaton for finding matches of a finite set of keywords in a text. It has the minimum number of transitions needed for this task. The DFA-Homomorphic Algorithm (DHA) algorithm is more general, deriving from an arbitrary complete deterministic finite automaton a language-equivalent failure deterministic finite automaton. DHA takes formal concepts of a lattice as input. This lattice is built from a state/outtransition formal context that is derived from the complete deterministic finite automaton. In this paper, three general variants of the abstract DHA are benchmarked against the specialised Aho-Corasick algorithm. It is shown that when heuristics for these variants are suitably chosen, the minimality attained by the Aho-Corasick algorithm can be closely approximated. A published non-lattice-based algorithm is also shown to perform well in experiments.",

keywords = "Aho-Corasick algorithm, Failure deterministic finite automaton",

author = "Madoda Nxumalo and Kourie, {Derrick G.} and Loek Cleophas and Watson, {Bruce W.}",

year = "2015",

language = "English",

isbn = "9782954494807",

series = "CEUR Workshop Proceedings",

publisher = "CEUR-WS.org",

pages = "87--98",

editor = "{Ben Yahia}, S. and J. Konecny",

booktitle = "Proceedings of the Twelfth International Conference on Concept Lattices and Their Applications, October 13-16, 2015, Clermont-Ferrand, France",

note = "12th International Conference on Concept Lattices and their Applications (CLA 2015), October 13-16, 2015, Clermont-Ferrand, France, CLA 2015 ; Conference date: 13-10-2015 Through 16-10-2015",

url = "http://cla2015.isima.fr/",

}

Nxumalo, M, Kourie, DG, Cleophas, L & Watson, BW 2015, An Aho-Corasick based assessment of algorithms generating failure deterministic finite automata. in S Ben Yahia & J Konecny (eds), Proceedings of the Twelfth International Conference on Concept Lattices and Their Applications, October 13-16, 2015, Clermont-Ferrand, France . CEUR Workshop Proceedings, vol. 1466, CEUR-WS.org, pp. 87-98, 12th International Conference on Concept Lattices and their Applications (CLA 2015), October 13-16, 2015, Clermont-Ferrand, France, Clermont-Ferrand, France, 13/10/15.

An Aho-Corasick based assessment of algorithms generating failure deterministic finite automata. / Nxumalo, Madoda; Kourie, Derrick G.; Cleophas, Loek et al.
Proceedings of the Twelfth International Conference on Concept Lattices and Their Applications, October 13-16, 2015, Clermont-Ferrand, France . ed. / S. Ben Yahia; J. Konecny. CEUR-WS.org, 2015. p. 87-98 (CEUR Workshop Proceedings; Vol. 1466).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - An Aho-Corasick based assessment of algorithms generating failure deterministic finite automata

AU - Nxumalo, Madoda

AU - Kourie, Derrick G.

AU - Cleophas, Loek

AU - Watson, Bruce W.

PY - 2015

Y1 - 2015

N2 - The Aho-Corasick algorithm derives a failure deterministic finite automaton for finding matches of a finite set of keywords in a text. It has the minimum number of transitions needed for this task. The DFA-Homomorphic Algorithm (DHA) algorithm is more general, deriving from an arbitrary complete deterministic finite automaton a language-equivalent failure deterministic finite automaton. DHA takes formal concepts of a lattice as input. This lattice is built from a state/outtransition formal context that is derived from the complete deterministic finite automaton. In this paper, three general variants of the abstract DHA are benchmarked against the specialised Aho-Corasick algorithm. It is shown that when heuristics for these variants are suitably chosen, the minimality attained by the Aho-Corasick algorithm can be closely approximated. A published non-lattice-based algorithm is also shown to perform well in experiments.

AB - The Aho-Corasick algorithm derives a failure deterministic finite automaton for finding matches of a finite set of keywords in a text. It has the minimum number of transitions needed for this task. The DFA-Homomorphic Algorithm (DHA) algorithm is more general, deriving from an arbitrary complete deterministic finite automaton a language-equivalent failure deterministic finite automaton. DHA takes formal concepts of a lattice as input. This lattice is built from a state/outtransition formal context that is derived from the complete deterministic finite automaton. In this paper, three general variants of the abstract DHA are benchmarked against the specialised Aho-Corasick algorithm. It is shown that when heuristics for these variants are suitably chosen, the minimality attained by the Aho-Corasick algorithm can be closely approximated. A published non-lattice-based algorithm is also shown to perform well in experiments.

KW - Aho-Corasick algorithm

KW - Failure deterministic finite automaton

UR - http://www.scopus.com/inward/record.url?scp=84950144069&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84950144069

SN - 9782954494807

T3 - CEUR Workshop Proceedings

SP - 87

EP - 98

BT - Proceedings of the Twelfth International Conference on Concept Lattices and Their Applications, October 13-16, 2015, Clermont-Ferrand, France

A2 - Ben Yahia, S.

A2 - Konecny, J.

PB - CEUR-WS.org

T2 - 12th International Conference on Concept Lattices and their Applications (CLA 2015), October 13-16, 2015, Clermont-Ferrand, France

Y2 - 13 October 2015 through 16 October 2015

ER -

Nxumalo M, Kourie DG, Cleophas L, Watson BW. An Aho-Corasick based assessment of algorithms generating failure deterministic finite automata. In Ben Yahia S, Konecny J, editors, Proceedings of the Twelfth International Conference on Concept Lattices and Their Applications, October 13-16, 2015, Clermont-Ferrand, France . CEUR-WS.org. 2015. p. 87-98. (CEUR Workshop Proceedings).

An Aho-Corasick based assessment of algorithms generating failure deterministic finite automata

Abstract

Publication series

Conference

Keywords

Other files and links

Fingerprint

Cite this