algoritmo rápido cadeia correspondente com suporte simples wildcards

Question

Eu preciso corresponder cadeias de entrada (URLs) contra um grande conjunto (em qualquer lugar de 1k-250k) de regras de cordas com apoio de curinga simples.

Requisitos para apoio de curinga são os seguintes:

Wildcard (*) só pode substituir uma "parte" de uma URL. Isso é fragmentos de um domínio, caminho e parâmetros. Por exemplo, "* .part.part / * / parte? Part = parte e parte = *". A única exceção a esta regra é na área de caminho onde "/ *" deve coincidir com qualquer coisa depois da barra.

Exemplos:

• * site.com/* -. Deve corresponder sub.site.com/home.html, sub2.site.com/path/home.html
.
• sub.site * / path / * - deve corresponder sub.site.com/path/home.html, sub.site.net/path/home.html, mas não sub.site.com/home. html

Requisitos adicionais:

• pesquisa rápida (eu percebo "rápido" é um termo relativo. Dadas as max 250k regras, ainda caem dentro <1.5s se possível .)
• Trabalho no âmbito de um desktop moderno (por exemplo, não uma implementação de servidor)
• Capacidade de retornar 0: n corresponde dada uma seqüência de entrada
• Partidas terá dados da regra que lhes são inerentes

O que é o melhor sistema / algoritmo para tais como tarefa? I será o desenvolvimento da solução em C ++ com as próprias regras armazenadas em um banco de dados SQLite.

Answer 1

Se não me engano, você pode tomar regra corda e dividi-lo em domínio, caminho e pedaços de consulta, assim como é uma URL. Então você pode aplicar um padrão curinga correspondência algoritmo com cada uma dessas peças contra as peças correspondentes a partir das URLs que você deseja testar. Se todas as peças iguais, a regra é um jogo.

Exemplo

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

Como você está armazenando as regras em um banco de dados que eu iria armazená-los já quebrado em esses três pedaços. E se você quiser super-velocidade que você poderia converter o * da % do e, em seguida, usar a operação LIKE nativa do banco de dados para fazer a correspondência para você. Então você só tem uma consulta como

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

onde @urlDomain, @urlPath e @urlQuery são variáveis ??em uma declaração preparada. A consulta retornaria as regras que correspondam a um URL, ou um conjunto de resultados vazio se partidas nada.

Answer 2

Em primeiro lugar, um dos piores pesquisas desempenho que você pode fazer é com um curinga em ambas as extremidades da cadeia " .domain.com / path " - e eu acho que você vai para bater neste caso muito. Assim, a minha primeira recomendação é para inverter a ordem dos domínios como eles estão armazenados na DB: com.domain.example / path1 / path2 / page.html. Isso vai permitir que você mantenha as coisas muito mais arrumado e só usar curingas em "uma direção" na corda, que irá fornecer pesquisas muito mais rápido.

Eu acho que John menciona alguns bons pontos sobre como fazer isso tudo dentro de seu DB. Se isso não funcionar, eu usaria uma biblioteca regex em C ++ contra a lista. Aposto que você vai obter a melhor performance e mais sintaxe geral regex dessa forma.