Efficient Approaches to Compute Longest Previous Non-overlapping Factor Array

• Autorzy: Chairungsee S.

Identyfikatory

DOI

10.3233/FI-2018-1745

• Języki publikacji: EN

Abstrakty

EN

In this article, we introduce new methods to compute the Longest Previous nonoverlapping 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 and this table is related to Ziv-Lempel factorization of a text which is useful for text compression and data compression. The LPnF table has the important role for data compression, string algorithms and computational biology. In this paper, we present three approaches to produce the LPnF table of a string from its augmented position heap, from its position heap, and from its suffix heap. We also present the experimental results from these three solutions. The algorithms run in linear time with linear memory space.

Słowa kluczowe

EN

augmented position heap; data compression; longest previous non-overlapping factor; position heap; suffix heap; text compression

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2018
• Tom: Vol. 163, nr 3
• Strony: 291--304
• Opis fizyczny: Bibliogr. 22 poz., rys., tab., wykr.

Twórcy

autor

Chairungsee S.

• School of Informatics, Walailak University, Nakhonsithammarat, Thailand

Bibliografia

• [1] Bell TC, Clearly JG, Witten IH. Text Compression. Prentice Hall Inc., New Jersey, 1990.
• [2] Böckenhauer HJ, Bongartz D. Algorithmic Aspects of Bioinformatics. Springer, Berlin, 2007. ISBN:3540719121.
• [3] 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. doi:10.1109/DEXA.2014.21.
• [4] Chairungsee S, Butrak T, Chareonrak S, Charuphanthuset T. Longest Previous Non-Overlapping Factors Computation. In: 26th International Workshop on Database and Expert Systems Applications, IEEE 2015 pp. 5-8. doi:10.1109/DEXA.2015.21.
• [5] Chairungsee S, Crochemore M. Longest Previous Non-overlapping Factors Table Computation. In: 11th International Conference on Combinatorial Optimization and Applications, 2017 pp. 483-491. doi:10.1007/978-3-319-71147-8_35.
• [6] Coffman EG, Eve J. File Structures Using Hashing Functions. Communications of the ACM. 1970;13(7):427-432. doi:10.1145/362686.362693.
• [7] Cormen TH, Leiserson CE, Rivest RL, Stein C. Introduction to Algorithms. The MIT Press, Massachusetts, 2009.
• [8] Crochemore M, Hancart C, Lecroq T. Algorithms on Strings. Cambridge University Press, Cambridge, UK, 2007. ISBN:0521848997, 9780521848992.
• [9] Crochemore C, Ilie L. Computing longest previous factor in linear time and applications. Inf. Process. Lett. 2008;106(2):75-80. URL https://doi.org/10.1016/j.ipl.2007.10.006.
• [10] Crochemore M, Ilie L, Iliopoulos C, Kubica M, Rytter W, Walén T. LPF computation revisited. In: International Workshop on Combinatorial Algorithms, Springer vol 5874, 2009 pp. 158-169. doi:10.1007/978-3-642-10217-2_18.
• [11] Crochemore M, Iliopoulos C, Kubica M, Rytter W, Walén T. Efficient algorithms for two extensions of the LPF table: the power of Suffix Arrays. In: International Conference on Current Trends in Theory and Practice of Computer Science, Springer vol 5901, 2010 pp. 296-307. doi:10.1007/978-3-642-11266-9_25.
• [12] Crochemore C, Tischler G. Computing Longest Previous nonoverlapping Factors. Inf. Process. Lett. 2011;111(6):291-295. URL https://doi.org/10.1016/j.ipl.2010.12.005.
• [13] Drozdek A. Data Structures and Algorithms in C++. Cengage Learning, 2013. ISBN-10:0470383275, 13:978-0470383278.
• [14] Ehrenfeucht A, McConnell RM, Osheim N, Woo SW. Position heaps: A simple and dynamic text indexing data structure. J. Discrete Algorithms. 2011;9(1):100-121. URL https://doi.org/10.1016/j.jda.2010.12.001.
• [15] Gagie T, Hon WK, Ku TH. New Algorithms for Position Heaps. In: 24th Annual Symposium on Combinatorial Pattern Matching, Bad Herrenalb, Germany 2013 pp. 95-106, vol 7922, Springer. doi:10.1007/978-3-642-38905-4_11.
• [16] Kolpakov R, Kucherov G. Finding Repeats with Fixed Gap. In: 7th International Symposium on String Processing and Information Retrieval, A Curuna, Spain, 2000. doi:10.1109/SPIRE.2000.878192.
• [17] Kolpakov R, Kucherov G. Finding approximate repetitions under Hamming distance. J. Theoretical Computer Science. 2003;303(1):135-156. URL https://doi.org/10.1016/S0304-3975(02)00448-6.
• [18] National Center for Biotechnology Information. URL https://www.ncbi.nlm.nih.gov/nucgss/.
• [19] Pu IM. Fundamental Data Compression. A Butterworth-Heinemann, 2006. ISBN: 9780750663106.
• [20] Storer JA. Data Compression: Methods and Theory. Computer Science Press, 1988. ISBN:0-7167-8156-5.
• [21] Witten IH, Moffat A, Bell TC. Managing Gigabytes. Van Nostrand Reinhold, New York, 1994. ISBN-10:1558605703, 13:978-1558605701.
• [22] Ziv J, Lempel A. A universal algorithm for sequential data compression. IEEE Transactions on Information Theory. 1977;23(3)337-343. doi:10.1109/TIT.1977.1055714.