crazyinsomniac asked me to clarify what a trie is, and also the module that I meant was the one that RMGir pointed out Regexp::PreSuf, which almost for sure uses a trie implementation to do its business (I havent checked, but...)

So what is a trie? Well the first thing is that 'trie' is short for a 'patricia trie'. And yes crazyinsomniac its a form of tree. First off lets just consider a classic tree, such as a binary tree. (What all this has to do with regexes will become clear a bit later).

In common tree implementations such as a binary tree, each node holds a key. Searching the tree involves comparing the key we are looking for against the key inside of the current node. Based on the relationship (as in greater than less than etc) between the keys we follow the appropriate branch. If the keys are equal we have found our node. If we get to a leaf node without finding the key we are looking for we know the key is not present in the tree. This type of tree has a number of fairly efficient properties, such as inserting and deleting. The efficiency (look ups especially) is bound to N. (Actually its O(log₂N) ). This means that the number of comparisons involved is related to the number of elements in the over all data structure. Also, it may be useful to think of a binary tree as being a tree representation of a binary search (divide and conquor).

A patricia trie (or trie or digit tree or digit trie) is also a tree, however it differs quite radically (no pun intended, (you'll see :-)) from a binary tree in that internal nodes usually do not carry a payload (as in they do not hold a 'key'), only external (leaf nodes) contain data. Instead the structure of the tree (er trie :-) is determined by the digit of the key (at the position correlating to the depth in the trie). In a sense it may be helpful to think of a digit trie as being a tree version of a radix sort (although it doesnt sort explicitly, reading off subkeys in a sorted order would (note the pun)) This may seem a bit opaque so lets look at an example. Lets say we have the following strings 'FOOL','FOOD','FOAM','FEAR','FOLLY' we would turn them into the following structure:

F--+-O--+-O--+-L        (FOOL)
   |    |    |
   |    |    +-D        (FOOD)
   |    |
   |    +-A----M        (FOAM)
   |    |
   |    +-L----L----Y   (FOLLY)
   |
   +-E----A----R        (FEAR)

Now this structure has a number of interesting properties. First off, search efficiency is not a function of the number of items the structure holds, but rather the length of the key we are looking for, which means that it is O(1) for look ups. Unfortunately this wonderful search time (think of it, you could have 10¹² records and still find any element in the same number of steps as there are digits in the longest key) is paid for by a very inefficient use of memory (unless the data is extraordinarily dense and the alphabet for the keys is small,) although a hybrid approach can greatly improve the memory efficiency without impacting the speed significantly. Beside the above interesting properties tries are perfect for creating an efficient regex:

/^F(O(O[LD]|AM|LLY)|EAR)/
[download]

Actually in experiments ive done with a module I should have put on CPAN ages ago, (I'll do it today) Tie::Hash::Trie, when there are many keys it actually turns out that using a normal trie lookup outperforms the equivelent regex (only when anchored at the beginning though). A simple implementation of a trie for this purpose (generating regexes) can be found at RE (tilly) 4: SAS log scanner.

So tries are trees with some funky twists, and with an application toward prefix and suffix matching. (although only one or the other... :-)

Hope that clears things up,

Updated: uc()'d the example. Minor typographic corrections, and left anchored the regex.

Yves / DeMerphq
---
Writing a good benchmark isnt as easy as it might look.

---

---

• Are you posting in the right place? Check out Where do I post X? to know for sure.
• Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:

  <code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>

• Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
• Want more info? How to link or How to display code and escape characters are good places to start.