has external nodes the number of nodes of is (sthe attentive reader may wonder whether the compression of paths provides any significant advantagesince it is offset by corresponding expansion of the node labels indeeda compressed trie is truly advantageous only when it is used as an auxiliary index structure over collection of strings already stored in primary structureand is not required to actually store all the characters of the strings in the collection supposefor examplethat the collection of strings is an array of strings [ ] [ ] [ instead of storing the label of node explicitlywe represent it implicitly by triplet of integers (ijk)such that [ ][ ]that isx is the substring of [iconsisting of the characters from the jth to the kth included (see the example in figure also compare with the standard trie of figure figure (acollection of strings stored in an array (bcompact representation of the compressed trie for this additional compression scheme allows us to reduce the total space for the trie itself from (nfor the standard trie to (sfor the compressed triewhere is the total length of the strings in and is the number of strings in we must still store the different strings in sof coursebut we nevertheless reduce the space for the