Suffix trees for universal source modeling with applications

Suffix trees are shown to reveal significant information about the internal structure of an individual sequence S. Specifically it is shown how the number of occurrences of any subsequence of S, the recurrence period for any subsequence that occurs at least twice in S, and the longest subsequence that occurs at least twice in S are determined from the sequences suffix tree. Since suffix trees can be constructed with low, O(N) computational complexity, they provide a powerful tool for information-theoretic sequence analysis. We further demonstrate the utility of suffix trees by using the collected statistics for two common problems in information theory: variable order source modeling and entropy estimation.