Aqui está um problema que me incomoda há um tempo. Digamos que uma string seja uma sequência de 1s e 0s, e uma string curinga é uma sequência de 1, 0 e? S. Todas as strings e curingas têm o mesmo comprimento. Esses são curingas UNIX padrão; 10 ?? 1 corresponde a 10011, 10111, etc - a? corresponde a 1 ou 0 nessa posição. Se e w são caracteres curinga, então escrevemos v ≤ w se todas as seqüências correspondidas por v também corresponderem a w .
Os problemas : dado um conjunto de sequências curinga e uma consulta v (também uma sequência curinga), existe um w ∈ S tal que v ≤ w ? E se não, podemos adicionar v a S com eficiência?
Aqui está o óbvio solução (ondeké o tamanho das seqüências de caracteres,mé o tamanho da palavra RAM (geralmente 32 ou 64)): analise cada elemento da lista e teste a condição (que pode ser feita em 2 ou 3 operações) usando ajustes de bits). Teste também sev≥wé válido para qualquer itemwenquanto estiver digitalizando. Sevfalhar em nosso teste, adicionevao conjunto e remova oswque marcamos.
Mas isso não é rápido o suficiente. Seria muito legal se houvesse uma solução ou, em um mundo perfeito, complexidade semelhante a uma árvore de raiz ( O ( k ) ). Também é aceitável que as consultas estejam aproximadamente corretas : ou seja, se v ≤ w , retorne sim ou não; mas se a condição não se mantiver definitivamente retorne não.
Embora isso não ajude na pior das hipóteses, você pode assumir que todos os elementos em são limitados por uma string curinga; isto é, existe algum v tal que para todos w ∈ S , v ≥ w .
Idéias que tentei
Trabalho relatado
Na comunidade de rede, esse problema se manifesta como "classificação de pacotes", aqui está uma boa pesquisa dos algoritmos e estruturas de dados conhecidos . Infelizmente, quase sempre é assumido que as sequências curinga correspondem apenas aos prefixos, e a consulta é uma tupla dessas sequências. Obviamente, sempre podemos converter uma string curinga geral para atender a esses critérios: 1? 00? 1 ?? é (1,?, 0, 0,?, 1,?,?). Isso não seria eficiente, no entanto. A outra suposição é que essas tuplas estão associadas a uma "cor" e a consulta deve retornar a cor (não apenas se ela corresponder). Isso torna o problema muito mais difícil, porque temos que ordenar as tuplas (caso contrário, é ambíguo qual de (0,?) E (?, 1) corresponde (0, 1)).
Na comunidade de algoritmos, encontrei muitos resultados relacionados à localização de substrings que correspondem a "não se importa". Esse é um problema consideravelmente mais difícil, e eu realmente não posso usar nenhuma das técnicas.
Em conclusão
Obrigado por qualquer ajuda!
fonte
Respostas:
Quanto à adição de strings à máquina, há alguns trabalhos recentes sobre a alteração gradual de um autômato de estado finito. Veja este artigo de Daciuk et al: "Construção incremental de autômatos de estados finitos acíclicos mínimos".
Isso ajuda?
fonte