Wie findet man möglcihst schnell eine Bitsequenz z.B. 0101011010101101 in einer ca. 100 Mb großen Datei?
-
Gibt es dafür besonders gute Algorithmen die ihr empfehlen könnt, oder soll ich besser etwas eigenes Basteln?
Wichtig ist mir dabei, daß ich hier nicht nur Byteweise die 100 MB Datei durchlaufe, sondern dies Bitweise machen kann bis eben die Stelle gefunden wird, die mit der Bitsequenz übereinstimmt.
-
Bitsequenz schrieb:
Wichtig ist mir dabei, daß ich hier nicht nur Byteweise die 100 MB Datei durchlaufe, sondern dies Bitweise machen kann bis eben die Stelle gefunden wird, die mit der Bitsequenz übereinstimmt.
Das klingt nach string search algorithms, zum Beispiel den Boyer–Moore algorithm. Du wirst aber ein paar Bit-Tricksereien brauchen, um den effizient umzusetzen. Ich nehme mal an, dass die Variante auf Bit-Ebene, die du bräuchtest, auch irgendwo schonmal untersucht wurde, aber bisher habe ich die noch nicht gesehen.
-
Der Klassiker wäre der Knuth-Morris-Pratt Algorithmus.
-
Danke, ich werde mir das mal alles durchlesen.
Falls ihr noch weitere Vorschläge habt, dann schaue ich mir die natürlich auch noch an.
-
wenn du viele solche sequenzen in der gleichen datei suchen möchtest, dann würde sich ein preprocessing der datei lohnen.
-> suffixbaum
danach hast du nur einen suchaufwand von O(suchstringlänge) statt O(dateilänge)
jenz