An experimental study of a compressed index

DOI10.1016/S0020-0255(01)00098-6MaRDI QIDQ5944434zbMATH OpenOpenAlexWikidataFDO

Authors Paolo Ferragina, Giovanni Manzini

Publication date 10 October 2001

Published in Information Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0020-0255(01)00098-6

zbMATH Keywords

Burrows-Wheeler transformcompressed full-text indexpattern matching on compressed text

Mathematics Subject Classification ID

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

Recommendations

• A compressed text index on secondary memory
• When indexing equals compression, experiments with compressing suffix arrays and applications
• scientific article; zbMATH DE number 6469201
• Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
• Indexing compressed text

Cites work

• A locally adaptive data compression scheme
• Compressed suffix arrays and suffix trees with applications to text indexing and string matching (extended abstract)
• scientific article; zbMATH DE number 1615289 (Why is no real title available?)
• scientific article; zbMATH DE number 1099195 (Why is no real title available?)
• scientific article; zbMATH DE number 2080264 (Why is no real title available?)
• scientific article; zbMATH DE number 756768 (Why is no real title available?)
• scientific article; zbMATH DE number 6472611 (Why is no real title available?)
• Let sleeping files lie: Pattern matching in Z-compressed files.
• String matching in Lempel-Ziv compressed strings
• Suffix Arrays: A New Method for On-Line String Searches

Cited in

(7)

• Resolution cannot polynomially simulate compressed-BFS
• Fast decoding algorithms for variable-lengths codes
• An encoding for order-preserving matching
• Compressed inverted indexes for in-memory search engines
• The Burrows-Wheeler transform of an elastic-degenerate string and its application to pattern matching
• A class of heuristics for reducing the number of BWT-runs in the string ordering problem
• A simple optimal representation for balanced parentheses

Describes a project that uses

Uses Software

• Canterbury
• GLIMPSE

This page was built for publication: An experimental study of a compressed index

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