---

Geschrieben von Johannes1st am 31.01.2018 um 11:27:

  effektive Suchalgorithmen

Meine Frage:
Gegeben ist ein sehr langer String(ca. 200.000 Zeichen und mehr) in dem es gilt bestimmte Substrings zu finden, sprich in ababab gilt es aha zu finde so kommt man zum Schluss [0,2]. Großes Problem ist das sich Teile im String dessen Länge unbekannt ist sekündlich (sehr oft) ändern -> ababab wird ababac usw. Dabei geht ja lediglich ein teil der Information verloren welche wir durch eine vorherige Suche erhalten haben. Gibt es schnelle Verfahren wie man diese Problem lösen kann? (Ich schätze durch KI kann man einen besseren Weg finden.)

Meine Ideen:
Meine bisherige Lösung sieht vor den kompletten String in einen Suffixbaum zu überführen, mit dem dann die Suche sehr einfach geht. Ebenfalls habe ich die Suffixbaumkonstruktion in linearer Zeit (Ukkonen) implementiert.
Nur ist dies nicht sehr schön gelöst da jedes mal ein neuer Baum erstellt werden muss wenn dich der String maßgeblich ändert. Meist lässt sich die zu extrahierende Stelle, also das Vorkommen des Wortes auf bestimmte Bereiche eingrenzen -> ein Algorithmus der immer weiter lernt (Kombi mit neuronalem Netz?)

---

Geschrieben von eulerscheZahl am 31.01.2018 um 18:42:

 

Ist diese Aufgabe etwa, was du suchst?
Hier ist eine entsprechende Lösung dazu.