Decidindo se uma string curinga é completamente correspondida por outra string curinga em um conjunto

9

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 .vwvwvw

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?SvwSvwvS

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 sevwé válido para qualquer itemwenquanto estiver digitalizando. Sevfalhar em nosso teste, adicionevao conjunto e remova oswque marcamos.O(kmn)kmvwwvvw

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.O(logn)O(k)vw

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 .SvwSvw

Idéias que tentei

  • O(n)
  • SS

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!

Christopher Monsanto
fonte
11
Ω(logn)nO(n)o(n)
O(1)vw
O(n)

Respostas:

3

SO(k)

S

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?

Pessoa tímida
fonte
Eu tinha considerado autômatos, sim (o que eu estava fazendo com o trie era semelhante a como alguém aceitaria uma string com um autômato). No entanto, eu não havia encontrado esse trabalho na construção incremental dos referidos autômatos. Vou verificar isso, obrigado pelo ponteiro ShyPerson.
Christopher Monsanto
Eu citei o artigo de Daciuk et al., Porque parecia mais próximo do que você está tentando alcançar. Mas acho que vale a pena mencionar que o problema foi resolvido mais recentemente para autômatos arbitrários de estado finito por Carrasco e Forcada em seu artigo "Construção e manutenção incrementais de autômatos mínimos de estado finito": mitpressjournals.org/doi/abs/10.1162/ ...
ShyPerson 14/04
OK, acho que não vou tirar muito mais deste tópico, por isso estou aceitando sua resposta. Obrigado!
Christopher Monsanto