Tries, a generalized form of digital trees, are a data structure widely used in numerous domains: algorithms for searching words, compression, dynamical hashing, ... Their interest and construction lie in the partitioning of a set of words. We present a compact form of tries, called Patricia tries, in which all unary nodes are suppressed (and thus do not intervene in the partitioning). We then study the means of the memory occupation and of the cost of inserting a word for that data structure when words are produced by a probabilistic source for which the dependencies between the emitted symbols can be very important.
Tr(X)=  ·, Tr 
æ è 

_{[a1]}X 
ö ø 
, Tr 
æ è 

_{[a2]}X 
ö ø 
,... Tr 
æ è 

_{[ar]}X 
ö ø 
. 
Hence with any finite set X of infinite words produced by the same source, we associate a Patricia trie PaTr(X). The first two rules are the same, but the last rule (R'_{2}) is more sophisticated:
Figure 1: Standard trie and corresponding Patricia trie.
PaTr(X)=  ·, PaTr 
æ è 

_{[a1]}X 
ö ø 
, PaTr 
æ è 

_{[a2]}X 
ö ø 
,··· PaTr 
æ è 

_{[ar]}X 
ö ø 
. 


_{[w]}X:= 
æ è 


_{[w]}(x_{1}),···, 


_{[w]}(x_{n}) 
ö ø 
. 
g[X]= 

d_{S}(s)= 
ì í î 

d_{PS}(s)= 
ì í î 

d_{L}(s)= 
ì í î 

d_{PL}(s)= 
ì í î 

Size of Tr S^{^}(n)=å_{wÎS*}( 1(1+(n1)p_{w})(1p_{w})^{n1} ) Path Length of Tr L^{^}(n)=å_{wÎS*}np_{w}( 1(1p_{w})^{n1} ) Size of PaTr S_{P}^{^}(n)=å_{wÎS*}( 1(1p_{w})^{n}å_{iÎS}( (1p_{w}(1p_{[iw]}))^{n}(1p_{w})^{n} ) ) Path Length of PaTr L_{P}^{^}(n)=å_{wÎS*}np_{w}( 1(1p_{w})^{n1}å_{iÎS}p_{[iw]}( 1p_{w}(1p_{[iw]}))^{n1} )
Size of Tr S^{*}(s)=L(s)(s+1)G(s) Path Length of Tr L^{*}(s)=L(s)G(s+1) Size of PaTr S_{P}^{*}(s)=G(s)L_{S}(s) Path Length of PaTr L_{P}^{*}(s)=G(s+1) (L(s)+L_{L}(s))
Figure 2 displays several types of dynamical sources:
Figure 2: Memoryless source, Markov chain of order 1, continued fraction source, heteroclinal source.
G  [f](x):= 

  h_{a}'(x)    f° h_{a}(x), 
G  _{s}[f](x):= 


(x)^{s} f° h_{a}(x). 
G  _{s}[L](x):= 


^{s}[h_{a}](x,y) L  (  h_{a}(x),h_{a}(y)  )  . 
G  _{s}^{[m]}[L]:= 

H_{s}^{[m]}[h_{a}] L° V[h_{a}], 
L(s)= 

p_{w}^{s}=(IdG  _{s})^{1}[Q^{s}](0,1); L^{[k]}(s)= 

(  IdG_{s}^{[k]}  )  ^{1}  [  H_{s}^{[k]}[F]  ]  (  0,1,h_{i}(0),h_{i}(1)  )  . 
(IdG_{s})^{1} = 

P_{s}+(IdN_{s})^{1} ), 

(s1)(IdG_{s})^{1}[L](x)= 

Y_{1}(x)  ó õ 

l(t) dt), 
L(s)=L^{[1]}(s)~ 

+C(S), 
C_{1}(S)  = 


C_{2}(S)  = 

Size of Tr S(n)»1/h(S)n Path Length of Tr L(n)~1/h(S)nlogn +(C(S)g/h(S))n Size of PaTr S_{P}(n)»1/h(S) (1C_{1}(S))n Path Length of PaTr L(n)~1/h(S)nlogn +(C(S)g+C_{2}(S)/h(S))n
h(S)  = 

C(S)  = 


C_{1}(S)  = 

C_{2}(S)  = 

This document was translated from L^{A}T_{E}X by H^{E}V^{E}A.