Procurando um algoritmo para identificar séries repetidas contíguas de linhas em uma sequência longa

Eu gostaria de um algoritmo que possa identificar partes repetidas de grandes rastreamentos de pilha como este:

java.lang.StackOverflowError
at transform.Erasure$Eraser.typed1(Erasure.scala:789)
at typechecker.Typers$Typer.runTyper$1(Typers.scala:5640)
at typechecker.Typers$Typer.typedInternal(Typers.scala:5672)
at typechecker.Typers$Typer.body$2(Typers.scala:5613)
at typechecker.Typers$Typer.typed(Typers.scala:5618)
at typechecker.Typers$Typer.$anonfun$typed1$38(Typers.scala:4752)
at typechecker.Typers$Typer.silent(Typers.scala:700)
at typechecker.Typers$Typer.normalTypedApply$1(Typers.scala:4754)
at typechecker.Typers$Typer.typedApply$1(Typers.scala:4801)
at typechecker.Typers$Typer.typedInAnyMode$1(Typers.scala:5586)
at typechecker.Typers$Typer.typed1(Typers.scala:5603)
at transform.Erasure$Eraser.typed1(Erasure.scala:789)
at typechecker.Typers$Typer.runTyper$1(Typers.scala:5640)
at typechecker.Typers$Typer.typedInternal(Typers.scala:5672)
at typechecker.Typers$Typer.body$2(Typers.scala:5613)
at typechecker.Typers$Typer.typed(Typers.scala:5618)
at typechecker.Typers$Typer.typedQualifier(Typers.scala:5723)
at typechecker.Typers$Typer.typedQualifier(Typers.scala:5731)
at transform.Erasure$Eraser.adaptMember(Erasure.scala:714)
at transform.Erasure$Eraser.typed1(Erasure.scala:789)
at typechecker.Typers$Typer.runTyper$1(Typers.scala:5640)
at typechecker.Typers$Typer.typedInternal(Typers.scala:5672)
at typechecker.Typers$Typer.body$2(Typers.scala:5613)
at typechecker.Typers$Typer.typed(Typers.scala:5618)
at typechecker.Typers$Typer.$anonfun$typed1$38(Typers.scala:4752)
at typechecker.Typers$Typer.silent(Typers.scala:700)
at typechecker.Typers$Typer.normalTypedApply$1(Typers.scala:4754)
at typechecker.Typers$Typer.typedApply$1(Typers.scala:4801)
at typechecker.Typers$Typer.typedInAnyMode$1(Typers.scala:5586)
at typechecker.Typers$Typer.typed1(Typers.scala:5603)
at transform.Erasure$Eraser.typed1(Erasure.scala:789)
at typechecker.Typers$Typer.runTyper$1(Typers.scala:5640)
at typechecker.Typers$Typer.typedInternal(Typers.scala:5672)
at typechecker.Typers$Typer.body$2(Typers.scala:5613)
at typechecker.Typers$Typer.typed(Typers.scala:5618)
at typechecker.Typers$Typer.typedQualifier(Typers.scala:5723)
at typechecker.Typers$Typer.typedQualifier(Typers.scala:5731)
at transform.Erasure$Eraser.adaptMember(Erasure.scala:714)
at transform.Erasure$Eraser.typed1(Erasure.scala:789)
at typechecker.Typers$Typer.runTyper$1(Typers.scala:5640)
at typechecker.Typers$Typer.typedInternal(Typers.scala:5672)
at typechecker.Typers$Typer.body$2(Typers.scala:5613)
at typechecker.Typers$Typer.typed(Typers.scala:5618)
at typechecker.Typers$Typer.$anonfun$typed1$38(Typers.scala:4752)
at typechecker.Typers$Typer.silent(Typers.scala:700)
at typechecker.Typers$Typer.normalTypedApply$1(Typers.scala:4754)
at typechecker.Typers$Typer.typedApply$1(Typers.scala:4801)
at typechecker.Typers$Typer.typedInAnyMode$1(Typers.scala:5586)
at typechecker.Typers$Typer.typed1(Typers.scala:5603)
at transform.Erasure$Eraser.typed1(Erasure.scala:789)
at typechecker.Typers$Typer.runTyper$1(Typers.scala:5640)
at typechecker.Typers$Typer.typedInternal(Typers.scala:5672)
at typechecker.Typers$Typer.body$2(Typers.scala:5613)
at typechecker.Typers$Typer.typed(Typers.scala:5618)
at typechecker.Typers$Typer.typedQualifier(Typers.scala:5723)
at typechecker.Typers$Typer.typedQualifier(Typers.scala:5731)
at transform.Erasure$Eraser.adaptMember(Erasure.scala:714)
at transform.Erasure$Eraser.typed1(Erasure.scala:789)
at typechecker.Typers$Typer.runTyper$1(Typers.scala:5640)
at typechecker.Typers$Typer.typedInternal(Typers.scala:5672)
at typechecker.Typers$Typer.body$2(Typers.scala:5613)
at typechecker.Typers$Typer.typed(Typers.scala:5618)
at typechecker.Typers$Typer.$anonfun$typed1$38(Typers.scala:4752)

