Constructing Efficient Dictionaries in Close to Sorting Time

DOI10.1007/978-3-540-70575-8_8MaRDI QIDQ3521910zbMATH OpenOpenAlexFDO

Authors Milan Ružić

Publication date 28 August 2008

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-70575-8_8

Mathematics Subject Classification ID

Data structures (68P05) Searching and sorting (68P10) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Algorithms – ESA 2004
• scientific article; zbMATH DE number 1305431
• scientific article; zbMATH DE number 1445338
• A trade-off for worst-case efficient dictionaries
• scientific article; zbMATH DE number 2089203
• Fast approximate search in large dictionaries
• Bounded ordered dictionaries in O(log log N) time and O(n) space
• Optimal-Time Dictionary-Compressed Indexes
• Low redundancy in static dictionaries with constant query time
• An Efficient Trie Construction for Natural Language Dictionaries

Cited in

(36)

• Universal compressed text indexing
• New space/time tradeoffs for top-\(k\) document retrieval on sequences
• Construct a perfect word hash function in time independent of the size of integers
• Dynamic construction of an antidictionary with linear complexity
• The parameterized suffix tray
• Optimal encodings for range majority queries
• Alphabet-dependent string searching with wexponential search trees
• Time-optimal top-k document retrieval
• Dispersing Hash functions
• Dictionary matching in a stream
• Approximating LZ77 via Small-Space Multiple-Pattern Matching
• On the Complexity of a Game Related to the Dictionary Problem
• Motif matching using gapped patterns
• scientific article; zbMATH DE number 176153 (Why is no real title available?)
• A distribution-sensitive dictionary with low space overhead
• scientific article; zbMATH DE number 1305431 (Why is no real title available?)
• \(k\)-abelian pattern matching
• scientific article; zbMATH DE number 1445339 (Why is no real title available?)
• Computing runs on a trie
• Longest unbordered factor in quasilinear time
• Even faster elastic-degenerate string matching via fast matrix multiplication
• Real-Time Streaming Multi-Pattern Search for Constant Alphabet
• Using hashing to solve the dictionary problem
• Elastic-Degenerate String Matching via Fast Matrix Multiplication
• Circular pattern matching with \(k\) mismatches
• Elastic-degenerate string matching with 1 error
• Internal pattern matching queries in a text and applications
• Elastic-degenerate string matching with 1 error or mismatch
• Internal quasiperiod queries
• Internal pattern matching in small space and applications
• Maintaining the size of LZ77 on semi-dynamic strings
• Optimal-time queries on BWT-runs compressed indexes
• Compressed dictionary matching on run-length encoded strings
• Sorted consecutive occurrence queries in substrings
• Faster approximate elastic-degenerate string matching. Part A
• Faster approximate elastic-degenerate string matching. Part B

This page was built for publication: Constructing Efficient Dictionaries in Close to Sorting Time

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