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
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Greedy Shortest Common Superstring Approximation in Compact Space Kapitel lesen Erstes Kapitel lesen

2017 | OriginalPaper | Buchkapitel

Practical Evaluation of Lempel-Ziv-78 and Lempel-Ziv-Welch Tries

verfasst von : Johannes Fischer, Dominik Köppl

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 thorough practical study of the Lempel-Ziv-78 and the Lempel-Ziv-Welch computation based on trie data structures. With a careful selection of trie representations we can beat well-tuned popular trie data structures like Judy, m-Bonsai or Cedar.

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 Lightweight BWT and LCP Merging via the Gap Algorithm
Nächstes Kapitel Regular Abelian Periods and Longest Common Abelian Factors on Run-Length Encoded Strings
Fußnoten
2
There are artificial texts like \(\mathtt{a}^n\) for which we overestimate the number of factors.
 
5
Popular hash functions like MurmurHash 3 (https://​github.​com/​aappleby/​smhasher) use a post-processing step that applies multiple LCGs \({\mathsf {lcg}}_{a,0,2^{64}}\) with a as a predefined odd constant, and some xorshift-operations.
 
6
https://​github.​com/​lemire/​rollinghashcpp. The function is https://static-content.springer.com/image/chp%3A10.1007%2F978-3-319-67428-5_16/440205_1_En_16_IEq152_HTML.gif , where w is the word size and h is a hash function that maps the alphabet uniformly to the range \([0..2^{32}-1]\).
 
7
The source code of our implementations is freely available at https://​github.​com/​tudocomp, except for cht and bonsai due to copyright restrictions.
 
Literatur
1.
Arroyuelo, D., Navarro, G.: Space-efficient construction of Lempel-Ziv compressed text indexes. Inf. Comput. 209(7), 1070–1102 (2011)MathSciNetCrossRefMATH
2.
Arz, J., Fischer, J.: LZ-compressed string dictionaries. In: Proceedings of the DCC, pp. 322–331. IEEE Press (2014)
3.
Askitis, N.: Fast and compact hash tables for integer keys. In: Proceedings of the ACSC. CRPIT, vol. 91, pp. 101–110. Australian Computer Society (2009)
4.
Bannai, H., Inenaga, S., Takeda, M.: Efficient LZ78 factorization of grammar compressed text. In: Calderón-Benavides, L., González-Caro, C., Chávez, E., Ziviani, N. (eds.) SPIRE 2012. LNCS, vol. 7608, pp. 86–98. Springer, Heidelberg (2012). doi:10.​1007/​978-3-642-34109-0_​10 CrossRef
5.
Belazzougui, D., Puglisi, S.J.: Range predecessor and Lempel-Ziv parsing. In: Proceedings of the SODA, pp. 2053–2071. SIAM (2016)
6.
Bentley, J.L., Sedgewick, R.: Fast algorithms for sorting and searching strings. In: Proceedings of the SODA, pp. 360–369. ACM/SIAM (1997)
7.
Black, J.R., Martel, C.U., Qi, H.: Graph and hashing algorithms for modern architectures: design and performance. In: Proceedings of the WAE, pp. 37–48. Max-Planck-Institut für Informatik (1998)
8.
9.
Chung, K., Mitzenmacher, M., Vadhan, S.P.: Why simple hash functions work: exploiting the entropy in a data stream. Theor. Comput. 9, 897–945 (2013)MathSciNetCrossRefMATH
10.
Cleary, J.G.: Compact hash tables using bidirectional linear probing. IEEE Trans. Comput. 33(9), 828–834 (1984)CrossRefMATH
11.
Dinklage, P., Fischer, J., Köppl, D., Löbel, M., Sadakane, K.: Compression with the tudocomp framework. In: Proceedings of the SEA. LIPIcs, vol. 75, pp. 13:1–13:22 (2017)
12.
Feldman, J.A., Low, J.R.: Comment on Brent’s scatter storage algorithm. Commun. ACM 16(11), 703 (1973)CrossRef
13.
Fischer, J., Gawrychowski, P.: Alphabet-dependent string searching with wexponential search trees. In: Cicalese, F., Porat, E., Vaccaro, U. (eds.) CPM 2015. LNCS, vol. 9133, pp. 160–171. Springer, Cham (2015). doi:10.​1007/​978-3-319-19929-0_​14 CrossRef
14.
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
15.
Gonnet, G.H., Baeza-Yates, R.A.: An analysis of the Karp-Rabin string matching algorithm. Inf. Process. Lett. 34(5), 271–274 (1990)MathSciNetCrossRefMATH
16.
Heileman, G.L., Luo, W.: How caching affects hashing. In: Proceedings of the ALENEX, pp. 141–154. SIAM (2005)
17.
Jansson, J., Sadakane, K., Sung, W.K.: Linked dynamic tries with applications to LZ-compression in sublinear time and space. Algorithmica 71(4), 969–988 (2015)MathSciNetCrossRefMATH
18.
Kärkkäinen, J., Kempa, D., Puglisi, S.J.: Lazy Lempel-Ziv factorization algorithms. ACM J. Exp. Algorithmics 21(1), 2.4:1–2.4:19 (2016)
19.
Kärkkäinen, J., Kempa, D., Puglisi, S.J.: Lightweight Lempel-Ziv parsing. In: Bonifaci, V., Demetrescu, C., Marchetti-Spaccamela, A. (eds.) SEA 2013. LNCS, vol. 7933, pp. 139–150. Springer, Heidelberg (2013). doi:10.​1007/​978-3-642-38527-8_​14 CrossRef
20.
21.
Knuth, D.: Sorting and Searching, the Art of Computer Programming, vol. III. Addison-Wesley, Reading (1973)
22.
Köppl, D., Sadakane, K.: Lempel-Ziv computation in compressed space. In: Proceedings of the DCC, pp. 3–12. IEEE Press (2016)
23.
Lemire, D.: The universality of iterated hashing over variable-length strings. Discrete Appl. Math. 160(4–5), 604–617 (2012)MathSciNetCrossRefMATH
24.
Lemire, D., Kaser, O.: Recursive \(n\)-gram hashing is pairwise independent, at best. Comput. Speech Lang. 24(4), 698–710 (2010)CrossRef
25.
Lemire, D., Kaser, O.: Faster 64-bit universal hashing using carry-less multiplications. J. Cryptographic Eng. 6(3), 171–185 (2016)CrossRef
26.
Luan, H., Du, X., Wang, S., Ni, Y., Chen, Q.: J\(^{+}\)-Tree: a new index structure in main memory. In: Kotagiri, R., Krishna, P.R., Mohania, M., Nantajeewarawat, E. (eds.) DASFAA 2007. LNCS, vol. 4443, pp. 386–397. Springer, Heidelberg (2007). doi:10.​1007/​978-3-540-71703-4_​34 CrossRef
27.
Maier, T., Sanders, P.: Dynamic Space Efficient Hashing. ArXiv CoRR 1705.00997 (2017)
28.
29.
McIlroy, M.D.: A research UNIX reader: annotated excerpts from the programmer’s manual, 1971–1986. Technical report CSTR 139, AT&T Bell Laboratories (1987)
30.
Munro, J.I., Navarro, G., Nekrich, Y.: Space-efficient construction of compressed indexes in deterministic linear time. In: Proceedings of the SODA, pp. 408–424. SIAM (2017)
31.
Nakashima, Y.: I, T., Inenaga, S., Bannai, H., Takeda, M.: Constructing LZ78 tries and position heaps in linear time for large alphabets. Inform. Process. Lett. 115(9), 655–659 (2015)MathSciNetCrossRef
32.
Navarro, G.: Implementing the LZ-index: theory versus practice. ACM J. Exp. Algorithmics 13(2), 2:1.1–2:1.49 (2008)
33.
Poyias, A., Puglisi, S.J., Raman, R.: Compact dynamic rewritable (CDRW) arrays. In: Proceedings of the ALENEX, pp. 109–119. SIAM (2017)
34.
35.
36.
Steele Jr., G.L., Lea, D., Flood, C.H.: Fast splittable pseudorandom number generators. In: Proc. OOPSLA. pp. 453–472. ACM (2014)
37.
Tchebychev, P.: Mémoire sur les nombres premiers. J. de mathématiques pures et appliquées 1, 366–390 (1852)
38.
Welch, T.A.: A technique for high-performance data compression. IEEE Computer 17(6), 8–19 (1984)CrossRef
39.
Yoshinaga, N., Kitsuregawa, M.: A self-adaptive classifier for efficient text-stream processing. In: Proceedings of the COLING, pp. 1091–1102. ACL (2014)
40.
Ziv, J., Lempel, A.: A universal algorithm for sequential data compression. IEEE Trans. Inform. Theory 23(3), 337–343 (1977)MathSciNetCrossRefMATH
41.
Ziv, J., Lempel, A.: Compression of individual sequences via variable length coding. IEEE Trans. Inform. Theory 24(5), 530–536 (1978)MathSciNetCrossRefMATH
42.
Zobrist, A.L.: A new hashing method with application for game playing. Technical report 88, Computer Sciences Department, University of Wisconsin (1970)
Metadaten
Titel
Practical Evaluation of Lempel-Ziv-78 and Lempel-Ziv-Welch Tries
verfasst von
Johannes Fischer
Dominik Köppl
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_16

Neuer Inhalt

    Bildnachweise