درختهای پسوند ساختارهای داده‌های با بیشترین استفاده در الگوریتمهای روی واژه‌ها هستند. در این مقاله، ژرفای یک درخت پسوند فشرده را، که به درخت ‎PAT‎ هم موسوم است، تحت برخی فرضهای احتمالاتی ساده در نظر می‌گیریم. برای یک منبع بی‌حافظه اریب، ثابت می‌کنیم که توزیع حدی برای ژرفا در یک درخت ‎PAT‎ همانند توزیع حدی برای ژرفای یک ترای ‎PATRICIA‎ است، اگر چه ترای ‎PATRICIA‎ از رشته‌های مستقل از لحاظ آماری ساخته می‌شود. در نتیجه نشان می‌دهیم که توزیع حدی برای ژرفا در یک درخت ‎    PAT‎که روی ‎n‎ پسوند ساخته می‌شود، نرمال است

متن کامل [PDF 161 kb]   (1846 دریافت)