Binär ersetzen / binäre Suche

[marabu]

Moin,

Zitat von blackdrake:

Ich möchte ein gewissen Binär-Suchmuster (mit enthaltenen 00h's) durch ein anderes Suchmuster der selben Länge in einer Datei ersetzen.

du könntest die Funktion PatchString() als Ausgangspunkt für deine eigenen Bemühungen verwenden.

Grüße vom marabu

[Reinhard Kern]

Zitat von blackdrake:

Hallo oki.

Danke für den Tipp. Erscheint zwar logisch, jedoch wäre diese Lösung

a) nicht dynamisch (da kein beliebiges Such/Ersatz-Muster angegeben werden kann. Jedoch ist mein Beispiel statisch)
b) ziemlich langsam, da die Datei ca. 1 MB groß ist.

Wenn man eine 1 MB große Datei byteweiße abgehen und die vorrangehenden Bytes auf das Suchmuster überprüfen würde, wäre das sehr uneffektiv. Gibt es keine bessere Lösung (z.B. eine solche, wie sie in Hex-Editoren bei der Ersatz-Funktion angewandt wird)? Die Methode des byteweisen Abtastens des Streams würde ich nur anwenden, wenn sich keine bessere Methode anbieten würde.

Gruß
blackdrake

Hallo,

das ist eine kapitale Fehleinschätzung. Eine Datei seriell zu lesen und dabei auf Muster zu untersuchen ist grundsätzlich die schnellste Methode. Jede unnötige Verkomplizierung durch VCL-Komponenten macht die Sache nur langsamer, ganz besonders die hier für fast alles empfohlene Methode, erst mal die ganze Datei in eine TStringList einzulesen, die praktisch immer und in diesem Fall ganz besonders blödsinnig ist, weil es sich ja nicht einmal um Text handelt. Nebenbei bemerkt, das Einlesen in eine TStringList muss ja selbst eine Mustererkennung durchführen nach CR-LF, und dann das Gnaze nochmal nach der gesuchten Folge - wer behauptet, dass das durch irgendeine Borland-Zauberei schneller geht als 1 mal direkt, glaubt sicher auch an Weihnachtsmann und Osterhase.

Also lesen und prüfen, ob das nächste Zeichen gleich dem ersten des Vergleichsarrays ist, wenn ja, ist das nächste gleiche dem 2. usw. bis die Länge des Vergleichs erreicht ist, wenn nicht, dann weitersuchen wie zuvor nach dem ersten Zeichen.

Es gibt noch Optimierungen, v.a. für lange Vergleiche, dazu gab es einen c't-Artikel, aber bei so geringen Programmierkenntnissen sollte man sich auf die einfachste Form beschränken.

Gruss Reinhard

[Gausi]

Wenn die zu durchsuchenden Daten größer werden, und der Suchstring auch mehr als ein halbes Dutzend Zeichen lang ist, könnte man den Boyer-Moore-Algorithmus darauf ansetzen. Da das Alphabet hier recht groß ist, dürfte die Bad-Character-Regel (die recht einfach zu implementieren ist), voll zuschlagen und eine deutliche Verschnellerung der Suche bewirken.
Bei sehr kurzen Suchmustern dürfte sich der Aufwand allerdings nicht lohnen.

[oki]

imho sollte dann mein Vorschlag mit dem byteweisen Vergleich bei kurzen Elementen gar nicht so schlecht sein. Flexibilität sollte eigentlich nicht das Problem sein. Das kann man ja mit einer kleinen Function erledigen können.

Delphi-Quellcode:

type TByteArr = Array of Byte;
Procedure ReplaceBytes(Buffer : Pointer; SercheBytes, NewBytes : TByteArr);

Buffer ist hier jetzt mal der Dummy für das Datenfile in dem ersetzt wird.

Gruß oki

[blackdrake]

Hallo.

Vielen Dank für euere Antworten.

Ich dachte, dass es uneffizient sei, eine Datei byteweise abzugehen, da ich es mit dem pixelweisen abgehen eines TImages verglich. Bei einem Projekt ging ich ein großes Bild pixelweise ab, was dazu führte, dass man den Fortschritt regelrecht mitanzusehen konnte, während man Kaffee aufkochte.

In meinem Projekt möchte ich nur kleine Muster ersetzen und die Performance ist nicht so wichtig, da die Dateien eher klein sind.

Die Funktion PatchString(), die Pos verwendet, hat mir sehr weitergeholfen. Es gab jedoch damit 3 Probleme:

a) Es wurde nur das erste Vorkommen ersetzt
b) Die Ersetzung geschah nach dem Vorkommnis und hat das Vorkommnis somit nicht ersetzt.
c) Verkürzungen und Verlängerungen (wenn Länge des Suchmusters ungleich der Länge des Ersatzmusters ist) sind nicht möglich

Ich habe deswegen folgende Funktion aus gebastelt, die ReplaceString() durch eine Binary-Safe-Funktion ersetzt und sie bei der CodeLib vorgeschlagen:
http://www.delphipraxis.net/internal...t.php?p=778431

Gruß
blackdrake

[oki]

und warum nun auf einmal mit Strings? Sollte doch Byte-Array sein.

gruß oki

[blackdrake]

Hallo.

Nein, kein Byte-Array, ein Binärmuster. Und ein String ist ja nichts anderes als ein max. 4 GB großes, dynamsiches ByteArray.

Gruß
blackdrake