更新理論在隨機Tries 上的應用

Abstract

在電腦科學中，trie 是相當重要的資料結構，由於它的特殊生成方式， 在生活中有很多很好的應用，像是搜索物件，輸入一個開頭來找出所有的 可能，而trie 的演算法很容易修改也是被廣泛應用的原因之一，其中2- protected nodes 更是在近期很多人研究的重點。 在這篇論文裡，我們的主要目標是用機率中的更新理論來分析trie 的一 些性質，我們先證明更新理論的一些定理，並證明關鍵更新定理，接著我們 介紹一些Svante Jason 在他的paper 中提出的一些結果並補足證明，最後我 們利用更新理論算出2-protected nodes 和3-protected nodes 在trie 中的期 望值。 接著我們介紹一下整篇論文的架構。 第一章我們先從電腦科學中的樹開始介紹，介紹樹的定義，樹中一些有 用到的名詞和各種樹的畫法與優缺點，最後介紹的trie 與patricia trie 的生 成方式和比較，並提出了接下來要研究的方向。 第二章我們討論要用到的研究工具－更新理論，從更新過程開始，中間 證明了一些接下來要使用的定理，最後證明了基本更新定理和關鍵更新定 理，並區分了算術型與d

The trie is a data structure of fundamental importance in Computer Science. This is reflected by the fact that tries have found numerous applications, such as in searching, sorting, contention tree algorithms, retrieving IP addresses and satellite data, internet routing, etc. In this master’s thesis, our primary target is to analyze some properties of tries using renewal theory. First, we will give a brief, self-contained introduction into renewal theory. Then, we will introduce some results of a recent paper of S. Jason in which the application of renewal theory to the analysis of tries was pioneered. Finally, we will add some new results. The following is an outline of the structure of the thesis. In Chapter 1, we will give some basics from Computer Science. More precisely, we will give the definitions of some data structures (including tries) and discuss their advantages and disadvantages. Moreover, the aim of this thesis will be stated in Chapter 1. In Chapter 2, we give a detailed review of renewal theory. The main focus in this chapter will be on limit laws and we will discuss both the elementary and the key renewal theorem in details. In particular, the latter will turn out to be of key importance for the analysis of trie parameters. At the end of the chapter, we will also briefly discuss results for the delayed renewal process. In Chapter 3, the renewal theory from Chapter 2 will be applied to tries.First we will introduce some results from a recent paper of S. Jason and prove them. Next, we will propose other interesting results which can also be handled by S. Janson’s tools. In Chapter 4, we use the method from Chapter 3 to calculate the asymptotic mean of 2-protected and 3-protected nodes in tries. These kind of nodes have been recently introduced and have already been studied in many papers. Parts of the extensive computations in this chapter will be done with the help of Maple. Finally, in Chapter 5, we give a conclusion to the thesis. 3