Analytic Pattern Matching: From DNA to Twitter by Philippe Jacquet & Wojciech Szpankowski

Author:Philippe Jacquet & Wojciech Szpankowski [Jacquet, Philippe]
Language: eng
Format: epub, pdf
Publisher: Cambridge University Press
Published: 2015-06-29T23:00:00+00:00

7.2.Moments

In this section we focus on evaluating the moments (mostly the mean and variance) of some shape parameters of tries and digital trees. We do our analysis for binary alphabets but all results can be extended easily to an arbitrary alphabet.

7.2.1.Average path length in a trie by Rice’s method

Let us consider a trie built over n strings generated by a binary memoryless source with p the probability of generating a zero and q = 1 − p. We first deal with the average depth E[Dn] and the average path length E[Ln]. Clearly, E[Ln] = nE[Dn], thus we need to evaluate only one of these parameters. It turns out that the average path length is easier to derive.

Let ln = E[Ln] in a binary trie. It should be easy to see that ln satisfies the following recurrence for n ≥ 2:

(7.5)

with l0 = l1 = 0. Indeed, n strings at the root are split into left and right subtrees according to whether the first symbol of these strings is 0 or 1. The probability that k out of n strings starts with 0 is binomially distributed, i.e., it is equal to

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.