Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

LZ78 Substring Compression with CDAWGs

  • Conference paper
  • First Online:
String Processing and Information Retrieval (SPIRE 2024)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 14899))

Included in the following conference series:

  • 163 Accesses

Abstract

The Lempel–Ziv 78 (LZ78) factorization is a well-studied technique for data compression. It and its derivates are used in compression formats such as compress or gif. While most research focuses on the factorization of plain data, not much research has been conducted on indexing the data for fast LZ78 factorization. Here, we study the LZ78 factorization in the substring compression model, where we are allowed to index the data and have to return the factorization of a substring specified at query time. In that model, we propose an algorithm that works in CDAWG-compressed space, computing the factorization with a logarithmic slowdown compared to the optimal time complexity.

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

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 59.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 69.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

References

  1. Arimura, H., Inenaga, S., Kobayashi, Y., Nakashima, Y., Sue, M.: Optimally computing compressed indexing arrays based on the compact directed acyclic word graph. In: Nardini, F.M., Pisanti, N., Venturini, R. (eds.) SPIRE 2023. LNCS, vol. 14240, pp. 28–34. Springer, Heidelberg (2023). https://doi.org/10.1007/978-3-031-43980-3_3

    Chapter  Google Scholar 

  2. Babenko, M.A., Gawrychowski, P., Kociumaka, T., Starikovskaya, T.: Wavelet trees meet suffix trees. In: Proceedings of SODA, pp. 572–591 (2015)

    Google Scholar 

  3. Bannai, H., Gawrychowski, P., Inenaga, S., Takeda, M.: Converting SLP to LZ78 in almost Linear Time. In: Fischer, J., Sanders, P. (eds.) CPM 2013. LNCS, vol. 7922, pp. 38–49. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-38905-4_6

    Chapter  Google Scholar 

  4. Belazzougui, D., Boldi, P., Vigna, S.: Predecessor search with distance-sensitive query time. ArXiv CoRR arxiv:1209.5441 (2012)

  5. Belazzougui, D., Cunial, F.: Representing the suffix tree with the CDAWG. In: Proceedings of CPM, vol. 78 of LIPIcs, pp. 7:1–7:13 (2017)

    Google Scholar 

  6. Belazzougui, D., Cunial, F., Gagie, T., Prezza, N., Raffinot, M.: Composite repetition-aware data structures. In: Cicalese, F., Porat, E., Vaccaro, U. (eds.) CPM 2015. LNCS, vol. 9133, pp. 26–39. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-19929-0_3

    Chapter  Google Scholar 

  7. Belazzougui, D., Kosolobov, D., Puglisi, S.J., Raman, R.: Weighted ancestors in suffix trees revisited. In: Proceedings of CPM, vol. 191 of LIPIcs, pp. 8:1–8:15 (2021)

    Google Scholar 

  8. Bille, P., Landau, G.M., Raman, R., Sadakane, K., Satti, S.R., Weimann, O.: Random access to grammar-compressed strings and trees. SIAM J. Comput. 44(3), 513–539 (2015)

    Article  MathSciNet  Google Scholar 

  9. Blumer, A., Blumer, J., Haussler, D., Ehrenfeucht, A., Chen, M.T., Seiferas, J.I.: The smallest automaton recognizing the subwords of a text. Theor. Comput. Sci. 40, 31–55 (1985)

    Article  MathSciNet  Google Scholar 

  10. Cormode, G., Muthukrishnan,: Substring compression problems. In: Proceedings of SODA, pp. 321–330 (2005)

    Google Scholar 

  11. Crochemore, M., Vérin, R.: Direct construction of compact directed acyclic word graphs. In: Apostolico, A., Hein, J. (eds.) CPM 1997. LNCS, vol. 1264, pp. 116–129. Springer, Heidelberg (1997). https://doi.org/10.1007/3-540-63220-4_55

    Chapter  Google Scholar 

  12. Ehrhardt, M., Mulzer, W.: Delta-fast tries: local searches in bounded universes with linear space. In: WADS 2017. LNCS, vol. 10389, pp. 361–372. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-62127-2_31

    Chapter  Google Scholar 

  13. Ferragina, P., González, R., Navarro, G., Venturini, R.: Compressed text indexes: from theory to practice. ACM J. Exp. Algor. 13, 1.12:1 – 1.12:31 (2008)

    Google Scholar 

  14. Ferragina, P., Grossi, R., Gupta, A., Shah, R., Vitter, J.S.: On searching compressed string collections cache-obliviously. In: Proceedings of PODS, pp. 181–190 (2008)

    Google Scholar 

  15. Fischer, J., Tomohiro, I.,  Köppl, D., Sadakane, K.: Lempel–Ziv factorization powered by space efficient suffix trees. Algorithmica 80(7), 2048–2081 (2018)

    Google Scholar 

  16. Gagie, T., Navarro, G., Prezza, N.: Optimal-time text indexing in BWT-runs bounded space. In: Proceedings of SODA, pp. 1459–1477 (2018)

    Google Scholar 

  17. Gawrychowski, P., Lewenstein, M., Nicholson, P.K.: Weighted ancestors in suffix trees. In: Schulz, A.S., Wagner, D. (eds.) ESA 2014. LNCS, vol. 8737, pp. 455–466. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-44777-2_38

    Chapter  Google Scholar 

  18. Keller, O., Kopelowitz, T., Feibish, S.L., Lewenstein, M.: Generalized substring compression. Theor. Comput. Sci. 525, 42–54 (2014)

    Article  MathSciNet  Google Scholar 

  19. Kempa, D., Kociumaka, T.: Collapsing the hierarchy of compressed data structures: Suffix arrays in optimal compressed space. In: Proceedings of FOCS, pp. 1877–1886 (2023)

    Google Scholar 

  20. Kociumaka, T.: Efficient Data Structures for Internal Queries in Texts. PhD thesis, University of Warsaw (2018)

    Google Scholar 

  21. Köppl, D.: Non-overlapping LZ77 factorization and LZ78 substring compression queries with suffix trees. Algorithms 14(2)(44), 1–21 (2021)

    Google Scholar 

  22. Köppl, D.: Computing LZ78-derivates with suffix trees. In: Proceedings of DCC, pp. 133–142 (2024)

    Google Scholar 

  23. Mäkinen, V., Navarro, G.: Succinct suffix arrays based on run-length encoding. Nord. J. Comput. 12(1), 40–66 (2005)

    MathSciNet  Google Scholar 

  24. Manber, U., Myers, E.W.: Suffix arrays: a new method for on-line string searches. SIAM J. Comput. 22(5), 935–948 (1993)

    Article  MathSciNet  Google Scholar 

  25. Nakashima, Y., Tomohiro, I., Inenaga, S., Bannai, H., Takeda, M.: Constructing LZ78 tries and position heaps in linear time for large alphabets. Inf. Process. Lett. 115(9), 655–659 (2015)

    Google Scholar 

  26. Navarro, G.: Indexing highly repetitive string collections, part I: repetitiveness measures. ACM Comput. Surv. 54(2), 29:1–29:31 (2021)

    Google Scholar 

  27. Nekrich, Y.: A dynamic stabbing-max data structure with sub-logarithmic query time. In: Asano, T., Nakano, S., Okamoto, Y., Watanabe, O. (eds.) ISAAC 2011. LNCS, vol. 7074, pp. 170–179. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25591-5_19

    Chapter  Google Scholar 

  28. Raffinot, M.: On maximal repeats in strings. Inf. Process. Lett. 80(3), 165–169 (2001)

    Article  MathSciNet  Google Scholar 

  29. Rytter, W.: The structure of subword graphs and suffix trees of Fibonacci words. Theor. Comput. Sci. 363(2), 211–223 (2006)

    Article  MathSciNet  Google Scholar 

  30. Sleator, D.D., Tarjan, R.E.: Self-adjusting binary search trees. J. ACM 32(3), 652–686 (1985)

    Article  MathSciNet  Google Scholar 

  31. Storer, J.A., Szymanski, T.G.: The macro model for data compression (extended abstract). In: Proceedings of STOC, pp. 30–39 (1978)

    Google Scholar 

  32. Weiner, P.: Linear pattern matching algorithms. In: Proceedings of SWAT, pp. 1–11 (1973)

    Google Scholar 

  33. Ziv, J., Lempel, A.: Compression of individual sequences via variable-rate coding. IEEE Trans. Inf. Theory 24(5), 530–536 (1978)

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgements

