No label defined (Q4945077)

The Burrows and Wheeler universal data compression algorithm (BW-algorithm) achieves compression rates that are close to the best known rates achieved in practice. The author further improves on \textit{S.~Kurtz} [Reducing the space Requirement of Suffix tree. Report 98-03, Technische Fakultät, Universität Bielefeld (1998)], and shows that a suffix tree based method requires on average about the same amount of space. The improvement is achieved by exploiting the fact, that in practice, the BW-algorithm processes long input strings in blocks of a limited size. Assuming a maximal block size of \(2^{21} - 1,\) it is shown that the suffix tree can be implemented in \(8.83n\) bytes on average for the files of the Calgary Corpus. This is \(0.6n\) and \(9.77n\) bytes less than the implementation technique of Kurtz and of \textit{E.~McCreight} [A Space-Economical Suffix Tree Construction Algorithm, J. of the ACM, 23, No. 2, 262-272 (1976)], respectively. The worst case space requirement of this implementation technique is \(16n\) bytes, compared to \(20n\) bytes for the Kurtz algorithm and \(28n\) bytes for the McCreight one. For the entire collection see [Zbl 0933.00056].