Com um pouco de inspeção, fica claro que esse segmento está sendo repetido três vezes:

at typechecker.Typers$Typer.runTyper$1(Typers.scala:5640)
at typechecker.Typers$Typer.typedInternal(Typers.scala:5672)
at typechecker.Typers$Typer.body$2(Typers.scala:5613)
at typechecker.Typers$Typer.typed(Typers.scala:5618)
at typechecker.Typers$Typer.$anonfun$typed1$38(Typers.scala:4752)
at typechecker.Typers$Typer.silent(Typers.scala:700)
at typechecker.Typers$Typer.normalTypedApply$1(Typers.scala:4754)
at typechecker.Typers$Typer.typedApply$1(Typers.scala:4801)
at typechecker.Typers$Typer.typedInAnyMode$1(Typers.scala:5586)
at typechecker.Typers$Typer.typed1(Typers.scala:5603)
at transform.Erasure$Eraser.typed1(Erasure.scala:789)
at typechecker.Typers$Typer.runTyper$1(Typers.scala:5640)
at typechecker.Typers$Typer.typedInternal(Typers.scala:5672)
at typechecker.Typers$Typer.body$2(Typers.scala:5613)
at typechecker.Typers$Typer.typed(Typers.scala:5618)
at typechecker.Typers$Typer.typedQualifier(Typers.scala:5723)
at typechecker.Typers$Typer.typedQualifier(Typers.scala:5731)
at transform.Erasure$Eraser.adaptMember(Erasure.scala:714)
at transform.Erasure$Eraser.typed1(Erasure.scala:789)

O objetivo final é que eu possa imprimir traços de pilha de funções recursivas de uma maneira melhor

java.lang.StackOverflowError
at transform.Erasure$Eraser.typed1(Erasure.scala:789)
------------------------- Repeated 3x -------------------------
at typechecker.Typers$Typer.runTyper$1(Typers.scala:5640)
at typechecker.Typers$Typer.typedInternal(Typers.scala:5672)
at typechecker.Typers$Typer.body$2(Typers.scala:5613)
at typechecker.Typers$Typer.typed(Typers.scala:5618)
at typechecker.Typers$Typer.$anonfun$typed1$38(Typers.scala:4752)
at typechecker.Typers$Typer.silent(Typers.scala:700)
at typechecker.Typers$Typer.normalTypedApply$1(Typers.scala:4754)
at typechecker.Typers$Typer.typedApply$1(Typers.scala:4801)
at typechecker.Typers$Typer.typedInAnyMode$1(Typers.scala:5586)
at typechecker.Typers$Typer.typed1(Typers.scala:5603)
at transform.Erasure$Eraser.typed1(Erasure.scala:789)
at typechecker.Typers$Typer.runTyper$1(Typers.scala:5640)
at typechecker.Typers$Typer.typedInternal(Typers.scala:5672)
at typechecker.Typers$Typer.body$2(Typers.scala:5613)
at typechecker.Typers$Typer.typed(Typers.scala:5618)
at typechecker.Typers$Typer.typedQualifier(Typers.scala:5723)
at typechecker.Typers$Typer.typedQualifier(Typers.scala:5731)
at transform.Erasure$Eraser.adaptMember(Erasure.scala:714)
at transform.Erasure$Eraser.typed1(Erasure.scala:789)
-------------------------------------------------------------
at typechecker.Typers$Typer.runTyper$1(Typers.scala:5640)
at typechecker.Typers$Typer.typedInternal(Typers.scala:5672)
at typechecker.Typers$Typer.body$2(Typers.scala:5613)
at typechecker.Typers$Typer.typed(Typers.scala:5618)
at typechecker.Typers$Typer.$anonfun$typed1$38(Typers.scala:4752)

