Revisiting the Folklore Algorithm for Random Access to Grammar-Compressed Strings

Alan M. Cleary; Joseph Winjum; Jordan Dood; Shunsuke Inenaga

doi:10.1007/978-3-031-72200-4_7

Revisiting the Folklore Algorithm for Random Access to Grammar-Compressed Strings

Alan M. Cleary, Joseph Winjum, Jordan Dood, Shunsuke Inenaga

Mathematical Informatics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Grammar-based compression is a widely-accepted model of string compression that allows for efficient and direct manipulations on the compressed data. Most, if not all, such manipulations rely on the primitive random access queries, a task of quickly returning the character at a specified position of the original uncompressed string without explicit decompression. While there are advanced data structures for random access to grammar-compressed strings that guarantee theoretical query time and space bounds, little has been done for the practical perspective of this important problem. In this paper, we revisit a well-known folklore random access algorithm for grammars in the Chomsky normal form, modify it to work directly on general grammars, and show that this modified version is fast and memory efficient in practice.

Original language	English
Title of host publication	String Processing and Information Retrieval - 31st International Symposium, SPIRE 2024, Proceedings
Editors	Zsuzsanna Lipták, Edleno Moura, Karina Figueroa, Ricardo Baeza-Yates
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	88-101
Number of pages	14
ISBN (Print)	9783031721991
DOIs	https://doi.org/10.1007/978-3-031-72200-4_7
Publication status	Published - 2025
Event	31st International Symposium on String Processing and Information Retrieval, SPIRE 2024 - Puerto Vallarta, Mexico Duration: Sept 23 2024 → Sept 25 2024

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	14899 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	31st International Symposium on String Processing and Information Retrieval, SPIRE 2024
Country/Territory	Mexico
City	Puerto Vallarta
Period	9/23/24 → 9/25/24

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-031-72200-4_7

Cite this

Cleary, A. M., Winjum, J., Dood, J., & Inenaga, S. (2025). Revisiting the Folklore Algorithm for Random Access to Grammar-Compressed Strings. In Z. Lipták, E. Moura, K. Figueroa, & R. Baeza-Yates (Eds.), String Processing and Information Retrieval - 31st International Symposium, SPIRE 2024, Proceedings (pp. 88-101). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14899 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-031-72200-4_7

Revisiting the Folklore Algorithm for Random Access to Grammar-Compressed Strings. / Cleary, Alan M.; Winjum, Joseph; Dood, Jordan et al.
String Processing and Information Retrieval - 31st International Symposium, SPIRE 2024, Proceedings. ed. / Zsuzsanna Lipták; Edleno Moura; Karina Figueroa; Ricardo Baeza-Yates. Springer Science and Business Media Deutschland GmbH, 2025. p. 88-101 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14899 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Cleary, AM, Winjum, J, Dood, J & Inenaga, S 2025, Revisiting the Folklore Algorithm for Random Access to Grammar-Compressed Strings. in Z Lipták, E Moura, K Figueroa & R Baeza-Yates (eds), String Processing and Information Retrieval - 31st International Symposium, SPIRE 2024, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 14899 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 88-101, 31st International Symposium on String Processing and Information Retrieval, SPIRE 2024, Puerto Vallarta, Mexico, 9/23/24. https://doi.org/10.1007/978-3-031-72200-4_7

Cleary AM, Winjum J, Dood J, Inenaga S. Revisiting the Folklore Algorithm for Random Access to Grammar-Compressed Strings. In Lipták Z, Moura E, Figueroa K, Baeza-Yates R, editors, String Processing and Information Retrieval - 31st International Symposium, SPIRE 2024, Proceedings. Springer Science and Business Media Deutschland GmbH. 2025. p. 88-101. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-72200-4_7

