algoritmo di matching stringa veloce con semplice supporto caratteri jolly

Question

Ho bisogno di abbinare le stringhe di input (URL) nei confronti di un grande insieme (ovunque da 1k-250k) delle regole di stringa con semplice supporto jolly.

Requisiti per il supporto jolly sono i seguenti:

jolly (*) può sostituire solo una "parte" di un URL. Questo è frammenti di un dominio, il percorso, e parametri. Ad esempio, "* .part.part / * / parte? Part = parte & part = *". L'unica eccezione a questa regola è nella zona percorso in cui "/ *" dovrebbe corrispondere nulla dopo la barra.

Esempi:

.
• * site.com/* - deve corrispondere sub.site.com/home.html, sub2.site.com/path/home.html
• sub.site * / percorso / * -. Deve corrispondere sub.site.com/path/home.html, sub.site.net/path/home.html, ma non sub.site.com/home. html

Ulteriori requisiti:

• ricerca veloce (mi rendo conto "veloce" è un termine relativo. Date le regole max 250K, rientrano ancora <1.5s se possibile .)
• Il lavoro nell'ambito di un desktop moderno (ad esempio, non è un server di attuazione)
• capacità di restituire 0: n partite data una stringa di input
• Partite avranno dati della regola ad essi connessi

Qual è il miglior sistema / algoritmo per quali compiti? Sarò sviluppare la soluzione in C ++ con le regole stesse memorizzati in un database SQLite.

Answer 1

Se non mi sbaglio, si può prendere regola d'archi e suddividerlo in dominio, il percorso, e pezzi di query, proprio come se fosse un URL. Poi si può applicare un jolly algoritmo di matching con ciascuno di quei pezzi contro i corrispondenti pezzi gli URL che si desidera testare contro. Se tutti i pezzi corrispondono, la regola è una corrispondenza.

Esempio

Rule: *.site.com/*
    domain => *.site.com
    path   => /*
    query  => [empty]

URL: sub.site.com/path/home.html
    domain => sub.site.com
    path   => /path/home.html
    query  => [empty]

Matching process:
    domain => *.site.com matches sub.site.com?     YES
    path   => /*         matches /path/home.html?  YES
    query  => [empty]    matches [empty]           YES

Result: MATCH

Come si archiviano le regole in un database avrei memorizzarli già suddivisi in quei tre pezzi. E se si vuole super-velocità si potrebbe convertire il * 's per %' s e quindi utilizzare il funzionamento del database nativo LIKE a fare l'abbinamento per voi. Poi si era appena dispone di una query come

SELECT *
FROM   ruleTable
WHERE  @urlDomain LIKE ruleDomain
   AND @urlPath   LIKE rulePath
   AND @urlQuery  LIKE ruleQuery

dove @urlDomain, @urlPath e @urlQuery sono variabili in una dichiarazione preparata. La query restituirebbe le regole che corrispondono a un URL, o un set di risultati vuoto se non corrisponde.

Answer 2

Prima di tutto, una delle peggiori ricerche dello spettacolo che si può fare è con un jolly ad entrambe le estremità della stringa " .dominio.com / path " - e penso che stai andando per colpire questo caso molto. Così la mia prima raccomandazione è quella di invertire l'ordine dei domini come sono memorizzate nel DB: com.domain.example / percorso1 / percorso2 / page.html. Che vi permetterà di tenere le cose molto più ordinata e utilizzare solo i caratteri jolly in "un senso" sulla corda, che fornirà le ricerche molto più veloce.

Credo che Giovanni menziona alcuni buoni punti su come fare tutto questo all'interno del vostro DB. Se questo non funziona vorrei usare una libreria regex in C ++ con l'elenco. Scommetto che otterrà le migliori prestazioni e la sintassi più generale regex in quel modo.