Não tenho certeza do quanto isso é viável, mas ficaria feliz com todas e quaisquer soluções possíveis, mesmo que elas tenham suas próprias limitações e restrições. O Google preliminar não encontrou nada para mim, mas provavelmente não sei o que pesquisar no Google

Sob circunstâncias normais, a JVM preenche apenas as últimas 1024 chamadas em um rastreamento de pilha, e no Dotty / Scalac a maioria dos fluxos de empilhamento tem um fragmento repetido de comprimento ≈ 70 ou menos. Um stacktrace T de StackOverflowException pode ser decomposto em três partes S · R ^ N · P, em que R é a parte repetitiva do stacktrace, S é um sufixo de R e P é um prefixo de R ou uma sequência não relacionada de chamadas. Estamos interessados ​​em uma solução em que o comprimento total C = | S · R ^ N | da parte de repetição e N são máximos e | S | é mínimo.

// Scala Pseudocode (beware of for comprehensions)
//
// Stack is assumed to be in reverse order, 
// most recent stack frame is last.
val stack: Array[StackTraceElement]
val F: Int // Maximum size of R.

val candidates = for {
  // Enumerate all possible suffixes S.
  S <- ∀ prefix of stack
  if |S| < F

  // Remove the suffix from the stack,
  R <- ∀ non-empty prefix of stack.drop(|S|)
  // Find a fragment that ends with S.
  if R.endsWith(S)

  // Find out how many fragments fit into the stack.
  // (how many times we can remove R from the stack)
  N = coverSize(R, stack.drop(|S|))
  if N >= 2 // Or higher.
} yield (S, R, N)

// Best cover has maximum coverage, 
// minimum fragment length, 
// and minimum suffix length.
val bestCandidate = candidates.maxBy { (S, R, N) =>
  val C = |S| + |R| * N
  return (C, -|R|, -|S|)
}

O algoritmo inteiro pode ser implementado de uma maneira que não aloque nenhuma memória (para manipular o OOM). Possui complexidade O (F ^ 2 | T |), mas as exceções são raras o suficiente e essa é uma pequena constante (F << 1024, T = 1024).

Eu implementei esse algoritmo exato na minha biblioteca https://github.com/alexknvl/tracehash ( https://github.com/alexknvl/tracehash/blob/master/src/main/java/tracehash/internal/SOCoverSolver.java ) com o mesmo objetivo de simplificar erros de scalac / dotc;)

EDIT: Aqui está uma implementação do mesmo algoritmo em Python:

stack = list(reversed([3, 4, 2, 1, 2, 1, 2, 1, 2, 1, 2]))
F = 6

results = []
for slen in range(0, F + 1):
    suffix, stack1 = stack[:slen], stack[slen:]

    for flen in range(1, F + 1):
        fragment = stack1[:flen]

        if fragment[flen - slen:] != suffix:
            continue

        stack2 = stack1[:]
        n = 0
        while stack2[:flen] == fragment:
            stack2 = stack2[flen:]
            n += 1

        if n >= 2: # A heuristic, might want to set it a bit higher.
            results.append((slen, flen, n))

def cost(t):
    s, r, n = t
    c = s + r * n
    return (c, -r, -s)

