بررسی مدل ترای‌های d-d یی اریب تصادفی

نویسندگان
رامین کاظمی 1
حدیثه عبدالهی نهوجی 1
سولماز نوروزی 2
1 دانشگاه بین‌المللی امام خمینی(ره)، گروه آمار
2 دانشگاه غیرانتفاعی البرز، گروه آمار
10.29252/mmr.2.2.39
چکیده
ترای‌ها عمومی‌ترین ساختار داده‌ای روی رشته‌ها هستند. با استفاده از رشته‌ها روی الفبایی که منجر به تولید درخت­های d-d یی می‌شود، می­توان ترای‌های d-d یی ساخت. سراسر مقاله فرض می‌کنیم که رشته‌های ذخیره شده در ترای به‌وسیلۀ منشأ بی‌حافظه مناسب تولید می‌شوند. در این مقاله، تحلیل میانگین نمایه با روی‌کرد ترکیبیاتی خاصی به ترای‌های d-d یی توسیع داده می‌شود. از این رویکرد ترکیبیاتی برای بررسی میانگین نمایه استفاده می‌کنیم زیرا تابع احتمال آن نامعلوم است. تابع احتمال عمق و تابع توزیع ارتفاع را هنگامی که n بزرگ است، به‌دست می‌آوریم. این نتایج از بررسی معادله‌های بازگشتی مشخصی که آن‌ها را با روش تحلیلی حل می‌کنیم، به‌دست می‌آیند.
کلیدواژه‌ها
ترای‌های d-d یی
نمایه
ارتفاع
عمق

عنوان مقاله English

Study of Random Biased d-ary Tries Model

نویسندگان English

r kazemi 1
h. abdolahinohoji 1
s norouzi 2
چکیده English

Tries are the most popular data structure on strings. We can construct d-ary tries by using strings over an alphabet leading to d-ary tries. Throughout the paper we assume that strings stored in trie are generated by an appropriate memory less source. In this paper, with a special combinatorial approach we extend their analysis for average profiles to d-ary tries. We use this combinatorial approach for studying of average profile, since its probability distribution is unknown. We obtain the probability distribution of depth and the distribution function of height as n is large. These results follow from the study of certain recurrence equations that we solve by a analytic method.

کلیدواژه‌ها English

d-ary tries
profile
height
depth
1. Briandais R. De La., "File searching using variable length keys, in Proceedings of the AFIPS Spring Joint Computer Conference", AFIPS Press, Reston, Va. (1959) 295-298.

2. Clement J., Flajolet P., Vallee B., "Dynamical sources in information theory: a general analysis of trie structures", Algorithmica, 29 (2001) 307-369.

3. Devroye L, "A study of trie-like structures under the density model", Annals of Applied Probaility, 2 (1992) 402-434.

4. Devroye L., "A note on the average depth of tries", Computing, 28 (1982) 367-371.

5. Drmota M., Szpankowski W., "The expected profile of digital search trees", Journal of Combinatorial Theory, Series A, 118 (2011) 1939-1965.

6. Flajolet P., Sedgewick R., "Analytic combinatorics", Cambridge University Press, Cambridge (2008).

7. Fredkin E., "Trie memory, Communications of the ACM", 3 (1960) 490-499.

8. Gusfield D. "Algorithms on strings, and sequences", Cambridge University Press, Cambridge (1997)..

9. Kazemi R., Vahidi-Asl M. Q., "The variance of the profile in digital search trees", Discrete Mathematics and Theoretical Computer Science, 13: 3 (2011) 21-38.

10. Kazemi R., Delaver S., "The moments of the profile in random binary digital trees", Journal of Mathematics and Computer Science, 6 (2013)176-190.

11. Kazemi R., Vahidi-Asl M. Q., "Probabilistic analysis of the asymmetric digital search trees", International Journal of Nonlinear Analysis and Applications, 6 (2) (2015) 161-173.

12. Kukich k., "Techniques for automatically correcting words in text", ACM Computing Surveys (1992)377-439.

13. Mahmoud H., "Evolution of random search tress", John Wiley and Soun Inc., New York (1992).

14. Park G., Hwang H. K., Nicodeme P., Szpankowski W., "Profile of tries, SIM J. Computing", 39 (2009) 1821-1880.

15. Szpankowski W., "Average case analysis of algorithms on sequences", Wiley, New York (2001).