جلد 3، شماره 2 - ( آبان 1383 )
جلد 3 شماره 2 صفحات 139-148 |
برگشت به فهرست نسخه ها
چکیده: (9096 مشاهده)
درختهای پسوند ساختارهای داده‌های با بیشترین استفاده در الگوریتمهای روی واژه‌ها هستند. در این مقاله، ژرفای یک درخت پسوند فشرده را، که به درخت PAT هم موسوم است، تحت برخی فرضهای احتمالاتی ساده در نظر می‌گیریم. برای یک منبع بی‌حافظه اریب، ثابت می‌کنیم که توزیع حدی برای ژرفا در یک درخت PAT همانند توزیع حدی برای ژرفای یک ترای PATRICIA است، اگر چه ترای PATRICIA از رشته‌های مستقل از لحاظ آماری ساخته می‌شود. در نتیجه نشان می‌دهیم که توزیع حدی برای ژرفا در یک درخت PATکه روی n پسوند ساخته می‌شود، نرمال است
دریافت: 1390/6/4 | پذیرش: 1394/6/21 | انتشار: 1383/8/25