Suffi x Trees Revisited: (Un)Expected Asymptotic Behaviors
Wojciech Szpankowski · Purdue e-Pubs (Purdue University System) · 1991
Suffix trees find several applications in computer sciences and telecommunications, most notably in algorithms on strings, data compressions and codes.Despite this, very little is known about their typical behavior.We consider in a probabilistic framework a family of suffix trees -further called b-suffix trees -built from the first n suffixes of a random word.In this family a noncompact suffix trees (Le., such that every edge is labeled by a single symbol) is represented by b = 1, and a compact suffix tree (Le., without unary nodes) is asymptotically equivalent to b ~00.Several parameters of b-suffix trees are of interest, namely the typical depth D~b), the depth of insertion L~), the height HA b ), the external path length E~b), and so forth.We establish several results concerning typical, that is, almost sure (a.s.), behavior of these parameters.For example, we show that D~b)Ilogn converges (a.s.) to I/h where h is entropy of the alphabet, but not the depth of insertion for which L~) Ilogn oscillates between I/h l and I/h~b) (a.s.) where 0 < h~b) < h ~hI < 00 are some parameters of the underlying probabilistic model.These findings are used to obtain several insights into certain algorithms on words and universal data compression schemes.As a simple consequence of our results, we settle in the negative the conjecture of Wyner and Ziv regarding the typical length of repeated subwords; we present a new surprising results concerning the length of a block in the Lempel-Ziv parsing algorithm; and finally we demonstrate how to obtain precise asymptotic results for the average time-complexity of some algorithms on strings.