File PatriciaTrie.h

↰ Parent directory (ADS/dictionary)

The Patricia trie with the blind search of Ferragina and Grossi, beyond the book: the compacted trie of a sorted dictionary of n strings [see RadixTree in File Trie.h, whose edges keep their whole labels] stripped of the labels, each edge keeping only its first character (the branching one) and each node the length of the prefix it stands for, so that it takes O( n ) space whatever the length of the strings, which are stored apart (e.g., on disk).

Definition (ADS/dictionary/PatriciaTrie.h)

Detailed Description

The blind search of a pattern P of p characters finds its lexicographic position (the number of strings smaller than P) reading a single string, in three stages:

  • it goes down from the root comparing only the branching characters with the characters of P at the lengths of the nodes, possibly skipping characters that do not match, until a leaf or a node with no edge for P, and takes a leaf l below it;

  • it computes the longest common prefix :math:` ell ` of P and the string s of l, which shares with P a prefix as long as any other string does;

  • it finds on the path the edge :math:` ( u , v ) ` where :math:` ell ` falls, :math:` | s[ u ] | le ell < | s[ v ] | : if :math: ell = | s[ u ] | ` the position of P is among the children of u, by its character :math:` P[ ell ] , else it is just before or just after the strings below v, by the comparison of :math: P[ ell ] ` and :math:` s[ ell ] `.

The two traversals take :math:` O( p log sigma ) ` time with the edges of a node in a sorted array (O( p ) with a perfect hash at each node [see File PerfectHashing.h]) and touch no string, and the comparison reads one string, i.e., :math:` O( p / B ) ` transfers of blocks against the :math:` O( p ) ` of the compacted trie, which reads a label per edge, and the :math:` O( ( p / B ) log n ) ` of the binary search [see File PrefixSearch.h]. The positions of P and of P# give the range of the strings prefixed by P (Theorem 9.8 of the notes). A string that is a prefix of another ends with a character smaller than all the others, the leaf of a string s having length :math:` | s | + 1 `. The trie is built from the sorted strings and the longest common prefixes of adjacent ones in O( N ) time with a stack, N being the characters of the strings.

The contracts [see File Contract.h]: the strings sorted and distinct (an audit); each position r is such that the strings before r are smaller than the pattern (or than P#) and those from r on are not, a postcondition; the invariant is that every node but the root has at least two children and that the children of a node have increasing characters and consecutive strings. The functions are defined in PatriciaTrie.tpp.

  1. Ferragina, Pearls of Algorithm Engineering, Cambridge University Press, 2023, chapter 9 (sections 9.4 and 9.5)

    1. Morrison, PATRICIA: practical algorithm to retrieve information coded in alphanumeric, Journal of the ACM 15(4), 514-534, 1968, doi:10.1145/321479.321481

  1. Ferragina, R. Grossi, The string B-tree: a new data structure for string search in external memory and its applications, Journal of the ACM 46(2), 236-280, 1999, doi:10.1145/301970.301973

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Classes