3

So, quite often I'll come across a situation where I'd like to process hostnames in a hierarchical manner.

For example, given a hostname "foo.bar.baz.example.com", I might want to compare it against a data structure that contains a higher authority like "example.com" or "baz.example.com" and see if I get a match.

Usually, the way I handle this is to simply use a hashtable, and iteratively remove subdomains until I find a match (or, never find a match, whatever the case may be.)

But, I was thinking that something like a trie/prefix-tree might be a lot better suited for this (if I were to reverse the domain labels).

Of course, the problem is that a trie usually works on individual characters - whereas in this case I'd want to make each subdomain (or "label", in DNS-speak), a single "unit".

Is there a data-structure that might be well suited for something like this?

2
  • 3
    A reversed prefix tree is a suffix tree... and who says you have to only use a single character for the suffix?
    – user40980
    Oct 21, 2014 at 17:04
  • this was fun dotnetfiddle.net/ihB8FQ <-- functional approach Oct 21, 2014 at 21:44

1 Answer 1

3

Use a tree, where each node will be a subdomain. The top level will be the start symbol. Then it would branch into k nodes, where k is the number of top level domains you have.

For instance, if your entire database was two entities: foo.bar.example.com and boo.car.ample.net, k will be 2 (net and com). Each of net and com nodes will have one children each: ample and example. And so on.

As an another example, let's consider you have only two entities again. But this time it's foo.bar.example.com and boo.bar.example.com. Now the tree would be something like this.

                                      root
                                       |       
                                      com
                                       |
                                    example
                                       |
                                      bar 
                                    /     \
                                  foo     boo

This will be your tree. If you the input is example.com, you would split by '.' and reverse to get [com, example]. You will go down your tree by matching the list with the tree. Since 'com' is a child of root, you take that path, and from 'com', you search for the next element in your input list 'example'. Since 'example' is a child of 'com' in the tree, we proceed. But now we have exhausted the input list and this means we found a match. At any point in the traversal, if you don't find a child for the current input element from the list, you are guaranteed that there is no match in your database. For instance if you got the input string zoo.bar.example.com. Our input list will be [com, example, bar, zoo]. We would traverse the tree until bar, but in the tree 'bar' doesn't have a child 'zoo'. This implies we don't have zoo.bar.example.com in our database.

You can find a match within O(n), where n is the number of subdomains in your input string that you're trying to match.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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