Regular expression searching on compressed text

Ganty, Pierre and Valero Mejía, Pedro (2019). Regular expression searching on compressed text. In: "Data Compression Conference (DCC 2019)", 26-29 Mar 2019, Snowbird, USA. ISBN 978-1-7281-0657-1. pp. 528-737. https://doi.org/10.1109/DCC.2019.00061.

Description

Title: Regular expression searching on compressed text
Author/s:
  • Ganty, Pierre
  • Valero Mejía, Pedro
Item Type: Presentation at Congress or Conference (Article)
Event Title: Data Compression Conference (DCC 2019)
Event Dates: 26-29 Mar 2019
Event Location: Snowbird, USA
Title of Book: 2019 Data Compression Conference (DCC)
Date: 2019
ISBN: 978-1-7281-0657-1
Subjects:
Faculty: E.T.S. de Ingenieros Informáticos (UPM)
Department: Otro
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[img]
Preview
PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (830kB) | Preview

Abstract

We present an algorithm for searching regular expression matches in compressed text. The algorithm reports the number of matching lines in the uncompressed text in time linear in the size of its compressed version. We define efficient data structures that yield nearly optimal complexity bounds and provide a sequential implementation --zearch-- that requires up to 25% less time than the state of the art.

More information

Item ID: 57609
DC Identifier: http://oa.upm.es/57609/
OAI Identifier: oai:oa.upm.es:57609
DOI: 10.1109/DCC.2019.00061
Official URL: https://ieeexplore.ieee.org/document/8712660
Deposited by: Memoria Investigacion
Deposited on: 18 Feb 2020 07:58
Last Modified: 18 Feb 2020 07:58
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM