Faster compressed dictionary matching

DOI10.1016/J.TCS.2012.10.050MaRDI QIDQ1939285zbMATH OpenOpenAlexFDO

Authors Wing-Kai Hon, Tsung-Han Ku, Rahul Shah, Sharma V. Thankachan, Jeffrey Scott Vitter

Publication date 4 March 2013

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

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

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Computing methodologies for text processing; mathematical typography (68U15) Analysis of algorithms (68W40)

Recommendations

• Succinct Dictionary Matching with No Slowdown
• Compressing dictionary matching index via sparsification technique
• Succinct 2D dictionary matching
• Compressed suffix arrays and suffix trees with applications to text indexing and string matching (extended abstract)
• Dynamic dictionary matching and compressed suffix trees

Cited in

(29)

• Dictionary matching with a bounded gap in pattern or in text
• Compressed matching in dictionaries
• Fast approximate matching of words against a dictionary
• Internal dictionary matching
• On the complexity of recognizing Wheeler graphs
• Streaming dictionary matching with mismatches
• Compressing dictionary matching index via sparsification technique
• Compressed text indexing with wildcards
• Dictionary matching with uneven gaps
• Fast circular dictionary-matching algorithm
• The compressed permuterm index
• Space-efficient frameworks for top-k string retrieval
• Searching and indexing circular patterns
• Approximating LZ77 via Small-Space Multiple-Pattern Matching
• Small-Space 2D Compressed Dictionary Matching
• Succinct Dictionary Matching with No Slowdown
• Compressed indexes for text with wildcards
• Fast entropy-bounded string dictionary look-up with mismatches
• Optimal-Time Dictionary-Compressed Indexes
• On the Hardness and Inapproximability of Recognizing Wheeler Graphs
• Compressed Multiple Pattern Matching
• Streaming Dictionary Matching with Mismatches
• A grouping approach for succinct dynamic dictionary matching
• Compressed automata for dictionary matching
• Succinct backward-DAWG-matching
• Sorting circular suffixes in linear time
• Compressed dictionary matching on run-length encoded strings
• Improved circular dictionary matching
• Compressed dictionary matching on run-length encoded strings

This page was built for publication: Faster compressed dictionary matching

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