On the bit-parallel simulation of the nondeterministic Aho-Corasick and suffix automata for a set of patterns

DOI10.1016/J.JDA.2011.02.001MaRDI QIDQ414441zbMATHOpenAlexFDO

Authors Domenico Cantone, Simone Faro, Emanuele Giaquinta

Publication date 11 May 2012

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jda.2011.02.001

zbMATH Keywords

automatatext processingmultiple pattern matchingbit-parallelism

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Combinatorics on words (68R15) Algorithms on strings (68W32)

Recommendations

• A compact representation of nondeterministic (suffix) automata for the bit-parallel approach
• A compact representation of nondeterministic (suffix) automata for the bit-parallel approach
• A SPACE EFFICIENT BIT-PARALLEL ALGORITHM FOR THE MULTIPLE STRING MATCHING PROBLEM
• Run-Length Encoded Nondeterministic KMP and Suffix Automata
• scientific article; zbMATH DE number 1949653

Cites work

• scientific article; zbMATH DE number 1517989 (Why is no real title available?)
• scientific article; zbMATH DE number 1754502 (Why is no real title available?)
• scientific article; zbMATH DE number 801745 (Why is no real title available?)
• A SPACE EFFICIENT BIT-PARALLEL ALGORITHM FOR THE MULTIPLE STRING MATCHING PROBLEM
• Average complexity of exact and approximate multiple string matching
• Average sizes of suffix trees and DAWGs
• Complete inverted files for efficient text retrieval and analysis
• Efficient string matching
• Fast Pattern Matching in Strings
• Fast and flexible string matching by combining bit-parallelism and suffix automata
• Matters computational. Ideas, algorithms, source code.
• New techniques for regular expression searching

Cited in

(8)

• A Table Compression Method for Extended Aho-Corasick Automaton
• Combinatorial Pattern Matching
• A SPACE EFFICIENT BIT-PARALLEL ALGORITHM FOR THE MULTIPLE STRING MATCHING PROBLEM
• A compact representation of nondeterministic (suffix) automata for the bit-parallel approach
• A compact representation of nondeterministic (suffix) automata for the bit-parallel approach
• Construction of Aho Corasick automaton in linear time for integer alphabets
• A New Approach to Determinisation Using Bit-Parallelism
• scientific article; zbMATH DE number 1949653 (Why is no real title available?)

Describes a project that uses

Uses Software

• FXT
• hfloat

This page was built for publication: On the bit-parallel simulation of the nondeterministic Aho-Corasick and suffix automata for a set of patterns

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q414441)