Compressed automata for dictionary matching

DOI10.1016/J.TCS.2015.01.019MaRDI QIDQ2344744zbMATH OpenOpenAlexFDO

Authors Takaaki Nishimoto, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Tomohiro I

Publication date 18 May 2015

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2015.01.019

zbMATH Keywords

pattern matchingdictionary matchingAho-Corasick automatonstraight-line programMorris-Pratt automaton

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Compressed automata for dictionary matching
• Succinct Dictionary Matching with No Slowdown
• Efficient dictionary matching by Aho-Corasick automata of truncated patterns
• Compressing dictionary matching index via sparsification technique
• Small-Space 2D Compressed Dictionary Matching

Cites work

• scientific article; zbMATH DE number 1045405 (Why is no real title available?)
• scientific article; zbMATH DE number 801745 (Why is no real title available?)
• A universal algorithm for sequential data compression
• Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
• Collage system: A unifying framework for compressed pattern matching.
• Compression of individual sequences via variable-rate coding
• Data compression via textual substitution
• Efficient algorithms for Lempel-Ziv encoding
• Efficient string matching
• Lempel-Ziv-78 compressed string dictionaries
• Random access to grammar-compressed strings
• Succinct Dictionary Matching with No Slowdown

Cited in

(7)

• Finger search in grammar-compressed strings
• Efficient dictionary matching by Aho-Corasick automata of truncated patterns
• Collage system: A unifying framework for compressed pattern matching.
• Unification and matching on compressed terms
• Compressed automata for dictionary matching
• Computer Science Logic
• A RUN-TIME EFFICIENT IMPLEMENTATION OF COMPRESSED PATTERN MATCHING AUTOMATA

This page was built for publication: Compressed automata for dictionary matching

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