fa نمایۀ تِرای های سطلی آمار stat علمی پژوهشی بنیادی S <span style="font-family:B Nazanin;"><span style="font-size:10.0pt;">تِرای&shy;ها یکی از کاربردی&shy;ترین ساختمان داده&shy;ها با ساختار درختی در علوم کامپیوتر هستند. تِرای&shy;ها، داده&shy;های رشته&shy;&shy;ای را در برگ&shy;های درخت ذخیره می&shy;کنند. یک نسخۀ تعمیم یافتۀ تِرای، موسوم به تِرای سطلی است که در آن هر برگ یا سطل، ظرفیت ذخیرۀ بیش از یک داده را دارد. تِرای تصادفی با تعریف یک قاعده رشد تصادفی برای تِرای حاصل می&shy;شود. تعداد گره&shy;های هم نوع که در فاصلۀ یک‌سان از ریشۀ یک درخت ریشه دار هستند را نمایه نامند. بررسی نمایۀ یک درخت، اهمیت زیادی دارد. زیرا بسیاری از پارامترهای درخت ریشه&shy;دار را می&shy;توان برحسب نمایۀ آن درخت بیان کرد. در این مقاله به بررسی مجانبی امیدریاضی، واریانس و توزیع حدی هر یک از دو نمایۀ سطلی و داخلی (تعداد گره&shy;های سطلی یا برگ و تعداد گره&shy;های داخلی یا غیربرگ که در فاصلۀ یک‌سان از ریشه هستند) در تِرای سطلی تصادفی می&shy;پردازیم، وقتی که تعداد داده&shy;های ذخیره شده در تِرای افزایش یابد. </span></span><span style="font-family:B Nazanin;"><span style="font-size:10.0pt;">امید ریاضی و واریانس&shy;های هر دو نمایه شامل توابعی متناوب هستند و نشان می‌دهیم آن توابع متناوب ناصفرند که این نکته در مقاله مربوط به نمایه ترای معمولی، به اثبات نرسیده است. </span></span><span style="font-family:B Nazanin;"><span style="font-size:10.0pt;">هم‌چنین به بررسی مقدار مجانبی نسبت امید ریاضی&shy;های دو نمایۀ سطلی و داخلی می&shy;پردازیم. روش&shy;هایی که برای حصول نتایج به‌کار می&shy;بریم، براساس استفاده از پواسونی سازی، تبدیل ملین، معادلات بازگشتی، توابع مولد، تحلیل تکینی و روش نقطۀ زینی است.</span></span> <strong>Introduction</strong><br> Tries (from re<em>trie</em>val) are one of the most practical data structures with a tree construction in computer science. Tries store string data in leaves of tree. They are often used to store such data so that future retrieval can be made efficient. For example, tries are widely used in algorithms for automatically correcting words in texts. The number of nodes of the same type, which are at the same distance from the root of a rooted tree, is called profile. The analysis of the profile of a tree is of great importance. Because many of the parameters of a rooted tree can be expressed in terms of its profile. Although profiles represent one of the most fundamental parameters of tries, they have hardly been studied in the past. A generalized version of trie is called bucket trie where each leaf or bucket has a storage capacity of more than one string. Random trie is obtained by defining a random grow rule for trie. We present a detailed study of the limit behavior of the profiles in a random bucket tries.<br> &nbsp;<strong>Material and methods</strong><br> In this paper, the methods we apply to derive recurrences satisfied by the expected profiles and to solve them asymptotically for all possible ranges of the distance from the root, are based on the use of Poissonization, Mellin transform, recurrence equations, generating functions, singularity analysis and saddle-point method.<br> <strong>Results and discussion</strong><br> Here, as the number of stored strings in a random bucket trie increases, we investigate the asymptotic expectation, variance and limiting distribution of each of the two internal and bucket profiles (i.e. the number of bucket nodes or leaves, and the number of internal nodes or non-leaves which are at the same distance from the root) in random bucket tries. Both the expectation and variances of the two profiles contain periodic functions, and we show those periodic functions are not zero that this point has not been proven in the paper on the ordinary trie. Also, we examine the amount of asymptotic ratio of the expectations of the bucket and internal profiles.<br> <strong>Conclusion</strong><br> In this research, we will generalize the most important part of the results for the ordinary tries and also provide a proof for an unproven point in those results. More precisely, the purpose of this article is to study the internal profile (the number of non-leaf nodes at distance <img alt="" height="19" src="file:///C:Users1AppDataLocalTempmsohtmlclip11clip_image002.gif" width="9" >&nbsp;from the root) and bucket profile (the number of buckets at distance <img alt="" height="19" src="file:///C:Users1AppDataLocalTempmsohtmlclip11clip_image002.gif" width="9" >&nbsp;from the root) in an important data structure called random bucket trie (random trie based on <img alt="" height="19" src="file:///C:Users1AppDataLocalTempmsohtmlclip11clip_image004.gif" width="9" >&nbsp;data and maximum capacity of <img alt="" height="19" src="file:///C:Users1AppDataLocalTempmsohtmlclip11clip_image006.gif" width="35" >&nbsp;data per each leaf). By some methods in complex analysis, we have shown that for every <img alt="" height="19" src="file:///C:Users1AppDataLocalTempmsohtmlclip11clip_image008.gif" width="34" >&nbsp;and some fixed constants <img alt="" height="19" src="file:///C:Users1AppDataLocalTempmsohtmlclip11clip_image010.gif" width="15" >&nbsp;and <img alt="" height="19" src="file:///C:Users1AppDataLocalTempmsohtmlclip11clip_image012.gif" width="16" >, if <img alt="" height="19" src="file:///C:Users1AppDataLocalTempmsohtmlclip11clip_image002.gif" width="9" >&nbsp;is in the range<br> <img alt="" height="19" src="file:///C:Users1AppDataLocalTempmsohtmlclip11clip_image014.gif" width="216" >,<br> then the expectations and variances of both profiles contain non-zero periodic functions (the non-zero property of these periodic functions has not been proved for the ordinary tries up to now). We also provide a graph of those periodic functions for <img alt="" height="19" src="file:///C:Users1AppDataLocalTempmsohtmlclip11clip_image016.gif" width="76" >&nbsp;by MAPLE. Then we study the ratio of the two profiles for <img alt="" height="19" src="file:///C:Users1AppDataLocalTempmsohtmlclip11clip_image018.gif" width="38" >&nbsp;Finally, by finding the asymptotic expansions of&nbsp; Poisson generating functions for the probability generating functions of profiles and then using the Cauchy integral formula, we obtain the asymptotic expansions for the probability generating functions, which indicate that the limiting distributions of profiles are normal. <a href="./files/site1/files/62/3Abstract.pdf">./files/site1/files/62/3Abstract.pdf</a><br> <strong>&nbsp;</strong><br> &nbsp;  تِرای­های سطلی, نمایه, پواسونی سازی, تبدیل ملین, معادلات بازگشتی, توابع مولد, تحلیل تکینی, روش نقطۀ زینی. Bucket tries, Profile, Poissonization, Mellin transform, Recursive equations, Generating functions, Singularity analysis, Saddle point method 169 182 http://mmr.khu.ac.ir/browse.php?a_code=A-10-274-1&slc_lang=fa&sid=1 Mehri Javanian مهری جوانیان javanian@znu.ac.ir 10031947532846003709 10031947532846003709 Yes دانشگاه زنجان، دانشکدۀ علوم، گروه آمار