Séminaire du 22 novembre 04, by Mark Daniel Ward.
Analysis of the Multiplicity Matching Parameter in Suffix Trees
In this talk, I will discuss the asymptotics of the "multiplicity matching parameter" in suffix trees by making comparisons to its behavior in tries constructed over independent strings. I will give a description of this parameter, a brief motivation about its importance in my Ph.D. thesis (on joint source-channel coding), and some preliminary results of my analysis. Pattern matching plays an interesting role throughout the investigation.