جلد 3، شماره 2 - ( آبان 1383 )                   جلد 3 شماره 2 صفحات 139-148 | برگشت به فهرست نسخه ها

XML English Abstract Print


چکیده:   (9096 مشاهده)
درختهای پسوند ساختارهای داده‌های با بیشترین استفاده در الگوریتمهای روی واژه‌ها هستند. در این مقاله، ژرفای یک درخت پسوند فشرده را، که به درخت ‎PAT‎ هم موسوم است، تحت برخی فرضهای احتمالاتی ساده در نظر می‌گیریم. برای یک منبع بی‌حافظه اریب، ثابت می‌کنیم که توزیع حدی برای ژرفا در یک درخت ‎PAT‎ همانند توزیع حدی برای ژرفای یک ترای ‎PATRICIA‎ است، اگر چه ترای ‎PATRICIA‎ از رشته‌های مستقل از لحاظ آماری ساخته می‌شود. در نتیجه نشان می‌دهیم که توزیع حدی برای ژرفا در یک درخت ‎    PAT‎که روی ‎n‎ پسوند ساخته می‌شود، نرمال است
متن کامل [PDF 161 kb]   (2316 دریافت)    

دریافت: 1390/6/4 | پذیرش: 1394/6/21 | انتشار: 1383/8/25