position tree

views updated

position tree Let α = a1a2an denote a string, or word, in the set of all Σ-words, Σ*, and let # be in the alphabet Σ. Then the position tree T(α) for α# is a tree whose edges are labeled with elements of Σ ∪ {#}

and is constructed according to the following rules:

(a) T(α) has (n+1) leaves labeled 1, 2,…, n+1

(see diagram);

(b) the sequence of labels on the edges of the path from the root to the leaf labeled i is the substring identifier for position i in α#.