Affiliations: School of Informatics, Walailak University, Nakhonsithammarat, Thailand. [email protected]
Correspondence:
[*]
Address for correspondence: School of Informatics, Walailak University, Nakhonsithammarat, Thailand
Abstract: 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.
Keywords: Longest Previous non-overlapping Factor, Augmented position heap, Position heap, Suffix heap, Data compression, Text compression
