A Note on the Height of Suffix Trees
A Note on the Height of Suffix Trees
复制标题
关于后缀树高度的注意事项
DOI：
10.1137/0221005
复制
发表时间：
1992
期刊：
影响因子：
--
通讯作者：
Bonita Rais
中科院分区：
文献类型：
--
作者：
L. Devroye;W. Szpankowski;Bonita Rais
考虑一个随机字，其中各个符号是从符号概率为$p_i$的有限或无限字母表中提取的，并设$H_n$是由该单词的前n个后缀构成的后缀树的高度。证明了$H_n$在许多方面与$2\logn/\log(1/\sum_i p_i^2)$渐近：在概率上相差$O(\log\logn)$，并且在平均值上几乎必然地趋于1。
Consider a random word in which the individual symbols are drawn from a finite or infinite alphabet with symbol probabilities $p_i $ , and let $H_n $ be the height of the suffix tree constructed from the first n suffixes of this word. It is shown that $H_n $ is asymptotically close to $2\log n/\log (1/\sum_i p_i^2 )$ in many respects: the difference is $O(\log \log n)$ in probability, and the ratio tends to one almost surely and in the mean.