Benutzer: Gast  Login
Dokumenttyp:
Technical Report 
Autor(en):
Stefan Eckhardt; Sven Kosub; Johannes Nowak 
Titel:
Smoothed Analysis of Trie Height 
Abstract:
Tries are very simple general purpose data structures for information retrieval. A crucial parameter of a trie is its height. In the worst case the height is unbounded when the trie is built over a set of n strings. Analytical investigations have shown that the average height under many random sources is logarithmic in n. Experimental studies of trie height suggest that this holds for non-random data. In order to give an analytical explanation to these findings we perform a smoothed analysis of...    »
 
Stichworte:
Trie Height; Smoothed Analysis; Edit Perturbations; Probabilistic Finite Automatons 
Jahr:
2007 
Jahr / Monat:
2007-07-01 00:00:00 
Seiten/Umfang:
28