Efficient algorithms for two extensions of LPF table: the power of suffix arrays
Su?x arrays provide a powerful data structure to solve several questions related to the structure of all the factors of a string. We show how they can be used to compute e?ciently two new tables storing di?erent types of previous factors (past segments) of a string. The concept of a longest previous...
| Main Authors: | , , , , |
|---|---|
| Other Authors: | |
| Format: | Conference Paper |
| Published: |
Springer
2010
|
| Subjects: | |
| Online Access: | http://www.springerlink.com/content/5177t4t8k4m66112 http://hdl.handle.net/20.500.11937/19459 |
| _version_ | 1848750039905599488 |
|---|---|
| author | Crochemore, M. Iliopoulos, Costas Kubica, M. Rytter, W. Walen, T. |
| author2 | Jan v Leeuwen |
| author_facet | Jan v Leeuwen Crochemore, M. Iliopoulos, Costas Kubica, M. Rytter, W. Walen, T. |
| author_sort | Crochemore, M. |
| building | Curtin Institutional Repository |
| collection | Online Access |
| description | Su?x arrays provide a powerful data structure to solve several questions related to the structure of all the factors of a string. We show how they can be used to compute e?ciently two new tables storing di?erent types of previous factors (past segments) of a string. The concept of a longest previous factor is inherent to Ziv-Lempel factorization of strings in text compression, as well as in statistics of repetitions and symmetries. The longest previous reverse factor for a given position i is the longest factor starting at i, such that its reverse copy occurs before, while the longest previous non-overlapping factor is the longest factor v starting at i which has an exact copy occurring before. The previous copies of the factors are required to occur in the pre?x ending at position i -1. We design algorithms computing the table of longest previous reverse factors (LPrF table) and the table of longest previous nonoverlapping factors (LPnF table). The latter table is useful to computerepetitions while the former is a useful tool for extracting symmetries. These tables are computed, using two previously computed read-only arrays (SUF and LCP) composing the su?x array, in linear time on anyinteger alphabet. The tables have not been explicitly considered before, but they have several applications and they are natural extensions of the LPF table which has been studied thoroughly before. Our results improve on the previous ones in several ways. The running time of the computation no longer depends on the size of the alphabet, which drops a log factor. Moreover the newly introduced tables store additional information on the structure of the string, helpful to improve, for example, gapped palindrome detection and text compression using reverse factors. computing their primitive roots. Applications of runs, despite their importance, are underrepresented in existing literature (approximately one page in the paper of Kolpakov & Kucherov, 1999). In this paper we attempt to ?ll in this gap. We use Lyndon words and introduce the Lyndon structure of runs as a useful tool when computing powers. In problems related to periods we use some versions of the Manhattan skyline problem. |
| first_indexed | 2025-11-14T07:30:30Z |
| format | Conference Paper |
| id | curtin-20.500.11937-19459 |
| institution | Curtin University Malaysia |
| institution_category | Local University |
| last_indexed | 2025-11-14T07:30:30Z |
| publishDate | 2010 |
| publisher | Springer |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | curtin-20.500.11937-194592023-01-13T07:56:30Z Efficient algorithms for two extensions of LPF table: the power of suffix arrays Crochemore, M. Iliopoulos, Costas Kubica, M. Rytter, W. Walen, T. Jan v Leeuwen Anca Muscholl David Peleg Jaroslav Pokorny Bernhard Rumpe Su?x Array Longest previous reverse factor longest previous factor longest previous non-overlapping factor runs palindrome text compression Su?x arrays provide a powerful data structure to solve several questions related to the structure of all the factors of a string. We show how they can be used to compute e?ciently two new tables storing di?erent types of previous factors (past segments) of a string. The concept of a longest previous factor is inherent to Ziv-Lempel factorization of strings in text compression, as well as in statistics of repetitions and symmetries. The longest previous reverse factor for a given position i is the longest factor starting at i, such that its reverse copy occurs before, while the longest previous non-overlapping factor is the longest factor v starting at i which has an exact copy occurring before. The previous copies of the factors are required to occur in the pre?x ending at position i -1. We design algorithms computing the table of longest previous reverse factors (LPrF table) and the table of longest previous nonoverlapping factors (LPnF table). The latter table is useful to computerepetitions while the former is a useful tool for extracting symmetries. These tables are computed, using two previously computed read-only arrays (SUF and LCP) composing the su?x array, in linear time on anyinteger alphabet. The tables have not been explicitly considered before, but they have several applications and they are natural extensions of the LPF table which has been studied thoroughly before. Our results improve on the previous ones in several ways. The running time of the computation no longer depends on the size of the alphabet, which drops a log factor. Moreover the newly introduced tables store additional information on the structure of the string, helpful to improve, for example, gapped palindrome detection and text compression using reverse factors. computing their primitive roots. Applications of runs, despite their importance, are underrepresented in existing literature (approximately one page in the paper of Kolpakov & Kucherov, 1999). In this paper we attempt to ?ll in this gap. We use Lyndon words and introduce the Lyndon structure of runs as a useful tool when computing powers. In problems related to periods we use some versions of the Manhattan skyline problem. 2010 Conference Paper http://hdl.handle.net/20.500.11937/19459 10.1007/978-3-642-11266-9_25 http://www.springerlink.com/content/5177t4t8k4m66112 Springer restricted |
| spellingShingle | Su?x Array Longest previous reverse factor longest previous factor longest previous non-overlapping factor runs palindrome text compression Crochemore, M. Iliopoulos, Costas Kubica, M. Rytter, W. Walen, T. Efficient algorithms for two extensions of LPF table: the power of suffix arrays |
| title | Efficient algorithms for two extensions of LPF table: the power of suffix arrays |
| title_full | Efficient algorithms for two extensions of LPF table: the power of suffix arrays |
| title_fullStr | Efficient algorithms for two extensions of LPF table: the power of suffix arrays |
| title_full_unstemmed | Efficient algorithms for two extensions of LPF table: the power of suffix arrays |
| title_short | Efficient algorithms for two extensions of LPF table: the power of suffix arrays |
| title_sort | efficient algorithms for two extensions of lpf table: the power of suffix arrays |
| topic | Su?x Array Longest previous reverse factor longest previous factor longest previous non-overlapping factor runs palindrome text compression |
| url | http://www.springerlink.com/content/5177t4t8k4m66112 http://hdl.handle.net/20.500.11937/19459 |