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:
Speeding Up Cover Time of Sparse Graphs Using Local Knowledge Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

Computing the BWT and the LCP Array in Constant Space

verfasst von : Felipe A. Louza, Guilherme P. Telles

Erschienen in: Combinatorial Algorithms

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

We show how to modify the in-place Burrows-Wheeler transform (\(\mathsf {BWT}\)) algorithm proposed by Crochemore et al. [4, 5] to also compute the longest common prefix (\(\mathsf {LCP}\)) array. Our algorithm runs in quadratic time, as its predecessor, constructing both the BWT and the LCP array using just O(1) additional space. It is supported by interesting properties of the \(\mathsf {BWT}\) and of the \(\mathsf {LCP}\) array and inherits its predecessor simplicity.

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 1.5-Approximation Algorithm for the 2-Convex Recoloring Problem
Nächstes Kapitel EERTREE: An Efficient Data Structure for Processing Palindromes in Strings
Anhänge
Nur mit Berechtigung zugänglich
Literatur
1.
Adjeroh, D., Bell, T., Mukherjee, A.: The Burrows-Wheeler transform: data compression, suffix arrays, and pattern matching. Springer, Boston (2008)CrossRef
2.
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)CrossRefMathSciNetMATH
3.
Burrows, M., Wheeler, D.: A block-sorting lossless data compression algorithm. Technical report, Digital SRC Research Report (1994)
4.
Crochemore, M., Grossi, R., Kärkkäinen, J., Landau, G.M.: A constant-space comparison-based algorithm for computing the Burrows–Wheeler transform. In: Fischer, J., Sanders, P. (eds.) CPM 2013. LNCS, vol. 7922, pp. 74–82. Springer, Heidelberg (2013)CrossRef
5.
Crochemore, M., Grossi, R., Kärkkäinen, J., Landau, G.M.: Computing the Burrows-Wheeler transform in place and in small space. J. Discrete Algorithms 32, 44–52 (2015). stringMasters 2012 and 2013 Special Issue (Volume 2)CrossRefMathSciNet
6.
Dhaliwal, J., Puglisi, S.J., Turpin., A.: Trends in suffix sorting : a survey of low memory algorithms. In: Reynolds, M., Thomas, B.H. (eds.) Proceedings of Australasian Computer Science Conference (ACSC), CRPIT, vol. 122, pp. 91–98. Australian Computer Society, Melbourne, Australia (2012)
7.
Fischer, J.: Inducing the LCP-array. In: Dehne, F., Iacono, J., Sack, J.-R. (eds.) WADS 2011. LNCS, vol. 6844, pp. 374–385. Springer, Heidelberg (2011)CrossRef
8.
Franceschini, G., Muthukrishnan, S.M.: In-place suffix sorting. In: Arge, L., Cachin, C., Jurdziński, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol. 4596, pp. 533–545. Springer, Heidelberg (2007)CrossRef
9.
Gonnet, G.H., Baeza-yates, R., Snider, T.: New Indices for Text: PAT Trees and PAT Arrays. Prentice-Hall Inc., Upper Saddle River (1992)
10.
Gusfield, D.: Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press, New York (1997)CrossRefMATH
11.
Kärkkäinen, J., Manzini, G., Puglisi, S.J.: Permuted longest-common-prefix array. In: Kucherov, G., Ukkonen, E. (eds.) CPM 2009 Lille. LNCS, vol. 5577, pp. 181–192. Springer, Heidelberg (2009)CrossRef
12.
Kärkkäinen, J., Sanders, P., Burkhardt, S.: Linear work suffix array construction. ACM J. 53(6), 918–936 (2006)CrossRef
13.
Kasai, T., Lee, G.H., Arimura, H., Arikawa, S., Park, K.: Linear-time longest-common-prefix computation in suffix arrays and its applications. In: Amir, A., Landau, G.M. (eds.) CPM 2001. LNCS, vol. 2089, p. 181. Springer, Heidelberg (2001)CrossRef
14.
Kim, D.K., Sim, J.S., Park, H., Park, K.: Constructing suffix arrays in linear time. J. Discret. Algorithms 3(2–4), 126–142 (2005)CrossRefMathSciNetMATH
15.
Ko, P., Aluru, S.: Space efficient linear time construction of suffix arrays. J. Discret. Algorithms 3(2–4), 143–156 (2005)CrossRefMathSciNetMATH
16.
17.
Manzini, G.: Two space saving tricks for linear time LCP array computation. In: Hagerup, T., Katajainen, J. (eds.) SWAT 2004. LNCS, vol. 3111, pp. 372–383. Springer, Heidelberg (2004)CrossRef
18.
Nong, G.: Practical linear-time O(1)-workspace suffix sorting for constant alphabets. ACM Trans. Inform. Syst. 31(3), 1–15 (2013)CrossRef
19.
Nong, G., Zhang, S., Chan, W.H.: Two efficient algorithms for linear time suffix array construction. IEEE Trans. Comput. 60(10), 1471–1484 (2011)CrossRefMathSciNet
20.
Ohlebusch, E.: Bioinformatics Algorithms: Sequence Analysis, Genome Rearrangements, and Phylogenetic Reconstruction. Oldenbusch Verlag, Bremen (2013)
21.
Ohlebusch, E., Gog, S., Kügel, A.: Computing matching statistics and maximal exact matches on compressed full-text indexes. In: Chavez, E., Lonardi, S. (eds.) SPIRE 2010. LNCS, vol. 6393, pp. 347–358. Springer, Heidelberg (2010)CrossRef
22.
Okanohara, D., Sadakane, K.: A linear-time Burrows-Wheeler transform using induced sorting. In: Karlgren, J., Tarhio, J., Hyyrö, H. (eds.) SPIRE 2009. LNCS, vol. 5721, pp. 90–101. Springer, Heidelberg (2009)CrossRef
23.
Puglisi, S.J., Smyth, W.F., Turpin, A.H.: A taxonomy of suffix array construction algorithms. ACM Comp. Surv. 39(2), 1–31 (2007)CrossRef
Metadaten
Titel
Computing the BWT and the LCP Array in Constant Space
verfasst von
Felipe A. Louza
Guilherme P. Telles
Copyright-Jahr
2016
Buch
Combinatorial Algorithms

Print ISBN: 978-3-319-29515-2

Electronic ISBN: 978-3-319-29516-9

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-319-29516-9_26

Premium Partner

    Bildnachweise