1
$\begingroup$

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?

Improve this question
$\endgroup$
  • 1
    $\begingroup$ You seem to be asking two questions: 1. "does it work like this" and 2. "Isn't there are problem if we do it like this". I think it is better to edit your question to simply state how you think a trie works and then ask only about what you think the problem is with that. This would make it more clear where the source of your confusion lies, I think. $\endgroup$ – Discrete lizard♦ Apr 23 '18 at 14:23
2
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.