Skip to main content
SpringerLink
Log in
Book cover

Compressed Data Structures for Strings

On Searching and Extracting Strings from Compressed Textual Data

  • Book
  • © 2014

Overview

Authors:
  1. Rossano Venturini

    1. Department of Computer Science, University of Pisa, Pisa, Italy

    View author publications

    You can also search for this author in PubMed   Google Scholar

  • Presents new results to improve data compression by solving optimization problems
  • Presents efficient solutions to pattern matching problems in compressed space
  • Nice balance of theoretical achievements and algorithm-engineering results for compressed data structures
  • Includes supplementary material: sn.pub/extras

Part of the book series: Atlantis Studies in Computing (ATLANTISCOMP, volume 4)

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution
eBook USD 39.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Hardcover Book USD 54.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (8 chapters)

  1. Front Matter

    Pages i-xiv
    Download chapter PDF

  2. Introduction

    • Rossano Venturini
    Pages 1-4

  3. Basic Concepts

    • Rossano Venturini
    Pages 5-14

  4. Optimally Partitioning a Text to Improve Its Compression

    • Rossano Venturini
    Pages 15-31

  5. Bit-Complexity of Lempel-Ziv Compression

    • Rossano Venturini
    Pages 33-54

  6. Fast Random Access on Compressed Data

    • Rossano Venturini
    Pages 55-60

  7. Experiments on Compressed Full-Text Indexing

    • Rossano Venturini
    Pages 61-88

  8. Dictionary Indexes

    • Rossano Venturini
    Pages 89-106

  9. Future Directions of Research

    • Rossano Venturini
    Pages 107-110

  10. Back Matter

    Pages 111-118
    Download chapter PDF
Back to top

Keywords

About this book

Data compression is mandatory to manage massive datasets, indexing is fundamental to query them. However, their goals appear as counterposed: the former aims at minimizing data redundancies, whereas the latter augments the dataset with auxiliary information to speed up the query resolution. In this monograph we introduce solutions that overcome this dichotomy. We start by presenting the use of optimization techniques to improve the compression of classical data compression algorithms, then we move to the design of compressed data structures providing fast random access or efficient pattern matching queries on the compressed dataset. These theoretical studies are supported by experimental evidences of their impact in practical scenarios.

Authors and Affiliations

  • Department of Computer Science, University of Pisa, Pisa, Italy

    Rossano Venturini

Bibliographic Information

  • Book Title: Compressed Data Structures for Strings

  • Book Subtitle: On Searching and Extracting Strings from Compressed Textual Data

  • Authors: Rossano Venturini

  • Series Title: Atlantis Studies in Computing

  • DOI: https://doi.org/10.2991/978-94-6239-033-1

  • Publisher: Atlantis Press Paris

  • eBook Packages: Mathematics and Statistics, Mathematics and Statistics (R0)

  • Copyright Information: Atlantis Press and the authors 2014

  • Hardcover ISBN: 978-94-6239-032-4Published: 18 November 2013

  • eBook ISBN: 978-94-6239-033-1Published: 31 October 2013

  • Series ISSN: 2212-8557

  • Series E-ISSN: 2212-8565

  • Edition Number: 1

  • Number of Pages: XIV, 118

  • Number of Illustrations: 18 b/w illustrations

  • Topics: Arithmetic and Logic Structures

Publish with us

Policies and ethics

Societies and partnerships

Back to top

Search

Navigation