Many-MADFAct: concurrently constructing MADFAs

T. Runge; I. Schaefer; L.G.W.A. Cleophas; B.W. Watson

Many-MADFAct: concurrently constructing MADFAs

T. Runge, I. Schaefer, L.G.W.A. Cleophas, B.W. Watson

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

1 Citation (Scopus)

25 Downloads (Pure)

Abstract

Minimal acyclic deterministic finite automata (MADFAs) are used to represent dictionaries, i.e., finite sets of finite words, in, e.g., spell checkers and network security applications. Given the size of such dictionaries, which may contain millions of words, their efficient construction is a critical issue. Watson (2010) published a classification of such algorithms in an algorithm taxonomy with correctness arguments. We report on a new algorithm which constructs MADFAs in parallel---each for a keyword set from a partition of the original keyword set---and afterwards merges and minimizes the resulting automata into a single MADFA; on our experience implementing the algorithms in a Java-based toolkit; and on empirical performance results obtained.

Original language	English
Title of host publication	Proceedings of the Prague Stringology Conference PSC 2017, August 28-30, 2017, Prague, Czech Republic
Editors	J. Holub, J. Zdarek
Place of Publication	Prague
Publisher	Czech Technical University in Prague
Pages	126-142
Number of pages	17
ISBN (Print)	978-80-01-06193-0
Publication status	Published - 2017
Event	Prague Stringology Conference 2017 - Prague, Czech Republic Duration: 28 Aug 2017 → 30 Aug 2017

Conference

Conference	Prague Stringology Conference 2017
Abbreviated title	PSC
Country/Territory	Czech Republic
City	Prague
Period	28/08/17 → 30/08/17

Access to Document

author versionFinal author version , 317 KB

http://www.stringology.org/event/2017/p13.html

Cite this

@inproceedings{44b3c3a11e4543ccbfd42d3ea30caf08,

title = "Many-MADFAct: concurrently constructing MADFAs",

abstract = "Minimal acyclic deterministic finite automata (MADFAs) are used to represent dictionaries, i.e., finite sets of finite words, in, e.g., spell checkers and network security applications. Given the size of such dictionaries, which may contain millions of words, their efficient construction is a critical issue. Watson (2010) published a classification of such algorithms in an algorithm taxonomy with correctness arguments. We report on a new algorithm which constructs MADFAs in parallel---each for a keyword set from a partition of the original keyword set---and afterwards merges and minimizes the resulting automata into a single MADFA; on our experience implementing the algorithms in a Java-based toolkit; and on empirical performance results obtained.",

author = "T. Runge and I. Schaefer and L.G.W.A. Cleophas and B.W. Watson",

year = "2017",

language = "English",

isbn = "978-80-01-06193-0",

pages = "126--142",

editor = "J. Holub and J. Zdarek",

booktitle = "Proceedings of the Prague Stringology Conference PSC 2017, August 28-30, 2017, Prague, Czech Republic",

publisher = "Czech Technical University in Prague",

address = "Czech Republic",

note = "Prague Stringology Conference 2017, PSC ; Conference date: 28-08-2017 Through 30-08-2017",

}

Runge, T, Schaefer, I, Cleophas, LGWA & Watson, BW 2017, Many-MADFAct: concurrently constructing MADFAs. in J Holub & J Zdarek (eds), Proceedings of the Prague Stringology Conference PSC 2017, August 28-30, 2017, Prague, Czech Republic . Czech Technical University in Prague, Prague, pp. 126-142, Prague Stringology Conference 2017, Prague, Czech Republic, 28/08/17. <http://www.stringology.org/event/2017/p13.html>

Many-MADFAct : concurrently constructing MADFAs. / Runge, T.; Schaefer, I.; Cleophas, L.G.W.A.; Watson, B.W.

Proceedings of the Prague Stringology Conference PSC 2017, August 28-30, 2017, Prague, Czech Republic . ed. / J. Holub; J. Zdarek. Prague : Czech Technical University in Prague, 2017. p. 126-142.

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

TY - GEN

T1 - Many-MADFAct

T2 - Prague Stringology Conference 2017

AU - Runge, T.

AU - Schaefer, I.

AU - Cleophas, L.G.W.A.

AU - Watson, B.W.

PY - 2017

Y1 - 2017

N2 - Minimal acyclic deterministic finite automata (MADFAs) are used to represent dictionaries, i.e., finite sets of finite words, in, e.g., spell checkers and network security applications. Given the size of such dictionaries, which may contain millions of words, their efficient construction is a critical issue. Watson (2010) published a classification of such algorithms in an algorithm taxonomy with correctness arguments. We report on a new algorithm which constructs MADFAs in parallel---each for a keyword set from a partition of the original keyword set---and afterwards merges and minimizes the resulting automata into a single MADFA; on our experience implementing the algorithms in a Java-based toolkit; and on empirical performance results obtained.

AB - Minimal acyclic deterministic finite automata (MADFAs) are used to represent dictionaries, i.e., finite sets of finite words, in, e.g., spell checkers and network security applications. Given the size of such dictionaries, which may contain millions of words, their efficient construction is a critical issue. Watson (2010) published a classification of such algorithms in an algorithm taxonomy with correctness arguments. We report on a new algorithm which constructs MADFAs in parallel---each for a keyword set from a partition of the original keyword set---and afterwards merges and minimizes the resulting automata into a single MADFA; on our experience implementing the algorithms in a Java-based toolkit; and on empirical performance results obtained.

M3 - Conference contribution

SN - 978-80-01-06193-0

SP - 126

EP - 142

BT - Proceedings of the Prague Stringology Conference PSC 2017, August 28-30, 2017, Prague, Czech Republic

A2 - Holub, J.

A2 - Zdarek, J.

PB - Czech Technical University in Prague

CY - Prague

Y2 - 28 August 2017 through 30 August 2017

ER -

Many-MADFAct: concurrently constructing MADFAs

Abstract

Conference

Access to Document

Fingerprint

Cite this