Determine a expressão regular mínima da entrada

9

Eu tenho um "agente" remoto que retorna "sim" ou "não" quando recebe uma string. Comunicando-se com este agente é caro, então eu estou esperando para encontrar uma biblioteca que me permita construir iterativamente uma expressão regular, dada feedback positivo e negativo, enquanto sendo inteligente sobre a sua construção. Isso me permitiria armazenar em cache as respostas no lado do envio.

Por exemplo, suponha que consultemos o agente com "bom" e recebamos um "sim". A expressão regular derivada inicial deve ser "boa".

Suponha que eu consulte com "goop" e receba um "sim". Eu esperaria que a expressão regular derivada fosse "goo [dp]", não "boa | goop".

E assim por diante.

Eu não preciso de backtracking ou qualquer outra operação de tempo não linear na minha regex derivada. Presumivelmente, o regex gerado seria um DFA sob o capô. Alguém está ciente de qualquer biblioteca de expressões regulares c / c ++ capaz de fazer isso? Alternativamente, as razões pelas quais isso é uma idéia idiota e melhores soluções para o meu problema real também seriam úteis.

    
por tgoodhart 29.09.2011 в 01:46
fonte

2 respostas

5

Em vez de uma expressão regular, você pode usar uma Trie .

Em seguida, para cada nova string, você percorre o nó de um trio para cada caractere. Eu suspeito que você também queira um caractere marcador para o final da string - assim que você alcançar este caractere, se o nó existir, ele terá a resposta sim / não.

    
por Trejkaz 29.09.2011 / 02:01
fonte
0

Bem, a menos que eu esteja perdendo algo na sua situação, eu acho que a memória é barata o suficiente para apenas implementar um cache burro - digamos, um unordered_map de <std::string, bool> . Não só isso será muito mais fácil de construir, provavelmente será mais rápido também, já que você está construindo um mapa hash. A única desvantagem disso é se você fosse consultar o serviço remoto com um bazillion de chaves diferentes, então essa pode não ser a melhor abordagem.

    
por Matt 29.09.2011 / 01:54
fonte