0

I have a list of domain name that contains wildcard ('*' character)

Example:

  • *.google.com

  • *.domain.com

  • ...

It contains nearly 1 million domains.

The data will be stored on a mongodb or redis database.

Given a domain name, such as "abc.domain.com", I need an algorithm that will check the data for a match.

For example, with list above:

  • "abc.domain.com" has a match to *.domain.com.

  • "xyz.domain.com" also matches against *.domain.com.

  • "abc.domain.com.xyz" does not match as the .xyz breaks the rule (if the rule was *.domain.com.* the first two wouldn't match, but this one would)

Given the above, what algorithm will yield me the quickest results for this problem?

Thanks,

  • 2
    It is more a search then an algorithm. This is a bit of an XY problem. – paparazzo Oct 26 '16 at 13:19
1

The quickest algorithm for matching a *.<any>.* pattern is to just find .<any>.:

function match(pattern, url) {
  var matchUrl;

  if (pattern[0] === '*') {
    matchUrl = pattern.substring(1);
  }
  if (pattern.length !== 0 && pattern[pattern.length-1] === '*') {
    matchUrl = pattern.substring(0, matchUrl.length-1);
  }
  return url.indexOf(matchUrl) !== -1;
}
1

If you can put the domain strings into an in-memory data structure, you will have many options. For example, you can sort them or hash them, and lookups will be quite reasonable.

However, if you manually fetch all the rows from the database so you can perform a match test against each one, the performance of the match will probably pale in comparison to the query overhead.

The alternative is to ask the database to do the search for you, so you should look to see if mongo or redis provide a regular expression or some wild card match operator in their query capabilities.

Still, the best will be if you can preprocess the list into a dedicated data structure.

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.