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

XML English Abstract Print


چکیده:   (7605 مشاهده)
درختهای پسوند ساختارهای داده‌های با بیشترین استفاده در الگوریتمهای روی واژه‌ها هستند. در این مقاله، ژرفای یک درخت پسوند فشرده را، که به درخت ‎PAT‎ هم موسوم است، تحت برخی فرضهای احتمالاتی ساده در نظر می‌گیریم. برای یک منبع بی‌حافظه اریب، ثابت می‌کنیم که توزیع حدی برای ژرفا در یک درخت ‎PAT‎ همانند توزیع حدی برای ژرفای یک ترای ‎PATRICIA‎ است، اگر چه ترای ‎PATRICIA‎ از رشته‌های مستقل از لحاظ آماری ساخته می‌شود. در نتیجه نشان می‌دهیم که توزیع حدی برای ژرفا در یک درخت ‎    PAT‎که روی ‎n‎ پسوند ساخته می‌شود، نرمال است
متن کامل [PDF 161 kb]   (1787 دریافت)    
موضوع مقاله: 60: Probability theory and stochastic processes
دریافت: ۱۳۹۰/۶/۴ | پذیرش: ۱۳۹۴/۶/۲۱