Academic
Publications
An Online Algorithm for Finding the Longest Previous Factors

An Online Algorithm for Finding the Longest Previous Factors,10.1007/978-3-540-87744-8_58,Daisuke Okanohara,Kunihiko Sadakane

An Online Algorithm for Finding the Longest Previous Factors   (Citations: 3)
BibTex | RIS | RefWorks Download
We present a novel algorithm for finding the longest factors in a text, for which the working space is proportional to the history text size. Moreover, our algorithm is online and exact; in that, unlike the previous batch algorithms [4, 5, 6, 7, 14], which needs to read the entire input beforehand, our algorithm reports the longest match just after reading each character. This algorithm can be directly used for data compression, pattern analysis, and data mining. Our algorithm also supports the window buffer, in that we can bound the working space by discarding the history from the oldest character. Using the dynamic rank/select dictionary [17], our algorithm requires n logσ + O(n logσ) + O(n) bits of working space, and O(log3 n) time per character, O(n log3 n) total time, n is the length of the history, and σ is the alphabet size. We implemented our algorithm and compared it with the recent algorithms [4, 5, 14] in terms of speed and the working space. We found that our algorithm can work with a smaller working space, less than 1/2 of those for the previous methods in real-world data, and with a reasonable decline in speed.
Conference: European Symposium on Algorithms - ESA , pp. 696-707, 2008
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...We define the Burrows-Wheeler Transform BWT of x [7]: for SA[j] > 1 ,B WT[j ]= x SA[j] − 1 , while for j such that SA[j ]=1 , BWT[j ]=$ , a sentinel letter not equal to any other in x. BWT can clearly be computed in linear time from SA; some of our algorithms [34] and LZ algorithms [32] use the BWT array since it occupies only n rather than 4n bytes...

    W. F. Smythet al. Computing regularities in strings

    • ...Furthermore, there is another LZ-factorization algorithm that uses succinct data structures: the online algorithm developed by Okanohara and Sadakane [18]...
    • ...(As a matter of fact, the online algorithm from [18] uses even less space than CPS2, but it is not competitive in terms of time; see the experimental results in [18,2].) Our results can be found in Table 2. Note that the construction time of the indexes is not included...
    • ...(As a matter of fact, the online algorithm from [18] uses even less space than CPS2, but it is not competitive in terms of time; see the experimental results in [18,2].) Our results can be found in Table 2. Note that the construction time of the indexes is not included...
    • ...Special thanks go to an anonymous reviewer, who brought [15,18] to our attention...

    Enno Ohlebuschet al. Lempel-Ziv Factorization Revisited

    • ...Given the ubiquity of arrays and the fundamental nature of this question, it is not surprising that RMQs have a wide range of applications in various elds of computing: text indexing [1,22,47], pattern matching [3,11], string mining [20,32], text compression [9,42], document retrieval [40,48,55], trees [5,7,36], graphs [26,44], bioinformatics [54], and in other types of range queries [10, 51], to mention just a few...

    Johannes Fischeret al. Preprocessing Schemes for Range Minimum Queries on Static Arrays

Sort by: