Top

Published in:

2015 | OriginalPaper | Chapter

Faster Lightweight Lempel-Ziv Parsing

Author : Dmitry Kosolobov

Published in: Mathematical Foundations of Computer Science 2015

Publisher: Springer Berlin Heidelberg

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We present an algorithm that computes the Lempel-Ziv decomposition in \(O(n(\log \sigma + \log \log n))\) time and \(n\log \sigma + \epsilon n\) bits of space, where \(\epsilon \) is a constant rational parameter, n is the length of the input string, and \(\sigma \) is the alphabet size. The \(n\log \sigma \) bits in the space bound are for the input string itself which is treated as read-only.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now

previous chapter A Numbers-on-Foreheads Game

next chapter Parallel Identity Testing for Skew Circuits with Big Powers and Applications

Throughout the paper, \(\log \) denotes the logarithm with the base 2.

Belazzougui, D.: Succinct dictionary matching with no slowdown. In: Amir, A., Parida, L. (eds.) CPM 2010. LNCS, vol. 6129, pp. 88–100. Springer, Heidelberg (2010) CrossRef

Beller, T., Gog, S., Ohlebusch, E., Schnattinger, T.: Computing the longest common prefix array based on the Burrows-Wheeler transform. J. Discrete Algorithms 18, 22–31 (2013)MathSciNetCrossRefMATH

Bender, M.A., Cole, R., Demaine, E.D., Farach-Colton, M., Zito, J.: Two simplified algorithms for maintaining order in a list. In: Möhring, R.H., Raman, R. (eds.) ESA 2002. LNCS, vol. 2461, pp. 152–164. Springer, Heidelberg (2002) CrossRef

Blelloch, G.E.: Space-efficient dynamic orthogonal point location, segment intersection, and range reporting. In: SODA 2008. pp. 894–903. SIAM (2008)

Burkhardt, S., Kärkkäinen, J.: Fast lightweight suffix array construction and checking. In: Baeza-Yates, R., Chávez, E., Crochemore, M. (eds.) CPM 2003. LNCS, vol. 2676, pp. 55–69. Springer, Heidelberg (2003) CrossRef

Burrows, M., Wheeler, D.J.: A block-sorting lossless data compression algorithm. Technical report 124 (1994)

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, Heidelberg (2015) CrossRef

Hagerup, T., Miltersen, P.B., Pagh, R.: Deterministic dictionaries. J. Algorithms 41(1), 69–85 (2001)MathSciNetCrossRefMATH

Hon, W.K., Sadakane, K., Sung, W.K.: Breaking a time-and-space barrier in constructing full-text indices. In: FOCS 2003. pp. 251–260. IEEE (2003)

10.

Kärkkäinen, J., Kempa, D., Puglisi, S.J.: Lightweight lempel-ziv parsing. In: Demetrescu, C., Marchetti-Spaccamela, A., Bonifaci, V. (eds.) SEA 2013. LNCS, vol. 7933, pp. 139–150. Springer, Heidelberg (2013) CrossRef

11.

Kopelowitz, T., Lewenstein, M.: Dynamic weighted ancestors. In: SODA 2007. pp. 565–574. SIAM (2007)

12.

Kosolobov, D.: Lempel-Ziv factorization may be harder than computing all runs. In: STACS 2015. LIPICS, vol. 30, pp. 582–593 (2015)

13.

Lempel, A., Ziv, J.: On the complexity of finite sequences. IEEE Trans. Inf. Theor. 22(1), 75–81 (1976)MathSciNetCrossRefMATH

14.

Navarro, G., Sadakane, K.: Fully functional static and dynamic succinct trees. ACM Trans. Algorithms (TALG) 10(3), 16 (2014)MathSciNet

15.

Ohlebusch, E., Gog, S.: Lempel-ziv factorization revisited. In: Giancarlo, R., Manzini, G. (eds.) CPM 2011. LNCS, vol. 6661, pp. 15–26. Springer, Heidelberg (2011) CrossRef

16.

Okanohara, D., Sadakane, K.: An online algorithm for finding the longest previous factors. In: Halperin, D., Mehlhorn, K. (eds.) ESA 2008. LNCS, vol. 5193, pp. 696–707. Springer, Heidelberg (2008) CrossRef

17.

Raman, R., Raman, V., Rao, S.S.: Succinct indexable dictionaries with applications to encoding k-ary trees and multisets. In: SODA 2002. pp. 233–242. SIAM (2002)

18.

Starikovskaya, T.: Computing lempel-ziv factorization online. In: Rovan, B., Sassone, V., Widmayer, P. (eds.) MFCS 2012. LNCS, vol. 7464, pp. 789–799. Springer, Heidelberg (2012) CrossRef

19.

Yamamoto, J., I, T., Bannai, H., Inenaga, S., Takeda, M.: Faster compact on-line Lempel-Ziv factorization. In: STACS 2014. LIPICS, vol. 25, pp. 675–686 (2014)

Title: Faster Lightweight Lempel-Ziv Parsing
Author: Dmitry Kosolobov
Publisher: Springer Berlin Heidelberg
Book: Mathematical Foundations of Computer Science 2015
Print ISBN: 978-3-662-48053-3

Electronic ISBN: 978-3-662-48054-0

Copyright Year: 2015
DOI: https://doi.org/10.1007/978-3-662-48054-0_36

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner