Analysieren langer Strings/Zeichenketten

[Bleiglanz]

@Oneric

Mir fiele momentan nur eine Implementierung ein, in der in einem einzelnen Suchdurchlauf der Suchstring konstant bleibt. Vielleicht ändert sich das aber noch wenn ich mir das suffix-sorting mal genauer angesehen habe.

Mir fiele momentan nur ein, dass ich schon lange mal ein Buch über Präzision schreiben wollte. Was soll das heißen, mir fiele ein?

Hast du keine präzise Vorgabe, weißt du gar nicht genau, was du machen willst?

Wenn das so ist, also wenn VOR der Suchaktion mehrere feststehende Suchpatterns gegeben sind, dann hat die ganze Diskussion einfach wenig Sinn: du kannst ohne Probleme auch 100GB Daten verarbeiten - weil du beim Suchen einfach alles überlesen kannst, was dich nicht interessiert.

@Oneric;112661

Das ließe sich ganz einfach beheben, wenn ich fertig gesucht habe und die sich wiederholenden Basen-Folgen inklusive ihrer Häufigkeit in irgendeiner Liste hinterlegt habe, gehe ich einfach noch einmal durch diese Liste und sortiere alle Ergebnisse deren String ein Substring eines Anderen, mit der gleichen Häufigkeit, ist aus.

Schon klar, aber Vorsicht: wenn du ATG und TGC suchst, dann musst du in ATGC zwei Treffer vermerken etc. Soweit ich weiß, kommen solche Überlappungen und Shifts im Genom tatsächlich vor.

[quote=Oneric;112661]Also, unabhängig vom letztlich verwendeten Such-Algorithmus, würde ich sagen, dass sich
ein RandomAccesFile, für besonders große Texte lohnt, die das LImit des Hauptspeicher durchaus sprengen könnte, dafür muss man dann aber auf Parallelisierung o.ä. verzichten (wahrscheinlich langsamer)[/quote]

Quatsch, du brauchst einen Byte-Inputstream und liest einfach vorwärts. Wozu ein Random Access File???

Ich vermute mal, deine Quelldatei enthält einfach nur Bytes, und zwar 4 verschiedene? Mehr brauchst du ja nicht?

[Dow_Jones]

@Oneric

Ich will dagegen nur einen einzelnen auf besonders häufig auftretende Basen-Folgen untersuchen.

Um mal Vergleichswerte zu bekommen habe ich spaßeshalber was mit dem LCP-Algorithmus von Johannes Fischer gebastelt. Wenn ich das richtig gesehen habe dann läuft der in O(n) und braucht 9n Speicherplatz.
Paper: Inducing the LCP-Array
Source: GitHub - elventear/sais-lite-lcp: Induced Suffix Array with LCP construction (Mirror)

Das Programm erzeugt ein Array, füllt es mit Zufallswerten aus dem Bereich [0-3], generiert das LCP-Array und sucht anschließend nach sich wiederholenden Substrings.

Die Ausgabe schaut exemplarisch so aus:

data:   "11323132312202231321"
pos:     01234567890123456789
         0         1

2 occurences of substring size 5         "13231"
positions: 1, 5

2 occurences of substring size 4         "1323"
positions: 1, 5

3 occurences of substring size 3         "132"
positions: 1, 5, 16

3 occurences of substring size 2         "13"
positions: 1, 5, 16

6 occurences of substring size 1         "1"
positions: 1, 5, 16, 9, 0, 19

2 occurences of substring size 2         "22"
positions: 13, 10

2 occurences of substring size 5         "23132"
positions: 3, 14

2 occurences of substring size 4         "2313"
positions: 3, 14

3 occurences of substring size 3         "231"
positions: 3, 14, 7

3 occurences of substring size 2         "23"
positions: 3, 14, 7

7 occurences of substring size 1         "2"
positions: 3, 14, 7, 13, 10, 18, 11

2 occurences of substring size 4         "3132"
positions: 4, 15

2 occurences of substring size 3         "313"
positions: 4, 15

3 occurences of substring size 2         "31"
positions: 4, 15, 8

2 occurences of substring size 4         "3231"
positions: 2, 6

2 occurences of substring size 3         "323"
positions: 2, 6

3 occurences of substring size 2         "32"
positions: 2, 6, 17

6 occurences of substring size 1         "3"
positions: 2, 6, 17, 4, 15, 8

Für den Test habe ich es mit den Arraygrößen 1mb, 10mb, 100mb und 200mb laufen lassen. Die Ausgabe bestand in allen vier Fällen in der Auflistung aller Substrings, die mindestens 5 Zeichen lang waren und mindestens 100 mal auftraten. Der Testrechner war ein AMD Phenom II X4 945, 3GHz, 4GB RAM.

1 mb:
1.999.998 Wiederholungen gefunden
real 0m0.526s, user 0m0.280s, sys 0m0.218s

10 mb:
39.999.992 Wiederholungen gefunden
real 0m8.153s, user 0m3.999s, sys 0m0.530s

100 mb:
536.810.537 Wiederholungen gefunden
real 1m6.807s, user 0m51.671s, sys 0m2.250s

200 mb:
1.200.000.000 Wiederholungen gefunden
real 2m19.737s, user 1m49.078s, sys 0m5.031s

[Oneric]

So, leider bin ich in nächster Zeit doch etwas beschäftigter als ich dachte, deshalb wird es wohl noch ein paar Wochen dauern bevor ich mich daran mache das Programm tatsächlich umzusetzen.
Aber eure Vorschläge und Anregungen sollten mir auf jeden Fall gut weiterhelfen, also nochmal allen Danke !

MfG
~Oneric