Compressing dictionary matching index via sparsification technique

DOI10.1007/S00453-013-9863-3MaRDI QIDQ2354027zbMATH OpenOpenAlexWikidataFDO

Authors Wing-Kai Hon, Tsung-Han Ku, Rahul Shah, Siu-Lung Tam, Sharma V. Thankachan, Jeffrey Scott Vitter, Tak-Wah Lam

Publication date 10 July 2015

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-013-9863-3

zbMATH Keywords

data compressiontext indexingdictionary matchingsparsification technique

Mathematics Subject Classification ID

Searching and sorting (68P10) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Recommendations

• Compressed matching in dictionaries
• Faster compressed dictionary matching
• Optimal-Time Dictionary-Compressed Indexes
• Compressed Indexes for Approximate String Matching
• Compressed indexes for approximate string matching
• Dynamic dictionary matching and compressed suffix trees
• Indexing methods for approximate dictionary searching, comparative analysis

Cites work

• scientific article; zbMATH DE number 1947389 (Why is no real title available?)
• A Space-Economical Suffix Tree Construction Algorithm
• A simple storage scheme for strings achieving entropy bounds
• Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
• Compressed indexes for dynamic text collections
• Compressed suffix trees with full functionality
• Deterministic dictionaries
• Dictionary matching and indexing with errors and don't cares
• Dynamic dictionary matching
• Efficient data structures for range searching on a grid
• Efficient string matching
• Faster compressed dictionary matching
• Improved dynamic dictionary matching
• Indexing compressed text
• Log-logarithmic worst-case range queries are possible in space theta(N)
• Lowest common ancestors in trees and directed acyclic graphs
• Multi-method dispatching: a geometric approach with applications to string matching problems
• Optimal External Memory Interval Management
• Priority Search Trees
• Space-efficient preprocessing schemes for range minimum queries on static arrays
• Succinct Dictionary Matching with No Slowdown
• Suffix Arrays: A New Method for On-Line String Searches
• Text Indexing and Dictionary Matching with One Error
• The string B-tree

Cited in

(8)

• Compressed automata for dictionary matching
• Dictionary matching with uneven gaps
• Faster compressed dictionary matching
• Indexing a Dictionary for Subset Matching Queries
• scientific article; zbMATH DE number 2080210 (Why is no real title available?)
• A grouping approach for succinct dynamic dictionary matching
• Small-Space 2D Compressed Dictionary Matching
• Dictionary matching with a bounded gap in pattern or in text

This page was built for publication: Compressing dictionary matching index via sparsification technique

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