Succinct 2D dictionary matching

DOI10.1007/S00453-012-9615-9MaRDI QIDQ2392930zbMATH OpenOpenAlexFDO

Authors Shoshana Neuburger, Dina Sokol

Publication date 5 August 2013

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/s00453-012-9615-9

zbMATH Keywords

two-dimensionaldictionary matchingcompressed self-indexsmall space algorithm

Mathematics Subject Classification ID

Pattern recognition, speech recognition (68T10) Searching and sorting (68P10) Nonnumerical algorithms (68W05)

Recommendations

• Succinct 2D dictionary matching with no slowdown
• Two-dimensional dictionary matching
• Two-dimensional dynamic dictionary matching
• Small-Space 2D Compressed Dictionary Matching
• Succinct Dictionary Matching with No Slowdown
• Fast approximate dictionary matching
• Compressed matching in dictionaries
• An improved query time for succinct dynamic dictionary matching

Cites work

• scientific article; zbMATH DE number 2079421 (Why is no real title available?)
• scientific article; zbMATH DE number 1512678 (Why is no real title available?)
• scientific article; zbMATH DE number 2183071 (Why is no real title available?)
• A Constant Time Optimal Parallel Algorithm for Two-Dimensional Pattern Matching
• A Technique for Extending Rapid Exact-Match String Matching to Arrays of More than One Dimension
• A simple storage scheme for strings achieving entropy bounds
• An Alphabet Independent Approach to Two-Dimensional Pattern Matching
• An O(n log n) algorithm for finding all repetitions in a string
• An analysis of the Burrows-Wheeler transform
• Compressed indexes for dynamic text collections
• Compression of individual sequences via variable-rate coding
• Efficient string matching
• Fast Algorithms for Finding Nearest Common Ancestors
• Fast Pattern Matching in Strings
• Faster entropy-bounded compressed suffix trees
• Fully compressed suffix trees
• Inplace 2D matching in compressed images
• Multiple matching of rectangular patterns
• On-line construction of suffix trees
• Simple Random Access Compression
• Small-Space 2D Compressed Dictionary Matching
• Succinct Dictionary Matching with No Slowdown
• Succinct backward-DAWG-matching
• Two-dimensional dictionary matching
• Two-dimensional pattern matching in linear time and small space
• Wee LCP

Cited in

(13)

• Full sets of pictures to encode pictures
• Succinct Dictionary Matching with No Slowdown
• Indeterminate string factorizations and degenerate text transformations
• A failure function for multiple two-dimensional pattern matching
• Faster compressed dictionary matching
• Small-Space 2D Compressed Dictionary Matching
• scientific article; zbMATH DE number 7559178 (Why is no real title available?)
• Compressed Multiple Pattern Matching
• Succinct 2D dictionary matching with no slowdown
• An improved query time for succinct dynamic dictionary matching
• Dictionary matching in a stream
• Two-dimensional dictionary matching
• 2D Lyndon words and applications

This page was built for publication: Succinct 2D dictionary matching

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