Ich möchte einen Algorithmus, der wiederholte Teile von Big-Stack-Traces wie folgt identifizieren kann:
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)
Mit ein wenig Inspektion ist klar, dass dieses Segment dreimal wiederholt wird:
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)
Das Endziel ist, dass ich Stapelspuren rekursiver Funktionen auf schönere Weise ausdrucken kann
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)
Ich bin mir nicht sicher, wie machbar dies ist, aber ich würde mich über alle möglichen Lösungen freuen, selbst wenn sie ihre eigenen Einschränkungen und Einschränkungen haben. Vorläufiges Googeln hat mich nicht gefunden, aber wahrscheinlich weiß ich einfach nicht, was ich googeln soll
quelle
Erstellen Sie einen Suffixbaum mit dem Ukkonen-Algorithmus . Auf diese Weise finden Sie in alle Teilzeichenfolgen im bereitgestellten Text mit Indizes.O (n)
Im Falle einer ungefähren Übereinstimmung gibt es auch eine erweiterte Version des Ukkonen-Algorithmus .
quelle
Wenn Sie der Meinung sind, dass "eine Zeile der Stapelverfolgung" = "ein Zeichen" ist, können Sie Folgendes verwenden:
http://en.wikipedia.org/wiki/Longest_repeated_substring_problem
Eine Möglichkeit, dieses Problem effizient zu lösen, besteht darin, einen Suffix Trie zu erstellen: http://en.wikipedia.org/wiki/Suffix_tree
Jedes Mal, wenn Sie einen bereits festgelegten Pfad durchlaufen, entdecken Sie tatsächlich eine Wiederholung in Ihrer Zeichenfolge.
Listen Sie nun einfach alle Wiederholungen in einer separaten Datenstruktur auf und extrahieren Sie die längste ... oder alle, wenn Sie möchten.
quelle
Ein effizienter String-Faktorisierungsalgorithmus kann helfen. Gegeben eine ZeichenfolgeS. , n = | S.| Maximum finden p so dass S.=T.p z.B T. verkettet p mal rufen wir an T. der Samen und p die Periode . Dies kann in erfolgenO ( n ) Verwenden Sie die Präfixfunktion des (Knuth-) Morris-Pratt-Algorithmus, aber keine Angst vor dem Namen. Es ist ein sehr einfacher und schöner Algorithmus. Hier ist meine Lösung für das entsprechende Problem SPOJ PERIOD .
Mit einer schnellen String-Faktorisierung können wir dann fortfahren, einen String als Verkettung von faktorisierten Chunks (dynamische Programmierung) unter Verwendung einer benutzerdefinierten Kostenfunktion zu zerlegen, z. B. die Gesamtlänge der Samen minimieren, die Summe der Quadrate der Samenlängen minimieren. .
Gesamtkomplexität istO (n2) .
WennÖ(n2) ist viel zu kostspielig. Sie können zu einer gierigen Strategie übergehen, z. B. sobald Sie einen faktorisierbaren Teil finden, ihn zusammendrücken und von diesem Punkt aus fortfahren und auch die maximale Samengröße begrenzen (z | T.| ≤200 ) und beschneiden Sie die Suche, wenn Sie keinen Punkt finden ≥ 2 in den ersten zB 400 Zeichen.
quelle
Rufen
contiguous_repeated_string("abcdefgabcdabcdabcd")
Sie an, Sie werden bekommenabcdabcdabcd
.Rufen
contiguous_repeated_string("ATCGATCGA")
Sie an, Sie werden bekommenATCGATCG
.Und dann können Sie KMPs verwenden
Longest Proper Prefix Postfix array
, um die resultierende Zeichenfolge mit zu faltenO(N)
.Die Gesamtzeitkomplexität beträgt
O(N^2)
.quelle