S, R, N = max(results, key=cost)
print('%s · %s^%d · %s' % (stack[:S], stack[S:S+R], N, stack[S+R*N:]))
# Prints [] · [2, 1]^4 · [2, 4, 3]

EDIT2: Seguindo algumas das idéias da resposta de mukel, aqui está uma função https://gist.github.com/alexknvl/b041099eb5347d728e2dacd1e8caed8c que resolve algo ao longo das linhas de:

stack = a[1]^k[1] · a[2]^k[2] · ...
argmax (sum |a[i]| * k[i] where k[i] >= 2, 
        -sum |a[i]| where k[i] >= 2, 
        -sum |a[i]| where k[i] == 1)

Como é ganancioso, não é necessariamente uma solução ideal, mas parece funcionar razoavelmente bem em casos simples, como, por exemplo,

stack = list(reversed([
  3, 4, 2, 
  1, 2, 1, 2, 1, 2, 1, 2, 
  5, 
  4, 5, 4, 5, 4, 5, 
  3, 3, 3, 3]))

produz uma resposta

[([3], 4), ([5, 4], 3), ([5], 1), ([2, 1], 4), ([2, 4, 3], 1)] 

Construa uma árvore de sufixos usando o algoritmo de Ukkonen , desta maneira em$\mathcal O(n)$ você encontrará todas as substrings no texto fornecido com índices.

No caso de correspondência aproximada, há também uma versão estendida do algoritmo de Ukkonen .

Se você considerar que "uma linha de rastreamento de pilha" = "um caractere", poderá usar:

http://en.wikipedia.org/wiki/Longest_repeated_substring_problem

Uma maneira de resolver esse problema com eficiência é construindo um Suffix Trie: http://en.wikipedia.org/wiki/Suffix_tree

Toda vez que você percorre um caminho já estabelecido, está realmente descobrindo uma repetição em sua string.

Agora, basta listar todas as repetições em uma estrutura de dados separada e extrair a mais longa ... ou todas, se desejar.

Um algoritmo eficiente de fatoração de string pode ajudar. Dada uma string$S$, $n = |S|$ encontre o máximo $p$ de tal modo que $S = T^p$ por exemplo $T$ concatenado $p$ vezes chamamos $T$a semente ep o período . Isso pode ser feito em$O(n)$usando a função prefixo do algoritmo (Knuth-) Morris-Pratt, mas não se assuste com o nome, é um algoritmo muito simples e bonito; aqui está minha solução para o problema correspondente: SPOJ PERIOD .

Armado com uma rápida fatoração de string, podemos então decompor uma string como concatenação de pedaços fatorados (programação dinâmica) usando uma função de custo personalizada, por exemplo, minimizar o comprimento total das sementes, minimizar a soma dos quadrados dos comprimentos das sementes. .

$S = {T_1}^{p_1}{T_2}^{p_2}\cdots{T_k}^{p_k}$

A complexidade total é $O(n^2)$.

E se $O(n^2)$ é muito caro, você pode mudar para uma estratégia gananciosa, por exemplo, assim que encontrar um pedaço fatorável, apertá-lo e continuar a partir desse ponto, além de limitar o tamanho máximo de semente (por exemplo, $|T|\le 200$) e poda a pesquisa se você não encontrar um período $\ge 2$ nos primeiros, por exemplo, 400 caracteres.

  string contiguous_repeated_string(string A){
    string r(1,A[0]);
    for(int i=0;i<A.size();i++){
      for(int l=2;l<=A.size();l++){
        string s=A.substr(i,l);
        if ((s+s).substr(1,2*s.size()-1).find(s)!=s.size()-1 and s.size()>r.size()){
          r=s;
        }
      }
    }
    return r;
  }

Ligue para contiguous_repeated_string("abcdefgabcdabcdabcd")você abcdabcdabcd.

Ligue para contiguous_repeated_string("ATCGATCGA")você ATCGATCG.

E então você pode usar os KMPs Longest Proper Prefix Postfix arraypara dobrar a sequência resultante O(N).

A complexidade do tempo total é O(N^2).