Top

Published in:

2017 | OriginalPaper | Chapter

Longest Previous Non-overlapping Factors Table Computation

Authors : Supaporn Chairungsee, Maxime Crochemore

Published in: Combinatorial Optimization and Applications

Publisher: Springer International Publishing

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

search-config

AI-assisted search

Off

Abstract

We examine the computation of the Longest Previous non-overlapping Factor (LPnF) table. The LPnF table is the table that stores the maximal length of factors re-occurring at each position of a string without overlapping. The LPnF table is related to well-known techniques for data compression, such as Ziv-Lempel factorization. This table is useful both for string algorithms and for text compression. In this paper, we present two algorithms to compute the LPnF table of a string: one from its augmented position heap and the other from its suffix heap. The proposed algorithms run in linear time with linear memory space.

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 On Structural Parameterizations of the Matching Cut Problem

next chapter Modeling and Verifying Multi-core Programs

Bell, T.C., Clearly, J.G., Witten, I.H.: Text Compression. Prentice Hall Inc., New Jersey (1990)

Böckenhauer, H.J., Bongartz, D.: Algorithmic Aspects of Bioinformatics. Springer, Berlin (2007)MATH

Butrak, T., Chareonrak, S., Charuphanthuset, T., Chairungsee, S.: A new approach for longest previous non-overlapping factors computation. In: International Conference on Computer and Information Sciences, Hongkong, China (2015)

Chairungsee, S., Butrak, T., Chareonrak, S., Charuphanthuset, T.: Longest Previous non-overlapping Factors computation. In: 26th International Workshop on Database and Expert Systems Applications, pp. 5–8. IEEE (2015)

Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. The MIT Press, Massachusetts (2009)MATH

Crochemore, M., Hancart, C., Lecroq, T.: Algorithms on Strings. Cambridge University Press, Cambridge (2007)CrossRefMATH

Crochemore, C., Ilie, L.: Computing longest previous factor in linear time and applications. Inf. Process. Lett. 106(2), 75–80 (2008)CrossRefMATHMathSciNet

Crochemore, M., Ilie, L., Iliopoulos, C.S., Kubica, M., Rytter, W., Waleń, T.: LPF computation revisited. In: Fiala, J., Kratochvíl, J., Miller, M. (eds.) IWOCA 2009. LNCS, vol. 5874, pp. 158–169. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-10217-2_18 CrossRef

Crochemore, M., Iliopoulos, C.S., Kubica, M., Rytter, W., Waleń, T.: Efficient algorithms for two extensions of LPF table: the power of suffix arrays. In: van Leeuwen, J., Muscholl, A., Peleg, D., Pokorný, J., Rumpe, B. (eds.) SOFSEM 2010. LNCS, vol. 5901, pp. 296–307. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-11266-9_25 CrossRef

10.

Crochemore, C., Tischler, G.: Computing longest previous nonoverlapping factors. Inf. Process. Lett. 111, 291–295 (2011)CrossRefMATH

11.

Drozdek, A.: Data Structures and Algorithms in C++. Cengage Learning, Boston (2013)

12.

Ehrenfeucht, A., McConnell, R.M., Osheim, N., Woo, S.W.: Position heaps: a simple and dynamic text indexing data structure. J. Discret. Algorithms 9, 100–121 (2011)CrossRefMATHMathSciNet

13.

Gagie, T., Hon, W.-K., Ku, T.-H.: New algorithms for position heaps. In: Fischer, J., Sanders, P. (eds.) CPM 2013. LNCS, vol. 7922, pp. 95–106. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-38905-4_11 CrossRef

14.

Pu, I.M.: Fundamental Data Compression. A Butterworth-Heinemann, Oxford (2006)

15.

Storer, J.A.: Data Compression: Methods and Theory. Computer Science Press, New York (1988)

16.

Witten, I.H., Moffat, A., Bell, T.C.: Managing Gigabytes. Van Nostrand Reinhold, New York (1994)MATH

17.

Ziv, J., Lempel, A.: A universal algorithm for sequential data compression. IEEE Trans. Inf. Theory 23(3), 337–343 (1977)CrossRefMATHMathSciNet

Title: Longest Previous Non-overlapping Factors Table Computation
Authors: Supaporn Chairungsee
Maxime Crochemore
Publisher: Springer International Publishing
Book: Combinatorial Optimization and Applications
Print ISBN: 978-3-319-71146-1

Electronic ISBN: 978-3-319-71147-8

Copyright Year: 2017
DOI: https://doi.org/10.1007/978-3-319-71147-8_35

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