How does a Trie work?

Question

Specifically, many say that to speed up an HTTP routing code going from regex to a Trie is the solution. Sometimes also a compressed Trie or Radix Tree.

The problem though is that after reading everything I think I could read from Wikipedia to blog articles and even Stack Exchange answers I couldn't wrap my head on how this is implemented. Maybe it's simpler than I think but I'm looking at it from the wrong perspective, no idea.

So let's take this HTTP request:

GET /hello HTTP/1.1 
Host: www.stackoverflow.com 
User-Agent: Mozilla/4.0 (compatible; MSIE5.01; Windows NT)  
Accept: */*

With a Trie are you going to iterate on GET, then "/" then "hello" then "HTTP" then "1.1" etc until you get to the end of the request with matches or does it work differently than this?

               root
           /  /   \  \
         GET POST PUT DELETE
         /
       "/"
       ...
       /
    "HTTP"
      /
     "1"
     /  \
   "0" "1"

I have a hunch that that's not exactly the case because it has the potential to lock a loop or function where it's executed in, or waste resources if event'ed. Given the fact that this solution is considered when the HTTP routing itself becomes a problem it must work differently?

Answer 1

At it's core a trie is a tree-shaped deterministic finite state machine (no loops, no merges). They work best when you have a preset number of keywords to search for.

The root is the start state and the leaves are all final states but each with its own action.

However for parsing the http optimally one wouldn't use a pure trie. BEcause the input is mostly freeform you are better off using a custom state machine.

Answer 2

A trie is the complete decision tree, character after character, corresponding to the acceptance of a string among a set of strings.

For instance for the set {abc, aa, cdf}, the root node accepts {a, c}. Then the son a accepts {a, b} and the son c accepts {d}. And so on.

In the simplest implementation, the sons of a node are linked to by an array of pointers (one per character in the alphabet). So this representation is heavy, but extremely efficient in terms of running time.