A compressed trie has nodes including multiple character sub-strings. Such
multiple character storage reduces the number of nodes in the trie,
thereby reducing the amount of memory required for storing the trie and
reducing the amount of time required to perform matching. Furthermore, in
such a compressed trie, sub-strings are stored in a single character
string. Each node references its corresponding sub-string by the
sub-string's starting position and length in the character string.
Multiple nodes may reference a single sub-string. Thus, referencing
rather than storing sub-strings in corresponding nodes eliminates
repetitive sub-string storage, thereby reducing the amount of memory
required for storing the trie.
Un trie comprimé a des noeuds comprenant des sous-chaînes de caractère multiples. Un tel stockage multiple de caractère réduit le nombre de noeuds dans le trie, réduisant de ce fait la quantité de mémoire exigée pour stocker le trie et réduire la quantité de temps requise pour effectuer l'assortiment. En outre, dans un trie si comprimé, des sous-chaînes sont stockées dans une chaîne de caractères simple. Chaque noeud met en référence sa sous-chaîne correspondante par la position du départ de la sous-chaîne et longueur dans la chaîne de caractères. Les noeuds multiples peuvent mettre en référence une sous-chaîne simple. Ainsi, la mise en référence plutôt que de stocker des sous-chaînes dans des noeuds correspondants élimine le stockage réitéré de sous-chaîne, réduisant de ce fait la quantité de mémoire exigée pour stocker le trie.
