Detecção de sobreposição de strings

Como você consegue detectar a sobreposição (overlap) de duas
strings? No caso abaixo, o sufixo de 4 letras da string 1 corresponde ao
prefixo de 4 letras da string 2.

1: "Fire at Will"
2:         "William Riker is number one"

Às vezes existem várias correspondências; encontrar a mais longa não
é sempre algo simples.

1: "Have some CoCo and CoCo"
2:                      "CoCo and CoCo is here."
2:                    "CoCo and CoCo is here."
2:           "CoCo and CoCo is here."

A solução naïve é pegar as menores substrings de cada string,
compará-las, e então sair quando a primeira correspondência for encontrada.
Isso é fácil de programar, bastante confiável, e muito ineficiente para strings
longas.

def commonOverlapNaive(text1, text2):  
  x = min(len(text1), len(text2))  
  while x > 0:  
    if text1[-x:] == text2[:x]:  
      break  
    x -= 1  
  return x 

Uma solução mais eficiente é utilizar uma versão modificada do algoritmo Knuth-Morris-Pratt para escanear as strings enquanto você mantém o
controle das correspondências parciais. Isso é bastante complicado de programar
com várias oportunidades para erros “por um”.

def commonOverlapKmp(text1, text2):  
  # Cache the text lengths to prevent multiple calls.  
  text1_length = len(text1)  
  text2_length = len(text2)  
  # Eliminate the null case.  
  if text1_length == 0 or text2_length == 0:  
    return 0  
  # Truncate the longer string.  
  if text1_length > text2_length:  
    text1 = text1[-text2_length:]  
  elif text1_length < text2_length:  
    text2 = text2[:text1_length]  
  text_length = min(text1_length, text2_length)  
  # Quick check for the worst case.  
  if text1 == text2:  
    return text_length  

  # Build partial match table from text2.  
  table = [0] * text_length  
  table[0] = -1  
  #table[1] = 0  
  pos = 2  
  cnd = 0  
  while pos < text_length:  
    if text2[pos - 1] == text2[cnd]:  
      cnd += 1  
      table[pos] = cnd  
      pos += 1  
    elif cnd > 0:  
      cnd = table[cnd]  
    else:  
      table[pos] = 0  
      pos += 1  

  # Search text1.  
  m = 0  
  i = 0  
  while m + i < text_length:  
    if text2[i] == text1[m + i]:  
      i += 1  
      if m + i == text_length:  
        return i  
    else:  
      m += i - table[i]  
      if table[i] > -1:  
        i = table[i]  
      else:  
        i = 0  
  return 0

Uma abordagem um pouco mais simples
é alavancar a função altamente eficiente indexOf que está construída na maioria
das linguagens (ela é chamada de find no Python). Comece por pressupor uma sobreposição
de uma única letra e procure por aquela letra na segunda string. Se você
encontrá-la, cheque as duas substrings
por igualdade. Então use indexOf para localizar quaisquer instâncias da substring
mais um caractere. Continue repetindo até que nenhuma correspondência seja
encontrada, então retorne a última correspondência confirmada da substring.

def commonOverlapIndexOf(text1, text2):  
  # Cache the text lengths to prevent multiple calls.  
  text1_length = len(text1)  
  text2_length = len(text2)  
  # Eliminate the null case.  
  if text1_length == 0 or text2_length == 0:  
    return 0  
  # Truncate the longer string.  
  if text1_length > text2_length:  
    text1 = text1[-text2_length:]  
  elif text1_length < text2_length:  
    text2 = text2[:text1_length]  
  # Quick check for the worst case.  
  if text1 == text2:  
    return min(text1_length, text2_length)  

  # Start by looking for a single character match  
  # and increase length until no match is found.  
  best = 0  
  length = 1  
  while True:  
    pattern = text1[-length:]  
    found = text2.find(pattern)  
    if found == -1:  
      return best  
    length += found  
    if text1[-length:] == text2[:length]:  
      best = length  
      length += 1

Agora que temos três funções que fazem a mesma coisa, qual delas é mais
rápida? Bom, depende. Vamos adicionar strings aleatórias para cada função,
assim:

cAx&"[|J{aL[xJu081e:(grxnV`kOOe#&`y#AxfA/;o2~WVE1qMUVqk~ ^]>...

O resultado das
parcelas de tempo logarítmicas é bem claro. O algoritmo naïve escala pior que O(n),
apesar de ganhar do KMP até que o comprimento da string chegue a 10.000. O KMP
está solidamente O(n), como anunciado. O algoritmo IndexOf também está O(n) –
mas 100 vezes mais rápido que o KMP.

No entanto, o algoritmo IndexOf se apoia no fato de que não existem muitas
correspondências coincidentes. Vamos ver o que acontece se adicionarmos uma
input string patológica, como esta:

baaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

 As parcelas de tempo
logarítmicas resultantes mostram uma mudança repentina de comportamento. Os
algoritmos naïve e KMP não mudaram, enquanto o IndexOf se tornou o pior de
todos.

Agora temos um problema. O
melhor algoritmo pode se tornar o pior algoritmo, dependendo dos inputs. O KPM
oferece uma solução consistentemente escalável independentemente do input, mas a um
custo potencial de 100x a performance. Vamos olhar mais de perto os inputs.
Conseguimos recriar o comportamento patológico com dados do mundo real? Vamos
começar criando strings fractal com muitas repetições, assim:

N>NeN>N`N>NeN>NVN>NeN>N`N>NeN>NRN>NeN>N`N>NeN>NVN>NeN>N`N>Ne...

Isso é parecido com
padrões encontrados no código-fonte. As parcelas de tempo logarítmicas
resultantes mostram que a performance retorna níveis quase otimizados.

Um grande uso da manipulação
de strings nos dias de hoje é no mundo da genética. O DNA tem um alfabeto de 4
letras, A, C, G e T. Isso irá certamente resultar em um grande numero de
correspondências coincidentes. Vamos fazer o download do genoma humano,
assim:

TCGGTCTCCTTTGGGTAATTTTCCATTATGTCATAACAGTAAATATTAATATGTGCTCCT...

As parcelas de tempo
logarítmicas resultantes mostram mais uma vez que isso é quase ideal. Eu
adicionei com um quinto do genoma e consegui uma resposta em 15 segundos.

A Ciência da Computação
(sempre suspeite de que qualquer disciplina que precise adicionar a palavra
‘ciência’ no nome) muitas vezes é um exercício de compromissos. Você deve
escolher o algoritmo que funciona melhor na maioria das vezes (IndexOf)? Você
deve escolher o algoritmo que nunca irá falhar feio (KMP)? Você deve escolher o
algoritmo que é mais fácil de programar e menos provável de conter bug (Naïve)? Você desova uma de duas
threads, cada uma executando diferentes algoritmos para serem executados em
diferentes processadores com o vencedor acabando com o perdedor?

Agradecimentos especiais a Tancred
Lindholm por sempre perguntar questões estranhas toda vez que eu pensava que
havia terminado.

?

Texto original disponível em http://neil.fraser.name/news/2010/11/04/