نمایۀ تِرای های سطلی

تِرای ها یکی از کاربردی ترین ساختمان داده ها با ساختار درختی در علوم کامپیوتر هستند. تِرای ها، داده های رشته ای را در برگ های درخت ذخیره می کنند. یک نسخۀ تعمیم یافتۀ تِرای، موسوم به تِرای سطلی است که در آن هر برگ یا سطل، ظرفیت ذخیرۀ بیش از یک داده را دارد. تِرای تصادفی با تعریف یک قاعده رشد تصادفی برای تِرای حاصل می شود. تعداد گره های هم نوع که در فاصلۀ یک‌سان از ریشۀ یک درخت ریشه دار هستند را نمایه نامند. بررسی نمایۀ یک درخت، اهمیت زیادی دارد. زیرا بسیاری از پارامترهای درخت ریشه دار را می توان برحسب نمایۀ آن درخت بیان کرد. در این مقاله به بررسی مجانبی امیدریاضی، واریانس و توزیع حدی هر یک از دو نمایۀ سطلی و داخلی (تعداد گره های سطلی یا برگ و تعداد گره های داخلی یا غیربرگ که در فاصلۀ یک‌سان از ریشه هستند) در تِرای سطلی تصادفی می پردازیم، وقتی که تعداد داده های ذخیره شده در تِرای افزایش یابد. امید ریاضی و واریانس های هر دو نمایه شامل توابعی متناوب هستند و نشان می‌دهیم آن توابع متناوب ناصفرند که این نکته در مقاله مربوط به نمایه ترای معمولی، به اثبات نرسیده است. هم‌چنین به بررسی مقدار مجانبی نسبت امید ریاضی های دو نمایۀ سطلی و داخلی می پردازیم. روش هایی که برای حصول نتایج به‌کار می بریم، براساس استفاده از پواسونی سازی، تبدیل ملین، معادلات بازگشتی، توابع مولد، تحلیل تکینی و روش نقطۀ زینی است.

Profile of Bucket Tries

IntroductionTries (from retrieval) 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. Material and methodsIn 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 saddlepoint method.Results and discussionHere, 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 nonleaves 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.ConclusionIn 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 nonleaf nodes at distance from the root) and bucket profile (the number of buckets at distance from the root) in an important data structure called random bucket trie (random trie based on data and maximum capacity of data per each leaf). By some methods in complex analysis, we have shown that for every and some fixed constants and , if is in the range,then the expectations and variances of both profiles contain nonzero periodic functions (the nonzero 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 by MAPLE. Then we study the ratio of the two profiles for Finally, by finding the asymptotic expansions of 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. ./files/site1/files/62/3Abstract.pdf