Suffix tree  is a data structure widely used in algorithms on words and data compression. Despite this, very little is known about its typical behavior. Recently, Chang and Lawler have designed a sublinear expected time algorithm for approximate string matching using simple estimates of some parameters of suffix trees. It seems that any further advances in such an endover are subject to better understanding of suffix trees behavior. In this paper, we use a novel technique called  string ruler  approach to provide a characterization of several basic parameters of suffix trees (dependency among symbols are allowed !). These findings are used to :(i) settle in the negative the conjecture of Wyner and Ziv regarding the typical behavior of the universal data compression scheme of Lampel and Ziv; (ii) prove an open problem regarding the length of a block in the Lampel-Ziv parsing algorithm; (iii) provide new insights and generalizations of string matching algorithms, particularly the one by Chang and Lawler.
['Wojciech Szpankowski']
Un)expected behavior of typical suffix trees