Suchen/Ersetzen in grossen Dateien

[CCRDude]

Zitat von Iwo Asnet:

@mkinzler: Ich weiss nicht, ob StringReplace auf die Stringlänge schaut, oder bis zum ersten #0 Byte geht... Aber dann wäre ja meine Idiotenlösung auch für den Arm.

Das ist versionsabhängig. Hab ich vor Ewigkeiten mal in's QC gestellt, ist inzwischen gefixt (ticket 60730).

Zum Thema Boyer Moore: die zwei am häufigsten zu findenden Delphi-Implementierungen, die ich im Netz gefunden habe, habe selten auftretende Fehler. Lieber selber implementieren. Aber wenn schon das, besser gleich einen Aho-Corasick, um auch mal mehrere Begriffe in einem Durchlauf ersetzen zu können.

[Gausi]

Zitat von CCRDude:

Aber wenn schon das, besser gleich einen Aho-Corasick, um auch mal mehrere Begriffe in einem Durchlauf ersetzen zu können.

Wird zwar etwas OT, weil hier der Flaschenhals höchstwahrscheinlich nicht die Suche, sondern das Ersetzen ist (wenn nur nach einem Zeichen gesucht wird, bringen KMP, Boyer-Moore und Konsorten gar nichts ). Aber für die mehrfache Suche gibt es afaik deutlich bessere Algorithmen als Aho-Corasick. Ich habe sehr gute Erfahrungen mit Wu-Manber gemacht, der auch nicht furchtbar kompliziert zu implementieren ist.

[CCRDude]

Zitat von Gausi:

weil hier der Flaschenhals höchstwahrscheinlich nicht die Suche, sondern das Ersetzen ist (wenn nur nach einem Zeichen gesucht wird, bringen KMP, Boyer-Moore und Konsorten gar nichts ).

Einfach mal den Original-Post lesen Es geht um 6 Zeichen, und da Hoika schreibt, dass er die Datei Byte für Byte ausliest, ist eigentlich schon klar, daß der Flaschenhals das üble I/O und momentan noch weder die eigentliche Suche noch das Ersetzen ist

Aber: nach Umstellung auf blockweise Verarbeitung ist bei 6 Zeichen ja schon was rauszuholen. Kommt halt drauf an, um wie viele dieser Dateien und wie automatisiert das gehen mag, ob sich der Aufwand lohnt.

AC vs. (M)WM: "besser" ist immer relativ, muss man imo einzeln abstimmen, ob Geschwindigkeit oder Speicherbedarf wichtiger sind. War ja aber auch nur ein Beispiel, da so ein Template-System ja schnell mal auf mehr als eines wächst.

[Gausi]

Ich hatte das so verstanden, dass "NAME" variabel ist und daher nur nach den umschließenden "<" und ">" gesucht wird. Ansonsten kann man da natürlich schon mit BM was rausholen.

(Das byteweise auslesen der Datei habe ich tatsächlich überlesen. Aber das ist ja nun wirklich eine extrem doofe Idee. (Ist ja nicht sein Code, dann darf ich das hier hoffentlich sagen. ))

[hoika]

Hallo,

danke, danke

Es sind auch DOC dabei, deswegen die Frage nach dem #0.
<NAME> war nur ein Bsp., die Datei wird einmalig durchlaufen, da können noch mehr Kenner drinstehn.

Da ich hier nur D2007 zur Verfügung habe, klappt das StringReplace leider nicht mit #0 ;(
(der QC ist zwar closed, aber ich habe das Bsp. mal ausprobiert, bei mir wird nicht alles ersetzt).


Heiko

[himitsu]

PS:
.DOC ... die alten Binärdateien oder das neue gezippte XML ... da muß man ein bissl aufpassen,
wobei das neue Format sich doch eigentlich .DOCX nennt und im XML nach < und > zu suchen könnte auch etwas unhandlich werden.

Bei den binären Dateien sollte man besser nicht die Strucktur verändern, also keine Ersetzungen mit unterschiedlichen längen, da dann das Dateiformat schnell mal zerschossen ist.

[Amateurprofi]

Hallo Heiko,

mal auf die Schnelle etwas für Text Dateien.
Ich habe meine Zweifel, ob das so auch für .doc oder .rtf Dateien funktioniert, aber eventuell kannst du das für deine Zwecke anpassen.

Ich hab es mal mit einer Datei (3.3 MB) getestet.
(Es ist die von der Deutschen Bundesbank publizierte Liste aller Banken in Deutschland.)

Um alle Vorkommen von "Bank" in "ank" zu ändern, braucht die Routine 65 ms, um "Bank" in "GeldBank" zu ändern brauchte sie 340 ms.
StringReplace braucht für die gleiche Aufgabe 54000 ms.

Frage am Rande : So etwas kannst du doch sehr bequem mit Word machen?

Delphi-Quellcode:

PROCEDURE TextFileReplace(const olddsn,newdsn,old,new:String);
var list:TStrings; data,newdata:String; oldlen,newlen:integer;
PROCEDURE Grow(required:integer);
var current:integer;
begin
   current:=Length(newdata);
   if current>=required then exit;
   required:=Max(current+current shr 2,required);
   SetLength(newdata,required);
end;
PROCEDURE Replace;
var p,i,j,len:integer;
begin
   SetLength(newdata,Length(data)+100);
   j:=1;
   p:=1;
   repeat
      i:=p;
      p:=PosEx(old,data,p);
      if p=0 then break;
      len:=p-i;
      Grow(j+len+newlen);
      Move(data[i],newdata[j],len*SizeOf(char));
      Move(new[1],newdata[j+len],newlen*SizeOf(char));
      inc(j,len+newlen);
      p:=p+oldlen;
   until false;
   len:=Length(data)-i+1;
   Grow(j+len);
   Move(data[i],newdata[j],len*SizeOf(char));
   SetLength(newdata,j+len-1);
   list.Text:=newdata;
end;
PROCEDURE ReplaceInplace;
var p,i,j,len:integer;
begin
   j:=1;
   p:=1;
   repeat
      i:=p;
      p:=PosEx(old,data,p);
      if p=0 then break;
      len:=p-i;
      Move(data[i],data[j],len*SizeOf(char));
      Move(new[1],data[j+len],newlen*SizeOf(char));
      inc(j,len+newlen);
      p:=p+oldlen;
   until false;
   len:=Length(data)-i+1;
   Move(data[i],data[j],len*SizeOf(char));
   SetLength(data,j+len-1);
   list.Text:=data;
end;
begin
   list:=TStringList.Create;
   list.LoadFromFile(olddsn);
   data:=list.Text;
   list.Clear;
   oldlen:=Length(old);
   newlen:=Length(new);
   if newlen<=oldlen then ReplaceInplace else Replace;
   list.SaveToFile(newdsn);
end;