Cleary, Alan M. ; Winjum, Joseph ; Dood, Jordan et al. / Revisiting the Folklore Algorithm for Random Access to Grammar-Compressed Strings. String Processing and Information Retrieval - 31st International Symposium, SPIRE 2024, Proceedings. editor / Zsuzsanna Lipták ; Edleno Moura ; Karina Figueroa ; Ricardo Baeza-Yates. Springer Science and Business Media Deutschland GmbH, 2025. pp. 88-101 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{ebe911417521421c9d0aecf4c875de15,

title = "Revisiting the Folklore Algorithm for Random Access to Grammar-Compressed Strings",

abstract = "Grammar-based compression is a widely-accepted model of string compression that allows for efficient and direct manipulations on the compressed data. Most, if not all, such manipulations rely on the primitive random access queries, a task of quickly returning the character at a specified position of the original uncompressed string without explicit decompression. While there are advanced data structures for random access to grammar-compressed strings that guarantee theoretical query time and space bounds, little has been done for the practical perspective of this important problem. In this paper, we revisit a well-known folklore random access algorithm for grammars in the Chomsky normal form, modify it to work directly on general grammars, and show that this modified version is fast and memory efficient in practice.",

keywords = "grammar-based compression, random access, straight-line programs",

author = "Cleary, {Alan M.} and Joseph Winjum and Jordan Dood and Shunsuke Inenaga",

note = "Publisher Copyright: {\textcopyright} The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.; 31st International Symposium on String Processing and Information Retrieval, SPIRE 2024 ; Conference date: 23-09-2024 Through 25-09-2024",

year = "2025",

doi = "10.1007/978-3-031-72200-4_7",

language = "English",

isbn = "9783031721991",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "88--101",

editor = "Zsuzsanna Lipt{\'a}k and Edleno Moura and Karina Figueroa and Ricardo Baeza-Yates",

booktitle = "String Processing and Information Retrieval - 31st International Symposium, SPIRE 2024, Proceedings",

address = "Germany",

}

TY - GEN

T1 - Revisiting the Folklore Algorithm for Random Access to Grammar-Compressed Strings

AU - Cleary, Alan M.

AU - Winjum, Joseph

AU - Dood, Jordan

AU - Inenaga, Shunsuke

N1 - Publisher Copyright: © The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.

PY - 2025

Y1 - 2025

N2 - Grammar-based compression is a widely-accepted model of string compression that allows for efficient and direct manipulations on the compressed data. Most, if not all, such manipulations rely on the primitive random access queries, a task of quickly returning the character at a specified position of the original uncompressed string without explicit decompression. While there are advanced data structures for random access to grammar-compressed strings that guarantee theoretical query time and space bounds, little has been done for the practical perspective of this important problem. In this paper, we revisit a well-known folklore random access algorithm for grammars in the Chomsky normal form, modify it to work directly on general grammars, and show that this modified version is fast and memory efficient in practice.

AB - Grammar-based compression is a widely-accepted model of string compression that allows for efficient and direct manipulations on the compressed data. Most, if not all, such manipulations rely on the primitive random access queries, a task of quickly returning the character at a specified position of the original uncompressed string without explicit decompression. While there are advanced data structures for random access to grammar-compressed strings that guarantee theoretical query time and space bounds, little has been done for the practical perspective of this important problem. In this paper, we revisit a well-known folklore random access algorithm for grammars in the Chomsky normal form, modify it to work directly on general grammars, and show that this modified version is fast and memory efficient in practice.

KW - grammar-based compression

KW - random access

KW - straight-line programs

UR - http://www.scopus.com/inward/record.url?scp=85205359378&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85205359378&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-72200-4_7

DO - 10.1007/978-3-031-72200-4_7

M3 - Conference contribution

AN - SCOPUS:85205359378

SN - 9783031721991

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 88

EP - 101

BT - String Processing and Information Retrieval - 31st International Symposium, SPIRE 2024, Proceedings

A2 - Lipták, Zsuzsanna

A2 - Moura, Edleno

A2 - Figueroa, Karina

A2 - Baeza-Yates, Ricardo

PB - Springer Science and Business Media Deutschland GmbH

T2 - 31st International Symposium on String Processing and Information Retrieval, SPIRE 2024

Y2 - 23 September 2024 through 25 September 2024

ER -