Name
Abstract | ||
|---|---|---|
We present efficient algorithms for storing past segments of a text. They are computed using two previously computed read-only arrays (SUF and LCP) composing the Suffix Array of the text. They compute the maximal length of the previous factor (subword) occurring at each position of the text in a table called LPF. This notion is central both in many conservative text compression techniques and in the most efficient algorithms for detecting motifs and repetitions occurring in a text.The main results are: a linear-time algorithm that computes explicitly the permutation that transforms the LCP table into the LPF table; a time-space optimal computation of the LPF table; and an O(nlogn) strong in-place computation of the LPF table. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1007/978-3-642-10217-2_18 | IWOCA |
Keywords | Field | DocType |
maximal length,time-space optimal computation,ziv-lempel factorisa- tion,linear-time algorithm,longest previous factor,lpf table,detection of repetitions.,efficient algorithm,conservative text compression technique,main result,strong in-place computation,lpf computation revisited,suffix array,lcp table,text compression | Text compression,Permutation,Arithmetic,Algorithm,Suffix array,Mathematics,Computation | Conference |
Volume | ISSN | Citations |
5874 | 0302-9743 | 17 |
PageRank | References | Authors |
0.71 | 19 | 6 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Maxime Crochemore | 1 | 2655 | 281.75 |
| Lucian Ilie | 2 | 840 | 76.50 |
| Costas S. Iliopoulos | 3 | 1534 | 167.43 |
| Marcin Kubica | 4 | 629 | 29.26 |
| Wojciech Rytter | 5 | 2290 | 181.52 |
| Tomasz Waleń | 6 | 706 | 39.62 |