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

Giancarlo et al., 2023 - Google Patents

A new class of string transformations for compressed text indexing

Giancarlo et al., 2023

View HTML
Document ID
10931969751870574629
Author
Giancarlo R
Manzini G
Restivo A
Rosone G
Sciortino M
Publication year
Publication venue
Information and Computation

External Links

Snippet

Introduced about thirty years ago in the field of data compression, the Burrows-Wheeler Transform (BWT) is a string transformation that, besides being a booster of the performance of memoryless compressors, plays a fundamental role in the design of efficient self-indexing …
Continue reading at www.sciencedirect.com (HTML) (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/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/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
    • 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/30923—XML native databases, structures and querying
    • G06F17/30929—Query processing
    • G06F17/30938—Query execution
    • 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
    • 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
    • G06F17/30389—Query formulation
    • 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
    • G06F17/30424—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/30312—Storage and indexing structures; Management thereof
    • G06F17/30321—Indexing structures
    • 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
    • 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

Similar Documents

Publication Publication Date Title
US8156156B2 (en) Method of structuring and compressing labeled trees of arbitrary degree and shape
Wang et al. Discovering structural association of semistructured data
Navarro Wavelet trees for all
Ferragina et al. Structuring labeled trees for optimal succinctness, and beyond
Policriti et al. LZ77 computation based on the run-length encoded BWT
Beller et al. Computing the longest common prefix array based on the Burrows–Wheeler transform
Alanko et al. Wheeler languages
Charalampopoulos et al. Internal dictionary matching
Kärkkäinen et al. Tighter bounds for the sum of irreducible LCP values
Giancarlo et al. A new class of string transformations for compressed text indexing
Sadakane et al. Indexing huge genome sequences for solving various problems
Jansson et al. Linked dynamic tries with applications to LZ-compression in sublinear time and space
Gao Computing matching statistics on repetitive texts
Farruggia et al. Relative suffix trees
Park et al. Finding patterns and periods in cartesian tree matching
Hsu et al. CIS-X: A compacted indexing scheme for efficient query evaluation of XML documents
Fischer et al. Simple, fast and lightweight parallel wavelet tree construction
Grabowski et al. Sampled suffix array with minimizers
Daykin et al. A bijective variant of the Burrows–Wheeler Transform using V-order
Manzini XBWT tricks
Bille et al. Compressed subsequence matching and packed tree coloring
Giancarlo et al. A new class of searchable and provably highly compressible string transformations
Hon et al. Compressed index for dictionary matching
Giancarlo et al. The Alternating BWT: an algorithmic perspective
Ganguly et al. Succinct non-overlapping indexing