[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

Jansson et al., 2015 - Google Patents

Linked dynamic tries with applications to LZ-compression in sublinear time and space

Jansson et al., 2015

View PDF
Document ID
3448245861203349907
Author
Jansson J
Sadakane K
Sung W
Publication year
Publication venue
Algorithmica

External Links

Snippet

The dynamic trie is a fundamental data structure with applications in many areas of computer science. This paper proposes a new technique for maintaining a dynamic trie T of size at most 2 w nodes under the unit-cost RAM model with a fixed word size w. It is based …
Continue reading at dflund.se (PDF) (other versions)

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/3061—Information retrieval; Database structures therefor; File system structures therefor of unstructured textual data
    • G06F17/30613—Indexing
    • G06F17/30619—Indexing indexing structures
    • G06F17/30625—Trees
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/30286—Information retrieval; Database structures therefor; File system structures therefor in structured data stores
    • G06F17/30312—Storage and indexing structures; Management thereof
    • G06F17/30321—Indexing structures
    • G06F17/3033—Hash tables
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/30943—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type
    • G06F17/30946—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type indexing structures
    • G06F17/30961—Trees
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/20—Handling natural language data
    • G06F17/21—Text processing
    • G06F17/22—Manipulating or registering by use of codes, e.g. in sequence of text characters
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/3061—Information retrieval; Database structures therefor; File system structures therefor of unstructured textual data
    • G06F17/30634—Querying
    • G06F17/30657—Query processing
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/30286—Information retrieval; Database structures therefor; File system structures therefor in structured data stores
    • G06F17/30386—Retrieval requests
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/30943—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type
    • G06F17/30964—Querying
    • G06F17/30979—Query processing
    • G06F17/30985—Query processing by using string matching techniques
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/30908—Information retrieval; Database structures therefor; File system structures therefor of semistructured data, the undelying structure being taken into account, e.g. mark-up language structure data
    • G06F17/30914—Mapping or conversion
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/30861—Retrieval from the Internet, e.g. browsers

Similar Documents

Publication Publication Date Title
Munro et al. Space-efficient construction of compressed indexes in deterministic linear time
Belazzougui et al. Composite repetition-aware data structures
CN107153647B (en) Method, apparatus, system and computer program product for data compression
Jansson et al. Linked dynamic tries with applications to LZ-compression in sublinear time and space
Beller et al. Computing the longest common prefix array based on the Burrows–Wheeler transform
Nishimoto et al. Optimal-time queries on BWT-runs compressed indexes
Claude et al. Grammar-compressed indexes with logarithmic search time
Barbay et al. Compressed representations of permutations, and applications
Fischer et al. Lempel–Ziv factorization powered by space efficient suffix trees
Vyverman et al. Prospects and limitations of full-text index structures in genome analysis
Barbay et al. Compact binary relation representations with rich functionality
Brisaboa et al. Compressed representation of dynamic binary relations with applications
Navarro Document listing on repetitive collections with guaranteed performance
Takagi et al. Packed compact tries: A fast and efficient data structure for online string processing
Cole et al. Suffix trays and suffix trists: Structures for faster text indexing
Arroyuelo et al. Succinct dynamic cardinal trees
González et al. Rank/select on dynamic compressed sequences and applications
Arz et al. Lempel–Ziv-78 compressed string dictionaries
Bille et al. Compressed subsequence matching and packed tree coloring
Belazzougui et al. Range majorities and minorities in arrays
Akagi et al. Grammar index by induced suffix sorting
Hon et al. Compressed property suffix trees
Gupta et al. A framework for dynamizing succinct data structures
Boffa et al. CoCo-trie: Data-aware compression and indexing of strings
Prezza et al. Faster online computation of the succinct longest previous factor array