Sequencematcher para várias entradas, não apenas duas?

Question

Quer saber a melhor maneira de abordar esse problema em particular e se houver bibliotecas (o Python de preferência, mas posso ser flexível, se necessário).

Eu tenho um arquivo com uma string em cada linha. Eu gostaria de encontrar os padrões mais comuns mais longos e seus locais em cada linha. Sei que posso usar o SequenceMatcher para comparar a linha um e dois, um e três, e depois correlacionar os resultados, mas se houver algo que já o fizer?

Idealmente, essas partidas apareceriam em qualquer lugar de cada linha, mas para começar, posso ficar bem com eles existindo no mesmo deslocamento em cada linha e partir daí. Algo como uma biblioteca de compressão que tem uma boa API para acessar sua tabela de cordas pode ser ideal, mas não encontrei nada até agora que se encaixa nessa descrição.

Por exemplo, com estas linhas:

\x00\x00\x8c\x9e\x28\x28\x62\xf2\x97\x47\x81\x40\x3e\x4b\xa6\x0e\xfe\x8b
\x00\x00\xa8\x23\x2d\x28\x28\x0e\xb3\x47\x81\x40\x3e\x9c\xfa\x0b\x78\xed
\x00\x00\xb5\x30\xed\xe9\xac\x28\x28\x4b\x81\x40\x3e\xe7\xb2\x78\x7d\x3e

Eu gostaria de ver que 0-1 e 10-12 correspondem em todas as linhas na mesma posição e na linha1 [4,5] corresponde à linha2 [5,6] corresponde à linha3 [7,8].

Obrigado,

Answer 1

Se tudo o que você deseja é encontrar substringas comuns que estão no mesmo deslocamento em cada linha, tudo o que você precisa é algo assim:

matches = []
zipped_strings = zip(s1,s2,s3)
startpos = -1
for i in len(zipped_strings):
  c1,c2,c3 = zipped_strings[i]
  # if you're not inside a match, 
  #  look for matching characters and save the match start position
  if startpos==-1 and c1==c2==c3:
    startpos = i
  # if you are inside a match, 
  #  look for non-matching characters, save the match to matches, reset startpos
  elif startpos>-1 and not c1==c2==c3:
    matches.append((startpos,i,s1[startpos:i]))
    # matches will contain (startpos,endpos,matchstring) tuples
    startpos = -1
# if you're still inside a match when you run out of string, save that match too!
if startpos>-1:
  endpos = len(zipped_strings)
  matches.append((startpos,endpos,s1[startpos:endpos]))

Para encontrar o padrão comum mais longo, independentemente da localização, o SequenceMatcher parece a melhor idéia, mas em vez de comparar String1 com String2 e depois String1 com String3 e tentando mesclar os resultados, apenas obtenha todas as substringas comuns de String1 e String2 (com get_matching_blocks) e, em seguida, compare cada resultado disso com String3 para obter correspondências entre as três strings.

Answer 2

O seu problema é o desempenho?

Qual é o tamanho da sua entrada?

O comprimento mínimo das cordas é para corresponder 2?

Observe que seu exemplo não está correto, acho que os resultados que você espera não correspondem às seqüências de amostra que você forneceu.