Correspondência de padrões com não se importa: vários padrões

9

O artigo SODA de duas páginas da Kalai fornece um algoritmo simples e eficiente para a correspondência de padrões com não se preocupa (caracteres curinga que correspondem a um caractere). Em essência, é tão fácil quanto a convolução.

Mas o que acontece se estivermos procurando por vários padrões com não se importa? Ainda podemos de alguma forma resolvê-lo com, por exemplo, técnicas baseadas em FFT?

Jukka Suomela
fonte

Respostas:

5

Para o caso de múltiplos padrões, parece que a simples varredura de cada uma delas pode ser a melhor solução possível, pelo menos a menos que a forte hipótese de tempo exponencial falhe.

Lembre-se de que, dado os conjuntos e T 1 , T 2 , , T n sobre o universo [ m ] , se pudéssemos decidir se existem S i e T j tais que S iT j = [ m ] no tempo O ( n 2 - ε poli ( m ) )S1 1,S2,...,SnT1 1,T2,...,Tn[m]SEuTjSEuTj=[m]O(n2-εpoli(m)), então SETH falha, ou seja, temos um algoritmo CNF-SAT com tempo de execução .O(2(1 1-ε/2)n)

Dados os conjuntos e T 1 , T 2 , , T n , codificamos o problema acima como correspondência de vários padrões com não se preocupa com o alfabeto binário da seguinte maneira:S1 1,S2,...,SnT1 1,T2,...,Tn

  • O texto é Onde [ T I ] é a codificação natural de t i como uma cadeia binária.
    1 1[T1 1]10m+21 1[T2]10m+2...0 0m+21 1[Tn]1 1,
    [TEu]TEu
  • Temos padrões de forma 1 S i1 , onde S i é uma cadeia y = y 1 y 2 ... y m tal que y j = 1 se j S i e y j = * se j S i (aqui é o símbolo de não se importar).n1 1SEu1 1SEuy=y1 1y2...ymyj=1 1jSEuyj=jSEu

Agora é claro que um padrão pode coincidir com o texto em uma ocorrência de 1 [ T j ] 1 , e somente quando S iT j = [ m ] . O comprimento total dos padrões e o comprimento do texto são O ( n m ) , por exemplo, um algoritmo de passagem única quase linear para vários padrões daria melhorias substanciais em relação aos algoritmos CNF-SAT mais conhecidos ...1 1SEu1 11 1[Tj]1 1SEuTj=[m]O(nm)

(Observe que isso não diz nada sobre algoritmos que usam muito tempo para pré-processar os padrões, digamos, quadráticos na duração total dos padrões.)

Janne H. Korhonen
fonte