This work was supported by JSPS KAKENHI Grant Number JP23H04378.

Author information

Authors and Affiliations

  1. Department of Informatics, Kyushu University, Fukuoka, Japan

    Hiroki Shibata

  2. University of Yamanashi, Kofu, Japan

    Dominik Köppl

Authors
  1. Hiroki Shibata
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Dominik Köppl
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding authors

Correspondence to Hiroki Shibata or Dominik Köppl .

Editor information

Editors and Affiliations

  1. University of Verona, Verona, Italy

    Zsuzsanna Lipták

  2. Federal University of Amazonas, Manaus, Brazil

    Edleno Moura

  3. Michoacan University of Saint Nicholas of Hidalgo, Morelia, Mexico

    Karina Figueroa

  4. Northeastern University, Boston, MA, USA

    Ricardo Baeza-Yates

Rights and permissions

Reprints and permissions

Copyright information

© 2025 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Shibata, H., Köppl, D. (2025). LZ78 Substring Compression with CDAWGs. In: Lipták, Z., Moura, E., Figueroa, K., Baeza-Yates, R. (eds) String Processing and Information Retrieval. SPIRE 2024. Lecture Notes in Computer Science, vol 14899. Springer, Cham. https://doi.org/10.1007/978-3-031-72200-4_22

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-72200-4_22

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-72199-1

  • Online ISBN: 978-3-031-72200-4

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation