Algoritmo de correspondência rápida de cadeias de incompatibilidade k

Eu estou procurando um algoritmo de correspondência de seqüência k-incompatibilidade rápida. Dada uma string padrão P de comprimento me uma string de texto T de comprimento n, preciso de um algoritmo rápido (tempo linear) para encontrar todas as posições em que P corresponde a uma subcadeia de T com no máximo k incompatibilidades. Isso é diferente do problema das diferenças k (distância de edição). Uma incompatibilidade implica a subcadeia e o padrão tem uma letra diferente na maioria das k posições. Eu realmente preciso apenas de k = 1 (no máximo 1 incompatibilidade), portanto, um algoritmo rápido para o caso específico de k = 1 também será suficiente. O tamanho do alfabeto é 26 (texto em inglês que não diferencia maiúsculas de minúsculas); portanto, o requisito de espaço não deve aumentar muito rapidamente com o tamanho do alfabeto (por exemplo, acredito que o algoritmo FAAST ocupa espaço exponencial no tamanho do alfabeto e, portanto, é adequado apenas para sequências de proteínas e genes).

Uma abordagem dinâmica baseada em programação tenderá a ser O (mn) no pior caso, o que será muito lento. Acredito que há modificações no algoritmo de Boyer-Moore para isso, mas não sou capaz de colocar minhas mãos em tais documentos. Não tenho assinatura para acessar periódicos ou publicações acadêmicas; portanto, todas as referências deverão ser de domínio público.

Eu gostaria muito de receber dicas, referências a documentos disponíveis gratuitamente ou o próprio algoritmo para esse problema.

algorithms reference-request strings string-metrics substrings Paresh
fonte

Se o padrão for fixo (mas o texto a corresponder variar), você poderá criar um autômato finito e executar o texto através dele. Também existem algoritmos usando árvores de sufixo (geralmente bom se o texto for constante e o padrão variar, mas também aplicável se os dois variarem), você poderá encontrar algumas referências na Web. (Ainda não estou adicionando uma resposta, pois não tenho muita certeza dos algoritmos baseados em árvore de sufixos, se alguém souber, sinta-se à vontade para ignorar esse comentário).

Aryabhata

@Aryabhata Thanks! O padrão e o texto mudam. Nesse contexto, construir um autômato finito seria muito caro, especialmente ao incluir o escopo de 1 incompatibilidade. Quanto às árvores de sufixos / matrizes de sufixos, nunca as usei e sei pouco sobre elas, mas fiquei com a impressão de que elas são lentas na construção e eficientes principalmente para a correspondência exata. Mas vou explorar mais essa opção. Qualquer ponteiro nessa direção ou em qualquer outra direção seria mais útil!

Paresh

Não, árvores de sufixo também podem ser usadas para correspondências aproximadas. Pelo menos o wiki afirma: en.wikipedia.org/wiki/Suffix_tree

Aryabhata

Respostas:

Matrizes de sufixo podem ser usadas para esse problema. Eles contêm as posições iniciais de cada sufixo da sequência classificada em ordem lexicográfica. Mesmo que eles possam ser construídos ingenuamente na complexidade , existem métodos para construí-los na complexidade . Veja, por exemplo, isto e isto . Vamos chamar esse conjunto de sufixos SA. $O(n\log n)$ $\Theta(n)$

Depois que a matriz de sufixos foi construída, precisamos construir uma matriz LCP (Longest Common Prefix) para a matriz de sufixos. A matriz LCP armazena o comprimento do prefixo comum mais longo entre dois prefixos consecutivos na matriz de sufixos (sufixos consecutivos lexicográficos). Assim, o LCP [i] contém o comprimento do maior prefixo comum entre SA [i] e SA [i + 1]. Essa matriz também pode ser construída em tempo linear: veja aqui , aqui e aqui algumas boas referências.

Agora, para calcular o comprimento do prefixo mais longo comum a quaisquer dois sufixos na árvore de sufixos (em vez de sufixos consecutivos), precisamos usar alguma estrutura de dados RMQ . Mostrou-se nas referências acima (e pode ser visto facilmente se a matriz é visualizada como uma árvore de sufixos), que o comprimento da mais longa prefixo comum entre dois sufixos tendo posições e ( ) na matriz de sufixo , pode ser obtido como . Um bom RMQ pode pré-processar a matriz em ou e responder a consultas no formato em $u$ $v$ $u < v$ $min_{u<=k<=v-1}{LCP[k]}$ $LCP$ $O(n)$ $O(n\log n)$ $LCP[u, v]$ $O(1)$ Tempo. Veja aqui um algoritmo RMQ succint e aqui um bom tutorial sobre RMQs e o relacionamento (e reduções) entre LCA e RMQs. Isso tem outra boa abordagem alternativa.

Com essas informações, construímos a matriz de sufixos e matrizes associadas (como descrito acima) para a concatenação das duas seqüências com um delimitador no meio (como T # P, onde '#' não ocorre em nenhuma das seqüências). Em seguida, podemos executar a correspondência de k de incompatibilidade de caracteres usando o método "canguru". Isso e isso explicam o método canguru no contexto das árvores de sufixos, mas também podem ser diretamente aplicados às matrizes de sufixos. Para cada índice do texto , encontre o do sufixo de começando em o sufixo de iniciando em 0. Isso fornece o local após o qual a primeira incompatibilidade ocorre ao corresponder $i$ $T$ $LCP$ $T$ $i$ $P$ $P$ com . Seja esse comprimento . Pule o caractere incompatível em e e tente combinar as seqüências restantes. Ou seja, encontre novamente o de e . Repita isso até obter incompatibilidades, ou qualquer uma das seqüências termina. Cada é . Existem 's para cada índice de , dando a isso uma complexidade total de . $T[i]$ $l_0$ $T$ $P$ $LCP$ $T[i + l_0 + 1]$ $P[l_0 + 1]$ $k$ $LCP$ $O(1)$ $O(k)$ $LCP$ $i$ $T$ $O(nk)$

Eu usei um RMQ mais fácil de implementar, fornecendo uma complexidade total de ou se , mas também pode ser feito em como descrito acima. Pode haver outros métodos diretos para esse problema, mas essa é uma abordagem poderosa e genérica que pode ser aplicada a muitos problemas semelhantes. $O(nk + (n+m)\log(n+m))$ $O(nk + n\log n)$ $m = O(n)$ $O(nk)$

Paresh
fonte

Ótimo! Eu tenho alguma leitura na minha lista TODO agora :-)

Aryabhata

O link siam.org no segundo parágrafo está quebrado, mas o papel vinculado pode ser encontrada aqui epubs.siam.org/doi/pdf/10.1137/1.9781611972917.3

leecbaker

Abaixo está um algoritmo esperado (que pode ser estendido para outro , tornando-o ). (Ainda não fiz os cálculos para provar que é assim). $\mathcal{O}(n + m )$ $k$ $\mathcal{O}(nk +m )$

A idéia é semelhante ao algoritmo de hash de rolamento Rabin-Karp para correspondências exatas de substring.

A idéia é separar cada sequência de comprimento em blocos de tamanho cada e calcular o hash de rolagem para cada bloco (fornecendo valores de hash) e comparar esses valores de com o padrão. $m$ $2k$ $m/2k$ $2k$ $2k$

Permitimos no máximo desencontros nesses valores. $k$

Se ocorrerem mais de incompatibilidades, rejeitamos e seguimos em frente. Caso contrário, tentamos confirmar uma correspondência aproximada. $k$

Espero (ressalva: ainda não tentei) que isso provavelmente será mais rápido na prática e talvez mais fácil de codificar / manter do que usar uma abordagem baseada em árvore de sufixos.

Aryabhata
fonte

Só preciso de um esclarecimento. Por "..separar cada cadeia de comprimento m em 2k blocos de m / 2k de tamanho cada ...", você quer dizer que separa cada substring de comprimento m em T (de comprimento n) em 2k blocos. E esse hash pode ser calculado em O (n) pelo método de hash rotativo. Em seguida, a sequência de padrões também será dividida em blocos de 2k e os hashes correspondentes serão comparados, permitindo que no máximo k blocos sejam incompatíveis. Nesse caso, poderíamos descartar todos os casos em que o número de incompatibilidades é maior que k. Eu entendi certo?

Paresh

@Paresh: Sim, você acertou, exceto porque existem hashes, é , em vez de .

k

$k$

Ω (n k)

$\Omega(nk)$

O (n)

$O(n)$

Aryabhata

Eu gosto dessa abordagem! No entanto, essa abordagem é rápida em geral, mas degrada para O (mnk) se o número de correspondências for alto (O (n) correspondências). Mantendo isso em mente, mantive dois hashes rotativos, supondo que ambos não possam ter uma colisão para a mesma entrada (não fiz isso matematicamente, pois queria ver a velocidade). Dessa forma, não precisamos verificar uma correspondência char a char se os dois hashes concordarem. Isso é bastante rápido em geral, mas também é lento se o número de correspondências for grande. Com isso e da maneira que você sugeriu, demorou para grandes partidas.

Paresh

Isso poderia ser feito mais rapidamente, na pior das hipóteses, se dividirmos o texto em blocos de tamanho vez de blocos de . O padrão também será dividido em blocos (+1 se não for quadrado perfeito) e comparamos cada um dos blocos. Isso será mais lento que a sua abordagem se o número de incompatibilidades for pequeno, mas acho que deve ser no pior caso (ainda não verifiquei isso corretamente). Eu não tentei isso, mas primeiro explorarei árvores / matrizes de sufixo, como você sugeriu. Eles parecem oferecer bons limites. Obrigado!

\sqrt{m}

$\sqrt{m}$

m / 2 k

$m/2k$

\sqrt{m}

$\sqrt{m}$

O (n k \sqrt{m})

$O(nk\sqrt{m})$

Paresh

@Paresh: Você não pode vê-lo (no histórico de revisões), mas eu inicialmente tinha a abordagem , mas a alterei para a atual. Eu acho que usar é melhor. Você está computando desnecessariamente muitos valores de hash. Obviamente, o que é melhor depende dos seus dados. É claro que, em vez de , você pode também tentar ou etc. btw, pior caso é para ambos e abordagens ...

\sqrt{m}

$\sqrt{m}$

m / 2 k

$m/2k$

2 k

$2k$

k + 1

$k+1$

k + c

$k+c$

Ω (n m)

$\Omega(nm)$

\sqrt{m}

$\sqrt{m}$

m / 2 k

$m/2k$

Aryabhata