Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Greedy Shortest Common Superstring Approximation in Compact Space Kapitel lesen Erstes Kapitel lesen

2017 | OriginalPaper | Buchkapitel

LZ78 Compression in Low Main Memory Space

verfasst von : Diego Arroyuelo, Rodrigo Cánovas, Gonzalo Navarro, Rajeev Raman

Erschienen in: String Processing and Information Retrieval

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

We present the first algorithms that perform the LZ78 compression of a text of length n over alphabet \([1..\sigma ]\), whose output is z integers, using only \(O(z\lg \sigma )\) bits of main memory. The algorithms read the input text from disk in a single pass, and write the compressed output to disk. The text can also be decompressed within the same main memory usage, which is unprecedented too. The algorithms are based on hashing and, under some simplifying assumptions, run in O(n) expected time. We experimentally verify that our algorithms use 2–9 times less time and/or space than previously implemented LZ78 compressors.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel Distinct Squares in Circular Words
Nächstes Kapitel On Two LZ78-style Grammars: Compression Bounds and Compressed-Space Computation
Fußnoten
Literatur
1.
2.
Arroyuelo, D., Navarro, G.: Space-efficient construction of Lempel-Ziv compressed text indexes. Inf. Comput. 209(7), 1070–1102 (2011)MathSciNetCrossRefMATH
3.
Arroyuelo, D., Navarro, G., Sadakane, K.: Stronger Lempel-Ziv based compressed text indexing. Algorithmica 62(1), 54–101 (2012)MathSciNetCrossRefMATH
4.
Clark, D.R.: Compact PAT trees. Ph.D. thesis, University of Waterloo, Canada (1996)
5.
Ferrada, H., Navarro, G.: A Lempel-Ziv compressed structure for document listing. In: Kurland, O., Lewenstein, M., Porat, E. (eds.) SPIRE 2013. LNCS, vol. 8214, pp. 116–128. Springer, Cham (2013). doi:10.​1007/​978-3-319-02432-5_​16 CrossRef
6.
Ferrada, H., Navarro, G.: Efficient compressed indexing for approximate top-k string retrieval. In: Moura, E., Crochemore, M. (eds.) SPIRE 2014. LNCS, vol. 8799, pp. 18–30. Springer, Cham (2014). doi:10.​1007/​978-3-319-11918-2_​3
7.
8.
Fischer, J., I, T., Köppl, D.: Lempel Ziv Computation in Small Space (LZ-CISS). In: Cicalese, F., Porat, E., Vaccaro, U. (eds.) CPM 2015. LNCS, vol. 9133, pp. 172–184. Springer, Cham (2015). doi:10.​1007/​978-3-319-19929-0_​15 CrossRef
9.
Hardy, G.H., Wright, E.M.: An Introduction to the Theory of Numbers, 6th edn. Oxford University Press, Oxford (2008)MATH
10.
Jansson, J., Sadakane, K., Sung, W.: Linked dynamic tries with applications to LZ-compression in sublinear time and space. Algorithmica 71(4), 969–988 (2015)MathSciNetCrossRefMATH
11.
Köppl, D., Sadakane, K.: Lempel-Ziv Computation in Compressed Space (LZ-CICS). In: Proceedings of 26th Data Compression Conference, pp. 3–12 (2016)
12.
13.
Patrascu, M., Thorup, M.: On the k-independence required by linear probing and minwise independence. ACM Trans. Algorithms 12(1) (2016). Article 8
14.
15.
Russo, L.M.S., Oliveira, A.L.: A compressed self-index using a Ziv-Lempel dictionary. Inf. Retrieval 11(4), 359–388 (2008)CrossRef
16.
Sadakane, K., Grossi, R.: Squeezing succinct data structures into entropy bounds. In: Proceedings of 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1230–1239 (2006)
17.
Welch, T.A.: A technique for high performance data compression. IEEE Comput. 17(6), 8–19 (1984)CrossRef
18.
19.
Ziv, J., Lempel, A.: Compression of individual sequences via variable length coding. IEEE Trans. Inf. Theory 24(5), 530–536 (1978)CrossRefMATH
Metadaten
Titel
LZ78 Compression in Low Main Memory Space
verfasst von
Diego Arroyuelo
Rodrigo Cánovas
Gonzalo Navarro
Rajeev Raman
Copyright-Jahr
2017
Buch
String Processing and Information Retrieval

Print ISBN: 978-3-319-67427-8

Electronic ISBN: 978-3-319-67428-5

Copyright-Jahr: 2017

DOI
https://doi.org/10.1007/978-3-319-67428-5_4