zbMATH — the first resource for mathematics

Some results on V-ary asymmetric tries. (English) Zbl 0637.68072
Tries (radix search tries) find many applications in computer science and telecommunications. It is assumed that a trie is built over an alphabet \(U=\{\sigma_ 1,...,\sigma_ V\}\) (V-ary trie), and n (possible infinite) strings of elements from U (i.e., keys) are stored in external nodes of the trie. The occurrence of an element \(\sigma_ i\) in a key is represented by a probability \(p_ i\) (asymmetric trie). Our main interest is to compute all moments of the depth of a leaf (external node) in a random family of tries.
By solving a system of recurrences we find an exact formula for all factorial moments of the depth, and - using the Mellin transform technique - we derive asymptotic approximations for them. We prove that the mth factorial moment of the depth of a leaf in a trie with n keys is equal to \(\alpha\) ln\({}^ m n+\beta \ln^{m-1} n+O(\ln^{m-2} n)\), where the constants \(\alpha\) and \(\beta\) are functions of the probabilities, \(p_ i\), \(i=1,...,V\). In particular, we show that for symmetric tries the variance of the depth is O(1), while for asymmetric tries it is \(\alpha\) ln n\(+O(1)\), and we determine explicitly the constant O(1).
These results extend previous analyses by D. Knuth [The art of computer programming. Vol. 3: S25-29 (1986).
[For the entire collection see Zbl 0578.00003.]
Let’s start with the definitions of some notions considered in the paper. An infix code is a nonempty subset C of \(X^+\) such that \((xuy\in C \& u\in C \Rightarrow x=y=1).\) If \(L\subset X^*\), \(u\in X^*\) let \(L..u=\{(x,y)|\) \(x,y\in X^*\), xuy\(\in L\}\). The syntactic congruence \(P_ L\) is defined by \(u\equiv v (P_ L)\Leftrightarrow\) \(L..u=L..v \). The syntactic monoid of L is \(syn(L)=X^*/P_ L.\)
The first part of the paper establishes the following results related to an infix code C: (1) syn(C) is subdirectly irreducible; (2) if C is finite, then syn(C) is a finite subdirectly irreducible nil monoid and \(| syn(C)| \geq 3\); (3) conversely, every finite subdirectly irreducible nil monoid M with \(| M| \geq 3\) is isomorphic with syn(C) where C is finite; (4) if C is infinite context-free then syn(C) is not a nil monoid; (5) if C is infinite (but not context-free) then syn(C) can still be a nil monoid - even an infinite one - as in the case of Thue code.
The second part is devoted to the study of the reflective infix codes in relations with star reflective codes.
Reviewer: V.Coardoş

68P10 Searching and sorting
68Q25 Analysis of algorithms and problem complexity
60D05 Geometric probability and stochastic geometry
68Q45 Formal languages and automata
Full Text: DOI