[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/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/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/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
Beller et al. Computing the longest common prefix array based on the Burrows–Wheeler transform
Jansson et al. Linked dynamic tries with applications to LZ-compression in sublinear time and space
Nishimoto et al. Optimal-time queries on BWT-runs compressed indexes
Fischer et al. Lempel–Ziv factorization powered by space efficient suffix trees
Belazzougui et al. Representing the suffix tree with the CDAWG
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
Díaz-Domínguez et al. An LMS-based grammar self-index with local consistency properties
Chien et al. Geometric BWT: compressed text indexing via sparse suffixes and range searching
Gao Computing matching statistics on repetitive texts
González et al. Rank/select on dynamic compressed sequences and applications
Arroyuelo et al. Succinct dynamic cardinal trees
He et al. A framework for succinct labeled ordinal trees over large alphabets
Arz et al. Lempel–Ziv-78 compressed string dictionaries
Kanda et al. Dynamic path-decomposed tries
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
Bille et al. Top tree compression of tries
Gupta et al. A framework for dynamizing succinct data structures
Aluru Suffix trees and suffix arrays
Prezza et al. Faster online computation of the succinct longest previous factor array