Algoritmo per cercare un nome di dominio nell'elenco di caratteri jolly

Question

Algoritmo per cercare un nome di dominio nell'elenco di caratteri jolly

Naviga le tue risposte

#1 da (2 voti)
#2 da (1 voti)

0

Ho un elenco di nomi di dominio che contiene caratteri jolly ( '*' )

Esempio:

*. Google.com
*. Domain.com
...

Contiene circa 1 milione di domini.

I dati verranno archiviati su un database mongodb o redis .

Dato un nome di dominio, come " abc.domain.com ", ho bisogno di un algoritmo che verificherà i dati per una corrispondenza.

Ad esempio, con l'elenco sopra:

" abc.domain.com " ha una corrispondenza con *. dominio.com .
" xyz.domain.com " corrisponde anche a *. domain.com .
" abc.domain.com.xyz " non corrisponde a quanto .xyz infrange la regola (se la regola era *.domain.com. * la prima due non corrisponderebbero, ma questo sarebbe)

Considerato quanto sopra, quale algoritmo mi fornirà i risultati più rapidi per questo problema?

Grazie,

algorithms optimization mongodb redis

posta VuHoang 26.10.2016 - 05:09

fonte

2 risposte

Leggi altre domande sui tag algorithms optimization mongodb redis

Design pattern per classe di servizio java [chiuso] Enigma di ereditarietà e polimorfismo

score 2 · Answer 1

L'algoritmo più veloce per la corrispondenza con un modello *.<any>.* consiste nel trovare solo .<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;
}

score 1 · Answer 2

Se puoi mettere le stringhe del dominio in una struttura dati in memoria, avrai molte opzioni. Ad esempio, puoi ordinarli o cancellarli, e le ricerche saranno abbastanza ragionevoli.

Tuttavia, se recuperi tutte le righe manualmente dal database in modo da poter eseguire un test di corrispondenza su ciascuna di esse, le prestazioni della corrispondenza saranno probabilmente più chiare rispetto al sovraccarico della query.

L'alternativa è chiedere al database di fare la ricerca per te, quindi dovresti cercare di vedere se mongo o redis forniscono un'espressione regolare o qualche operatore di corrispondenza con caratteri jolly nelle loro funzionalità di query.

Tuttavia, il migliore sarà se si può pre-elaborare l'elenco in una struttura dati dedicata.