Many-MADFAct: concurrently constructing MADFAs

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

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    22 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 languageEnglish
    Title of host publicationProceedings of the Prague Stringology Conference PSC 2017, August 28-30, 2017, Prague, Czech Republic
    EditorsJ. Holub, J. Zdarek
    Place of PublicationPrague
    PublisherCzech Technical University in Prague
    Pages126-142
    Number of pages17
    ISBN (Print)978-80-01-06193-0
    Publication statusPublished - 2017
    EventPrague Stringology Conference 2017 - Prague, Czech Republic
    Duration: 28 Aug 201730 Aug 2017

    Conference

    ConferencePrague Stringology Conference 2017
    Abbreviated titlePSC
    CountryCzech Republic
    CityPrague
    Period28/08/1730/08/17

    Fingerprint Dive into the research topics of 'Many-MADFAct: concurrently constructing MADFAs'. Together they form a unique fingerprint.

    Cite this