Tries are a basic digital searching data structure (Knuth, D, The Art of Computer Programming: Sorting and Searching, Volume 3, 2ed, pp492-496). Please note that this code is not general purpose in that it only supports base 10 tries. Although it would be easily possible to enhance the code to other bases, we are dealing exclusively with numeric prefixes. We use a base 10 Trie as part of our verification of phone numbers. Although not theoretically optimal tries give us most of the speed of a hash based solution in a compact enough space and are well suited to the problem of parsing telephone numbers.
Phone numbers are typically constructed from a country code, an area or carrier code, and a local number. The lengths of each of these parts are variable, and are always encoded in base 10 numbers. The Trie data structure consists of a table which tells you which row in the table to go to next when a number matches as you progress through the string. This is fairly analogous to the process that electro mechanical stepper relays performed when automatic telephone exchanges where first built. Numbering plans still tend to reflect this prefix property.
Source code for our triemaker is found in the triemaker.tar.gz file. The README file contains examples of C, Perl and PHP code that access the Trie data structure.